Авт. обработка текстов на естественном языке и комп. лингвистика. Большакова (2014) (1185448), страница 56
Текст из файла (страница 56)
Вторые разбивают кластеры сверху вниз, начиная с одногокластера, которому принадлежат все документы коллекции, затем этот кластерделится на два и так рекурсивно до тех пор, пока каждый документ не окажется всвоём отдельном кластере. Нисходящие алгоритмы концептуально более сложные,так как необходимо на каждом шаге применять дополнительный алгоритм плоскойкластеризации. Нисходящая иерархическая кластеризация может оказать весьмаэффективной, если, например, нет необходимости генерировать полное дерево вплотьдо отдельных документов, а ограничиться только верхними уровнями.
Еслииспользовать эффективный линейный плоский алгоритм, например, k-средних, тоалгоритм нисходящей кластеризации окажется линейной сложности по размеруколлекции. Вдобавок, восходящий алгоритм начинает разбиение, основываясь толькона информации о локальных документах, а нисходящий начинает с анализа полнойинформации о глобальном распределении документов.Рассмотрим подробнее агломеративные алгоритмы.
Основное их различиезаключается в выборе критерия, используемого для принятия решения о том, какиекластеры следует объединить на текущем шаге алгоритма. Большое распространениеполучили три следующих критерия:а) одиночная связь (минимальное расстояние, или максимально сходство): сходстводвух кластеров есть сходство между их наиболее похожими документами;б) полная связь (максимальное расстояние, или минимальное сходство): сходстводвух кластеров есть сходство между их наиболее непохожими документами;193в) групповое усреднение (усреднение всех показателей сходства): сходство двухкластеров есть среднее сходство всех пар документов, включая пары документовиз одного кластера, исключая близость документа самому себе, см.
формулу(41).(41)1æÑ$$AA? M +g , g .? M+ ) , r .,+|g | f Bg B.+|g | f Bg B C 1.:k ∈_1 ∪_2 :k ∈_1 ∪_2 ::k è:éгде g и g – i-ый и j-ый кластер; sim – мера сходства, например, косинусная мераблизости (3).Кластеризация с одиночной связью создаёт протяженные («цепочные»)кластеры, «сцепленные вместе» элементами, возможно, случайно оказавшимисяближе остальных друг к другу (рис. 6). Этот критерий носит локальный характер, таккак не учитывает всю структуру кластера, например, его другие более удалённыечасти.
Кластеризация с полной связью создаёт компактные кластеры (рис. 7) и носитглобальный характер, так как на решение об объединении кластеров влияет всяструктура кластера, однако это одновременно повышает чувствительность квыбросам. Кластеризация с групповым усреднением позволяет избежать недостатков,свойственных критериям одиночной и полной связи.Иерархические алгоритмы в общем случае не требуют исходного заданияколичества кластеров, однако на практике часто бывает нужно разбиение нанепересекающиеся кластеры, как при плоской кластеризации.
Тогда следуетиерархию кластеров отсечь на некотором уровне. Выбор уровня может выполняться,например, так:а) указать точное число кластеров k, на рис. 6 и рис. 7 разбиение при k = 2 показанопунктирной линией: 1 = {d1, d2, d4, d5, d6}, 2 = {d3} и 1 = {d1, d4, d5, d6},2 = {d2, d3} соответственно;б) указать минимальное значение близости между кластерами и провести сечениена этом уровне;в) отсечь на уровне максимальной разницы между двумя последовательнымимерами сходства (различия) между кластерами, на рис. 6 и рис. 7 эта, такназываемая «естественная кластеризация», показана штриховой линией: 1 ={d4, d5}, 2 = {d1, d6}, 3 = {d2}, 4 = {d3} и 1 = {d4, d5}, 2 = {d1, d6}, 3 ={d2}, 4 = {d3} соответственно.Алгоритм в общем виде (алгомеративная иерархическая кластеризация).Вход: множество проиндексированных документов .Шаг 1.
Для каждого ∈ :Шаг 2.Для каждого ∈ :Шаг 3.? ≔ ? MX $ , $ Z, где S = {? } – матрица сходства междукластерами;Шаг 4.^ ≔ 1, где F – массив, сообщающий о кластерах, доступных дляобъединения.Шаг 5. A := ∅, где A – последовательность объединений кластеров;Шаг 6. Для всех k от 1 до N – 1:〈 , M〉 ≔ arg max〈 ,Ì〉: èÌ;Û1 E,; ÛîE, ? Ì ;Шаг 7.Шаг 8.A := A + 〈 , M〉;Шаг 9.Для всех j от 1 до |"|:194? ≔ ? MX ï ,Ìð , Z;? ≔ ? MX ï ,Ìð , Z,где ï ,Ìð – кластер, полученный путём объединениякластеров i и m,– j-ый кластер;Шаг 12.^Ì ≔ 0;Выход: список объединений A.Пример.
Вычислим матрицу расстояний для всех документов из нашегопримера.Sim d1d2d3d4d5 d60d10d2 1,360d3 1,37 1,390d4 1,36 1,39 1,400d5 1,32 1,36 1,38 0,27d6 0,66 1,43 1,41 1,30 1,21 0Результат иерархической агломеративной кластеризации по правилу одиночнойсвязи представлен на рис. 6.Шаг 10.Шаг 11.Рис. 6. Дендрограмма кластеризации с одиночной связью для примера из 6документовРезультат иерархической агломеративной кластеризации по правилу полнойсвязи представлен на рис. 7.Рис. 7. Дендрограмма кластеризации с полной связью для примера из 6 документовВычислительная сложность. Сложность агломеративного иерархическогоалгоритма зависит от выбранной меры близости (различия) между кластерами испособа реализации идеи алгоритма.
Известны реализации со следующими оценкамивычислительной сложности: одиночная связь – œX|"|V Z; полная связь –195œX|"|V log|"|Z; усреднение по группе – œX|"|V Z. Сложность дивизимного алгоритмазависит от выбранного дополнительного алгоритма плоской кластеризации, есливыбран алгоритм k-средних, то – œX|"|Z.§ 2.2.Алгоритм k-среднихПервые применения алгоритма k-средних были описаны в работе ДжеймсаМакКуина в 1967 году. При заранее известном числе кластеров k алгоритм k-среднихначинает с некоторого начального разбиения документов и уточняет его,оптимизируя целевую функцию – среднеквадратичную ошибку кластеризации каксреднеквадратичное расстояние между документами и центрами их кластеров:)(42)VŽX", žZ A A £ $ C Ÿ$ £ ,E, ::1 ∈_2где Ÿ – центр, или центроид, кластера g ,формуле:Ÿ$1A ###$% ,|g |: :1 ∈_21, |ž|, |ž|*, вычисляющийся по(43)где |g | – количество документов в g .Идеальным кластером алгоритм k-средних считает сферу с центроидом в центресферы.Действие алгоритма начинается с выбора k начальных центров кластеров.Обычно исходные центры кластеров выбираются случайным образом.
Затем каждыйдокумент присваивается тому кластеру, чей центр является наиболее близкимдокументу, и выполняется повторное вычисление центра каждого кластера какцентроида, или среднего своих членов. Такое перемещение документов и повторноевычисление центроидов кластеров продолжается до тех пор, пока не будет достигнутоусловие остановки. Условием остановки может служить следующее: (а) достигнутопороговое число итераций, (б) центроиды кластеров больше не изменяются и (в)достигнуто пороговое значение ошибки кластеризации. На практике используюткомбинацию критериев остановки, чтобы одновременно ограничить время работыалгоритма и получить приемлемое качество.В общем случае алгоритм k-средних достигает локального минимума целевойфункции, что приводит к субоптимальному разбиению документов.
Поэтому важенспособ выбора начальных значений центроидов. Для этого известны различныеэвристические правила, например, получить начальные центры с помощью другогоалгоритма – детерминированного, например, иерархического агломеративного.Алгоритм в общем виде.Вход: множество проиндексированных документов , количество кластеров k.1, *, например, случайнымиШаг 1. Инициализация центров кластеров Ÿ$ ,числами.Шаг 2. g ≔ ,1, *.Шаг 3. Для каждого ∈ :∗≔ ÚG9 min £Ÿ$ C $ £ ,1, *;Шаг 4.Шаг 5.g∗ ≔ g∗ f;196Шаг 6. Для каждого g ∈ :,∑ : :1∈_2 ###$% ,Шаг 7.Ÿ$ :B_2 BШаг 8.
Если не достигнуто условие остановки, то повторить с шага 2.Выход: множество центров кластеров Ÿ$ и множество самих кластеров .Пример. Пусть k=2.1, * инициализированы случайным образом:Итерация 1. Начальные Ÿ$ ,Ÿ, Š0.96 0.80 0.42 0.79 0.66 0.85‹;ŸV Š0.49 0.14 0.91 0.96 0.04 0.93‹dist d1d2d3d4d5d61.551.811.661.511.380.85ñòñó 1.82 1.38 1.37 1.74 1.59 0,93C1 := {d1, d4, d5, d6}; C2 := {d2, d3}.Ÿ, Š0.24 0.45 0 0 0.43 0.35‹;ŸV Š0.159 0 0.49 0.49 0 0‹dist d1d2d3d4d5d60.741.211.220.680.610.67ñòñó 1.18 0.69 0.69 1.21 1.18 1.24C1 := {d1, d4, d5, d6}; C2 := {d2, d3}.Разбиение на кластеры не изменилось – условие остановки выполнено, мыполучили итоговые два кластера.Вычислительная сложность.
Алгоритм k-средних линейно зависит от всехсвоих факторов: от количества документов, количества кластеров, количестватерминов и количества итераций. Для сохранения линейной сложности (œX|"|Z) прикомбинировании с иерархическим с целью эффективного задания начальныхцентроидов кластеров, предлагается квадратичный иерархический алгоритмприменить к выборке документов размером ¦|"|. Такой подход получил названиеалгоритм картечи.Итерация 2.§ 2.3.Плотностный алгоритм DBSCANАлгоритм DBSCAN (Density Based Spatial Clustering of Applications with Noise),плотностный алгоритм для кластеризации пространственных данных с присутствиемшума), был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в1996 году как решение проблемы разбиения (изначально пространственных) данныхна кластеры произвольной формы [4].
Большинство алгоритмов, производящихплоское разбиение, создают кластеры по форме близкие к сферическим, так какминимизируют расстояние документов до центра кластера.197Рис. 8. Примеры кластеров произвольной формыАвторыDBSCANэкспериментальнопоказали, что их алгоритмспособенраспознатькластерыразличнойформы, например, как нарис. 8.Идея, положенная в основу алгоритма, заключается в том, что внутри каждогокластера наблюдается типичная плотность точек (объектов), которая заметно выше,чем плотность снаружи кластера, а также плотность в областях с шумом нижеплотности любого из кластеров. Ещё точнее, что для каждой точки кластера еёсоседство заданного радиуса должно содержать не менее некоторого числа точек, эточисло точек задаётся пороговым значением. Перед изложением алгоритма дадимнеобходимые определения.Определение 1. Eps-соседство точки }, обозначаемое как õör÷ X}Z, определяетсякак множество документов, находящихся от точки } на расстояния не более Eps:õör÷ X}Z {ø ∈ "| ?(X}, øZ = Ê}? .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
