Динамическая иерархическая агломеративная кластеризация по принципу взаимного соседства

Основная особенность алгоритм, предложенного в [14], состоит в определении «соседей» для каждого объекта (каждого вектора) в пространстве. На входе алгоритма – матрица сходства документов, на выходе – иерархия кластеров.

Состав «соседей» данного объекта зависит от так называемого значения взаимного соседства (mutual neighborhood value – сокр. mnv) между двумя точками, взятого из теории распознавания образов. Пусть P и Q – две точки многомерного пространства. Если P – m-ый ближайший сосед (по степени сходства) Q и Q – n-ый ближайший сосед P, то для точек P и Q: mnv = m + n.

Смысл этой величины заключен в том, что две точки P и Q имеют высокую вероятность нахождения в одном и том же кластере, если не только P близко к Q, но и наоборот. Таким образом, mnv является псевдометрикой и не удовлетворяет аксиоме треугольника.

Параметр M_T используется для отражения степени «соседства» объекта в пространстве с использованием mnv. Данная точка Q считается принадлежащей окрестностям точки P (является «соседом» P), если выполняются следующие условия:

- mnv(P,Q) < M_T ;

- не существует точки K, такой, что mnv(Q,K) < mnv(Q,P), но sim(Q,K) ³ sim(Q,P) (sim – мера сходства), а точка P, нарушающая это ограничение становится невалидной по отношению к Q;

- точка Q не невалидная по отношению к P.

Такой подход позволяет на начальном этапе алгоритма получить мелкие кластеры –скопления точек пространства (поскольку никогда ни одна точка не будет по отношению к другой невалидной, если обе эти точки являются ближайщими соседями).

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

Необходимо заметить, что последние два условия не игнорируются, а лишь ослабляются, поскольку в противном случае может появиться несколько больших кластеров, которые притянут все более мелкие и затем объединятся сами.

Заключительное разбиение зависит от параметра M_T. Если этот параметр увеличивается, то усиливается тенденция к объединению кластеров. Опыты показали [14], что если увеличивать M_T, то обнаруживаются промежутки, на которых не наблюдается изменения заключительного разбиения. Очевидно, что разбиения на данных промежутках – оптимальные и при прочих равных требованиях к кластерному разбиению выбираются именно они.

Алгоритм.

Шаг 1. Сортировка матрицы сходства.

Пусть S – матрица сходства и m = M_T – 1. Поскольку M_T – максимальное разрешенное значение mnv между двумя «соседями», необходимо брать в расчет только m ближайших соседей данной точки. Далее необходимо отсортировать матрицу S, для получения для каждой точки m ближайших соседей. Таким образом, матрица будет представлена как R = [r_ij], где i – от 0 до N – 1, j – от 0 до m – 1, где r_ij – j-ый ближайший сосед i.

Шаг 2. Нахождение значений mnv.

Полученная матрица содержит пары N ´ m значений. Необходимо использовать матрицу R, чтобы построить новую матрицу, содержащую значения mnv для каждой из таких пар точек.

Шаг 3. Сортировка полученных значений mnv.

Отсортируем матрицу, полученную на шаге 2 и обозначим ее за V = [v_ij], где i – от 0 до N – 1, j – от 0 до m – 1, где v_ij – точка, которая j-ая по близости к i исходя из значения mnv.

Шаг 4. Выделение «соседних точек».

Пусть i=0, j=1 и r=0.

Если mnv(i, v_ij) £ M_T и сходство sim(i, v_ij) > r, то пометить v_ij как соседнюю точку i.

r = sim(i, v_ij). j = j + 1.

Если j ³ m или mnv(i, v_ij) > M_T, то i = i +1.

Если i ³ N, то остановиться, иначе повторить сначала этот шаг.

Можно отметить, что на этом шаге взяты в расчет только 1-ое и 2-ое условие. 3-е условие будет выполнено после удаления отношений соседства тех пар, которые не симметричны.

Шаг 5. Нахождение компонент связности.

Найти на графе окрестностей, составленном ранее, компоненты связности и выделить их как небольшие кластеры.

Шаг 6. Заключительная обработка.

Если есть мелкие кластеры, определить, объединяться ли они с каким-нибудь более крупным, если ослабить условия 2 и 3, и если да, то объединить их.