Авт. обработка текстов на естественном языке и комп. лингвистика. Большакова (2014) (1185448), страница 58
Текст из файла (страница 58)
Эксперименты, проведённые Ф. Кэном, показали, что после обновлениямассива документов С2ICM производит очень близкие кластеры к тем, что и C3Mпутём полной перекластеризации.Идея алгоритма C3M заключается в количественной оценке взаимоотношениякаждой пары документов: насколько первый документ «покрывает» второй инаоборот. Эта оценка по сути является ассиметричной оценка сходства двухдокументов, учитывающей сколько общих терминов у документов, сколько всеготерминов в первом документе и сколько раз каждый общий термин встречается вколлекции.
Матрица коэффициентов покрытия С (| |x| |) вычисляется следующимобразом:|"|(47)¸ ∑)E, ) ä)),|'||"|где ,1, |"|, ¸1⁄∑rE, r , ä) 1⁄∑rE, r) .показывает, с какой степенью документ покрывается документом .Коэффициентыобладают следующими свойствами:1) 0 <<1, 0 << 1;¶ , minX Z 1/|"| для бинарных весов терминов в документах;2)3) + , f V f ⋯ f |"| . 1;4)=0 ↔ =0;>0↔> 0; в общем случае» ;5)↔ di и dj – идентичны;6) di является отличным ото всех ↔1.Идентичные документы с равной степенью покрываются всеми другимидокументами.
Если у двух документов нет общих терминов, то их коэффициентыпокрытия cij и cji будут равны 0. Если di и dj имеют общие редкие термины, то cijвозрастает.Поскольку в общем случае, если документ имеет общие термины с малымчислом других документов, то значениебудет близко в 1, иначе к 0, тоназывают коэффициентом разделимости, а1C– коэффициентовобъединяемости. К коллекции, состоящей из близких документов, коэффициентразделяемости будет низким, а в коллекции из различных документов – высоким,поэтому количество кластеров предлагается вычислять следующим образом:(48)∑|"|| || |±E, , где 1 = ± = minX " , m Z.Затем для каждого документа ∈ вычисляется затравочная сила } :∑|'|}, если веса терминов в документах бинарные,E,(49)WWW(50)∑|'|иначе }Z, где W, W 1C W ,E,XW– элемент матрицы коэффициентов покрытия для каждой парытерминов, вычисляется аналогично по формуле (47) только не длядокументов, а для терминов1, |'| .Определим документы-затравки как nc документов с наибольшей затравочнойсилой.
Если в массиве документов есть идентичные документы, то выбираем толькоодин из них (любой). Для остальных документов коллекции определяем документызатравки, которые максимально покрывают их, и помещаем эти документы всоответствующие кластеры.203Алгоритм в общем виде.Начальная итерация (t = 0) – новая коллекция документов, тогда разбитьпосредством C3M.C3M:Вход: множество проиндексированных документов .Шаг 1. вычислить матрицу коэффициентов покрытия C = { } по формуле (47);Шаг 2.
вычислить количество кластеров nc по формуле (48);Шаг 3. для каждого документа ∈ :Шаг 4.вычислить затравочную силу } по формуле (49);Шаг 5. упорядочить ∈ по убыванию } ;Шаг 6. \ := <пороговое значение>;{0 © \ © 1 ; например, \ ≔ 0,001 }Шаг 7. выбрать первые nc документов в качестве затравок:? := ) ,1, ± , так, чтобы }÷2 C }÷2 I \;nc.Шаг 8. С ∶ ∅,1, ± ;Шаг 9. для каждого ∈ ::Шаг 10.для каждого ?) ∈∗Шаг 11.arg :÷2E:k max ) ;Шаг 12.С∗≔С∗f;Выход: множество кластеров = С, , … , Сùl ; множество затравок ? , j от 1 до(t > 0) – изменения в коллекции документов, требуется модифицироватьначальное разбиение.С2ICM:Вход: множество проиндексированных документов " j~, ; ž j~, ={С |? ∈ Cзатравка};, "Dj~, ;’ – множество новых документов; '' – множество удаляемых издокументов.Шаг 1.
обновить массив документов " j := " j~, f ’ – ’’;Шаг 2. обновить словарь ' j : удалить термины, которые не принадлежат ниодному документу; добавить термины из новых документов, если их раньше не былов словаре.Шаг 3. C3M: обновить матрицу C = { }, массив } , вычислить nc и {?) };Шаг 4.
Сформировать множество документов, подлежащих кластеризацииj"Dj ≔ "’ f ";÷f "Dj~,. где "Dj~, – множество документов, не покрытых ниодним кластером на шаге (t-1);j";÷=∈ " j~, | ∈ g , g C недействительный кластер на шаге ( ;Шаг 5. Кластеризовать "Dj с помощью C3M: шаги 5-12;Шаг 6. Если есть документы из "Dj , которые не попали ни в один кластер, топоместить их в "Dj;Выход: множество кластеров ž j = С, , … , Сùl ; множество затравок ? j , j от 1 доnc, "Dj.204Пример. Для простоты вычислений будем использовать бинарные весатерминов в наших документах.t1t2t3t4t5t6китайский пекин шанхай макао япония токио10000d1 101000d2 100100d3 100011d4 1100011d510001d6 0t=0. Целиком новый массив документов.
Алгоритм C3M.Матрица коэффициентов покрытия С:Затравочная сила документов } :0.3500 0.1000 0.1000 0.1000 0.1000 0.25000.45500.1000 0.6000 0.1000 0.1000 0.100000.48000.1000 0.1000 0.6000 0.1000 0.100000.48000.0667 0.0667 0.0667 0.3444 0.3444 0.11110.67740.0667 0.0667 0.0667 0.3444 0.3444 0.11110.67740.2500000.1667 0.1667 0.41670.4861Число кластеров nc = 3.Выбираем 3 документа-затравки с наибольшей затравочной силой.
Наибольшаясила 0.6774 у d4 и d5, проверим, являются ли они «идентичными» документами (см.определение матрицы коэффициентов покрытия): с44 = с55 = с45 = с54 = 0.3444.Только один из «идентичных» документов может быть выбран. выбираем d5. Итак,затравочные документы: d5, d6 и d2, обладающие затравочной силой 0.6774, 0.4861 и0.4800 соответственно.Получаем три кластера:1 = {d5,d4}; 2 = {d6,d1}; 3 = {d2,d3}.t=1. Обновление массива документов. Алгоритм C2ICM.Добавим новый документ d7 = [0 1 0 1 0 0] и удалим d2 = [1 0 1 0 0 0]:t1t2t4t5t6китайский пекин макао япония токио1000d1 10100d3 10011d4 10011d5 11001d6 01100d7 0Заметим, что признак t3 больше не принадлежит ни одному документу.Матрица коэффициентов покрытия С:Затравочная сила документов } :0.2917 0.1250 0.1250 0.1250 0.1667 0.16670.41320.1250 0.3750 0.1250 0.125000.25000.46880.0833 0.0833 0.3611 0.3611 0.111100.69210.0833 0.0833 0.3611 0.3611 0.111100.69210.166700.1667 0.1667 0.3333 0.16670.44440.1667 0.2500000.1667 0.41670.4861Число кластеров nc = 2.205Выбираем 2 документа-затравки с наибольшей затравочной силой: d5 (стараязатравка) и d7 (новая затравка), обладающие затравочной силой 0.6921 и 0.4861соответственно.Следовательно, r = {d6, d1, d3};Ищем документы-затравки, которые максимально покрывают элементымножества r.Получаем два кластера:1 = {d5,d4,d6}; 2 = {d7,d1,d3}.Вычислительная сложность.
Относительно размера коллекции документовалгоритмы C3M и C2ICM имеют линейную вычислительную сложность.§ 2.6.Нейросетевой алгоритм SOMАлгоритм самоорганизующихся карт (SOM, Self Organizing Maps) былпредложен Тойво Кохоненом в 1982 году как решение проблемы визуализации икластеризации данных. Визуализация данных осуществляется путём проецированиямногомерного пространства данных в двумерное пространство – карту данных.
Такаякарта, построенная для массива полнотекстовых документов, может служить какпоисковый механизм, альтернативный поиску по запросу, предлагающийпользователю обзор/навигацию по коллекции документов. Документы близкихтематик оказываются на карте рядом.Идея алгоритма заключается в том, чтобы обучить нейронную сеть без учителя.Сеть состоит из некоторого числа нейронов, упорядоченных по узлам двумернойсетки. Каждый нейрон имеет координаты в исходном |m|-мерном пространстведокументов и в двумерном пространстве карты. В процессе обучения нейроныупорядочиваются в пространстве документов так, чтобы наилучшим образом описатьвходной массив документов. Этот процесс является итерационным, на каждойитерации t:а) случайным образом выбирают из входного массива ∈ ;б) находят нейрон-победитель Ml ∈ , то есть ближайший к документу :(51)с = arg min £ C M £ , для ∀M ∈ , = 1, | |;‖ ‖ – евклидово расстояние между векторами в пространстве терминов;в) корректируют веса (координаты в пространстве терминов) нейронапобедителя и его соседей:(52)M X( f 1ZM X(Z f l X(ZŠ C M X(Z‹,где l X(Z – это функция соседства, которая определяет, у какого количестванейронов (узлов сетки), окружающих нейрон-победитель, изменятся веса и насколькосильно они изменятся.
Часто функция соседства имеет следующий вид:•££(53)³~ 1 • ´• X ZŽ,l X( Z = ¸X(Zгде ¸X(Z – коэффициент обучения, монотонно убывающий с ростом номераитерации t, 0 © ¸X(Z © 1; на начальных шагах работы сети происходит заметноеупорядочивание векторов нейронов, а на остальных –уточняющая подстройка карты;часто ¸X(Z задают как линейную, экспоненциальную или обратно пропорциональнуюфункцию ¸X( Z e⁄X( f hZ, где A и B – константы;G , Gl ∈ HV – координаты нейронов как узлов сетки;206X(Z – ширина соседства, монотонно убывающая с ростом номера итерации t.Процесс обучения сети завершается, когда ошибка E как среднее расстояниемежду документами и их ближайшими нейронами становится меньше требуемогопорогового значения:,(54)∑|"|‖‖ÊE, ¤ C Ml .|"|Координатами документов на карте являются узлы, соответствующиеближайшим им нейронам (нейронам-победителям).Для визуализации карты вычисляют матрицу расстояний между нейронами впространстве терминов.
Область карты, соответствующую очередному нейронуокрашивают цветом, определённым пропорционально среднему расстоянию данногонейрона до всех его ближайших соседей (узлов на карте). Если для окраскииспользуются градации серого цвета, то чем ближе расположились в результатеобучения соседние нейроны в пространстве терминов, тем светлее будутсоответствующие им ячейки карты, и наоборот, чем дальше, тем темнее.
Похарактеру окраски карты можно делать выводы о количестве и составе кластеровдокументов: темные области карты соответствуют границам между кластерами.Другим способом определения кластеров является кластеризация итоговых нейроновлюбым алгоритмом, например, алгоритмом k-средних.Алгоритм в общем виде. Построение самоорганизующейся карты.Вход: множество проиндексированных документов , размеры сетки (len x len).Шаг1.Инициализациякарты:распределениенейронов1, | |, | | 7Ž± 7Ž±, по узлам карты и присвоение случайныхM ∈ ,значений весам нейронов (координатам в пространстве терминов).t := 0; задать пороговое значение допустимой ошибки обучения \.Шаг 2. tr := .Шаг 3.
Извлечь случайный документ ∈ jD .Шаг 4. Вычислить нейрон-победитель Ml ∈по формуле (51).Шаг 5. Скорректировать веса нейрона-победителя и его соседей по формуле(52).Шаг 6. t := t + 1. Если "ß » ∅, то продолжить с шага 3, иначе перейти к шагу 7.Шаг 7. Вычислить текущую ошибку обучения E по формуле (54). Если Е > \, топовторить с шага 2.Выход: множество нейронов, представленных как в пространстве терминов,так и в двумерном пространстве карты (сетки).Пример. Продолжим наш пример с шестью документами, построим для нихкарту в виде прямоугольной сетки, содержащей 10 на 10 узлов (рис. 12).207Инициализацию весов нейроной выполним случайнымобразом. Коэффициент обучения зададим следующимобразом:¸ X( Z0,1 Ž X~ Z .Ширину соседства будем вычислять по формуле:Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
