Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика (1027379), страница 59
Текст из файла (страница 59)
Ключевым понятием в сравнении «эталонного» иавтоматически полученного разбиения является анализ сходства предсказанийэкспертов и предсказаний системы относительно принадлежности каждой парыдокументов одному или разным кластерам. Для каждой пары документов , , где, ∈ , на основе знания о двух разбиениях * и , ( * получено от экспертов, –алгоритмом кластеризации) необходимо составить таблицу следующего вида:,,,принадлежат одномукластеру в *принадлежат одномукластеру впринадлежат разнымкластерам в,принадлежатразным кластерам в *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. – San Francisco, 1997. – P. 412-420.4. Ester M. A Density-Based Algorithm for Discovering Clusters in Large SpatialDatabases with Noise / M. Ester, H.-P .Kriegel, J.
Sander, X. Xu // Proceedings of2nd International Conference on Knowledge Discovery and Data Mining (KDD96). – Portland, 1996. – P. 226-231.5. Can F. Experiments on Incremental Clustering. – Miami University,1991.–Access mode:http://sc.lib.muohio.edu/bitstream/handle/2374.MIA/187/fulltext.pdf?sequence=16. Kohonen T. Self organization of a massive document collection / T.
Kohonen, S.Kaski, K. Lagus, J. Salojärvi, J. Honkela, V. Paatero, A. Saarela // IEEETransactions on neural networks. – 2000. – Vol. 11, No. 3. – P. 574 - 585.7. van Rijsbergen C. J. Information retrieval [Electronic resource]. – Electronic textand graphic data. – 1979. – Аccess mode:http://www.dcs.gla.ac.uk/Keith/Preface.html8. Halkidi M. On Clustering Validation Techniques / M.
Halkidi, V. Batistakis, M.Vazirgiannis // Journal of Intelligent Information Systems, Kluwer AcademicPublishers. Manufactured in The Netherlands. – 2001. – 17:2/3. – P. 107-145.9. Sebastiani F. Machine Learning in Automated Text Categorization // ACMComputing Surveys. – 2002. – Vol. 34, No. 1. – 47 p.212ЧАСТЬ VI.Глава 1.§ 1.1.ИНФОРМАЦИОННЫЕ ПОТОКИИ СЛОЖНЫЕ СЕТИ(Д.В. ЛАНДЭ)Основы анализа информационного пространства иинформационных потоковПонятие информационного пространстваПод информационным пространством принято понимать совокупностьинформационных ресурсов, технологий их сопровождения и использования,информационных и телекоммуникационных систем, образующих некуюинформационную инфраструктуру.
Элементами информационного пространствамогут быть, в частности, документы, обобщающие самые различные видыинформации – файлы, электронные письма, веб-страницы не зависимо от форматових представления.Естественно, приведенноеопределение информационного пространстваявляется качественным. Конечно же, термин «пространство» в данном случае, несовпадает с понятием «пространство» в математике или физике. В качестве примеровудачных моделей информационного пространства можно приветсти «векторнопространственную» модель Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
