Создание пословарной модели документа для решения задач поиска документа по образцу

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Создание пословарной модели документа для решения задач поиска документа по образцу

Хусаинова М.А.

Основная проблема в решении задач тематической классификации и поиска документа по образцу сводится к проблеме определения тематики документа как таковой. Интуитивно понятно, что определение тематики должно исходить из анализа смысловой наполненности текста, каковую призвана отражать модель документа. Соответственно принципиальным является вопрос: какая модель документа способна помочь пользователю и системе в определении тематики документа, поскольку само понятие тематики является достаточно субъективным. Несмотря на актуальность и востребованность решений данных задач поиска, сколь-либо качественных универсальных методик соотнесения документов пока что нет, поэтому данный вопрос по-прежнему остается открытым в исследовательских задачах.[1]

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

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

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

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

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

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

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

Фактически, необходимо определить, какие из точек (леммат) исходного пространства (пространства разобранных текстовых документов), можно сгруппировать в классы, для составления словарей, основываясь только на частоте их появления в различных тематиках. Действительно, каждая леммата может быть представлена точкой пространства в координатах существующих тематик. Основной проблемой в решении задачи является неопределенность относительно вида изначального пространства, а также, относительно вида, размерности классов и их удаленности друг от друга. Поэтому, обычно применимые для подобных задач метод k-средних, метод динамических ядер, самоорганизующиеся карты (SOM), их вариант - карты Кохонена, метод GNG не могут быть задействованы в полной мере.

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

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

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

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

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

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

Для определения наиболее связных вершин графа и их взаимоотношений с другими вершинами строим остовное дерево графа и на его основании - фундаментальную систему разрезов.[3] Тогда можно оценивать отдельно каждый разрез и те части графа, которые получаются в результате проведения данного разреза.

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

1) удалять более длинные ребра, т.к. более короткие ребра сигнализируют о более высокой плотности связи между 2-мя конкретными точками;

2) если для разделения потребовалось удалять меньше связующих ребер, чем для первичного разбиения;

3) если в результате сообразного удаления ребер образуется более равномерное разбиение (например, если удаление 2-х ребер из 15 приводит к разбиению кластера на два существенно неравные, а удаление 3-х на равные по объему сегменты, то разбиение с тремя кластерами будет более предпочтительным);

4) разделение кластера, приводящее к выделению одной лишь точки в отдельный класс, менее предпочтительно, чем сохранение целостности всего графа;

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

a) для разбиений более предпочтительны сектора большей размерности,

b) для разбиений предпочтительны сектора меньшей плотности, т.е. для разбиений предпочтительны сектора более легко разбиваемые.

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

Совокупность действия критериев накладывает систему ограничений на граф. Обобщим принципы применения описанных выше критериев и опишем алгоритм принятия решения по сегментации исходного графа.

1. Рассекаем общее пространство на фрагменты для возможности дальнейшей работы алгоритма. Выделяем массивы точек для дальнейшей работы.

2. На основании имеющегося множества вершин строим полный граф, т.е. добавляем все возможные ребра графа.

3. Упорядочиваем ребра по длине и проводим отсечение наиболее длинных ребер, до начала разбиения графа. Т.е. как только граф распадается на 2 компонента связности, отсечение ребер, исходя только из критерия их длины, заканчивается.

4. Строим остовное дерево графа.[3]

5. Строим фундаментальную систему разрезов, упорядочиваем информацию о мощности разрезов и полученных в результате проведения этих разрезов кластеров. [3]

6. Запускаем в действие последовательно все описанные критерии и выбираем тот разрез кластера, который наиболее хорошо удовлетворяет описанные потребности.

7. Продолжаем разбиение кластеров до тех пор, пока не получим удовлетворительное для нас разбиение, т.е. предпочтительную систему кластеров.

Точка остановки действия алгоритма может быть определена несколькими способами:

1) изначально заданное пользователем - настройщиком системы желаемое количество словарей;

2) достижение равномерной плотности словарей; конечно, показатель плотности не может быть одинаков для всех кластеров, однако, можно определить некоторые его пределы.

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

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

1. «Упрощенный»: оценить «похожесть» структур документов в понятиях существующих словарей, например, соотношение долей наиболее популярных словарей, используемых в документах. В основе объективных количественных показателей схожести лежат принципы сравнения сонаправленности векторов: правила коллинеарности и принцип скалярного произведения векторов. Использование этих двух подходов указывает на степень тематической сонаправленности документов.

2. «Кластерный»: провести процедуру распределения документа в классы таким же образом, как и процедуру распределения слов в словари. В этом случае мы получим на любом требуемом уровне разделение и группировку документов. При оценке принадлежности нового документа вычисляются расстояния (единицей измерения выступают словари) между документом и кластерами, и документ отправляется в ближайший кластер.

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

Литература

алгоритм вектор документ

1. Когаловский М.Р. Перспективные технологии информационных систем. - М.: ДМК Пресс; М.: Компания АйТи, 2003. - 288 с.

2. Некрестьянов И.C. Тематико-ориентированные методы информационного поиска: Диссертационная работа к.т.н.: 05.13.11 / Санкт-Петербургский государственный университет - СПб., 2000. - 80 c.

3. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432с.

Размещено на Allbest.ru