Разработка и реализация быстрых алгоритмов классификации текстов опубликованных online

Разработка и реализация быстрых алгоритмов классификации текстов опубликованных online. Задача классификации текстов - одна из задач информационного поиска, заключающаяся в отнесении документа к одной из нескольких категорий на основании содержания документа. Задача классификации документов является подзадачей задачи Data Mining. Data Mining (добыча данных, интеллектуальный анализ данных) — собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Термин введён Григорием Пятецким-Шапиро в 1989 году. Определения классификации: Классификация - системное распределение изучаемых предметов, явлений, процессов по родам, видам, типам, по каким-либо существенным признакам для удобства их исследования; группировка исходных понятий и расположение их в определенном порядке, отражающем степень этого сходства. Классификация - упорядоченное по некоторому принципу множество объектов, которые имеют сходные классификационные признаки (одно или несколько свойств), выбранных для определения сходства или различия между этими объектами. Существующие алгоритмы классификации текстов, которые чаще всего используются: Ранжирование и четкая классификация; Метод Роше (Rocchio method); Деревья решений (Decision Tree); Метод опорных векторов (Support Vector Machine, SVM); Метод k-ближайших соседей (k-Nearest Neighbors, k-NN); Метод «случайный лес» (Random Forest); Метод Байеса (Naive Bayes). Для решения задачи классификации текстов был выбран метод частотного анализа. Частотный анализ основывается на предположении о существовании нетривиального статистического распределения отдельных слов и их последовательностей в тексте. Частотный анализ предполагает, что частота появления заданного слова алфавита в достаточно длинных текстах одна и та же для разных текстов одного языка. Постановка задачи. Существует множество категорий; Существует множества текстов по каждой категории; Имеется текстовый файл; Необходимо определить категорию текстового файла. Определение категорий В качестве категорий выступают 16 основных направлений деятельности Правительства Российской Федерации: Здравоохранение; Культура ; Природные ресурсы и экология; Внутренние дела (МВД); Иностранные дела (МИД); Образование и наука; Промышленность и торговля; Спорт; Связь и массовые коммуникации; Энергетика; Финансы; Транспорт; Труд и социальная защита; Сельское хозяйство; Оборона; Экономическое развитие. В качестве текстов, определяющих категории, используются нормативно-правовые акты Российской Федерации, регулирующие отношения в соответствующем направлении деятельности. Таким образом, построение категорий происходит на основании нормативно-правовых актов Российской Федерации. Нормативно-правовой акт. официальный документ установленной формы, принятый в пределах компетенции уполномоченного государственного органа  с соблюдением установленной законодательством процедуры, содержащий общеобязательные правила поведения, рассчитанные на неопределённый круг лиц и неоднократное применение; имеют определённый вид и облекаются в документальную форму; составляются по правилам юридической техники; нормативные правовые акты, действующие в стране, образуют единую систему. Определение категорий происходит в соответствии с выборкой нормативно-правовых актов, относящихся к соответствующим категориям. Анализ входящего текста Исключение частиц, предлогов, местоимений и слов длинной менее трех символов Нормализация слов Определение частоты появления каждого слова в тексте Сравнение Используется метод частотного анализа; Каждая категория – список слов с соответствующими частотами вхождения; Определяется вес каждого слова во входящем текстовом файле; Сравнение происходит при совпадении более пяти слов. Алгоритм сравнения X – функция соответствия a – отношение числа вхождения слова к общему количеству слов b - инверсия частоты, с которой слово встречается в документах категорий D - количество документов в категории n – количество документов, в которых встречается слово Используемые средства В качестве программных средств для решения задачи были выбраны язык Java и средства разработки Eclipse; Для хранения и обработки текстовой информации необходимы база данных и СУБД. База данных MySQL имеет хорошие показатели быстродействия, но ограничена в создании очень больших БД. Поскольку потенциально объём словарей лингвистической БД может быть очень большим, была выбрана СУБД MS SQL Server. Список литературы Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze An Introduction to Information Retrieval Draft Chisholm E., Kolda T. G. New term weighting formulas for the vector space method in information retrieval. Technical Report Number ORNL-TM-13756, Oak Ridge National Laboratory, Oak Ridge, TN, March 1999 Lan M. (2007) A New Term Weighting Method for Text Categorization. PhD Theses F. Sebastiani. Machine Learning in Automated Text Categorization Дюк В., Самойленко А. Data Mining Lancaster, F. W. (2003). Indexing and abstracting in theory and practice. Library Association, London  Jiawei Han and Micheline Kamber. Data Mining: Concepts and Techniques Ian H. Witten, Eibe Frank. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations Large Scale Hierarchical Text classification (LSHTC) Pascal Challenge http://lshtc.iit.demokritos.gr/ Xiao-Lin Wang, Bao-Liang Lu. Improved Hierarchical SVMs for Large-scale Hierarchical Text Classification Challenge Masand B., Linoff G., Waltz D. Classifying news stories using memory-based reasoning. Proceedings of SIGIR-92, 15th ACM International Conference on Research and Development in Information Retrieval, Copenhagen, Denmark, 1992, pp. 59–65 Salton G., Buckley C. (1988), Term-weighting approaches in automatic text retrieval, Information Processing & Management, Vol. 24, no. 5, pp. 513–523 Дунаев Е. В. Автоматическая рубрикация web-страниц в интернет-каталоге с иерархической структурой / Е. В. Дунаев, А. А. Шелестов // Интернет-математика 2005. Автоматическая обработка веб-данных. - М., 2005. - С. 382-398 Dumais S., Platt J,, Heckerman D., Sahami M. Inductive learning algorithms and representations for text categorization. // In Proc. Int. Conf. on Inform. and Knowledge Manage., 1998

Похожие:

	Программа по формированию навыков безопасного поведения на дорогах... Тема: Понятие алгоритмов, свойства алгоритма. Исполнители алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...		Отчет о научно-исследовательской работе, выполняемой по государственному... «Разработка алгоритмов для биоинформационного анализа комплексных метаболических и молекулярно-генетических сетей»
	Конспект урока на тему "Алгоритм. Свойства алгоритмов. Виды алгоритмов... ...		Тема урока: Виды алгоритмов и их реализация Воспитывать умение анализировать взаимосвязь между различными объектами программы
	Методическая разработка для преподавателей к интегрированному семинарско-практическому... Тема: «Реализация лекарственных препаратов противовирусного и противогрибкового действия»		Список опубликованных учебных изданий и научных трудов Шухман Елены Владимировны ...
	Online-школа «Ана теле» открыла двери первым 10 тысячам пользователей... ...		Пояснительная записка к курсовому проекту по дисциплине «Разработка сапр» Целью работы является разработка и реализация библиотеки элементов «Отвертка» на базе системы компас 3D, с использованием методов...
	Реферат: Шайдуров А. Г. Исследование и разработка некоторых графических... Шайдуров А. Г. Исследование и разработка некоторых графических алгоритмов. Квалификационная работа на степень магистра наук по направлению...		Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типа
	Программа по формированию навыков безопасного поведения на дорогах... Иметь представление об алгоритмах, свойствах алгоритмов и записи алгоритмов. Приводить примеры алгоритмов из жизни. Применять готовые...		Отчет о выполнении ниокр по теме: "Разработка опытного образца тягового... Этап №1 "Разработка и отладка алгоритмов блока управления опытного образца универсального тягового преобразователя."
	Урок по информатике по теме «Методика обучения сортировке одномерного массива» Образовательная: формирование у учащихся навыков составления алгоритмов сортировки массива методом прямого выбора и методом пузырька;...		Разработка и исследование алгоритмов распознавания изображений на...
	Пояснительная записка к курсовому проекту по дисциплине: «Разработка сапр» Целью данной работы является разработка и реализация модуля к сапр «Зубчатая передача с пересекающимися осями колес» на базе системы...		План-конспект урока алгоритм. Свойства алгоритмов. Виды алгоритмов. Формы записи алгоритмов Преподавание алгебры в 7 классе ведётся по умк «Алгебра 7 класс» под редакцией А. Г. Мордковича. Учебное пособие для изучения курса...