Авт. обработка текстов на естественном языке и комп. лингвистика. Большакова (2014) (1185448), страница 59
Текст из файла (страница 59)
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Внешние меры.
Ключевым понятием в сравнении «эталонного» иавтоматически полученного разбиения является анализ сходства предсказанийэкспертов и предсказаний системы относительно принадлежности каждой парыдокументов одному или разным кластерам. Для каждой пары документов , , где, ∈ , на основе знания о двух разбиениях * и , ( * получено от экспертов, –алгоритмом кластеризации) необходимо составить таблицу следующего вида:,,,принадлежат одномукластеру в *принадлежат одномукластеру впринадлежат разнымкластерам в,принадлежатразным кластерам в *acbdДальнейший анализ полученной таблицы аналогичен описанному в § 1.9:вычисляют меры качества, заданные формулами (35)-(40), применяют микро-, макроусреднение.Внутренние меры. Внутренние меры предназначены как для сравненияразбиения на кластеры разными алгоритмами, так и одним и тем же алгоритмом, но сразными значениями входных параметров.
Примером второго случая являетсяпопытка автоматически установить, какое количество кластеров приведёт коптимальному в определённом смысле разбиению. Внутренние меры строятся наоснове предположения, что оптимальное разбиение обладает свойствамикомпактности и отделимости. Компактность означает, что члены одного кластерадолжны быть настолько близкими друг другу, насколько это возможно. Отделимость– что сами кластеры должны достаточно далеко отстоять друг от друга.Приведём примеры трёх внутренних мер: для чёткого плоского, нечёткогоплоского и иерархического разбиения.
Подробнее об этих и других мерах можноузнать, например, из работы [8].Внутренняя мера чёткого плоского разбиения. Индекс Дана DI:(55)min δ (ci , c j )DI (C ) =где+ , .,|l1 | Bl2 Bкластерами;ΔX # Z2{}i≠ jmax ∆(cl )1≤l ≤ N c,C = c1 ,..., c NC – множество кластеров; õ_∑:k∈l1 ,:é∈l2∑„ ∈ : ÷j+:$2 ,l$$ .$³ 2 |l |´$?(+ $) , $r . –мера|ž|;расстояниямежду– мера диаметра кластера.rci – вектор центроида кластера ci.Оптимальному разбиению данных соответствует максимальное значениеиндекса Данна.Внутренняя мера нечёткого разбиения. Модифицированный коэффициентразбиения MPC:| |(56)a`g X| |Z 1 C .209a`g X| |Z1C`g X| |Z| |+1 C `g X| |Z.,| |C11| |(57)| | | |A A üV ,E, E,где 0 = a`g X| |Z = 1,,PC(| |) – коэффициент разбиения, | | = `g X| |Z = 1;ü – элемент матрицы нечёткого разбиения.Оптимальному разбиению данных соответствует максимальное значениемодифицированного коэффициента разбиения.Внутренняя мера иерархического разбиения. Кофенетический коэффициенткорреляции (CPCC), для вычисления которого необходимо сформироватькофенетическую матрицу SC.
Каждым элементом данной матрицы является номеруровня в иерархии кластеров, на котором документы di и dj впервые встретились водном кластере. Мера CPCC оценивает степень сходства кофенетической матрицы SCи действительной матрицы близости документов коллекции S.N −1 | N(58)(1 M ) ∑ ∑ (sij scij − µ S µ S )DCPCC (C ) =гдеDCi =1 j =i +1N D −1 N D (1 M ) ∑ ∑ sij2 − µ Si =1 j =i +1(-1 ≤ CPCC ≤ 1; M =N D −1 N D) (1 M ) ∑ ∑ (sci =1 j =i +12ijN D ( N D − 1); õ%2− µ SC ,)|"|;sij и scij – (i, j)-ые значения матриц S и SC соответственно;1µS =MNDND∑ ∑si =1 j = i +1ij, µ SC1=MNDND∑ ∑ sci =1 j =i +1ij– здесь средние значения матриц S и SCсоответственно.Чем ближе к нулю значение CPCC, тем ниже сходство между матрицами.§ 2.8.Выбор метода классификации без учителяОбзор экспериментальных исследований.
В области классификации безучителя сложилась не такая благоприятная среда для сравнительного анализаэкспериментов, как в области классификации с учителем. В первую очередь этосвязано с высокой трудоёмкостью формирования тестовых данных. В соответствии сопределением внешних критериев необходимо, чтобы эксперт заранее оценил( ( ( | | Z*X| | – 1 Z Z/2 Z пар документов, что является непосильной задачей дляреальных коллекций документов, содержащих десятки тысяч документов и более.Неизвестны готовые наборы данных для экспериментов, и большинство коллективовпроводят эксперименты на собственных данных и применяют собственные методикидля оценки, что затрудняет сравнительный анализ разных алгоритмов по результатамиз различных публикаций.Таким образом, главным основанием для выбора алгоритма кластеризацииявляется знание о его теоретических характеристиках и оценка пригодности длярешения частной задачи разбиения текстов.210Подход к поиску разбиения.
Алгоритмы, применяющие теоретико-графовыйподход, к ним относятся рассмотренные иерархические агломеративные алгоритмы,имеют как минимум квадратичную сложность вычислений, что делает ихмалопригодными для приложений, где на первом месте стоит производительностьсистемы. С другой стороны, этот вид алгоритмов может приносить выигрыш вэффективности, то есть в качестве классификации, поскольку имеет глобальнуюсходимость, детерминирован и частично лишен таких недостатков многих плоскихалгоритмов как, например, необходимость заранее знать число кластеров.Итеративные алгоритмы, пытающиеся улучшить изначальное разбиение массивадокументов путем оптимизации некоторой целевой функции, к ним относятсяалгоритм k-средних и его модификации, имеют линейную вычислительнуюсложность, что делает их привлекательными для реализации в составе программнойсистемы.
И не смотря на их теоретическую локальную сходимость, нередкопоказывают приемлемый уровень эффективности системы. Однако эти алгоритмычувствительны к шуму. Если известно, что массив документов содержит большойпроцент шума, то следует применять либо модификации k-средних, либоиерархические алгоритмы, либо алгоритмы, специально спроектированные дляборьбы с шумом, например, плотностный алгоритм DBSCAN.
У последнего имеетсяещё одно преимущество относительно k-средних – это распознавание кластеровпроизвольной формы. Но достичь этого возможно только при удачном подборепараметров плотности, что на практике не всегда удаётся. В вопросе количестванастроечных параметров и важности способа их инициализации самыминеприхотливыми являются иерархические агломеративные алгоритмы, которые вобщем случае не используют никаких дополнительных параметров.Нечёткие алгоритмы, относящие документы к нескольким кластерамодновременно, имеют преимущество над чёткими в тех приложениях, где природаданных подразумевает такую нечёткость.
Они имеют те же недостатки, что и ихчёткие предшественники, например, сказанное в этом подразделе про алгоритм kсредних верно и для алгоритма нечётких c-средних.И, наконец, если приложение требует визуализировать полученные кластеры, тоимеет смысл обратить внимание алгоритмы, специально на это нацеленные, к ним впервую очередь относится алгоритм самоорганизующихся карт, и в некоторомсмысле можно отнести иерархические алгоритмы. Однако не следует ожидать, чтотакие карты будут востребованы широкой аудиторией пользователей.211Список используемой литературы1.
Маннинг К. Д., Рагхаван П., Шютце Х. Введение в информационный поиск.:Пер. с англ. – М.: ООО «Вильямс», 2011. – 528 с.: ил.2. Yang Y., Liu X. A re-examination of text categorization methods, School ofComputer Science Carnegie Mellon University Pittsburgh, PA 15213-3702, USA,1999 – p. 8.3. Yang Y., Pedersen J. O. A Comparative Study on Feature Selection in TextCategorization // The Fourteenth International Conference on Machine Learning:Proceedings of ICML'97.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
