› › Технологии анализа данных (Text Mining, Data Mining). Text Mining: современные технологии на информационных рудниках

Технологии анализа данных (Text Mining, Data Mining). Text Mining: современные технологии на информационных рудниках



ЛЕКЦИЯ 6. Основы технологии Text Mining

Глава 5

Основы технологии Text Mining

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

Исследовательская служба Cyveillance сообщила, что еще в 2001 году общее количество страниц в Internet превысило 4 млрд. Средний размер Web-страницы - 10 Кбайт, среднестатистическая страница содержит 20-25 внутренних ссылок, 5-6 внешних и 14-15 изображений. Если к этому добавить массивы неструктурированных документов в корпоративных файловых системах и базах данных, то легко видеть, почему многие организации заинтересованы в технологиях автоматизированного анализа и классификации информации, представленной на естественном языке. Ведь по существующим оценкам, неструктурированные данные, главным образом текст, составляют не менее 90% информации. И лишь 10% приходится на структурированные данные, загружаемые в реляционные СУБД.

"Люди будут искать то, что они знают, обращаясь к документальным репозитариям. Однако они вообще не будут или просто не смогут выражать запросом то, чего они не знают, даже имея доступ к собранию документов", - заметил Джим Нисбет, вице-президент компании Semio, которая является одним из ведущих производителей систем "добычи данных" (Data Mining). "Метод эффективного анализа текста - Text Mining, - используя вычислительные мощности, позволяет выявить отношения, которые могут приводить к получению новых знаний пользователем."

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

В конце 2000 года ЦРУ опубликовало документ "Анализ плана стратегических инвестиций разведсообщества" (Strategic Investment Plan for Intelligence Community Analysis- http://www.cia.gov/cia/reports/unclass_sip - рис. 5.1). В этом документе разведчики признают, что ранее не использовали полностью возможности открытых источников, и теперь работа с ними должна стать "высшим приоритетом для инвестиций". Иначе говоря, в ЦРУ резонно по-

Лагают, что брать информацию из открытых источников безопаснее и дешевле, чем пользоваться разведданными. Технология глубинного анализа текста - Text Mining - и представляет собой тот самый инструментарий, который позволяет анализировать большие объемы информации в поисках тенденций, шаблонов и взаимосвязей, способных помочь в принятии стратегических решений. Кроме того, Text Mining - это новый вид поиска, который, в отличие от традиционных подходов, не только находит списки документов, формально релевантных запросам, но и позволяет получить ответ на просьбу: "Помоги мне понять смысл, разобраться с этой проблематикой".

Клод Фогель (Claude Vogel), один из основателей легендарной компании Semio, используя аналогию с библиотекой поясняет: "Технология Text Mining открывает перед читателем книги с подчеркнутой необходимой ему информацией. Сравните это с выдачей читателю кипы документов и книг, в которых где-нибудь содержится нужная читателю информация, однако найти ее читателю будет непросто". Процесс осмысленного поиска является далеко не тривиальным, часто в коллекции документов имеется только намек на необходимую информацию. Необходимы мощные интеллектуальные возможности, чтобы найти то, что требуется. В названии технологии слово mining ("добыча руды") выступает как метафора отыскания глубоко "зарытой" информации.

Следует заметить, что технологии глубинного анализа текста исторически предшествовало создание технологии глубинного анализа (добычи) данных (Data Mining), методология используются и в методах Text Mining. Для "добычи текстов" вполне справедливо определение, данное для добычи данных одним из ведущих мировых экспертов Григорием Пятецким-Шапиро из GTE Labs: "Процесс обнаружения в сырых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности". Как и большинство когнитивных технологий, Text Mining - это алгоритмическое выявление прежде неизвестных связей и корреляций в уже имеющихся текстовых данных.

Оформившись в середине 90-х годов XX века как направление анализа неструктурированных текстов, технология Text Mining сразу же взяла на вооружение методы классической добычи данных, такие как классификация или кластеризация. В Text Mining появились и дополнительные возможности, такие как автоматическое реферирование текстов и выявление феноменов, т.е. понятий и фактов. Возможности современных систем Text Mining могут применяться при управлении знаниями для выявления шаблонов в тексте, для автоматического "проталкивания" информации или ее распределения по интересующим пользователей профилям, а также для создания обзоров документов. Технологии Text

160 Глава 5. Основы технологии Text Mining

Mining, кроме того, присуща абсолютная объективность - в ней отсутствует субъективизм, свойственный человеку-аналитику.

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

5.1. Основные элементы Text Mining

В соответствии с уже сложившейся методологией, к основным элементам Text Mining относятся реферирование (summarization), выявление феноменов (feature extraction), классификация (classification), кластеризация (clustering), ответ на вопросы (question answering), тематическое индексирование (thematic indexing) и поиск по ключевым словам (keyword searching). Также в некоторых случаях указанный набор дополняют средства поддержки и создания таксономии (taxonomies) и тезаурусов (thesauri).

Александр Линден (Alexander Linden), директор компании Gartner Research, выделил четыре основных вида приложений технологии Text Mining.

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

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

3. Построение семантической сети или анализ связей, которые определяют появление дескрипторов (ключевых фраз) в документе для обеспечения поиска и навигации.

4. Извлечение фактов, цель которого - получение некоторых фактов из текста с целью улучшения классификации, поиска и кластеризации.

Так сложилось, что чаще всего решаемая в Text Mining задача - это классификация, т.е. отнесение объектов базы данных к заранее определенным категориям. Фактически задача классификации - это вариант классической задачи распознавания, когда система по обучающей выборке относит новый объект к той или иной категории. Особенность же системы Text Mining состоит лишь в том, что количество таких объектов и их атрибутов может быть очень большим; поэтому должны быть предусмотрены интеллектуальные механизмы оптимизации процесса классификации. В существующих сегодня системах классификация применяется, например, для решения таких задач, как группировка документов в intranet-сетях и на Web-сайтах, размещение документов в определенные папки, сортировка сообщений электронной почты, избирательное распространение новостей подписчикам и пр.

Вторая задача - кластеризация - состоит в выделении компактных подгрупп объектов с близкими свойствами. Система должна самостоятельно найти

Глава 5. Основы технологии Text Mining 161

признаки и разделить объекты по подгруппам. Решение этой задачи, как правило, предшествует задаче классификации, поскольку позволяет определить группы объектов. Различают два основных типа кластеризации - иерархическую и бинарную (двоичную). Иерархическая кластеризация заключается в построении дерева кластеров, в каждом из которых размещается небольшая группа документов. Пример утилиты двоичной кластеризации можно найти на сервере корпорации IBM по адресу http://www.software.ibm.com/data/iminer/fortext. Двоичная кластеризация обеспечивает группировку и просмотр документальных кластеров по ссылкам подобия. В один кластер помещаются самые близкие по своим свойствам документы. В процессе-кластеризации строится базис ссылок от документа к документу, основанный на весах и совместном употреблении определяемых ключевых слов. Сегодня кластеризация широко применяется при реферировании больших документальных массивов или определении взаимосвязанных групп документов, а также для упрощения процесса просмотра при поиске необходимой информации, для нахождения уникальных документов из коллекции, для выявления дубликатов или очень близких по содержанию документов.

Можно назвать еще несколько задач, которые могут решаться средствами технологии Text Mining, - например, прогнозирование, которое состоит в том, чтобы предсказать по значениям одних признаков объекта значения остальных. Еще одна задача - нахождение исключений, т.е. поиск объектов, которые своими характеристиками сильно выделяются из общей массы. Для этого сначала выясняются средние параметры объектов, а затем исследуются те объекты, параметры которых наиболее сильно отличаются от средних значений. Как правило, поиск исключений проводится после классификации или кластеризации, для того чтобы выяснить, насколько последние были точны.

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

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

5.2. Контент-анализ

Сегодня весьма актуальной является задача мониторинга ресурсов Internet, которая тесно связана с достаточно популярным в последние десятилетия контент-анализом. Это перспективное направление развития систем сетевой интеграции рассматривается сегодня многими экспертами как контент-мониторинг,

162 Глава 5. Основы технологии Text Mining

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

Контент-анализ начинался как количественно-ориентированный метод анализа текстов для изучения массовых коммуникаций. Впервые этот метод был применен в 1910 году социологом Максом Вебером (Max Weber), чтобы проанализировать охват прессой политических акций в Германии (рис. 5.2). Американский исследователь средств коммуникации Гарольд Лассвелл (Harold Lasswell) в 30-40-е годы использовал подобную методику для изучения содержимого пропагандистских сообщений военного времени. В 1943 году Абрахам Каплан (Abraham Kaplan) увеличил фокус контент-анализа от статистической семантики (значения текстов) политических дискуссий до анализа значений символов (семиотики). Во время Второй мировой войны растущая популярность семиотики способствовала использованию качественно-ориентированного контент-анализа для изучения "идеологических" аспектов в таких жанрах, как телевизионные шоу и коммерческая реклама. Ряд современных исследований с применением методологии контент-анализа включает, наряду с анализом текста, и анализ изображений.

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

Под Data Mining понимается механизм обнаружения

В потоке данных интересных новых знаний, таких как модели, конструкции, ассоциации, изменения, аномалии и структурные новообразования. Большой вклад в развитие контент-анализа внесли психологические исследования в области феноменологии, ведущая идея которой заключается в обращении к каждодневному миру через различные явления (phenomena) в фактических ситуациях. С феноменологией неразрывно связаны имена ее основателя Эдмунда Хассерла (Edmund Husserl) и нашего современника Амадео Джиорджи (Amadeo Giorgi).

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

5.2. Контент-анализ 163

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

Контент-анализ - это методика объективного качественного и систематического изучения содержания средств коммуникации (Д. Джери, Дж. Джери).

Контент-анализ - это систематическая числовая обработка, оценка и интерпретация формы и содержания информационного источника (Д. Мангейм, Р. Рич).

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

Контент-анализ состоит в нахождении в тексте определенных содержательных понятий (единиц анализа), выявлении частоты их встречаемости и соотношения с содержанием всего документа (Б. Краснов).

Контент-анализ - это исследовательская техника для получения результатов путем анализа содержания текста о состоянии и свойствах социальной действительности (Е. Таршис).

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

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

Описание проблемной ситуации, поиск цели исследования;

Уточнение объекта и предмета исследования;

Смысловое уточнение понятий;

Эмпирическая интерпретация понятий;

Описание процедур регистрации свойств и явлений;

Предварительный целостный анализ объекта;

164 Глава 5. Основы технологии Text Mining

Определение общего плана исследования;

Определение типа выборки и т.д. Методы сбора данных также многообразны:

Наблюдение;

Анкетный опрос;

Интервью;

Телефонный опрос;

Накопление совокупности писем;

Получение потока документов Сети.

Для отбора информации применяются такие методы:

Гнездовой;

Квотная выборка;

Неслучайная выборка;

Метод нетипичных представителей;

Метод "снежного кома";

Стихийная выборка;

Случайная выборка;

Одно- и многоступенчатая выборка;

Районированная (расслоение) выборка;

Систематическая выборка и т.д.

В контент-анализе применяются такие математические методы, как:

Дисперсионный анализ для выявления влияния отдельных, независимых факторов на наблюдаемый признак;

Кластерный анализ для классификации объектов и описывающих их признаков;

Логлинейный анализ для статистической проверки гипотезы о системе одновременных парных и множественных взаимосвязей в группе признаков;

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

Регрессионный анализ для исследования регрессионной зависимости между зависимыми и независимыми признаками;

Факторный анализ для получения обобщенной информации о структуре связи между наблюдаемыми признаками изучаемого объекта на основе выделения скрытых факторов;

Корреляционный анализ для выявления зависимости между числовыми случайными величинами, одна из которых зависит и от ряда других случайных факторов.

5.2. Контент-анализ 165

От поиска информации - к поиску знаний

В последнее время происходят изменения подходов к форме и семантике взаимодействия пользователей с поисковыми системами в Internet. Через десятилетие после возникновения первых поисковых серверов в Сети оказалось, что надежды на интеллект пользователя при формулировке запросов были тщетны. Это замечание относится как к обычным пользователям, так и к пользователям-профессионалам. В результате современные поисковые системы сами все более интеллектуализируются, включают семантические инструменты, пытаясь выявлять информационные потребности пользователей и учитывать их при поиске.

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

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

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

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

5.3. Модели поиска

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

5.3.1. Булева модель поиска

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

166 Глава 5. Основы технологии Text Mining

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

В рамках булевой модели документы и запросы представляются в виде множества морфемных основ ключевых слов, будем их в дальнейшем называть термами. Пусть документальный массив С состоит из множества документов d 1 ...d n , а документ d i содержит множество различных термов T(d i). Обозначим через T = U i=1…n Т(d i) словарь массива С, представляющий собой множество всех

Термов, встречающихся в документах из С, и через Т(d i) - словарь документа d i . В булевой модели запрос пользователя представляет собой логическое выражение, в котором ключевые слова (термы запроса) связаны логическими операторами AND, OR и NOT. В различных поисковых системах в Internet пользователи могут пользоваться умолчаниями, не используя в явном виде логических операций, а просто перечисляя ключевые слова. Чаще всего по умолчанию предполагается, что все ключевые слова соединяются логической операцией AND - в этих случаях в результаты поиска включаются только те документы, которые содержат одновременно все ключевые слова запроса. В тех системах, в которых пробел между словами приравнивается к оператору OR, в результаты поиска включаются документы, в которые входит хотя бы одно из ключевых слов запроса.

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

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

Существует несколько подходов к формированию архитектуры поисковых систем, соответствующих булевой модели и нашедших свое воплощение в реальных системах. Одной из наиболее удачных реализаций структуры базы данных информационно-поисковой системы на мэйнфреймах фирмы IBM была признана модель данных системы STAIRS (Storage and Information Retrieval System), которая, благодаря изначально удачным архитектурным решениям до сих пор продолжает развиваться. База данных информационно-поисковых систем этой традиционной архитектуры состоит из следующих основных таблиц :

Текстовой, содержащей текстовую часть всех документов;

Таблицы указателей текстов, включающей указатели местонахождения документов в текстовой таблице, а заодно и форматные поля всех документов;

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

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

5.3. Модели поиска 167

Процессы, происходившие при поиске информации в базе данных STAIRS, сегодня реализуются средствами современных СУБД и ИПС документального типа. Поиск термина в базе данных осуществляется следующим образом.

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

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

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

4. По номеру документа осуществляется прямое обращение к фрагменту текстовой таблицы - документу - и последующий его вывод.

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

5.3.2. Векторно-пространственная модель

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

В рамках этой модели с каждым термом t i в документе d j (и запросе q) сопоставляется некоторый неотрицательный вес w ij . Таким образом, каждый документ и запрос могут быть представлены в виде ^-мерного вектора ||w ij || i=1,…, к, где к - общее количество различных термов во всех документах. Согласно векторной модели, близость документа d i к запросу q оценивается как корреляция между векторами их описаний. Эта корреляция может быть вычислена как скалярное произведение соответствующих векторов описаний. При этом весовые коэффициенты отдельных термов можно вычислять множеством различных способов.

Один из возможных простейших (но эффективных) подходов - использовать в качестве веса терма wtj в документе dt нормализованную частоту его использования freg ij в данном документе.

W ij = tf ij = freq ij / max i 1 frequ i 1

168 Глава 5. Основы технологии Text Mining

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

W = tfidf ij - tf ij  log N /n i ,

Где n i - число документов, в которых используется терм t j , а N - общее число документов в массиве.

Обычно значения весов w ij нормируются (дополнительно делятся на квадратный корень из суммы весов всех термов, входящих в документ), что позволяет рассматривать документ как ортонормированный вектор. Такой метод взвешивания термов имеет стандартное обозначение - tfidf, где tf указывает на частоту использования термина в документе (term frequency), a idf- на величину, обратную числу документов массива, содержащих данный терм (inverse document frequency).

Когда возникает задача определения тематической близости двух документов или документа и запроса, в этой модели используется простое скалярное произведение sim(d 1 , d 2) двух векторов ||w i1 || i= 1, …k и ||w i2 || i= 1, …k , которое, очевидно, соответствует косинусу угла между векторами-образами документов d 1 и d 2 . Очевидно, sim(d 1 , d 2) принадлежит диапазону . Чем больше величина sim(d 1 , d 2) - тем более близки документы d 1 и, d 2 . Для любого документа d i , имеем sim(d i , d i) = 1. Аналогично мерой близости запроса q документу d i считается величина sim(q, d i).

Векторно-пространственная модель представления данных автоматически обеспечивает системам, построенным на ее основе, такие возможности:

Обработку сколь угодно больших запросов;

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

Сохранение результатов поиска в некотором виртуальном массиве с последующим уточняющим поиском в нем.

5.3.3. Гибридные модели поиска

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

5.4. Группировка текстовых данных

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

5.4. Группировка текстовых данных 169

и кластеризация. Здесь классификация - это отнесение каждого документа к определенному классу с заранее известными признаками, полученными на этапе обучения. Число классов строго ограничено.

Тематические каталоги, построенные с участием людей (например, Yahoo! или Open Directory), приводят к естественному вопросу: а не могут ли подобные каталоги быть построены автоматически? Один из путей решения этой проблемы - кластеризация, т.е. автоматическая группировка тематически близких документов.

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

Гипертекст достаточно богат возможностями: текстовые блоки, теги разметки, URL-адреса, имена доменов в URL, подстроки в URL, которые могут быть значащими словами, и т.д. Как в этом случае определить меру подобия таким образом, чтобы достичь хорошей кластеризации?

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

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

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

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

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

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

170 Глава 5. Основы технологии Text Mining

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

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

В области информационного поиска кластеризация применяется для решения двух задач - группировки документов и результатов поиска.

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

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

5.4.1. Кластеризация

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

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

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

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

5.4. Группировка текстовых данных 171

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

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

5.4.2. Тематическая близость

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

Обозначим тематическую близость двух термов wt и Wj как FSR(wb wj). Вычисление оценок тематической близости термов и, как следствие, задание функции FSR выполняются по результатам анализа использования термов в массиве документов, которыми описываются тематики. По исходному массиву документов строится матрица А, строки которой отражают распределение термов по документам. В качестве оценки тематической близости двух термов используется скалярное произведение соответствующих строк этой матрицы. Таким образом, для вычисления оценок близости между всеми парами термов достаточно вычислить матрицу ААТ.

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

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

Случайные неточности и зависимости оказывают существенное влияние на получаемые оценки и негативно влияют на точность метода;

Размер матрицы А очень велик - использование этой матрицы весьма ресурсоемко.

Дальнейшим развитием такого подхода является использование так называемого латентно-семантического анализа (LSA). По матрице АА Т строится ее аппроксимация ĂĂ Т, где Ă - это аппроксимация А, полученная методом латентно-семантического анализа (подробнее на этом мы остановимся далее).

Функция тематической близости двух термов FSR(wi, и>г) однозначно задается

Матрицей ĂĂ Т:

FSR(w 1 , w 2) = ĂĂ Т .

Отметим, что матрица ĂĂ Т имеет размерность k, где k - это выбранная при аппроксимации желаемая размерность пространства тематик. Таким образом, при данном подходе трудоемкость вычисления тематической близости двух термов составляет О(k), т.е. она не зависит от количества анализируемых документов и размера общего словаря.

Глава 5. Основы технологии Text Mining

-----------------------

Web Mining можно перевести как "добыча данных в Web". Web Intelligence или Web Интеллект готов "открыть новую главу" в стремительном развитии электронного бизнеса. Способность определять интересы и предпочтения каждого посетителя, наблюдая за его поведением, является серьезным и критичным преимуществом конкурентной борьбы на рынке электронной коммерции.

Системы Web Mining могут ответить на многие вопросы, например, кто из посетителей является потенциальным клиентом Web-магазина, какая группа клиентов Web-магазина приносит наибольший доход, каковы интересы определенного посетителя или группы посетителей.

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

Согласно таксономии Web Mining , здесь можно выделить два основных направления: Web Content Mining и Web Usage Mining .

Web Content Mining подразумевает автоматический поиск и извлечение качественной информации из разнообразных источников Интернета, перегруженных " информационным шумом ". Здесь также идет речь о различных средствах кластеризации и аннотировании документов.

В этом направлении, в свою очередь, выделяют два подхода: подход, основанный на агентах, и подход, основанный на базах данных.

Подход, основанный на агентах (Agent Based Approach ), включает такие системы:

  • интеллектуальные поисковые агенты (Intelligent Search Agents);
  • фильтрация информации / классификация;
  • персонифицированные агенты сети.

Примеры систем интеллектуальных агентов поиска:

  • Harvest (Brown и др., 1994),
  • FAQ -Finder (Hammond и др., 1995),
  • Information Manifold (Kirk и др., 1995),
  • OCCAM (Kwok and Weld , 1996), and ParaSite (Spertus, 1997),
  • ILA (Information Learning Agent) (Perkowitz and Etzioni, 1995),
  • ShopBot (Doorenbos и др., 1996).

Подход, основанный на базах данных (Database Approach ), включает системы:

  • многоуровневые базы данных;
  • системы web-запросов (Web Query Systems);

Примеры систем web-запросов:

  • W3QL (Konopnicki и Shmueli, 1995),
  • WebLog (Lakshmanan и др., 1996),
  • Lorel (Quass и др., 1995),
  • UnQL (Buneman и др., 1995 and 1996),
  • TSIMMIS (Chawathe и др.., 1994).

Второе направление Web Usage Mining подразумевает обнаружение закономерностей в действиях пользователя Web-узла или их группы.

Анализируется следующая информация:

  • какие страницы просматривал пользователь;
  • какова последовательность просмотра страниц.

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

Web Usage Mining включает следующие составляющие:

  • предварительная обработка;
  • операционная идентификация;
  • инструменты обнаружения шаблонов;
  • инструменты анализа шаблонов.

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

Задачи Web Mining согласно можно подразделить на такие категории:

  • Предварительная обработка данных для Web Mining .
  • Обнаружение шаблонов и открытие знаний с использованием ассоциативных правил, временных последовательностей, классификации и кластеризации;
  • Анализ полученного знания.

Text Mining

Text Mining охватывает новые методы для выполнения семантического анализа текстов, информационного поиска и управления. Синонимом понятия Text Mining является KDT (Knowledge Discovering in Text - поиск или обнаружение знаний в тексте).

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

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

Call Mining

По словам Энн Беднарц , "добыча звонков" может стать популярным инструментом корпоративных информационных систем.

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

Среди разработчиков новой технологии Call Mining ("добыча" и анализ звонков) - компании CallMiner, Nexidia, ScanSoft, Witness Systems. В технологии Call Mining разработано два подхода - на основе преобразования речи в текст и на базе фонетического анализа.

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

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

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

По словам Дэниэла Хонг, аналитика компании Datamonitor: "Использование этих технологий повышает оперативность и снижает стоимость обработки информации".

Типичная инсталляция продукции от разработчика Nexidia обходится в сумму от 100 до 300 тыс. долл. Стоимость внедрения системы CallMiner по преобразованию речи и набора аналитических приложений составляет около 450 тыс. долл.

По мнению Шоллера, приложения Audio Mining и Video Mining найдут со временем гораздо более широкое применение, например, при индексации учебных видеофильмов и презентаций в медиабиблиотеках компаний. Однако технологии Audio Mining и Video Mining находятся сейчас на уровне становления, а практическое их применение - на самой начальной стадии.


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


Основные элементы Text Mining В соответствии с уже сформированной методологии к основным элементам Text Mining относятся: классификация (classification), кластеризация (clustering), построение семантических сетей, извлечение фактов, понятий (feature extraction), суммаризация (summarization), ответ на запросы (question answering), тематическое индексирование (thematic indexing), поиск по ключевым словам (keyword searching). Также в некоторых случаях набор дополняют средства поддержки и создание таксономии (oftaxonomies) и тезаурусов (thesauri).


© ElVisti 4 Классификация При классификации текстов используются статистические корреляции для построения правил размещения документов в определенные категории. Задача классификации - это классическая задачу распознавания, где по некоторой контрольной выборке система относит новый объект к той или другой категории. Особенность систем Text Mining заключается в том, что количество объектов и их атрибутов может быть очень большой, поэтому должны быть предусмотрены интеллектуальные механизмы оптимизации процесса классификации. В существующих сегодня системах классификация применяется, например, в таких задачах: группировка документов в intranet-сетях и на Web-сайтах, размещение документов в определенные папки, сортировка сообщений электронной почты, избирательное распространение новостей подписчикам.


© ElVisti 5 Кластеризация Кластеризация базируется на признаках документов, которые использует лингвистические и математические методы без использования определенных категорий. Результат - таксономия или визуальная карта, которая обеспечивает эффективный охват больших объемов данных. Кластеризация в Text Mining рассматривается как процесс выделения компактных подгрупп объектов с близкими свойствами. Система должна самостоятельно найти признаки и разделить объекты по подгруппам. Кластеризация, как правило, передует классификации, поскольку разрешает определить группы объектов. Различают два основных типа кластеризации - иерархическую и бинарную. Кластеризация применяется при реферировании больших документальных массивов, определение взаимосвязанных групп документов, упрощения процесса просмотра при поиске необходимой информации, нахождения уникальных документов из коллекции, выявления дубликатов или очень близких по содержанию документов.


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


© ElVisti 7 Автоматическое реферирование Автоматическое реферирование (Automatic Text Summarization) - это составление коротких изложений материалов, аннотаций или дайджестов, т.е. извлечения наиболее важных сведений из одного или нескольких документов и генерация на их основе лаконичных и информационно-насыщенных отчетов. Существует два направления автоматического реферирования - квазиреферирование и краткое изложение содержания. Квазиреферирование основано на экстрагировании фрагментов документов - выделении наиболее информативных фраз и формировании из них квазирефератов. Краткое изложение исходного материала основывается на выделении из текстов с помощью методов искусственного интеллекта и специальных информационных языков наиболее важной информации и порождении новых текстов, содержательно обобщающих первичные документы. Семантические методы формирования рефератов-изложений допускают два основных подхода: метод синтаксического разбора предложений, и методы, базирующиеся на понимании естественного языка, методах искусственного интеллекта.


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


Новостное сообщение – опубликованное сообщение, обладающее следующими признаками: дата, время опубликования (может отличаться от даты/времени произошедшего события) и источник (название СМИ). Новостное сообщение – опубликованное сообщение, обладающее следующими признаками: дата, время опубликования (может отличаться от даты/времени произошедшего события) и источник (название СМИ). Новостной сюжет – совокупность сведений (новостных сообщений) о некоторых сущностях и явлениях (о людях, вещах, отношениях, действиях, процессах, свойствах, и т.д.), а также о связанных сущностях и явлениях. Делается допущение, что группа схожих по содержанию и близких по времени новостных сообщений соответствует новостному сюжету. Таким образом, выделение новостных сюжетов сводится к разбиению сообщений на группы. Новостной сюжет – совокупность сведений (новостных сообщений) о некоторых сущностях и явлениях (о людях, вещах, отношениях, действиях, процессах, свойствах, и т.д.), а также о связанных сущностях и явлениях. Делается допущение, что группа схожих по содержанию и близких по времени новостных сообщений соответствует новостному сюжету. Таким образом, выделение новостных сюжетов сводится к разбиению сообщений на группы. Выпуск новостей – ранжированный по некоторому признаку список новостных сюжетов. Выпуск новостей – ранжированный по некоторому признаку список новостных сюжетов. Отслеживание новостного потока. Постановка задачи


Новое направление исследования в области IR: Новое направление исследования в области IR: Отслеживание новостного потока. Постановка задачи TDT topic detection and tracking ??? Чем отличается новая задача от стандартных задач IR? ???Применимы ли стандартные методы IR к новой задаче? TDT - технологии, служащие не только для нахождения похожих новостей, но и для мониторинга отдельных событий, и для получения информационной картины мира в определенное время.


Отслеживание новостного потока. Постановка задачи Список основных задач Сегментация статей (Story Segmentation) - задача разделения непрерывного потока на новости, связанные одним и тем же событием. Отслеживание новостной дорожки (Topic Tracking) - нахождение всех новостей, которые похожи на множество эталонных новостей. Определение дорожки (Topic Detection) - кластеризация всех новостей, порожденных конкретным событием. Определение первой новости в дорожке (First Story Detection) - для нахождения самого первого сообщения в новом событии. Определение связей (Link Detection) - позволяет определить, порождены ли две новости одним и тем же событием.




TDT. Параметры. Пример 1. Министерство финансов внесло в правительство законопроект, предусматривающий поправки в закон об ОСАГО, куда теперь введено новое положение о выплате страховщиками неустойки в случае задержки страховых выплат. Участники рынка в целом приветствуют инициативы Минфина, поскольку считают, что выплат за просрочку будет немного. За 2006 год в ФССН поступило 3099 жалоб, из них жалобы на действия (бездействия) страховых организаций по вопросам нарушений при осуществлении ОСАГО 1679, или более 50% обращений. В 784 жалобах, связанных с ОСАГО, указывается «несоблюдение установленных сроков рассмотрения обращений и осуществления выплат». Вера Балакирева также пояснила, почему размер неустойки привязан к страховой сумме, а не к размеру выплаты: «Достаточно много случаев, когда страховщик, получив документы, вообще не пытается урегули­ровать страховой случай. Тогда он не рассчитывает сумму выплаты или отвечает немотивированным отказом. И привязать неустойку к выплате невозможно».


TDT. Параметры. Пример 1. Министерство финансов внесло в правительство законопроект, предусматривающий поправки в закон об ОСАГО, куда теперь введено новое положение о выплате страховщиками неустойки в случае задержки страховых выплат. Участники рынка в целом приветствуют инициативы Минфина, поскольку считают, что выплат за просрочку будет немного. За 2006 год в ФССН поступило 3099 жалоб, из них жалобы на действия (бездействия) страховых организаций по вопросам нарушений при осуществлении ОСАГО 1679, или более 50% обращений. В 784 жалобах, связанных с ОСАГО, указывается «несоблюдение установленных сроков рассмотрения обращений и осуществления выплат». Вера Балакирева также пояснила, почему размер неустойки привязан к страховой сумме, а не к размеру выплаты: «Достаточно много случаев, когда страховщик, получив документы, вообще не пытается урегулировать страховой случай. Тогда он не рассчитывает сумму выплаты или отвечает немотивированным отказом. И привязать неустойку к выплате невозможно».


TDT. Параметры. Пример 1. Проблемы Новостные сообщения тексты малого объема Новостные сообщения тексты малого объема Учитывать «нелингвистические признаки» Учитывать «нелингвистические признаки» Учитывать максимально большое количество слов в качестве параметров Учитывать максимально большое количество слов в качестве параметров Учитывать только лексемы с определенными семантическими или морфологическими свойствами Учитывать только лексемы с определенными семантическими или морфологическими свойствами Частотность «терминов» и «нетерминов» одинаковая Частотность «терминов» и «нетерминов» одинаковая «Неустойчивость» частотных характеристик тематических элементов «Неустойчивость» частотных характеристик тематических элементов


TDT. Параметры. Пример 1. Проблемы Новостные сообщения сообщения о часто случающихся событиях и о часто упоминаемых людях или организациях Новостные сообщения сообщения о часто случающихся событиях и о часто упоминаемых людях или организациях Много общеупотребительных слов, определяющих тему сообщения Много общеупотребительных слов, определяющих тему сообщения Признаки N-граммы из слов с высокими tf.idf Признаки N-граммы из слов с высокими tf.idf


TDT. Параметры. Пример 1. Проблемы Новостные сообщения сообщения о часто случающихся событиях и о часто упоминаемых людях или организациях Новостные сообщения сообщения о часто случающихся событиях и о часто упоминаемых людях или организациях Много общеупотребительных слов, определяющих тему сообщения Много общеупотребительных слов, определяющих тему сообщения Признаки N-граммы с высокими tf.idf Признаки N-граммы с высокими tf.idf


TDT. Параметры. Пример 1. Проблемы Много многословных устойчивых словосочетаний, состоящих из общеупотребительных слов Много многословных устойчивых словосочетаний, состоящих из общеупотребительных слов Нужен способ выделения их именно как устойчивых слвосочетаний Нужен способ выделения их именно как устойчивых слвосочетаний Вначале выделить N-грамм как устойчивое словосочетание, потом уже считать веса по устойчивому словосочетанию (t- статистика, взаимная информация и т.п.) Вначале выделить N-грамм как устойчивое словосочетание, потом уже считать веса по устойчивому словосочетанию (t- статистика, взаимная информация и т.п.) например, использовать специальные статистики для выделения устойчивых словосочетаний (MWU), использовать частеречные фильтры (shallow parsing, chunking)


TDT. Параметры. Пример 1. Проблемы Новостные сообщения компактные Новостные сообщения компактные Авторы сообщений стараются не повторяться про одно и то же событие разными словами, один и тот же объект называть по разному, т.е. Нет полных повторений, но есть семантические повторения низкие tf.idf у участников событий Авторы сообщений стараются не повторяться про одно и то же событие разными словами, один и тот же объект называть по разному, т.е. Нет полных повторений, но есть семантические повторения низкие tf.idf у участников событий ср. Министерство финансов, минфин, министерство и т.п., дворняга, собака, пес, Шарик ср. Министерство финансов, минфин, министерство и т.п., дворняга, собака, пес, Шарик Постулат о текcтовой связности Постулат о текcтовой связности Разные способы моделирования текстовой связности Разные способы моделирования текстовой связности


TDT. Параметры. Усовершенстования Постулат о текстовой связности Постулат о текстовой связности Математические методы моделирования Математические методы моделирования Лингвистические и «когнитивные» методы моделирования Лингвистические и «когнитивные» методы моделирования Меры ассоциативной связи между словами в предложении Кандидаты в признаки все биграмы в предложении Изменение технологии кластеризации (кластеризация по предложениям, по абзацам и т.п.) Математические «способы борьбы» Математические «способы борьбы»


TDT. Параметры усовершенствования Постулат о текстовой связности Постулат о текстовой связности Лингвистические и «когнитивные» методы моделирования: Лингвистические и «когнитивные» методы моделирования: вектор лексических цепочек (First Story Detection using a Composite Document Representation. Nicola Stokes, Joe Carthy) учет кластеризации по типу новостного сюжета (Activity clustering) – т.е. слова, имеющие высокий tf.idf засчет того, что характеризуют события определенного типа («ураган», «террористический акт» и т.п.) отдельные веса для имен собственных (named entities)


TDT. Параметры. Пример 1. Проблемы Новостные сообщения подвижные: условия группировки в сюжет меняются со временем Если вначале мы имеем новый текст, посвященный новой новости, то что будет с tf.idf нужных слов? Часть совпадет с ключевыми словами про новости об аналогичных событиях Часть совпадет с ключевыми словами про новости об аналогичных событиях Часть, наиболее значимых, будут иметь низкий tf.idf Часть, наиболее значимых, будут иметь низкий tf.idf Необходим пересчет весовых коэффициентов (как часто?) Возможно предварительное обучение на тестовом корпусе Раздельный подсчет весов для разных категорий лексических единиц (веса для именованных объектов отдельно)


TDT. Параметры. Усовершенстования признакового пространства. Резюме (1) tf.idf считается на тренинговом корпусе, при поступлении нового сообщения пересчитывается, вся коллекция, включая новое сообщение заново подвергается кластеризации (greedy agglomerative clustering algorithm) каждый термин получает дополнительный вес в зависимости от его близости к лексическим единицам, детектирующим время возниконовения события документ характеризуется комбинацией 2-х векторов: стандартый tf.idf вектор + вектор лексических цепочек (First Story Detection using a Composite Document Representation. Nicola Stokes, Joe Carthy)


TDT. Параметры. Усовершенстования признакового пространства. Резюме (2) учитываются традиционные параметры (позиция в тексте и т.п.) учет кластеризации по типу новостного сюжета (Activity clustering) – т.е. слова, имеющие высокий tf.idf засчет того, что характеризуют события определенного типа («ураган», «террористический акт» и т.п.) (Ronald K. Braun and Ryan Kaneshiro Exploiting topic pragmatics for New Event Detection in tdt-2003) отдельные веса для имен собственных (named entities) классификация документов по категориям, после чего удаление стоп-слов внутри каждой категории отдельно и выбор признаковой базы внутри каждой категории


TDT. Меры близости устанавливается порог: выше порога – «нет» - сообщение относится к старому сюжету, ниже порога – «да» - первое сообщение в сюжете устанавливается порог: выше порога – использование сразу нескольких методов кластеризации – результирующая мера близости как некоторая функция от результатов разных методов


TDT. Меры близости Векторная модель Другие меры близости: Во-первых, мера не учитывает разницу в размере сравниваемых документов, а во-вторых, при ее вычислении не используется информация о частоте употребления термов, составляющих документы. sim(D i, D j) = Prob(w D i | w D j). Мера Джаккарда


TDT. Методы математического моделирования. Определение новостной дорожки. Методы кластеризации. Формирование кластеров: Последний поступивший на вход системы документ (документ с номером 1 при обратной нумерации) порождает первый кластер и сравнивается со всеми предыдущими. Если мера близости для какого-нибудь документа оказывается ближе заданной пороговой, то текущий документ приписывается первому кластеру. Сравнение продолжается, пока не исчерпывается список актуальных документов потока. После такой обработки документа 1, происходит обработка следующего документа, не вошедшего в первый кластер, с которым последовательно сравниваются все актуальные документы потока и т.д.


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


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


Чем больше лексических совпадений, тем ближе тексты Чем больше лексических совпадений, тем ближе тексты Наиболее близкие тексты дубликаты кластеры, состоящие из дубликатов или очень близких текстов Наиболее близкие тексты дубликаты кластеры, состоящие из дубликатов или очень близких текстов Сначала удалить дубликаты, а затем кластеризовать Сначала удалить дубликаты, а затем кластеризовать TDT. Методы математического моделирования. Определение новостной дорожки. Проблемы Проблема семантически идентичных текстов Проблема семантически идентичных текстов (1)СООБЩИТЬ, СЕГОДНЯ, КОНФЕРЕНЦИЯ, ГЛАВА, АЛЕКСЕЙ, МИЛЛЕР, ПРЕМЬЕР- МИНИСТР, БЕЛОРУССИЯ, СЕРГЕЙ,З АВЕРШЕНИЕ, ПЕРЕГОВОРЫ, МОСКВА (2)РАНЕЕ, ПРЕДЛАГАТЬ, МИНСК, ПОКУПАТЬ, ГАЗ, ЦЕНА, ДОЛЛАР, ДОЛЛАР,БЫТЬ, ОПЛАТИТЬ, ДЕНЕЖНЫЙ, СРЕДСТВО, ЧАСТЬ, АКТИВ, БЕЛТРАНСГАЗ (3)АЛЕКСЕЙ, МИЛЛЕР, РАССКАЗАТЬ, ДОГОВОР, ПОСТАВКА, ТРАНЗИТ, РОССИЙСКИЙ, ГАЗ, ПОДПИСАТЬ, ПОСЛЕДНИЙ, МИНУТА, МИНУВШИЙ, ГОД, ЕСТЬ, (4) ОБЕЩАТЬ, БОЙ, КРЕМЛЕВСКИЙ, КУРАНТЫ СООБЩИТЬ, ТЕЧЕНИЕ, ЛЕТА, РАВНЫЙ, ДОЛЯ, ВЫПЛАЧИВАТЬ, ПОЛОВИНА, СТОИМОСТЬ, БЕЛТРАНСГАЗ, ОЦЕНИТЬ, ДОЛЛАР


Новости, посвященные одним и тем же типам событий (наводнения, заведение уголовного дела, теракт и т.п.), попадут в один и тот же кластер Новости, посвященные одним и тем же типам событий (наводнения, заведение уголовного дела, теракт и т.п.), попадут в один и тот же кластер Классификация по типам новостей (по событиям), потом уже выделение признаков Классификация по типам новостей (по событиям), потом уже выделение признаков Цепочки именованных объектов Цепочки именованных объектов TDT. Методы математического моделирования. Определение новостной дорожки. Методы кластеризации. Проблемы Альтернативный подход: параметры кластеризации основные координаты события Альтернативный подход: параметры кластеризации основные координаты события Фокус новости Фокус новости


TDT. Методы математического моделирования. Определение новостной дорожки. Фокус новости Фокус новости Ф окус события представляет собой совокупность объектов, каким-либо образом взаимодействующих в новости, и их тематического окружения (синонимов, описаний, дополнений объектов и других параметров, характеризующих рассматриваемое событие). Фокус события может отвечать на следующие вопросы (Сценарий (фрейм) для стандартной новости): Кто? Где? Когда?


Базовые технологии: Задачи TDT. «Переносимость» методов IR Параметры информационный портрет математические «корреляты» параметров (например, веса, оценки вероятности и т.п.) Параметры информационный портрет математические «корреляты» параметров (например, веса, оценки вероятности и т.п.) Методы разбиения объектов на классы Методы разбиения объектов на классы Меры близости - различия Меры близости - различия Задачи TDT База: методы IR Вопросы: Что считать признаками (размерностями пространства / параметрами интегральной характеристики)? Как оценивать вес признака (проекцию точки на соответствующую ось) Как оценивать интегральную характеристику (меру близости в пространстве) Как уменьшить количество признаков Как уменьшить шум (уменьшить число признаков, ослабить / усилить эффект корреляции признаков)


Развитие задач обработки текстов Технологическая цепочка обработки текстов в современных системах: На входе: поток текстов 1) 1. «Семантические» характеристики текста в целом Сгруппировать тексты по «событию» (кластеризация) Соотнести событие с некоторой областью знаний (рубрикация) Приписать тексту резюме (реферирование - summarization) Сопоставить тексту топики (семантические теги - топики)


Развитие задач обработки текстов 1) 2. Содержательный анализ текста Выделить в тексте «главных героев» (распознавание именованных сущностей – NER – named entities recognition Сопоставить сущности некоторое онтологическое описание - пресс- портрет, досье и т.п. (дополнительная задача разрешение неоднозначности - named entities disambiguation) Локализовать текст (геолокация) Определить в тексте тематические доминанты (семантические теги) Выделить главные события (Fact extraction)


Развитие задач обработки текстов На входе: пользователь + текст Задачи: (а) сформировать у пользователя некоторое отношение к объектам из текста (б) поставить пользователю дополнительный контент в соответствии с его интересами (в т.ч. детектировать интересы пользователя – персонализация) Opinion mining (sentiment analysis) Локализовать текст (геолокация) Поиск в социальных сетях сообщений на соответствующую тему Social tagging Рекомендации, контекстная реклама


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


© ElVisti 42 SemioMap (Semio Corp.) SemioMap - это продукт компании Entrieva, созданный в 1996 г. ученым- семиотиком Клодом Фогелем (Claude Vogel). В мае 1998 г. продукт был выпущен как промышленный комплекс SemioMap первая система Text Mining, работающая в архитектуре клиент-сервер.


© ElVisti 43 SemioMap (Semio Corp.) Система SemioMap состоит из двух основных компонент - сервера SemioMap и клиента SemioMap. Работа системы протекает в три фазы: Индексирование: сервер SemioMap автоматически читает массивы неструктурированного текста, извлекает ключевые фразы (понятия) и создает из них индекс; Кластеризация понятий: сервер SemioMap выявляет связи между извлеченными фразами и строит из них, на основе совместной встречаемости, лексическую сеть ("понятийную карту"); Графическое отображение и навигация: визуализация карт связей, которая обеспечивает быструю навигацию по ключевым фразам и связям между ними, а также возможность быстрого обращения к конкретным документам.

Технологии анализа данных (Text Mining, Data Mining)

Руководитель : Баяндин Николай Иванович.

Образовательное учреждение : Федеральное государственное бюджетное учреждение высшего профессионального образования "Московский государственный университет экономики, статистики и информатики (МЭСИ)", г. Москва

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

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

Рассмотрим подробнее технологию анализа данных.

Наиболее перспективные направления анализа данных:

·анализ текстовой информации

·интеллектуальный анализ данных

1. Анализ текстовой информации Text Mining

Анализ структурированной информации, хранящейся в базах данных, требует предварительной обработки: проектирования БД, ввод информации по определенным правилам, размещение ее в специальных структурах (например, реляционных таблицах) и т.п. Текстовые документы практически невозможно преобразовать в табличное представление без потери семантики текста и отношений между сущностями. По этой причине такие документы хранятся в БД без преобразований, как текстовые поля (BLOB-поля). В это же время в тексте скрыто огромное количество информации, но ее неструктурированность не позволяет использовать алгоритмы Data Mining. Решением этой проблемы занимаются методы анализа неструктурированного текста (Text Mining).

Определение Text Mining: Обнаружение знаний в тексте - это нетривиальный процесс обнаружения действительно новых, потенциально полезных и понятных шаблонов в неструктурированных текстовых данных. "Неструктурированные текстовые данные" - набор документов, представляющих собой логически объединенный текст без каких-либо ограничений на его структуру (web-страницы, электронная почта, нормативные документы).

Процесс анализа текстовых документов можно представить как последовательность нескольких шагов:

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

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

Извлечение информации. Выделение ключевых понятий для анализа.

Применение методов Text Mining. Извлекаются шаблоны и отношения, имеющиеся в текстах.

Интерпретация результатов. Представлении результатов на естественном языке, или в их визуализации в графическом виде.

Предварительная обработка документа

Удаление стоп-слов. Стоп-словами называются слова, которые являются вспомогательными и несут мало информации о содержании документа.

Стэмминг - морфологический поиск. Он заключается в преобразовании каждого слова к его нормальной форме.

Л-граммы это альтернатива морфологическому разбору и удалению стоп-слов. Позволяют сделать текст более строгим, не решают проблему уменьшения количества неинформативных слов;

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

Наиболее эффективно совместное применение всех методов.

Задачи Text Mining

Классификация (classification) - определение для каждого документа одной или нескольких заранее заданных категорий, к которым этот документ относится, автоматическое выявление групп семантически похожих документов среди заданного фиксированного множества

Автоматическое аннотирование (summarization) сокращение текста и сохранение его смысла. Результат включает в себя наиболее значимые предложения в тексте.

Извлечения ключевых понятий (feature extraction) - идентификация фактов и отношений в тексте (имена существительные и нарицательные: имена и фамилии людей, названия организаций и др.).

Навигация по тексту (text-base navigation) перемещение по документам по определённым темам и терминам. Это выполняется за счет идентификации ключевых понятий и некоторых отношений между ними.

Анализ трендов позволяет идентифицировать тренды в наборах документов на какой-то период времени.

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

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

Примеры средства анализа текстовой информации:

Средства Oracle - Oracle Text2.

Средства от IBM - Intelligent Miner for Text1

Средства SAS Institute - Text Miner

Интеллектуальный анализ данных Data Mining

Интеллектуальный анализа данных (англ. Data mining, другие варианты перевода - "добыча данных", "раскопка данных") - обнаружение неявных закономерностей в наборах данных.

·специализированных "коробочных" программных продуктов для интеллектуального анализа;

·математических пакетов;

·электронных таблиц (и различного рода надстроек над ними);

·средств интегрированных в системы управления базами данных (СУБД);

·других программных продуктов.

Задачи интеллектуального анализа данных:

Задача классификации определение категории и класса каждому объекту.

Задача регрессии - поиск шаблонов для определения числового значения.

Задача прогнозирования новых значений на основании имеющихся значений числовой последовательности. Учитываются тренды.

анализ text data mining

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

Задача определения взаимосвязей - определение часто встречающихся наборов объектов среди множества подобных наборов.

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

Анализ отклонений - поиск событий, отличающихся от нормы.

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

Вывод

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

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

Список используемой литературы и интернет - ресурсов

1.Л.М. Ермакова Методы классификации текстов и определения качества контента. Вестник пермского университета 2011. УДК 004.912

3.

4.

5.

6.



Популярное в рубрике:
Как объединить слои в фотошопе в один или соединить их в группу Как объединить несколько слоев в фотошоп
Как объединить слои в фотошопе в один или соединить их в группу...
читать
Перенос контактов на новый телефон android
Перенос контактов на новый телефон android
читать
Самсунг Галакси перезагружается сам по себе — Решения Galaxy note 4 перезагружается сам по себе
Самсунг Галакси перезагружается сам по себе — Решения Galaxy note...
читать
Основные возможности Kaspersky Rescue Disk
Основные возможности Kaspersky Rescue Disk
читать

Последние Статьи
Макбук не подключается к wifi Макбук не видит...
читать
Как заработать на WebMoney
читать
"Супра", планшет: отзывы покупателей
читать
Местонахождения судов в реальном времени
читать
Лучшие программы для Android Запись звонков от...
читать
Удаляем не читателей в Твиттере
читать
Подключаем интернет на ноутбуке: все возможные...
читать
Samsung Galaxy S IV – новый флагман...
читать
Top