Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика

Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика, страница 58

PDF-файл Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика, страница 58 Системы автоматизированного проектирования (САПР) (13021): Книга - 11 семестр (3 семестр магистратуры)Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика: Системы автоматизированного проектирования2017-12-21СтудИзба

Описание файла

PDF-файл из архива "Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика", который расположен в категории "". Всё это находится в предмете "системы автоматизированного проектирования (сапр)" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "интеллектуальные подсистемы сапр" в общих файлах.

Просмотр PDF-файла онлайн

Текст 58 страницы из PDF

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Внешние меры.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4995
Авторов
на СтудИзбе
467
Средний доход
с одного платного файла
Обучение Подробнее