Проектирование систем искусственного интеллекта



         

Кластерный анализ - часть 2


Расстояние ближайшего соседа есть расстояние между ближайшими объектами кластеров:

q_{\min}(w_1,w_m)=\mathop{\min d(x_i,x_j)}\limits_{x_i*w_1, x_j*w_m}

Расстояние дальнего соседа — расстояние между самыми дальними объектами кластеров:

q_{\max}(w_1,w_m)=\mathop{\max d(x_i,x_j)}\limits_{x_i*w_1, x_j*w_m}

Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

q(w_1,w_m)=d(\mu_1,\mu_m)

Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K-расстояние, вычисляется по формуле

q_{\tau}^{(K)}(w_1,w_m)\left[\frac{1}{N_1 N_m} \sum\limits_{x_i*w_1} \sum\limits_{x_j*w_m} d^{\tau}(x_i,x_j)\right]^{\frac{1}{\tau}}

В частности, при

\tau \to \propto
и при
\tau \to -\propto
имеем

q_{\infty}^{(K)}(w_1,w_m)=q_{max}(w_1,w_m)\\q_{-\infty}^{(K)}(w_1,w_m)=q_{max}(w_1,w_m)

Выбор той или иной меры расстояния между кластерами влияет, главным образом, на вид выделяемых алгоритмами кластерного анализа геометрических группировок объектов в пространстве признаков. Так, алгоритмы, основанные на расстоянии ближайшего соседа, хорошо работают в случае группировок, имеющих сложную, в частности, цепочечную, структуру. Расстояние дальнего соседа применяется, когда искомые группировки образуют в пространстве признаков шаровидные облака. И промежуточное место занимают алгоритмы, использующие расстояния центров тяжести и средней связи, которые лучше всего работают в случае группировок эллипсоидной формы.

Нацеленность алгоритмов кластерного анализа на определенную структуру группировок объектов в пространстве признаков может приводить к неоптимальным или даже неправильным результатам, если гипотеза о типе группировок неверна. В случае отличия реальных распределений от гипотетических указанные алгоритмы часто "навязывают" данным не присущую им структуру и дезориентируют исследователя. Поэтому экспериментатор, учитывающий данный факт, в условиях априорной неопределенности прибегает к применению батареи алгоритмов кластерного анализа и отдает предпочтение какому-либо выводу на основании комплексной оценки совокупности результатов работы этих алгоритмов.

Алгоритмы кластерного анализа отличаются большим разнообразием. Это могут быть, например, алгоритмы, реализующие полный перебор сочетаний объектов или осуществляющие случайные разбиения множества объектов. В то же время большинство таких алгоритмов состоит из двух этапов. На первом этапе задается начальное (возможно, искусственное или даже произвольное) разбиение множества объектов на классы и определяется некоторый математический критерий качества автоматической классификации.


Содержание  Назад  Вперед