Семантический поиск документов, классифицированных в международной системе классификации патентов



Патентная система является основой учета современных продвижений в различных областях науки. Однако из-за серьезного прорыва в науке и технологии последних десятилетий патентные базы растут с огромной скорость, что делает поиск необходимых патентов весьма трудоемкой задачей.

Для решения этой проблемы, а также для защиты прав интеллектуальной собственности, многие страны разработали свои системы учета изобретений. Например, в 1971 году была создана МПК — международная иерархическая система патентной классификации (International Patent Classification). В ней существует пять уровней иерархии:

1. Раздел — обозначается заглавной буквой латинского алфавита от A до H.
2. Класс — обозначается двузначным числом.
3. Подкласс — заглавная буква всего латинского алфавита.
4. Группа — одно- или двузначное число.
5. Подгруппа — одно-, двух- или трехзначное число.

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

Однако у этой системы тоже есть несколько недостатков. Во-первых, некоторые подгруппы могут подчиняться другим подгруппам, при этом логика нумерации таких подгрупп четко не описана. Это может привести к неоднозначной трактовке индекса. Во-вторых, доступ к электронной базе данных представляет из себя специализированную поисковую машину, которая требует определенных знаний и навыков работы с ней со стороны пользователя. В-третьих, «язык» патентных документов для понимания также требует некоторой подготовки.

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

Формально это можно выразить следующим образом:

Пусть задано некоторое множество текстовых документов:

Имеется обучающее множество документов:

Имеется тестовое множество документов:

При этом

Пусть задано дерево:

где — множество его ребер, а — множество его вершин. Каждая вершина соответствует определенному классу. Каждому листу дерева принадлежит некоторое подмножество текстовых документов из

Необходимо построить алгоритм, который сопоставит каждому документу ровно один лист, принадлежащий дереву [2].

При этом решаются сопутствующие задачи выделения ключевых слов и определения похожих документов:

− Для входного документа необходимо на основе обучающего множества выделить список слов которые в наибольшей степени характеризуют данный входной документ. [4]

Перед тем, как приступить к классификации, каждый документ был обработан с использованием следующих методов:

− Токенизация

− Удаление стоп-слов

− Стемминг (стеммер Поттера) [3]

Для представления предварительно обработанных документов используется векторная модель. Каждый документ в коллекции необходимо рассматривать как точку пространства , где — количество слов в словаре [5]. Координатами этой точки для документа является вес каждого термина.

Для каждого документа и каждого термина в документе можно определить следующие величины:

− (termfrequency) – количество вхождений термина в документ .

− (inversedocumentfrequency) – обратная документная частота термина . – количество документов в коллекции.

Чтобы получить вес термина в каждом документе, необходимо скомбинировать данные величины [6]:

Для оценки качества классификации использовались следующие числовые характеристики [8]:

Доля правильно предсказанных документов (accuracy):

где P — количество правильно классифицированных документов, а — общее количество документов.

Пусть:

− (truepositive) – количество документов, верно приписанных к классу .

− (falsepositive) – количество документов, неверно приписанных к классу .

− (truenegative) – количество документов, верно приписанных не к классу .

− (falsenegative) – количество документов, неверно приписанных не к классу .

Точность (precision):

Полнота (recall):

F1-мера (F1-score) — представляет собой гармоническое среднее предыдущих двух величин:

Для классификации текстовых документов была взята библиотека scikit-learn, написанная на Python [7].

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

1. NaïveBayes (наивный байесовский классификатор).
2. K-nearest neighbours (k-ближайшихсоседей).
3. Метод опорных векторов (SVM).
4. SGDClassifier (метод стохастического градиента) [1]

Для сравнения выбранных алгоритмов был выбран конкретный раздел «G06F», в котором были взяты только четыре основные темы, а также несколько подтем, починяющихся главным четырем, которые могут быть интересны ученым и инженерам, работающим в сфере разработки устройств или алгоритмов для ввода/вывода и различной обработки данных, а именно: G06F3, G06F7, G06F15, G06F17, G06F300, G06F301, G06F306, G06F700, G06F702, G06F706, G06F738, G06F1500, G06F1516, G06F15177, G06F1700, G06F1710, G06F1730, G06F1740.

Для сравнения используемых в данной работе алгоритмов классификации была сформирована произвольная (случайным образом) коллекция в размере 20000 документов. Каждый текстовый документ содержит название патента и резюме. Затем, произвольным образом 19000 документов были помещены в обучающее множество, оставшаяся тысяча документов была отнесена к тестовому множеству. Необходимо отметить, что на данном этапе и следующем этапе рассматривалась классификация первого уровня по главным четырем темам.

Оценки качества работы всех используемых алгоритмов представлены в Таблице 1.

Таблица 1

Сравнение алгоритмов классификации

	Accuracy	Precision	Recall	F1-score
Naive Bayes	0.6020	0.5695	0.5040	0.5348
kNN	0.5620	0.5219	0.4610	0.4896
LinearSVC (SVM)	0.5990	0.5386	0.4995	0.5183
SGDClassifier	0.6330	0.6750	0.5064	0.5787

Как видно из представленных результатов, классификация методом стохастического градиента показывает лучший результат на случайной выборке. Следовательно, разумно использовать данный алгоритм для более точной настройки, в частности, подбора оптимальных параметров (Таблица 2).

Таблица 2

Оптимальные параметры для SGDClassifier

Количество обучений	72
Максимальная документная частота	1.0
Количество итераций	10
Значение параметра	0.0001

Сравнение результатов полученных классификаторов показано в таблице 3.

Таблица 3

Сравнение оценок качества классификации

	Accuracy	Precision	Recall	F1-score
Standart	0.6330	0.6750	0.5064	0.5787
Optimal	0.6340	0.7254	0.5073	0.5970

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

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

Оптимальные значения параметров классификации для каждого классификатора также были найдены при помощи GridSearchCV (Таблица 4).

Таблица 4

Оценки качества для классификаторов

	Accuracy	Precision	Recall	F1-score
G06F3-standart	0.6882	0.7409	0.6971	0.7183
G06F3-optimal	0.7118	0.7783	0.6914	0.7322
G06F7-standart	0.7872	0.6755	0.6667	0.6710
G06F7-optimal	0.7979	0.6272	0.5958	0.6111
G06F15-standart	0.8286	0.7365	0.6699	0.7016
G06F15-optimal	0.8254	0.7410	0.6432	0.6886
G06F17-standart	0.7031	0.6967	0.6066	0.6485
G06F17-optimal	0.7007	0.7567	0.5724	0.6518

К сожалению, результат настройки параметров с помощью GridSearchCV дает не всегда лучшие показатели. Поэтому для классификаторов G06F7 и G06F15 будет применена стандартная параметризация.

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

Литература:

1. К. В. Воронцов. Математические методы обучения по прецедентам (теория обучения машин) // Курс лекций по машинному обучению. — 2011. — 141 с.
2. Киселев М. В. Оптимизация процедуры автоматического пополнения веб-каталога // Интернет-математика, 2005. Автоматическая обработка веб-данных. — М., 2005. — С. 342–363.
3. Celine Vens, Jan Struyf, Leander Schietgat, Sašo Džeroski, Hendrik Blockeel. Decision trees for hierarchical multilabel classification // Machine Learning. — 2008. — Vol. 73, №. 2. — P. 185–214.
4. Susan Dumais, Hao Chen. Hierarchical Classification of Web Content, 2000.
5. C. D. Manning, P. Raghavan and H. Schütze. Introduction to Information Retrieval. — 2009. — Cambridge University Press. — P. 569.
6. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Data Mining, Inference, and Prediction // Springer Series in Statistics. — 2009. P. 758.
7. http://scikit-learn.org/stable/modules/sgd.html
8. F. Pedregosa, G. Varoquaux, A. Gramfort et al. Scikitlearn: Machine Learning in Python. // Journal of Machine Learning Research. — 2011. — Vol. 12. — P. 2825–2830.