ооо!

БЛОГ разработчика

Анализ традиционных подходов к решению задачи автоматической классификации текста


Системы автоматической классификации имеют различные способы представления опи­саний классов (внутренней структуры элементов класса), и процедуры классификации. Из них можно выделить три ключевых направления:

1.       Статистические классификаторы на основе вероятностных методов.

2.       Классификаторы, построенные на основе искусственных нейронных сетей.

3.       Классификаторы, основанные на функциях подобия.



В первой группе одним из наиболее применяемых является метод Байеса и его многочисленные модификации [5,6], в основе которых лежит формула Байеса для условной вероятности (1.9) [1]. Применительно к классификации текстов анализируемый документ представляется в виде последовательности терминов, и рассчитывается вероятность того, что будет выбрана рубрика ci, при условии, что документ пройдет успешную классификацию

(1.9)

(1.10)

где:  

·          tанализируемый текст,

·          wтермин,

·          ci  – i-я рубрика классификатора,

·          P(ci)безусловной вероятно­стью выбора рубрики ci в процессе классификации некоторого документа,

·          P(w|ci)условной вероятностью встретить термин w в документе t,

·          Fi  – i-й элемент множества F описаний рубрик,

·          P(t|ci)вероятность того, что текст будет классифицирован при условии выбора рубрики ci.


Каждая рубрика ci характеризуется безусловной вероятно­стью ее выбора P(ci) в процессе классификации некоторого документа, а так же условной вероятностью встретить термин w в документе t при условии выбора рубрики ci. Процедура классификации сводится к подсчету вероятности P(ci|t) для всех рубрик ci и выбора той, для которой эта величина максимальна. Обучение рубрикатора сводится к составлению словаря терминов {wn} и определению для каждой рубрики величин P(ci) и P(w|ci), где w {wn}.

 

Дерево решений. Для решения задач распознавания и классификации также часто используется дерево решений[7].  В этом случае дерево решений может рассматриваться как некоторая иерархия категорий, к которым могут относиться классифицируемые объекты. Задача метода – определить наиболее узкую категорию (лист), к которой с заданной вероятностью относится анализируемый объект. Алгоритм дерева решений может применяться как на всех этапах анализа текста, используя в каждом случае различные типы предыстории, наборы вопросов и множества исходов [6], так и для морфологического и синтаксического анализа [8].

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

 

Метод ближайшего соседа, в отличие от других, не требует фазы обучения. Для того чтобы найти рубрики, релевантные документу d, этот документ сравнивается со всеми документами из обучающей выборки. Для каждого документа e из обучающей выборки, находится расстояние - косинус угла между векторами признаков:


(1.11)

 

Далее из обучающей выборки выбираются k документов, ближайших к d (k - параметр). Для каждой рубрики вычисляется релевантность по формуле


(1.12)

 

Рубрики с релевантностью выше некоторого заданного порога считаются соответствующими документу. Параметр k обычно выбирается в интервале от 1 до 100.

Пусть пространство признаков X - метрическое, пространство ответов Y - любое, и в качестве ответа f(x) распознавателя для объекта x берется ответ yi его ближайшего в смысле метрики на X "соседа" xi из обучающего набора T.

В случае наличия нескольких равноудаленных ближайших соседей определить ответ можно следующими способами:

·          если вероятность наличия равноудаленных соседей равна 0, например, когда пространство X - евклидово, а распределение p непрерывно, то как угодно,

·          если пространство ответов Y - линейное, например, R (одномерная регрессия), то ответы ближайших соседей можно усреднить,

·          если пространство ответов Y - конечное с небольшим числом элементов, например, {0,1} (двухклассовая классификация), то из ответов ближайших соседей можно выбрать самый частый.



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

         Обучение распознавателя при методе ближайшего соседа или k соседей [10] сводится к запоминанию обучающего набора. Распознавание, как было показано выше, просто, но очень трудоемко, и трудоемкость растет с ростом объема обучающего набора и размерности пространства признаков. Существует большое количество методов ускорения поиска ближайших соседей. Данный метод показывает довольно высокую эффективность [11], но требует больших вычислительных затрат на этапе рубрикации. При росте обучающего набора - распознавание методом ближайшего соседа работает хорошо (с малым ожиданием ошибки), но требуется слишком большое количество памяти и времени работы. А при малом обучающем наборе, не заполняющем достаточно плотно пространство признаков, метод ближайшего соседа работает плохо.

 

<<   >>


Материалы взяты из защищенной в ВАК диссертации по автоклассификации. Если вы считаете, что ваши права нарушаются -свяжитесь с нами