Розробка і дослідження алгоритмів кластеризації для великих колекцій документів
This paper focuses on document clustering algorithms that build hierarchical solutions. In this paper is evaluate the performance of different criterion functions for the problem of clustering documents.
Збережено в:
Дата: | 2010 |
---|---|
Автори: | , , , , |
Формат: | Стаття |
Мова: | Ukrainian |
Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2010
|
Назва видання: | Моделювання та інформаційні технології |
Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/21990 |
Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
Цитувати: | Розробка і дослідження алгоритмів кластеризації для великих колекцій документів / Ю.В. Стех, Файсал М.Е. Сардіх, М.В. Лобур, М.С. Домброва, В.Є. Арцибасов // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 58. — С. 288-290. — Бібліогр.: 19 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraineid |
irk-123456789-21990 |
---|---|
record_format |
dspace |
spelling |
irk-123456789-219902011-06-21T12:07:56Z Розробка і дослідження алгоритмів кластеризації для великих колекцій документів Стех, Ю.В. Файсал М.Е. Сардіх Лобур, М.В. Домброва, М.С. Арцибасов, В.Є. This paper focuses on document clustering algorithms that build hierarchical solutions. In this paper is evaluate the performance of different criterion functions for the problem of clustering documents. Дана робота зосереджується на алгоритмах кластеризації великих колекцій документів, які базуються на ієрархічних рішеннях. У даній статті оцінюється робота різних критеріальних функцій під час кластерізації документів. 2010 Article Розробка і дослідження алгоритмів кластеризації для великих колекцій документів / Ю.В. Стех, Файсал М.Е. Сардіх, М.В. Лобур, М.С. Домброва, В.Є. Арцибасов // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 58. — С. 288-290. — Бібліогр.: 19 назв. — укр. XXXX-0068 http://dspace.nbuv.gov.ua/handle/123456789/21990 681.322 uk Моделювання та інформаційні технології Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
collection |
DSpace DC |
language |
Ukrainian |
description |
This paper focuses on document clustering algorithms that build hierarchical
solutions. In this paper is evaluate the performance of different criterion functions for
the problem of clustering documents. |
format |
Article |
author |
Стех, Ю.В. Файсал М.Е. Сардіх Лобур, М.В. Домброва, М.С. Арцибасов, В.Є. |
spellingShingle |
Стех, Ю.В. Файсал М.Е. Сардіх Лобур, М.В. Домброва, М.С. Арцибасов, В.Є. Розробка і дослідження алгоритмів кластеризації для великих колекцій документів Моделювання та інформаційні технології |
author_facet |
Стех, Ю.В. Файсал М.Е. Сардіх Лобур, М.В. Домброва, М.С. Арцибасов, В.Є. |
author_sort |
Стех, Ю.В. |
title |
Розробка і дослідження алгоритмів кластеризації для великих колекцій документів |
title_short |
Розробка і дослідження алгоритмів кластеризації для великих колекцій документів |
title_full |
Розробка і дослідження алгоритмів кластеризації для великих колекцій документів |
title_fullStr |
Розробка і дослідження алгоритмів кластеризації для великих колекцій документів |
title_full_unstemmed |
Розробка і дослідження алгоритмів кластеризації для великих колекцій документів |
title_sort |
розробка і дослідження алгоритмів кластеризації для великих колекцій документів |
publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
publishDate |
2010 |
url |
http://dspace.nbuv.gov.ua/handle/123456789/21990 |
citation_txt |
Розробка і дослідження алгоритмів кластеризації для великих колекцій документів / Ю.В. Стех, Файсал М.Е. Сардіх, М.В. Лобур, М.С. Домброва, В.Є. Арцибасов // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 58. — С. 288-290. — Бібліогр.: 19 назв. — укр. |
series |
Моделювання та інформаційні технології |
work_keys_str_mv |
AT stehûv rozrobkaídoslídžennâalgoritmívklasterizacíídlâvelikihkolekcíjdokumentív AT fajsalmesardíh rozrobkaídoslídžennâalgoritmívklasterizacíídlâvelikihkolekcíjdokumentív AT loburmv rozrobkaídoslídžennâalgoritmívklasterizacíídlâvelikihkolekcíjdokumentív AT dombrovams rozrobkaídoslídžennâalgoritmívklasterizacíídlâvelikihkolekcíjdokumentív AT arcibasovvê rozrobkaídoslídžennâalgoritmívklasterizacíídlâvelikihkolekcíjdokumentív |
first_indexed |
2025-07-02T22:00:43Z |
last_indexed |
2025-07-02T22:00:43Z |
_version_ |
1836574199174397952 |
fulltext |
283 © �.�.����, �
� �
.�.� ����,
.�.�����,
.�.������� , �.�.����� ���
��� 681.322
�.�.����, �.�.!., ���. � ". ��#, $� «�%����%� &������!�� »,
�
� �
.�. � ����, �&�� !� � ". ��# $� «�%����%� &������!�� »,
.�.�����, �.�.!., &��"����, ' �. � ". ��#, $� «�%����%� &������!�� »,
.�. ������� , �&�� !� � ". ��# $� «�%����%� &������!�� »,
�.�. ����� ���, �&�� !� � ". ��# $� «�%����%� &������!�� »
�������� � �
�� �
��� ���������� ���
�
�������
�� �
����� ���
���� ����
����
This paper focuses on document clustering algorithms that build hierarchical
solutions. In this paper is evaluate the performance of different criterion functions for
the problem of clustering documents.
Keywords – method, algorithm, cluster, criterion function
� ! ����� '������(�)�%�* ! �+����� � �� �����' ��- ������� �������
������!���, *�� � '�/�%�* ! �)� ���0!�� ��4�!!*�. � � !�
�� ��� ���!/)�%�*
����� ��'!�� ������� �%!�� "�!���
&�� 0 � �� �����' ��- ������!���.
������� ���
– �����, �+�����, �� ����, ������� �%!�� "�!���*
�����
5����� � &��������!� �+������ �� �����' ��- ������!��� ����+� /�%
� (���� ���% � ' ��'&�0�!!� �!��-���!�- ! ��+ ��- � �������*� ������!��� �
��� !�'� � -� &���+�*�� [1-3]. 9� ' ��'&�0�)�%�* 4�*��� &��������!!*
������� � ����� �!"��� ��- � �*� �� ������ '! 0!� ��!4�+� ��'����.
:����� , �+������ �� �����' ��-, *�� "����/�% �)� ���0!� ��������� !
��!��� ������� �������
������!���, ) ��� �%!��� ' ��� �� ��*
�!��� ����!�- ��'� ��' ��- � ������(�!!*, �����%�� ' ��'&�0�/�%
&����� ���!!* !���&���0����� � &����� 0�� !�� � !�� ! ��'!�� ���!*�
��� ��' ��- [4-8]. � ! ����� '������(�)�%�* ! ������(�!!� �+�������
�� �����' ��- ������!���, *�� "����/�% �)� ���0!� ��4�!!*. � �� ���
���!/)�%�* ����� ��'!�� ������� �%!�� "�!���
��* &������ �� �����' ��-
������!���.
�����!"#$�%&' ()*�+!,�&-.
��+������ �� �����' ��- �����������/�% ������!�-&��������� �����%
��* &����� ���!!* ��(!�+� ������!��. � � ��
������, ��(!�
������!� d
��'+�*� )�%�* *� ������ � &������� ������ (�!"��� ��
!�� ��� �����
������!� ). � ���-
!
&�����4�
"���� ��(!�
������!� &����� ��*)�%�* �
��+�*�� ������ 0 ����� ����(�!!* ������ � ��
������!�:
� �1 2, ,...,tf md tf tf tf� (1)
�� tfi - 0 ���� ����(�!!* � ������!� i-�� ���� . 5����� �����������)�%�*
������! ��! ���� ��)- ������. ��! &��*+ ) � '� (�� !!� ��(!�+� ���� '
��&���+�/
�+� ����!�!�- 0 ����� ����(�!!* � ������!�� � ' + �%!�
�������- ������!��� [9-14]. #��0�!�/ � ��+� '� (�� !!* ) ��, @� �����, *��
284
0 ��� '�����0 /�%�* � ��'!�� ������!� �, ������/�% ����(�!�/ ���&�!!/
���������!!*. A��� � �� ����� !������!� &��!�� 0�!�� &�'� ���� ���
�&������!%. 9�, *� &� ����, '��
�!/)�%�* 4�*��� �!�(�!!* 0 �����
����(�!!* ��(!�+� ���� i ! log
i
N
df
� �� �
, �� N – ' + �%! ���%����%
������!��� � �������-, dfi - ���%����% ������!���, *�� ����*�% i-
���� (�����,
0 ���� ������!� ). 9� ���� �� tf-idf &����� ���!!* ������!� , �����
1 2
1 2
log , log ,...
, log
tfidf
m
m
N Ntf tfdf df
d
Ntf df
� �� � � �� � � �� �
� ��
� �� �� �� �
(2)
��* ������ ' ������!� �� ��'!�- ���(�!� ���(�! ��(!�+� ������
������!� !��� ��'�)�%�* 4�*��� -- &������!!* �� ���!�0!�- ���(�!�
� �1tfidfd � . 9� �'! 0 ), @� ��(!�
������!� ) �������� � ���!�0!�
+�&���"���. � ! ���&!�
0 ���!� �� ���, �� &��&��� )��, @� ������!�
&����� ���!!* ��(!�+� ������!� ���� '� (�!� �����������/0� tf-idf � )
!��� ��'�� !� 4�*��� &������!!* �� ���!�0!�- ���(�!�. $ &���*'�
���%��� ��� !!�� �����, ���� ' &��&�!�� !� �� &������ �� ��0����!!*
&����!���� ��( ���� ������!� �� di � dj. #��4�
&����� B��!��)�%�* !
' ������ !!� "�!���- ����!�� [4,15-17]:
cos(di,dj)=
t t
i j
i j
d d
d d
(3)
F����%�� ������� ������!� ��� ( /�%�* 0���' ���!�0!� ���(�!�, ��
! ����! ��@� "����� �&��@�)�%�* �� cos(di,dj) =di
t
dj. G�'��%� �� ��0����!%
�����!//�% ���!���, *�@� ������!�� &����!�, � !��/, *�@� ��(
������!� �� !�� ) !�0�+� �&��%!�+� (����� ��� ������� ������!��� )
����+�! �%!��� ��( ����/). ���+�
����� ��'! 0 ) &����!���% ��(
������!� �� �����������/0� ��������� ����� !% [6-8, 18]:
dis(di,dj)= � � � �t
i j i j i jd d d d d d� � � � (4)
H�@� ����� !% �����!/) !��/, ���� ������!�� ) &����!���, *�@� ��!�
!�&����!�, ���� ����� !% �����!/) 2 . ���� ' �� (���, @� !�'� ( /0� !
��
" ��, @� &��4�
&����� ���!/) ���&�!% &����!����, ���+�
– ���!/)
����� !�, ��!� ) &����!��� ��( ����/, �����%�� ������� ������!�
��� ( /�%�* 0���' ���!�0!� ���(�!�. � �� ��� �� �����������)�� �������
n, m, � k ��* &�'! 0�!!* ���%����� ������!���, ���%����� ���� � ���%�����
�� ������ ���&����!�.
� �����������)�� ������ S ��* &�'! 0�!!* ! ���� '
n ������!��� *�� �� ��0��� �� �����'�� ��, S1,S2 ,...,Sk ��* &�'! 0�!!*
��(!�+� ' k �� ������, � n1,n2...,nk ��* &�'! 0�!!* ��'����� ���&����!��
285
�� ������. : � !� �!�(�!� ������!��� A � -�!) ���&����!� ������!�
&����� ���!!* �� ��'! 0 )�� ��� ��!�� �������� DA:
DA=
d A
d
�
, (5)
���� *� ��!���-�!�
������ CA ���� � �� ! ���&!�
��+�*�:
CA = AD
A
(6)
��� ��!�
������ DA ) ����/ ���� �������� ������!��� � �,
��!���-�!�
������ CA – �� ������, ����� !�
4�*��� ������!�!!* � +
��'!�� ������, &����� ���!�� � �!�(�!� ������!��� A. ���� ' �� (���, @�
! ���% � ��& ���, ���� ������� ������!��� �����!//�% ���!���, ��!���-�!�
������� !� ����'*'���� �����% ���!�0!�- ���(�!�.
$ ��@��� ���!� ���� ���- &������ �� �����' ��- ��'! 0 )�%�*
! ���&!�� 0�!��. : � !� �������/ S, *� ��� � )�%�* ' n ������!���,
!������!� ��'������ ! ! &���� ��'! 0�!� ���%����% k &���!�(�! S1,S2,,...,SK
� �, @�� ������!��, *�� &��'! 0�!� � ��!� &���!�(�!�, ���� ��( ����/
&����!�4���, !�( ������!�� &��'! 0�!� � ��'!� &���!�(�!�.
��+����� ��+��!�!�- �� �����' ��- �����������) &����� &�����!�-
�� �����' ��- 4�*��� &����� ! �&��. � � ���� &������ ��� ������!��
�&�0 ��� ��'&����*/�%�* � �� �� �����. #���� �����%�* ���! �' ���
�� ������, @� ������% ���%4� !�( ���! ������!� � ��'���*)�%�* ! �&��. 9�
&����� &�����/)�%�* n - 1 � ', &��'���*0� �� n �������� �� ������, ��(!�
'
*��� ������% ���! ������!�. ��+�� &�� 0���, @� ' &��&�!�� !�
&�����
����) B����� ��
!� �)� ���0!� ������. �!�'� ��(!�
������!� '! �����%�*
� ���)�� �� �!��� �� �����. ��/0���/ � � ����������/ ���%4����
�+������� ��+��!�!�- �� �����' ��- ) ��, @� ��!� �����������/�% +��� �%!�
���!�0!� "�!���/ �&����' ��* *��- �&��� ) ! ���% &����� �� �����' ��-. ��*
� ��� �+������� ��+��!�!�- �� �����' ��- &������ �� �����' ��- ��(� ����
��'! 0�! ! ���&!�� 0�!��: &������!!* &������ �� �����' ��- � ��� 0�!��,
@�� '! 0�!!* ��!����!�- ���!�0!�- "�!���- ���� �&����'�� !��. � ������ ��
������(�)�� ��'!� ���!�0!� "�!���- �� �����' ��-. F��!�0! "�!���* L1
(���!*!!* 7) � �����'�) ���� �����!�� &�& �!�� &����!����
��(
������!� ��. ������!�� *�� ���!���!� �� ��(!�+� �� ���� '� (�/�%�*
���&����!� �� ��'���� �%�+� �� ���� .
L1 = maximize � �2
1 , 1
1 cos ,
i j r
k k
r
r i j
rr d d S rr
D
n d d
nn� � �
� �
� � �
� �
(7)
F��!�0! "�!���* L2 (���!*!!* 8) �����������) ������!�-&���������
� �� !� �+������ K-�!����4!�� +��&���� �����!��. � �%��� �+������
��(�! �� ���� &����� ���!�
�+� ��!���-�!�� �������� � ����/ )
'! ���(�!!* ��4�!!*, *�� � �����'�) &����!���% ��( ��(!�� ������!��� �
��!���� � +� �� ���� , �� *��+�
�+� ���� &��'! 0�!�.
286
L2 = maximize � �
1 1
cos ,
i k
k k
i r r
r d S r
d C D
� � �
�
(8)
#����!//0� L1 � L2 �� � 0���, @� �����!�/ ��'!���/ ��( !��� ) ��, @�
"�!���* L2 ���!/) �!����4!%�-�� ����!� &����!���% rD . rD )
�� �� �!�� ����!�� &�& �!�� &����!����
��( ���� ������!� �� � Sr �
&� +!� &�����&�������� �� �����, 0�- ������!�� � /�% ��!%4� &�& �!�
&����!���% � &����!*!!� ' �� ���� �� ' ��@�/ &�& �!�/ &����!���/.
F��!�0! "�!���* (���!*!!* 9) L3 ��0���/) �� �����' ��/ 4�*���
'! ���(�!!* ��4�!!*, *�� ���������/) ������!�� ��(!�+� �� ���� ���
' + �%!�- �������-. :����� , ��! ! � + )�%�* ��!���'�� �� ����!�� ��(
��!���-�!�� �������� ��(!�+� �� ���� � ��!���-�!�� �������� ' + �%!�-
�������-. �!���� ��(!�+� �� ���� '� (�)�%�* &��&����
!� ��
�+� ��'����
� ��� 0�!��, @� ���%4� �� ����� ���!//�%�* ��@� � ' + �%!��� ��4�!!�
�� �����' ��-.
L3=minimize � �
1 1
cos ,
tk k
r
r r r
rr r
D Dn C C n
D� �
�
(9)
: &��&�!�� !�
�+����� ��+��!�!�- �� �����' ��-, *��
�����������)
&����� ! *���� &������ !�
�+����� K-�!����4!�� +��&���� �����!�� [19],
�&����'�) ��(!� �' ��@� '+ � !�� ���!�0!�� "�!���
. $ &��4��� ����� �'
�������- ������!��� ����� )�%�* ��& ���� & � ������!���, *�� �� /�%
��!�� �� ���� �� ������. $ ���+��� ����� ��* ��(!�+� ������!�
��0���/)�%�*
�+� &����!���% �� ��� ���� ��!����. � ' ��(!���� ���
����� !�� '! 0�!% ������!�� &�����'&����*/�% � !
&����!�4� ��* !��
�� �����. 9� "����) &�0 ����� ��������!!/ �� �����' ��/. � &�� �%4���
&�������%�* &�����! �� �����' ��* ' ����/ �&����' ��- � ( !�- ���!�0!�-
"�!���- �� �����' ��-. ��� ��+�* &��� @�!!* ��'��%� ���, *�� ��
�����������)�� ��� � )�%�* �' !�'�� ���� ��
. #���*+�� ��(!�- ���� ��-,
������!�� ����� /�%�* � �����%!��� &��*���. ��* ��(!�+� ������!� di ��
��0���/)�� '��!� � '! 0�!!� ���!�0!�- "�!���-, ����( !�- 4�*���
&�����@�!!* di � �!4�
�� ����. H�@� ��!�/�% � �� &�����@�!!*, *��
&�����*�% �� &��� @�!!* ' + �%!�+� '! 0�!!* ���!�0!�- "�!���-, �� di
&�����@ )�%�* � �� ����, *��
&�������% �� !
���%4�+� &��� @�!!*. H�@�
!� ��!�) (��!�+� &�����@�!!*, ���� di ' ��4 )�%�* � �� �����, *���� !
� !�
����!� ! ��(��%. � ' &��� @�!* ' ��!0�)�%�*, *� ���%�� ����!�)�%�*
���� ��* &�� 0 � *��- ��( �� ���� �� !� ���� &�����@�!� (��!�+� ������!� .
���� ' �� (���, @� ! �����!� ��� �� ����
!�+� &������ [19] &��� @�!!*
��'��%� ���, @� �����������)�%�* � �+������ K-�!����4!�� +��&����
�����!��, ' &��&�!�� !�
�+����� &�����@ ) ������!�, *� ���%�� ��!
��'! 0��, @� �� &������ �� &��� @�!!* '! 0�!!* ���!�0!�- "�!���-. A ��
��& �+������� &��� @�!!* 0 ��� ! '�� /�% &���������. F����%�� ��(!�
&�����@�!!* ��'&������!%� �&����'�) ' � !� ���!�0!� "�!���/, �* ��� ��+�*
287
&��� @�!!* ' �(�� &�������% �� ����( !!* ��� �%!�+� ��!�����. K���' ��,
@� ��'!� ���!�0!� "�!���-, *�� �����������/�% ��� ��+�/ &��� @�!!*
��'��%� ���, ��'! 0 /�%�* � �����! � ��� ��!�� �� ������ � ��!���-�!��
��������, '��! � '! 0�!!� ���!�0!�� "�!���
� ��'��%� �� ��!�� '���+�
&�����@�!!* ������!� ��(� ���� ��0����! �"�����!�4�. ��/0����
������ � ' &��&�!�� !��� &������ &�����!�- �� �����' ��- 4�*��� &�����
! �&�� ) �����, *��
��'! 0 ) ! ���&!�
�� ����, @� � ) ���� &�����!�
! �&��. #���������* ���&�����!�� ' ���� ��'!��� ����� �� ������
�� ������. #��4�
����� �����������) &����� ��� ��+�/ &����� ! �&��
!
���%4�+� �����&!�+� � � !�
����!� �� ���� . ������ ������ ' � ���
&������� &�� ' �, @� ��! &�������% �� ���� �!%� ����4�� � '� (�!�� ��4�!%
&� �� �����' ��- ������� ������!���. ��� ��! � ) ����)��
!������. #�����
&� �/) !� '����� ������!� ! �������*� ������!���, � *��� &�����!�
�� ����� ) ��'!�- ����0�!�, �� &�������% �� &����� �&��4� !
���%4��
�� ������. ��* &���� !!* � !�- &������� � ����� !!* &�����!�4��
�)� ���0!�� ��4�!%, �� ��'��!��� �����, *��
����� &���0!�� k �� ������
����� ) �� ����, *��
���� �� k + 1 ��4�!% �� �����' ��-. 9� �&����'�)
'! 0�!!* ��!����!�- ���!�0!�- "�!���- (����� ��'!�� k �%���! ���). $ 4�
���&�����!�� &�� ' ��, @� ��
&����� &� �/) ��@� �� @�, !�( &�&����!*
���� . $ �����!� ��� �+������� ��+��!�!�- �� �����' ��-, *�� "����/�%
�)� ���0!� ��4�!!* ' ����� �!�', B����� ��
!� �+������ "����/�% ��4�!!*
&��'! 0 /0� �&�0 ��� ��(�! ������!�
�+� �� �!��� �� �����. #���* �%�+�
���� ��
!� &�������%�* ����� !!* � ��')�! !!* & � �� ������, ��* ����� !!*
)��!�+� ���&����!�+� �� ���� . �B����� ��
!� �+������ "����/�% ������
'!�'� (' �������) �+��� (����� �� ����!*). ��/0���
& � ���� �
B����� ��
!�� �+����� � ) �����, *��
�����������)�%�* ��* ��'! 0�!!*
& �� �� ������, *�� !������!� ��')�! �� ! � !��� �����. � ���%4����
B����� ��
!�� �+����� � �� '��
�!/)�%�* ����� /0� !
&����!�4� & ��
�� ������. $ � !�
0 � ��'�����!� 0����!!� &������ ��* ��0����!!*
&����!���� ��( ���� �� ���� ��. � ! 4��� ������(�!!� �� ������������ �
! ���&!� �����: )��!�+� '�’*'��, &��!�+� '�’*'��, +��&���� �����!��, � ��(
������� �%!� "�!���-, �&�� !� ��@�. ���� )��!�+� '�’*'�� ��'! 0 )
&����!���% ���� �� ������ ' � �������� &����!���� ��( ������!� �� '
��(!�+� �� ���� . A����, ���(���% ��( ���� �� ���� �� Si � Sj ��'! 0 )�%�*
! ���&!�� 0�!��:
simsingle-link(Si,Sj)= � �� �
,
max cos ,
i i j j
i j
d S d S
d d
� �
(10)
$ �����!� ��� &�&���!%�- �����, ���� &��!�+� '�’*'�� �����������)
��!�� �%!� &����!���% ��( & ��/ ������!���:
simcomplete-link(Si,Sj) = � �� �
,
min cos ,
i i j j
i jd S d S
d d
� �
(11)
� ' + �%!���, *� ���� )��!�+� '�’*'��, � � � ���� &��!�+� '�’*'�� !�
&� �//�% ��(� �����, ���� @� ��!� � '�/�%�* ! ����(�!��� ��’)��
288
�!��� ��- (� ��& ��� ����� )��!�+� '�’*'��), �� &��&��� /�%, @� ���
������!�� � �� ����� ��(� &����!� ��( ����/ (� ��& ��� ����� &��!�+�
'�’*'��). ���� +��&���� �����!�� ����4�) �� &�������, ��0���//0�
&����!���% ��� ���� �� ���� �� *� �����!/ ����0�!� &�& �!�- &����!����
������!��� ' ��(!�+� �� ���� :
simUPGMA(Si,Sj) = � �
,
1 cos ,
i i j j
t
i j
i j
i j i jd S d S
D D
d d
n n n n� �
�
(12)
F��!�0!� "�!���-, �&�� !� � �+����� � ��+��!�!�- �� �����' ��-,
��(��% ���� &��������!� ! �� ����!� ����� ������ ��* B����� ��
!�-
�� �����' �� �����������/0� ' + �%!� ����� &��������- �&����' ��-.
G�'+�*!��� �������/ ' n-������!��� � ��4�!!* �� �����' ��-, *�� ����
��0����!� &���* ����! !!* l ������ ��’)�! !!* �� ������. 9� ��4�!!*
��������� n - l �� ����, �����%�� ��(�! ��')�!�� �%!�
���� �����0�)
���%����% �� ������ ! ���!��/. A�&�� � �%��� (n – l) ��4�!!� �� �����' ��-,
����� )�%�* & � �� ������ ��* ��’)�! !!*, *�� &�������% �� (n V l V 1)
��4�!!*, *�� �&����'�) ��'! 0�!� ���!�0!� "�!���/. A����, ��(! ' (n Vl) ×
(n Vl V 1)/2 & � ��(����+� ��’)�! !!* ���!//�%�*, � ����� )�%�* ��, *��
�"����) ��4�!!* �� �����' ��-, *�� � ) � ���� �%!� ( �� ��!�� �%!�)
'! 0�!!* ��'! 0�!�- ���!�0!�- "�!���-. F��!�0! "�!���* ) ��� �%!�
�&��� �%!�/ � ��( � � !�+� ����� B����� ��
!�+� �+������. 9�
&�����
&�����(�)�%�* ���� !� ����� )�� &��!� B����� ��
!� ������.
�#�,)-*#
: &��&�!�� !�
�+����� ��+��!�!�- �� �����' ��- �&����'�) ���!�0!�
"�!���- L1 = maximize � �2
1 , 1
1 cos ,
i j r
k k
r
r i j
rr d d S rr
D
n d d
nn� � �
� �
� � �
� �
,
L2 = maximize � �
1 1
cos ,
i k
k k
i r r
r d S r
d C D
� � �
�
,
L3=minimize � �
1 1
cos ,
tk k
r
r r r
rr r
D Dn C C n
D� �
�
. $ �����!� ��� ���
�� ����
!�+� &������ &��� @�!!* ��'��%� ���, @� �����������)�%�* �
�+������ K-�!����4!�� +��&���� �����!��, ' &��&�!�� !�
�+�����
&�����@ ) ������!�, *� ���%�� ������, @� �� &������ �� &��� @�!!*
'! 0�!!* ���!�0!�- "�!���-. F����%�� ��(!� &�����@�!!* ��'&������!%�
�&����'�) ��!����!� ���!�0!� "�!���/, �* ��� ��+�* &��� @�!!* ' �(��
&�������% �� ����( !!* ��� �%!�+� ��!�����. G�'!� ���!�0!� "�!���-, *��
�����������/�% ��� ��+�/ &��� @�!!* ��'��%� ���, ��'! 0 /�%�* � �����! �
��� ��!�� �� ������ � ��!���-�!�� ��������, ���� '��! � '! 0�!!� ���!�0!��
289
"�!���
� ��'��%� �� ��!�� '���+� &�����@�!!* ������!� ��(� ����
��0����! 4���4�.
G�'��!��� �����, *��
����� &���0!�� k-�� ������, ����� ) ��
, *��
���� �� k + 1 ��4�!% �� �����' ��-. 9� �&����'�) '! 0�!!* ��!����!�-
���!�0!�- "�!���- (����� ��'!�� k �%���! ���). $ 4� ���&�����!�� &�� ' ��,
@� ��
&����� &� �/) ��@� �� @�, !�( &�&����!* ���� .
1. Charu C. Aggarwal, Stephen C. Gates, and Philip S. Yu. On the merits of building
categorization systems by supervised clustering. In Proc. of the Fifth ACM SIGKDD Int’l
Conference on Knowledge Discovery and Data Mining, pages 352–356, 1999.
2. Doug Beeferman and Adam Berger. Agglomerative clustering of a search engine query
log. In Proc. of the Sixth ACM SIGKDD Int’l Conference on Knowledge Discovery and
Data Mining, pages 407–416, 2000.
3. Daniel Boley. Principal direction divisive partitioning. Data Mining and Knowledge
Discovery, 2(4), 1998.
4. Chung-Kuan Cheng and Yen-Chuen A. Wei. An improved two-way partitioning algorithm
with stable performance. IEEE Transactions on Computer Aided Design, 10(12):1502–1511,
December 1991.
5. Inderjit S. Dhillon and Dharmendra S. Modha. Concept decompositions for large sparse
text data using clustering. Machine Learning, 42(1/2):143–175, 2001.
6. R.O. Duda, P.E. Hart, and D.G. Stork. Pattern Classi|cation. John Wiley & Sons, 2001.
7. A.K. Jain and R. C. Dubes. Algorithms for Clustering Data. Prentice Hall, 1988.
8. B. King. Step-wise clustering procedures. Journal of the American Statistical Association,
69:86–101, 1967.
9. Bjornar Larsen and Chinatsu Aone.Fast and effective text mining using linear-time
document clustering. In Proc. of the Fifth ACM SIGKDD Int’l Conference on Knowledge
Discovery and Data Mining, pages 16–22, 1999.
10. R. Ng and J. Han. Ef|cient and effective clustering method for spatial data mining. In
Proc. of the 20th VLDB Conference, pages 144–155, Santiago, Chile, 1994.
11. J. Puzicha, T. Hofmann, and J. Buhmann. A theory of proximity based clustering:
Structure detection by optimization. PATREC: Pattern Recognition, Pergamon Press,
33(4):617–634, 2000.
12. G. Salton. Automatic Text Processing: The Transformation, Analysis, and Retrieval of
Information by Computer. Addison-Wesley, 1989.
13. Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000.
14. K. Zahn. Graph-tehoretical methods for detecting and describing gestalt clusters.IEEE
Transactions on Computers, (C-20):68–86, 1971.
15. �
����� �.�., �
������� �.�. A������� !�� �� ����!�� �+������� !
�!� �� !�!���% ��!������%!� !���� ��� ��������. - �'�����* � ����� ! ��. A����*
� ������� �&� ���!�*.- 1997, 2, 165 - 168.
16. �
����� �.�., �
������� �.�. G '� ���� �+������� ��+!����!�+� �� ����!�+�
! ��' , � �!.: F�� ���� ����� � ��+!����!�� ���!���+��, ��&. 3/#�� ���.
�����%�� �.�. - #�@�!�, 1999, 43 - 47.
17. ���
��� �.�. A�� ��0����
! ��' ����� � ��*���!��� �����"� '���
���������
// �!"��� ���!!�� ���!���+��. - 2000. - N 11.
18. ���
��� �.�., ������ !.!. ������ ���! * �����% &���(��!�* ����� � ' � 0�
�� ���"�� ��� // �!"��� ���!!�� ���!���+��. - 2000. - N 12
290
19. �
��
��� �.�., ���
��� �.�., ��"��#�� $.%. A��!���+�* ��� ����� ��������
�!"��� ��� � �&���
! ��� !��0����� &����� ���!�� ! ��!��� ��� ���0�����
�������� �' ��! ��0����� !�
��!!�� ����
, �&� ��*���� ��� !�'��� �!�� !�* //
�!"��� ���!!�� ���!���+��. - 1998. - N 2. - �. 26-32.
��
�&��
27.09.2010�.
|