Подход выделения событий в новостном потоке

Восточно-Европейский журнал передовым технологий ISSN 1729-3774

УДК 004.021

ПОДХОД ВЫДЕЛЕНИЯ СОБЫТИЙ В НОВОСТНОМ ПОТОКЕ

У статтi розглянута проблема обробки дублiкатiв i сюжетних ланцюжтв новин при видшенш ушкальних подш у новинно-му потощ. Запропоновано метричш кри-тери ощнки ступеня близькостi новин. Сформульовано алгоритм обробки новин-ного потоку

Ключовi слова: новинний потш, синтаксичш моделi, лексеми, критерш близькостi □-□

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

-□ □1. Введение

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

Сформулируем метрические критерии близости двух новостных объектов и алгоритм объединения новостей в кластер.

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

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

Обозначим множество _лексем, формирующих словари категорий, L = ] = , где ^ - словарь синонимических лексем. Для множества категорий событий

И.А. Черенков

Аспирант*

Контактный тел.: (057) 707-64-74 E-mail: igor.cherenkov@gmail.com С. В. Орехов

Кандидат технических наук, доцент* Контактный тел: (057) 707-64-74 E-mail: osv@kpi.kharkov.ua *Кафедра системного анализа Национальный технический университет "Харьковский политехнический институт" ул. Фрунзе, 21, г. Харьков, Украина, 61002

K обозначим соответствующие им словари лексем Vk = {lk}, k е K .

При этом одни и те же лексемы могут формировать разные словари категорий Vk n Vr Ф 0;k Ф r; r,k е K , что делает невозможным однозначное выделение категории новости исключительно на словарях лексем. Необходимая точность идентификации достигается за счёт использование аппарата синтаксических моделей грамматик непосредственных составляющих применительно к анализу названия новости и лида, содержащих всю необходимую информацию о событии. Эффективность такого подхода заключается в том, что для новостей как специфических контейнеров информации в разрезе конкретной отрасли возможно формирование полного множества синтаксических моделей без значительных ресурсных затрат [4, 5]. Составление же некоторого универсального классификатора для любой предметной области не представляется возможным.

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

Обработка новости на основе синтаксических моделей предполагает формирование трёх векторов: вектора n лексем, отражающего информацию о том: что, где, когда и с кем происходит в новости; вектора П восстановленного на основе П ; вектора П лексем новости, уточняющие вектор П.

Вектор П всегда имеет фиксированную структуру П = (d, c,G, E,M), где d - содержит дату новости (когда), c - тип, категория события (что), G - география

© ИА Черенков, С.В. Орехов, 2013

Математика и кибернетика - фундаментальные и прикладные аспекты

события (где), Е - множество контрагентов новости, М - множество товаров (рынков), упомянутых в новости (с кем).

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

Ер™™, = (1 + 5>& - тр2)(1+]Ы - ер2)(1 + - gp2) ^

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

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

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

Откуда, объединяя все три критерия в один (1-4), можно получить метрический критерий близости новостей:

Id&- d&&|< dtreshold,

F . <а,

primary &

F <а-F

secondary — primary *

где М&,М&& - вектора, имеющие в качестве ко- Е5есшЛгу = (1 + ^(т&-тр2)(1 (е&-е&)2)(1 + ^-gJ")2)^тт.(4) ординат М&и М&& и принимающие значения ¡=о ¡=о 1=о

т& = (0,1) для тех лексем, что входят в вектора п сравниваемых новостей, Е&, Е&& - соответственно вектора контрагентов, G&, G&& - вектора географии и рынков новостей, при этом значения географии событий должны быть приведены к общей размерности.

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

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

Для векторов п прочих лексем, сформируем множества словарей синонимических лексем, упоминаемых в новостях, L&u L&&, на основе которых сформи- - |о,1 ей

руем векторы L&, L&&, такие что Li = < ... , откуда,

[1,1 е п

критерий близости векторов принимает вид

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

по третичному критерию; Fsecondary Ерптагу Означает что сходство по восстановленному вектору п должно быть больше (в связи с большим числом координат), чем для исходного вектора п в пределах погрешности

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

Ftertiary = ^ (Li Li0

На основании может быть получен коэффициент а :

tertiary

где вектор nU = n&un&&, р( n U)- длина вектора.

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

Однако, применение лишь этих двух критериев для оценки степени близости новостей не достаточно,

Рис. 1. Алгоритм выделения кластера события

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

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

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

Для безошибочного объединения новостей в событийные кластеры необходимо использовать разработанный алгоритм и критерий оценки степени близости.

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

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

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

Литература

Abstract

Market price forecasting allows effective manage of pricing policy and acquire competitive advantage. Most of existing price forecasting approaches are based either on experts& opinions or on raw price data models. Neither of this approaches allows to get a high forecasting accuracy due to nature of price behaving since price reflects events in real world. Possible solution could be in usage of news based forecasting models. Such forecasting models require processing of news streams.

Processing news streams is a complex task because reflection of event in the news isn&t very precise therefore there is a need in development of proper news data processing methods. Main problem in news data processing is filtering news duplicates and plots. One of the possible approaches in news& processing is based on extracting lexemes from news header and first sentence and their further processing.

By forming three vectors based on extracted lexemes for the news it is possible to develop an efficient criteria for duplicates detection. By itself criteria doesn&t include any kind of expert opinion for similarity detection except the basic processing logic.

Developed approach allows to extract events data from news stream sufficient for price forecasting