Описание метода решения

Содержание

Постановка задачи. 3

Описание метода решения. 3

Программная реализация. 6

Полученные результаты и их анализ. 7

Постановка задачи

Целью данной практической работы является реализация программы, позволяющей классифицировать текстовые документы. Задача заключается в том, чтобы, предварительно обучив программу соотносить документы к одному из пяти заранее определенных классов на обучающей выборке из 100 документов для каждого класса (т.е. всего 500 документов обучающей выборки), проверить работу алгоритма на контрольной выборке из 20 документов для каждого класса (т.е. всего 100 документов контрольной выборки). Классификацию документов необходимо осуществлять на основании выделенного набора признаков.

Результатом работы программы является подсчет процента ошибок контрольной выборки, процента ошибок обучающей выборки как в целом, так и по каждому классу в отдельности при различных значениях выбранного в ходе алгоритма параметра.

Описание метода решения

Перед началом работы были подготовлены 500 документов обучающей выборки и 100 документов контрольной выборки, разбитые по следующим классам:

1. Административные правонарушения.

2. Аренда - заключение договора.

3. Государственная регистрация сделок с недвижимым имуществом - Административные и иные публичные споры.

4. Налоговое законодательство.

5. Энергоснабжение - Теплоснабжение - Неисполнение или ненадлежащее исполнение обязательств.

В качестве алгоритма, реализующего классификацию текстовых документов, был выбран метод Потенциальных функций, который принадлежит к непараметрическим методам классификации. В методе производится классификация объекта по находящимся на некотором расстоянии от него объектах с весом, зависящим от расстояния. В основе метода лежит идея о том, что плотность выше в тех точках, рядом с которыми находится большое количество объектов выборки.

В данном методе вводится понятие “Окно” – это сферическая окрестность объекта u радиуса h, при попадании в которую обучающего объекта объект u “притягивается” к классу .

Парзеновская оценка плотности имеет вид:

где h – ширина окна;

К(r) – ядерная функция, невозрастающая на интервале [0; ];

V(h) – некоторая функция от ширины окна;

– дополнительный параметр, зависящий от класса.

Ядерная функция K(r) выбирается из стандартных функций:

Каждый документ обучающей выборки был проанализирован по определенным критериям для того, чтобы при распознавании контрольной выборки можно было основываться на полученных ранее данных. Каждый документ контрольной выборки также был проанализирован по этим критериям.

Для реализации алгоритма было определено 8 признаков (критериев):

1. X₁ — число предложений в тексте;

2. X₂ — среднее число слов в предложении;

3. X₃ — среднее число букв в слове;

4. X₄ — число букв в тексте;

5. X₅ — число цифр в тексте;

6. X₆ — число слов в тексте;

Каждый документ представляет собой вектор признаков:

Представив документы подобными векторами, будем рассчитывать расстояние от проверяемого текста контрольной выборки до каждого документа текущего класса как сумму абсолютных значений разностей критериев. Каждый раз, когда расстояние между проверяемым текстом контрольной выборки и текущим текстом класса меньше, чем установленное «окно», будем считать, что данный документ «притягивается» к текущему классу. Таким образом, документ из контрольной выборки будет в большей или меньшей степени «притягиваться» ко всем существующим классам. Среди полученных данных находим тот класс, к которому текущий документ контрольной выборки имеет наибольшее число «притяжений» и отнесем данных документ к этому классу.