Способ классификации документов по категориям
Владельцы патента RU 2491622:
Общество с ограниченной ответственностью "Центр Инноваций Натальи Касперской" (RU)
Изобретение относится к способу классификации документов по категориям. Техническим результатом является повышение скорости классификации и сокращение потребного объема памяти. Для достижения этого результата в способе классификации документов по категориям строят онтологию в виде совокупности категорий. Выявляют для каждой категории термины, т.е. последовательности слов, характерные для текстов данной категории, и определяют вес каждого из выявленных терминов в процессе считывания электронных версий документов из обучающей коллекции документов. Формируют профиль для каждой из категорий в виде списка всех терминов во всех категориях онтологии с указанием веса каждого термина в данной категории. Составляют для каждого термина перечень возможных комбинаций из словоформ слов этого термина. Выделяют выявленные термины в каждом подлежащем классификации документе при считывании его электронной версии, учитывая только словоформы из составленного перечня. Формируют для каждого подлежащего классификации документа профили для каждой из категорий на основе выделенных терминов. Находят релевантность данного документа каждой из категорий путем сопоставления профилей этого документа профилям категорий в онтологии. Строят классификационный спектр документа в виде совокупности категорий с релевантностью, найденной для каждой из них. 6 з.п. ф-лы.
Настоящее изобретение относится к способу классификации документов по категориям и может быть использовано при разработке новых и совершенствовании существующих систем проверки текстовых документов.
Уровень техники
В процессе автоматического анализа текстовых документов, например, в случае отслеживания документов, проходящих по сети компании, на предмет наличия в них конфиденциальной информации, требуется классифицировать проверяемый документ в ту или иную категорию.
Ныне известны различные способы классификации текстовых документов.
Так, в патенте РФ №2167450 (опубл. 20.05.2001) охарактеризован способ идентификации объектов по их описаниям, в котором осуществляют лингвистическую сортировку всех слов текста по заданным кластерам. Использование именно всех слов текста для классификации резко удлиняет процесс классификации и требует большого объема памяти для запоминания всех (или большей части) слов используемого языка.
В заявке на патент США №2008/0098010 (опубл. 24.04.2008) раскрыты система и способ для классификации, публикации, поиска и определения местоположения электронных документов. Согласно этой заявке, электронные документы классифицируют по онтологическому описанию, состоящему из векторов, каждый из которых содержит пару значений признаков. Каждый интервал вектора соответствует признаку, а векторный диапазон каждого интервала соответствует набору всех возможных значений каждого признака. Для построения классификации применяются две хэш-функции, первая из которых отображает каждый признак в номер интервала, соответствующий координате вектора, а вторая отображает значение каждой пары в численное значение интервала, соответствующее диапазону каждой координаты. Результат двух хэш-функции можно отобразить в узел гиперкуба. Данный способ также требует достаточно долгого времени для своей реализации.
Наиболее близкий аналог настоящего изобретения представлен в заявке на патент США №2010/0205525 (опубл. 12.08.2010), раскрывающей способ для автоматической классификации текста с помощью компьютерной системы. В этом способе подлежащий классификации текст преобразуют в последовательность алфавитно-цифровых символов, которую, в свою очередь превращают в так называемый шингл, т.е. байтовую строку, в которой некоторые специальные символы заменены на буквы. Находят частоту появления шингла в подлежащем классификации тексте, сравнивают ее с частотой такого же шингла в эталонных документах и в зависимости от результата этого сравнения классифицируют соответствующий документ.
Однако и в этом способе требуется достаточно длительное время для анализа, поскольку в шинглы преобразуют чаще всего полные слова, которые при этом снабжаются различными дополнительными указателями: тип части речи (существительное, прилагательное и т.п.), тип фразы (глагольная, деепричастная и т.п.), уровень синонимии (слова одного уровня - «моросит» и «льет как из ведра», слова соседних уровней - «ЦСКА» и «футбольная команда», и т.п.). Следовательно, в этом способе нужно анализировать шинглы, составленные из большинства слов используемого языка, что, кстати, требует значительного объема памяти для хранения таких шинглов.
Раскрытие изобретения
Настоящее изобретение сделано для преодоления указанных недостатков уровня техники и обеспечивает технический результат в виде повышения скорости классификации и сокращения потребного объема памяти.
Для достижения указанного технического результата предложен способ классификации документов по категориям, заключающийся в том, что: строят онтологию в виде совокупности категорий; выявляют для каждой из категорий термины, каждый из которых представляет собой последовательность слов, характерную для текстов данной категории; определяют вес каждого из выявленных терминов в каждой из категорий в процессе считывания электронных версий документов из обучающей коллекции документов; формируют для каждой из категорий ее профиль в виде списка всех терминов во всех категориях онтологии с указанием веса каждого термина в данной категории; составляют для каждого термина перечень возможных комбинаций из словоформ тех слов, которые входят в этот термин; выделяют выявленные термины в каждом подлежащем классификации документе при считывании его электронной версии, учитывая только словоформы из перечня, составленного для данного термина; формируют для каждого подлежащего классификации документа его профили для каждой из категорий на основе выделенных при считывании терминов; находят релевантность данного документа каждой из категорий путем сопоставления профилей этого документа профилям категорий в онтологии; строят классификационный спектр документа в виде совокупности категорий с релевантностью, найденной для каждой из них.
Особенность данного способа заключается в том, что каждой словоформе термина могут присваивать уникальный идентификатор и использовать уникальные идентификаторы при формировании профилей.
Еще одна особенность данного способа состоит в том, что для каждого из сформированных профилей могут строить его вектор в многомерном пространстве, каждое измерение которого соответствует одному термину, а при сопоставлении профилей вычислять косинусную меру между сопоставляемыми векторами в этом многомерном пространстве. В этом случае при построении классификационного спектра любого документа используют лишь те из категорий, для которых косинусная мера между сопоставляемыми векторами превышает заранее заданную пороговую величину.
Еще одна особенность данного способа состоит в том, что вес каждого термина могут определять как TF·IDF где TF - частота встречаемости термина во всех документах данной категории в обучающей коллекции документов, a IDF - обратная документная частота, характеризующая, в скольких документах данной категории из общего количества документов встречается данный термин.
Еще одна особенность данного способа состоит в том, что онтологию строят в виде иерархически связанной последовательности категорий.
Наконец, еще одна особенность данного способа состоит в том, что используют синтаксический анализ для разрешения лексической омонимии в текстах терминов на основе перечней, составленных для каждого термина.
Подробное описание вариантов осуществления
Настоящее изобретение может быть реализовано в любой вычислительной системе, например, в персональном компьютере, на сервере и т.п.Для осуществления изобретения необходимо также наличие соответствующей базы данных, в которой хранятся электронные файлы текстовых документов.
Способ по настоящему изобретению предназначен для классификации по различным категориям тех документов, которые могут далее подвергаться, например, так называемому копирайтному анализу (английский аналог - fingerprint detection), задачей которого является установление схожести бинарных и (или) текстовых документов документам, переданным ранее в базу данных (библиотеку) в качестве эталонных, или какой-либо иной текстовой обработке.
Классификация позволяет соотнести приходящие электронные версии текстовых документов одной или нескольким категориям. Категории могут быть выбраны по желанию проектировщика или в соответствии с требованиями, предъявляемыми к системе, в которой используется способ по настоящему изобретению. Примеры категорий можно найти в упомянутых выше заявках на патент США №№2008/0098010 и 2010/0205525, а также в заявке на патент США №2009/0327189 (опубл. 31.12.2009) и в международной заявке № WO 2010/134752. Категории могут выбираться независимо, однако предпочтительно, чтобы категории выстраивались в виде иерархически связанной последовательности, как это имеет место, например, в упомянутых международной заявке № WO 2010/134752 и заявке на патент США №2009/0327189.
Совокупность выбранных категорий, по которым будут классифицироваться поступающие электронные версии документов, составляет онтологию классификации. Как уже указано, онтологию строят предпочтительно в виде иерархически связанной последовательности выбранных категорий. Это позволяет в некоторых случаях в отсутствие соответствующей категории на некотором уровне онтологии переходить на более высокий уровень по иерархическому дереву.
Для каждой из выбранных категорий онтологии выявляют термины, каждый из которых представляет собой последовательность слов, характерную для текстов данной категории. Последовательность слов в каком-либо термине может содержать одно или несколько слов. При этом учитывают словоформы каждого слова, входящего к термин. Это особенно важно для таких высоко флективных языков как русский и другие славянские языки, однако вполне применимо и для менее флективных языков, как, к примеру, английский. Учет словоформ осуществляют следующим образом.
Для каждого термина составляется перечень возможных комбинаций словоформ всех слов, входящих в этот термин. Предпочтительно, каждой словоформе присваивают уникальный номер, а все последовательности словоформ (или их номеров), принадлежащих данному термину, помечают идентификатором этого термина. При этом последующее выделение выявленных терминов в ходе обработки поступающей электронной версии текстового документа осуществляют именно по словоформам, находя их в обрабатываемом тексте и определяя, в какой термин входит та или иная словоформа. А классификацию текста производят уже по комбинациям словоформ, входящих в тот или иной термин.
На этапе «обучения» - как, впрочем, и на последующем этапе классификации поступающих текстов - считывают электронные версии документов: на этапе обучения и построения онтологии это будут документы из обучающей коллекции документов (так сказать, эталонные документы). В процессе этого считывания и нахождения выявленных терминов определяют вес каждого из выявленных терминов в каждой из упомянутых категорий. Определение веса можно производить любым методом, к примеру, так же, как это делается в упомянутой заявке США №2008/0098010. В настоящем изобретении предпочтительно используется метод, при котором вес каждого термина определяют как TF·IDF, где TF - частота встречаемости термина во всех документах данной категории в обучающей коллекции документов (т.е. число вхождений данного термина во все документы данной категории), а IDF - обратная документная частота, характеризующая, в скольких документах данной категории из общего количества документов встречается данный термин (см. http://ru.wikipedia.org/wiki/TF-IDF).
После определения веса каждого термина формируют для каждой из выбранных категорий ее профиль в виде списка всех терминов во всех категориях построенной онтологии с указанием веса каждого термина в данной категории. Для документов из обучающей коллекции эти профили считаются эталонными, а для проверяемых документов - рабочими. При формировании профилей, если, как в предпочтительном варианте осуществления, каждой словоформе термина был присвоен уникальный идентификатор, эти уникальные идентификаторы используют для формирования профилей.
После формирования профиля конкретного классифицируемого документа для каждой из категорий онтологии, осуществляемого на основе терминов, выделенных при считывании данного текстового документа, находят релевантность данного документа каждой из категорий онтологии путем сопоставления профилей этого документа профилям категорий в онтологии. Указанное сопоставление можно осуществлять по-разному. Это можно делать, например, так же, как в упомянутой выше заявке на патент США №2008/0098010. Однако в настоящем изобретении предпочтительно используется сравнение профилей посредством вычисления коэффициента Пирсона, т.е. косинуса угла векторов профилей в многомерном векторном пространстве, где для каждого термина введено свое измерение (см. http://rcdl.ru/doc/2010/430-435.pdf). В этом случае косинусная мера сравнения может варьироваться в пределах от -1 до +1.
По найденным значениям релевантности строят классификационный спектр конкретного документа в виде совокупности категорий с релевантностью, найденной для каждой из них. В этот классификационный спектр попадают категории, для которых значение релевантности превышает некоторую пороговую величину, например, 0,1.
При считывании электронной версии подлежащего классификации документа, как уже было отмечено, учитывают только словоформы из перечня, составленного для данного термина. Это позволяет резко сократить время обработки, т.к., во-первых, при этом используются только те слова, которые есть в построенной онтологии, что ускоряет поиск выявленных терминов (т.е. на первом, нижнем уровне обработки), а во-вторых, выделяются только те словоформы, которые есть в выявленных терминах, что ускоряет классификацию текста (на втором, верхнем уровне обработки). Помимо этого, не требуется большой объем памяти, т.к. хранить нужно только имеющиеся словоформы, а не все слова того языка, на котором написан текст классифицируемого документа.
Есть и еще одно преимущества использования только имеющихся в терминах словоформ. В случае омонимии двух слов для разрешения такой лексической омонимии в текстах терминов на основе перечней, составленных для каждого термина, можно использовать синтаксический, а не семантический анализ, что значительно упрощает данную процедуру.
Таким образом, способ классификации документов по категориям в соответствии с настоящим изобретением обеспечивает технический результат в виде повышения скорости классификации и сокращения потребного объема памяти.
1. Способ классификации документов по категориям, заключающийся в том, что:
- строят онтологию в виде совокупности упомянутых категорий;
- выявляют для каждой из упомянутых категорий термины, каждый из которых представляет собой последовательность слов, характерную для текстов данной категории;
- определяют вес каждого из выявленных терминов в каждой из упомянутых категорий в процессе считывания электронных версий документов из обучающей коллекции документов;
- формируют для каждой из упомянутых категорий ее профиль в виде списка всех терминов во всех категориях упомянутой онтологии с указанием веса каждого термина в данной категории;
- составляют для каждого термина перечень возможных комбинаций из словоформ тех слов, которые входят в этот термин;
- выделяют упомянутые выявленные термины в каждом подлежащем классификации документе при считывании его электронной версии, учитывая только словоформы из упомянутого перечня, составленного для данного термина;
- формируют для каждого подлежащего классификации документа его профили для каждой из упомянутых категорий на основе выделенных при считывании терминов;
- находят релевантность данного документа каждой из упомянутых категорий путем сопоставления профилей этого документа профилям категорий в упомянутой онтологии;
- строят классификационный спектр упомянутого документа в виде совокупности упомянутых категорий с релевантностью, найденной для каждой из них.
2. Способ по п.1, в котором:
- присваивают каждой словоформе термина уникальный идентификатор;
- используют упомянутые уникальные идентификаторы при упомянутом формировании профилей.
3. Способ по п.1 или 2, в котором:
- строят для каждого из сформированных профилей его вектор в многомерном пространстве, каждое измерение которого соответствует одному термину;
- при упомянутом сопоставлении профилей вычисляют косинусную меру между сопоставляемыми векторами в упомянутом многомерном пространстве.
4. Способ по п.3, в котором при упомянутом построении классификационного спектра любого документа используют лишь те из упомянутых категорий, для которых упомянутая косинусная мера между сопоставляемыми векторами превышает заранее заданную пороговую величину.
5. Способ по п.1, в котором упомянутый вес каждого термина определяют как TF·IDF, где TF - частота встречаемости термина во всех документах данной категории в обучающей коллекции документов, a IDF - обратная документная частота, характеризующая, в скольких документах данной категории из общего количества документов встречается данный термин.
6. Способ по п.1, в котором упомянутую онтологию строят в виде иерархически связанной последовательности упомянутых категорий.
7. Способ по п.1 или 2, в котором используют синтаксический анализ для разрешения лексической омонимии в текстах упомянутых терминов на основе упомянутых перечней, составленных для каждого термина.
