Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика (1027379), страница 58
Текст из файла (страница 58)
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 .Ширину соседства будем вычислять по формуле:Рис. 12. Исходныйпорядок нейронов на картеX( Z 7Ž± Ž Q~ S ,где len – это число узлов на каждой стороне сетки, С –константа, g 1000⁄lnX7Ž±Z.Пороговому значению ошибки E присвоим значение0,0000001.Запустим алгоритм SOM.В результате было выполнено 1384 итерации, итоговые координаты документовв двумерном пространстве карты следующие: d1 (0;0), d2 (5;9), d3 (5;0), d4 (9;1), d5(9;5), d6 (0;5). Левый верхний узел карты – координаты (0;0).
Сама карта, построеннаяс помощью вычисления матрицы расстояний между нейронами, представлена на рис.13.Рис. 13. Самоорганизующаяся карта для примера из шести документовПо цвету ячеек на карте видим, что образовалось три кластера:1 = {d1,d6}; 2 = {d3,d4,d5}; 3 = {d2}.Вычислительная сложность. Алгоритм имеет квадратичную сложность почислу документов – œX|'| |"|V Z.§ 2.7.Экспериментальная оценка результата классификации безучителяРазбиение документов на кластеры оценивают путём вычисления мер качества,которые бывают двух видов:а) внешние меры, сравнивают созданное системой разбиение документов с«эталонным» разбиением;б) внутренние меры, автоматически анализируют внутренние свойства, присущиеконкретному массиву документов.208Внешние меры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
