Методології та програмні засоби класифікації природомовних текстових документів

Abstract

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 – Комп'ютерні системи та компоненти. Національний технічний університет України "Київський політехнічний інститут", м. Київ, 2012 р. Дисертаційна робота присвячена вирішенню задачі автоматичної ідентифікації мови і класифікації текстових природомовних документів. Запропоновано метод автоматичної ідентифікації мови з використанням статистик N-грам, проведено порівняльний аналіз різних способів класифікації текстових документів з метою вибору оптимальних за точністю і повнотою, запропонована класифікація природомовних текстових документів з 18 використанням розробленого методу статистик N-грам, запропоновано метод автоматичного створення багатотемної класифікації текстових документів в реальному часі, створено програмний модуль для ідентифікації мови та класифікації багатотемних текстових документів. Запропонований спосіб класифікації текстів і документів дозволив підвищити точність і швидкість класифікації, розробити відповідні програмні засоби для використання в системах автоматичної обробки текстів в багатомовних інформаційних системах.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. Национальный технический университет Украины "Киевский политехнический институт", г. Киев, 2012 г. Диссертационная работа посвящена задаче автоматической идентификации языка документа и классификации естественно-языковых текстовых документов. Проведен сравнительный анализ существующих методов идентификации языка текстовых документов. Среди них рассмотрены основные подходы: оптимизационный и подход на основе N-грамм. Сформулирована задача определения пригодности методов для решения задачи автоматической идентификации языка. Выполнена формализация модели процесса идентификации языка документа и предложен новый метод идентификации, получивший название метода статистик N-грамм. По сравнению с существующими метод позволяет сократить количество вычислительных операций и решить задачу идентификации в реальном времени. Как показали проведенные эксперименты, предложенный метод по точности идентификации находится среди лучших из рассмотренных методов, однако более прост в реализации и обеспечивает решение задачи идентификации в реальном времени. Выполнена постановка задачи классификации текстовых документов и обучения классификации. Проведен сравнительный анализ существующих методов классификации текстовых документов. Среди известных методов рассмотрены: метод опорных векторов (Support Vector Machine, SVM), метод k-ближайших соседей (k-Nearest neighbors, K-NN), метод деревьев решений (Decision Tree), метод Роше (Rocchio method), метод Байеса (Naïve Bayes).Проведены экспериментальные исследования по сравнительному анализу указанных методов. Наилучшие результаты по точности и полноте классификации получены SVM методом. Установлено, что недостатком этого метода является большой объем вычислений, что затрудняет его использование в реальном времени. Сделан вывод о том, что SVM метод может быть использован в качестве эталона для сравнения по эффективности с другими методами. Предложен новый метод классификации, основанный на принципах метода Байеса и k-близжайших соседей, которой получил название метода статистки N-грамм для классификации. Предложенный метод имеет сопоставимые результаты классификации по точности и полноте с SVM методом, однако значительно упрощает фазу обучения классификации, дополнения новых тематик, исключение тематик, обеспечивает уменьшение и распараллеливание вычислений в процессе классификации. Возможность вычисления критериев подобия параллельно для всего набора эталонов разрешает проблему реализации процесса классификации в реальном времени. Исследованы методы представления текстовых документов и влияние типа моделей на эффективность автоматической классификации документов. Экспериментальные исследования и сравнение между собой наиболее распространенных методов описания отдают предпочтенных методу N-грамм. В данном методе в качестве признаков текста используются подряд идущие буквосочетания фиксированной длины N. Тем самым каждое слово разбивается на набор признаков, а однокоренные слова образуют сходные наборы признаков. Отпадает необходимость в дополнительной лингвистической обработке текста. Кроме того, выполнение разбиения на N-граммы гораздо проще, чем выделение базовых лексем и применимо для большинства естественных языков за исключением иероглифических. Делается заключение о том, что метод N-грамм является универсальным методом выделения признаков, применимым ко всем языкам. Разработан экспериментальный программный модуль классификации текстовых документов. Приведено описание архитектуры модуля. Модуль состоит из трех основных компонент: компонента лексического анализа, компонента вычисления меры сходства и классификатор. Модуль имеет четыре сценария функционирования: обучение, дообучение (возможность добавления новых тематик), классификация документов и удаление темы. Разработанное программное обеспечение обладает свойствами масштабируемости и расширяемости. Программный модуль реализован на языке программирования JAVA с использованием платформы WINDOWS. Исследование работы комплекса выполнено с использованием текстов "Reuters-21578" и "20Newsgroups". При этом в выборке "Reuters-21578" использовались имеющиеся разбиения на обучающее и тестирующее множества. Из коллекции "20Newsgroups", в которых не предусмотрены стандартные разбиения, были отобраны 8 различных категорий документов: атеизм; компьютерная графика; автомобили; мотоциклы; религия; баскетбол; хоккей; криптография. Обучающий набор содержит 4967 документов, тестовый набор – 3303. В процессе исследования был сделан вывод о том, что созданный программный модуль позволяет классифицировать текстовые документы, используя SVM метод и предложенный метод статистики N-грамм. Оба метода показали эффективность классификации с точностью 84%-96%. Экспериментально подтверждена возможность классификации текстовых документов методом статистики N-грамм в реальном масштабе времени

Thesis for a Ph.D degree by the speciality 05.13.05 – Computer systems and components. National Technical University of Ukraine "Kyiv Polytechnic Institute", Kyiv, 2012. The thesis is devoted to solving the problem of automatic language identification and classification of natural language text documents. The method for automatic identification of languages using statistical N-grams, comparative analysis of different methods of classification of text documents in order to choose optimal precision and recall, the proposed classification natural language text documents using the method developed by statistical N-grams, the method automatically classify text documents in real time, created a software module for the identification and classification natural language text documents. The proposed method of classification of text documents allowed to improve accuracy and speed of classification, to develop appropriate software for use in automatic processing of texts in multilingual information systems.