Метод обнаружения изменений структуры веб-сайтов в
системе сбора новостной информации
© А.М. Андреев © Д.В. Березкин © И.А. Козлов © К.В. Симаков
МГТУ им. Н.Э. Баумана, г. Москва
arkandreev@gmail.com dmitryb2007@yandex.ru kozlovilya89@gmail.com skv@ixlab.ru
Аннотация 2 Постановка задачи
Работа посвящена решению задачи обнару- 2.1 Функционирование системы сбора
жения сбоев в работе системы сбора ново-
стной информации, вызванных изменения- Существует множество подходов к организации
ми структуры веб-сайтов. Приведены моде- сбора открытых текстовых материалов с веб-сайтов.
ли документа и набора документов, пред- Как правило, система сбора использует информа-
ложен двухступенчатый метод обнаружения цию об HTML-разметке целевых страниц для поис-
сбоев. Проведена экспериментальная оцен- ка в них нужной информации [12]. Эта информация
ка и даны направления по дальнейшему используется правилами распознавания, записывае-
усовершенствованию предложенного под- мыми на принятом в системе формальном языке.
хода. Распространение получили как ручной способ опи-
сания правил, когда правила распознавания форми-
1 Введение рует программист [13], так и автоматизированный
способ, когда правила формируются автоматически
Сбор текстовой информации из открытых Ин- на основе обучающей выборки, подготовленной
тернет-источников, ее унификация и накопление, оператором [1,2,8]. Имея набор правил, система
являются задачами, с которыми приходится сталки- сбора выполняет периодический опрос веб-сайтов в
ваться при разработке промышленных систем ин- поисках новых материалов.
теллектуальной обработки текстов, например, клас-
В данной работе рассматривается система, вы-
са Text Mining. Без наличия актуальной базы, посто-
полняющая сбор новостей на основе правил, задан-
янно пополняющейся текстами целевой предметной
ных вручную программистом. Основные функцио-
области, невозможно эффективно использовать ме-
нальные элементы системы сбора представлены на
тоды автоматической обработки (такие как класте-
рис. 1.
ризация, полнотекстовый поиск, выявление скрытых
зависимостей). Web-
Система Результат сбора
страница с сбора
В данной работе рассматривается решение зада- текстом
чи качественного сбора новостной информации. К БД с текстами
новостей
такой информации относится текст новости, а также RSS-лента
Очищенный Метаданные
текст
сопутствующие метаданные, включающие название, XPath
в XML форме
дату публикации, автора новости и др. Под качест- Новостной Web-сайт правила
Статистика
венным сбором в первую очередь подразумевается
очистка текста новости от окружающей его служеб- Рис.1. Функционирование системы сбора.
ной информации: меню сайта, рекламные баннеры,
блоки социальных сетей, комментарии пользовате- Система сбора выполняет чтение RSS-ленты
сайта, откуда извлекается метаданные о каждой но-
лей и т.д.
вости: название, аннотация, время публикации и
Основной акцент в данной статье делается на URL текста новости. Далее по полученному URL
проблеме своевременного обнаружения изменения осуществляется чтение страницы с текстом новости,
структуры опрашиваемых веб-сайтов, поэтому выполняется построение DOM-модели этой страни-
предлагаемый подход может быть использован не цы, откуда и выполняется извлечение чистого текста
только для обработки новостных сайтов, он также на основе имеющихся XPath правил. Результат сбо-
распространяется на сбор сообщений из электрон- ра представляет собой чистый текст новости и
ных библиотек, блогов, форумов и социальных се- XML-документ с метаданными. Далее эта информа-
тей. ция заносится в базу данных, где осуществляется
накопление и аналитическая обработка собираемых
Труды 14-й Всероссийской научной конференции данных. Кроме этого, система выполняет постоян-
«Электронные библиотеки: перспективные методы и ную регистрацию и накопление статистической ин-
технологии, электронные коллекции» — RCDL-2012, формации о состоянии и структуре опрашиваемого
Переславль-Залесский, Россия, 15-18 октября 2012 г. веб-сайта.
87
2.2 Задача обнаружения сбоев зует набор выделяемых из веб-страницы признаков.
Обучение классификатора осуществляется на пре-
Все методы сбора информации из веб-сайтов, допределенных наборах веб-страниц обоих классов.
использующих особенности разметки страниц, объ- Преимуществом такого подхода является высокая
единяет то, что при изменении верстки сайта, воз- скорость реакции детектора на сбой: «плохой» до-
никает необходимость перенастраивать правила кумент будет выявлен непосредственно после его
распознавания. При выполнении круглосуточного поступления. Однако этот метод имеет и серьезный
опроса целевых сайтов, своевременность обнаруже- недостаток. Статьи, подвергающиеся анализу, могут
ния изменения верстки является весьма актуальной сильно отличаться друг от друга. Так, иногда на
задачей, поскольку система сбора фактически пере- вход детектора поступают «хорошие», но нетипич-
стает работать до тех пор, пока оператор не откор- ные для данного источника новости. Если подобных
ректирует набор правил распознавания. документов не было в обучающей выборке класси-
В простейшем случае при существенном изме- фикатора, они не могут быть корректно распознаны,
нении структуры сайта система сбора станет выда- и в результате происходит ложное срабатывание.
вать в качестве результата пустые текстовые доку- При накапливании корректных документов и увели-
менты. Однако существуют достаточно сложные чении обучающей выборки частота возникновения
ситуации, когда при изменении верстки система таких ошибок постепенно уменьшается, но они про-
сбора начинает извлекать тексты не полностью, ли- должают периодически возникать.
бо фрагменты из других участков сайта, например, 2. Анализ контрольной серии из нескольких по-
комментарии пользователей. Именно выявлению следних загруженных веб-страниц. Данный подход
таких нетривиальных ситуаций посвящена данная позволяет избавиться от ложных срабатываний. Да-
статья. же если в контрольную серию попало несколько
подозрительных статей, то усредненные характери-
2.3 Существующие подходы к решению задачи стики этой коллекции останутся близкими к харак-
теристикам эталонной обучающей выборки. Если же
В работах, посвященных теме выявления сбоев
сомнительные документы будут поступать от ис-
систем извлечения данных [7,9,11], представлено
точника регулярно, то через некоторое время, когда
несколько подходов к решению вышеуказанной за-
в контрольной серии таких статей будет накоплено
дачи. Большинство из них основано на оценке ста-
достаточное количество, они будут составлять зна-
тистических характеристик документов, извлекае-
чительную долю анализируемого набора. В резуль-
мых системой. При этом оценке может подвергаться
тате характеристики контрольной серии изменятся,
как отдельно взятый документ [7] (в этом случае
и мы сможем обнаружить сбой. Такой подход к
вычисляется вероятность его корректности, которая
фиксации сбоев более надежен. Причём качество
затем сравнивается с задаваемым пользователем
проверки будет возрастать с увеличением количест-
пороговым значением), так и их набор [11] (оценке
ва документов в контрольной серии. Но это приве-
подвергается схожесть законов распределения слу-
дёт к возникновению значительной задержки между
чайных величин, соответствующих характеристикам
моментом, в который произошел сбой, и временем
документов из обучающей и тестовой выборок. Для
его обнаружения.
сравнения используется критерий согласия Пирсона
[20]). Предложенный в данной работе метод, сочетает
В [11] также представлен подход, основанный преимущества двух вышеописанных подходов (см.
на использовании методов machine learning для рис. 2): быструю реакцию на сбой и высокое качест-
обучения системы обнаружения сбоев на наборах во проверки.
корректных документов для последующего опреде-
ления правильности её работы на новых данных. В Статистика
качестве таких методов используется, в частности,
одноклассовая классификация (выявление анома-
лий) [5]. Система обнаружения
сбоев
Оперативный Отложенный Администратор
Система сбора
3 Принцип обнаружения сбоев детектор детектор
Для распознавания сбоев, связанных с измене-
нием верстки, в систему сбора встраивается подсис-
тема, осуществляющая контроль корректности по-
ступающих документов и выявляющая сбои в верст-
ке документов. Возможны два следующих подхода к
Правила
обнаружению сбоев.
1. Анализ одной загруженной веб-страницы. Суть Рис. 2. Предложенный подход.
данного подхода заключается в использовании клас- Данный метод положен в основу подсистемы
сификатора, который определяет принадлежность контроля корректности загружаемых документов.
веб-страницы к классу корректных или некоррект- Подсистема представляет собой двухступенчатый
ных страниц. В своей работе классификатор исполь- детектор сбоев. Один из его компонентов – «опера-
88
тивный детектор» – проверяет документы непо- 4.2 Модель набора документов
средственно в момент их поступления и делает
предварительный вывод о вероятности сбоя. Если Для описания модели набора из нескольких до-
вероятность высока, выполняется проверка «отло- кументов заметим следующее. Группы характери-
женным детектором», уточняющая этот результат. стик (P,S,N,V) и (TH,TB,TS,TI,TO) имеют разную при-
роду. Характеристики первой группы описывают
4 Предложенные модели документов свойства текста документа, тогда как характеристи-
ки второй группы отражают свойства его разметки.
В основе системы обнаружения сбоев лежит мо- Для описания свойств набора из нескольких доку-
дель анализируемых данных. Два основных компо- ментов, мы будем рассматривать эти группы харак-
нента системы работают с разными входными дан- теристик отдельно.
ными и анализируют различные характеристики, Случайные величины группы (P,S,N,V) имеют
поэтому для каждого из них предложена своя мо- разнородные области значений. Так величина N
дель: модель документа, подвергающаяся обработке обычно принимает значения в диапазоне от 1 до 100,
«оперативным детектором» и модель набора доку- величина V непрерывна, а значения дискретной ве-
ментов, анализируемая «отложенным детектором». личины P могут достигать 105. В связи с этим, для
последующего анализа удобно все величины при-
4.1 Модель документа вести к дискретному виду, а области их значений
Под моделью документа понимается совокуп- отобразить на множество фиксированной мощности.
ность его характеристик, учитываемых «оператив- Для этого необходимо разбить область значений
ным детектором» при его обработке. При создании каждой величины группы (P,S,N,V) на фиксирован-
детектора для системы сбора новостей выбор пара- ное количество интервалов равной длины. Пусть m
метров производился с учетом некоторых особенно- - количество таких интервалов. Это число выбирает-
стей функционирования системы. Статья извлекает- ся в зависимости от объема выборки. Одним из наи-
ся из веб-страницы, где текст обычно разбит на па- более распространенных способов определения оп-
раграфы (html-элемент ). Также внутри тексто- тимального числа интервалов является формула
вых параграфов могут встречаться стилевые элемен- Стерджесса:
ты разметки. С учётом этих факторов для оценки (2)
корректности новостей были выбраны следующие где n – количество документов в наборе[14].
характеристики:
Для снижения вычислительной сложности алго-
объем веб-страницы, содержащей статью (P); ритмов, использующих предлагаемую нами модель,
суммарный размер параграфов статьи (S). Учиты- в контексте набора из нескольких документов мы
вается только текст, без html-элементов; будем рассматривать величины (P,S,N,V) независи-
количество параграфов в статье (N); мо друг от друга. Поэтому, с точки зрения величин
дисперсия размера параграфа в рамках статьи (V); (P,S,N,V), модель для набора документов будет
количество html-элементов различных типов, представлять собой следующие четыре статистиче-
включенных в новость. Для сокращения типов ских ряда:
html-элементов, они были сгруппированы по не-
скольким категориям. Были выделены классы наи-
более часто встречающихся элементов: «Гипер- (3)
ссылки (H)» (в этот класс попал элемент href), Где –частота попадания в i-ый ин-
«Текстовые блоки (B)» (br, div, span), «Формати- тервал значения величины P, S, N и V соответствен-
рование текста (S)» (i, b, u, em, strong), «Изобра- но на выборке из n документов.
жения (I)» (img). Остальные теги попали в класс Для учета в модели (3) величин (TH,TB,TS,TI,TO)
«Прочее (O)». Для каждой категории был введен рассмотрим другой подход к представлению ин-
параметр (соответственно, TH,TB,TS,TI и TO), значе- формации о html-элементах. В i-ом документе вы-
ние которого равно количеству элементов соответ- борки встречается определенное количество тэгов
ствующего класса, включенных в новость. каждой из выделенных нами пяти категорий H, B, S,
I и O. Обозначим эти количества
В отличие от дисперсии, среднее значение раз- соответственно. Просуммируем их по всем доку-
мера параграфа не включено в число параметров, ментам выборки и получим следующие значения
поскольку оно может быть выражено через пара-
метры S и N - суммарный размер и количество пара-
графов соответственно. , которые образуют пятиэле-
ментный статистический ряд ,
Таким образом, каждый документ характеризу- который мы будем рассматривать в качестве модели
ется рядом параметров (в нашем случае – девятью), набора документов, с точки зрения, частоты встре-
поэтому, с точки зрения детектора, документ пред- чаемости в нем тэгов из пяти выделенных катего-
ставлен девятимерным случайным вектором, эле- рий.
ментами которого являются значения перечислен-
ных характеристик: Таким образом, модель набора документов
представляет собой совокупность из следующих
X=(P,S,N,V,TH,TB,TS,TI,TO) (1) пяти статистических рядов:
89
Таким образом, обучение оперативного детекто-
ра сводится к выделению таких областей, а класси-
фикация статей на корректные и некорректные – к
(4) определению, попадает ли документ в одну из выде-
ленных областей.
5 Оперативный детектор
Рисунок 3 демонстрирует применение предло-
женного подхода для определения корректности
5.1 Принцип работы оперативного детектора
объектов с двумерными векторами характеристик,
Быстродействующий компонент детектирующей но аналогичным образом может осуществляться
системы представляет собой бинарный классифика- классификация и в случае большей размерности
тор, который на основании значений параметров векторов. Однако с ростом размерности для форми-
документа делает вывод о его корректности или не- рования плотных областей требуется существенно
корректности. увеличивать обучающую выборку. Учитывая пред-
Такие популярные подходы к решению задачи полагаемые объемы наборов документов (десятки
бинарной классификации как нейронные сети [22], тысяч новостей), при использовании девяти харак-
опорные векторы [3], логистическая регрессия [10] теристик добиться высокой плотности при сохране-
могут быть использованы лишь при наличии обу- нии небольшого количества выделяемых зон невоз-
чающей выборки с большим количеством как пози- можно.
тивных, так и негативных примеров. Но при обуче- Таким образом, описанная в (1) модель доку-
нии оперативного детектора в большинстве случаев мента в виде 9-мерного вектора оказывается не-
получить такую выборку невозможно: количество удобной для непосредственного использования опе-
«хороших» документов при сборе новостей намного ративным детектором, поэтому в неё были внесены
больше числа «плохих». В некоторых случаях в изменения. Заменим девятимерный вектор X на на-
обучающей выборке может вообще не содержаться бор векторов меньшей размерности (Y1, Y2, … , Yk),
некорректных документов. Поэтому было решено каждый из которых содержит некоторое подмноже-
проводить обучение классификатора на позитивных ство элементов X. Будем выбирать этот набор векто-
примерах, но при этом его работа была организова- ров исходя из следующих соображений:
на следующим образом: в режиме проверки доку- нужно по возможности использовать векторы
ментов детектор должен считать корректными лишь наименьшей размерности (двумерные) для по-
статьи, похожие на элементы обучающей выборки. лучения максимальной плотности кластеров
Определим эту схожесть в терминах выбранной мо- нужно избегать использования векторов, кото-
дели документа. рые могут оказаться бесполезными для некото-
Каждый документ представлен девятимерным рых источников
вектором. Рассмотрим двумерную проекцию мно- Второй пункт относится, прежде всего, к харак-
жества таких векторов, соответствующих набору теристикам, отражающим количество html-
новостей с сайта kp.ru, на плоскость, задаваемую элементов, включенных в новость. Сайты обычно
параметрами N (количество параграфов в статье) и P применяют для оформления новостей лишь неболь-
(объем веб-страницы, содержащей статью) (рис. 3). шой набор тэгов, при этом некоторые группы html-
элементов могут не использоваться вовсе. Поэтому
только некоторые из параметров (TH,TB,TS,TI,TO) бу-
дут принимать ненулевые значения. Каждый сайт
использует собственный подход к оформлению но-
востей и выбору набора тэгов, что не позволяет оп-
ределить универсальный критерий полезности каж-
дой из этих характеристик и их совокупностей. По-
этому было решено все перечисленные величины
включить в пятимерный вектор Y1.
Каждый из оставшихся четырёх параметров яв-
ляется важной характеристикой структуры докумен-
Рис. 3. Распределение значений параметров N и P. та, поэтому в качестве элементов остальных векто-
Точки не распределены в пространстве равно- ров использовались все попарные сочетания вели-
мерно, они сгруппированы в некоторых областях. чин P,S,N и V. Так были получены 6 двумерных век-
Новый документ, поступающий на проверку, можно торов Y2, … ,Y7.
считать корректным, если соответствующая ему Таким образом, модель документа, подвергаю-
точка попадает в одну из таких областей. Если же щаяся обработке «оперативным детектором», пред-
точка находится в отдалении от этих зон (как, на- ставляет собой совокупность из следующих семи
пример, три точки в правой верхней части рисунка, случайных векторов:
помеченные крестиком), то соответствующая статья
является подозрительной.
(5)
90
5.2 Кластеризация документов варьировании размеров кластеров. Этот метод от-
вечает требованиям к виду формируемых класте-
Выделение областей необходимо производить ров, однако он имеет серьезный недостаток, харак-
таким образом, чтобы максимально облегчить по- терный для всех иерархических методов – высокая
следующую проверку принадлежности точек этим вычислительная сложность (O(n2)). Тем не менее, в
областям. Поэтому нет смысла выбирать зоны данной работе за основу был взят этот метод, в ко-
сложной формы – более эффективным решением торый были внесены следующие модификации.
является нахождение плотных групп точек и по- Ограничим число элементов, подвергающихся
строение простых ограничивающих поверхностей кластеризации методом средней связи, числом
для этих групп. Для разбиения всего множества до- n.Тогда кластеризация N элементов (N>n) будет
кументов из обучающей выборки на группы нужно осуществляться следующим образом.
решить задачу кластеризации. Существует множе-
ство подходов к кластерному анализу, и применение 1. Выбрать из множества документов n элементов.
различных алгоритмов к одним и тем же входным 2. Произвести кластеризацию этих элементов мето-
данным может дать совершенно разные результаты дом средней связи.
[21,18]. Основным требованием, определяющим 3. Найти центроиды кластеров.
пригодность метода для кластеризации новостей, 4. Поместить центроиды в множество точек в каче-
является простая, гиперсферическая форма класте- стве новых элементов.
ров, позволяющая получить с помощью простых 5. Повторять пункты 1-4 пока в множестве не оста-
ограничивающих поверхностей плотные области без нется необходимое число элементов.
разреженных участков. 6. Определить принадлежность исходных элементов
найденным кластерам.
Одним из наиболее популярных методов кла- Для простоты будем считать, что при кластери-
стеризации является k-means – итеративный метод зации всегда выделяется одинаковое число класте-
кластерного анализа, основная идея которого за- ров k. Найдём значение n, обеспечивающее мини-
ключается в минимизации суммарного квадратично- мальную вычислительную сложность алгоритма.
го отклонения точек кластеров от центроидов этих При каждой итерации из множества удаляется n
кластеров [4,15]. Несмотря на низкую вычислитель- элементов и вместо них туда помещается k новых,
ную сложность метод имеет существенный недоста- то есть число элементов уменьшается на (n-k). Зада-
ток, связанный со спецификой обрабатываемых де- чей алгоритма является замена N исходных элемен-
тектором данных. Некоторые из отдаленных точек – тов на k центроидов кластеров, то есть уменьшение
«выбросов» являются, всё же, корректными статья- числа элементов на (N-k). Поэтому выполнение кла-
ми, которые должны быть учтены при кластериза-
ции. Для достижения минимальной разреженности стеризации n объектов нужно произвести раз,
такие точки должны быть по возможности помеще- и сложность алгоритма равна . Функция
ны в отдельные кластеры. Однако этого сложно до-
биться с k-means, поскольку этот метод имеет тен- имеет минимум при n=2k. Таким
денцию к выделению кластеров схожего размера. образом, на каждой итерации кластеризации выпол-
Также широко распространены алгоритмы, ис- няется замена старых 2k элементов на новые k эле-
пользующие иерархический подход к кластеризации ментов. Результат кластеризации, произведенной
[19]. Они делятся на агломеративные (объединяю- описанным способом при k=10, приведён на рис. 4.
щие объекты в множества) и дивизимные (разде-
ляющие единое множество объектов на подмноже-
ства). При этом есть возможность выбора любого
количества кластеров после осуществления класте-
ризации. Иерархические методы различаются по
принципу определения двух ближайших кластеров
[17]. Существует несколько подходов:
Метод одиночной связи хорошо справляется с
проблемой выбросов, но имеет тенденцию к обра-
зованию кластеров в виде длинных цепочек эле-
ментов. Такой подход эффективен в случае, когда
кластеры имеют вытянутую или необычную фор-
му, но для решения рассматриваемой задачи он Рис. 4. Ограничивающие поверхности кластеров
неприменим. В качестве ограничивающих поверхностей для
Метод полной связи склонен к выделению класте- областей рассматривались гиперпараллелепипед,
ров приблизительно равных размеров, что может гиперсфера и гиперэллипсоид. Выбор был сделан в
приводить к появлению небольших разреженных пользу наиболее простых в построении гиперпарал-
кластеров вместо плотных, но крупных. лелепипедов, показавших хорошие результаты при
Метод средней связи имеет склонность к образо- оценке плотности точек. Таким образом, каждый
ванию гиперсферических кластеров, кроме того, кластер задается набором пар ( , ), опреде-
он даёт хороший результат при значительном ляющих граничные значения соответствующего
гиперпараллелепипеда по параметру Z. Элемент
91
принадлежит кластеру, если для каждого параметра
Z выполняется , где z – значение
параметра Z для рассматриваемого элемента. При
классификации документ считается подозритель-
ным, если он не попадает ни в один из кластеров.
Кластеризация и построение ограничивающих Рис. 5. Гистограммы выборок.
поверхностей и последующая классификация загру- Для оценивания сходства выборок используется
жаемых документов производятся отдельно для ка- относительная энтропия (расстояние Кульбака–
ждого из семи выделенных векторов (5). Таким об- Лейблера, KLIC[6]). Для дискретных случайных
разом, результатом классификации является набор величин с функциями вероятности p и q, прини-
из семи двоичных значений. Возможны различные мающих значения в одном множестве , это
подходы к принятию решения о корректности доку- расстояние задается формулой
мента на основании этого набора. Например, статья
может считаться корректной, если она успешно (6)
прошла проверку не менее чем по k критериям из Вместо функций вероятности используются час-
семи, где k–некоторое заданное значение. В разра- тоты рядов (4). При этом p(x) соответствует эталон-
ботанной системе используется наиболее строгий ной выборке, а q(x) – проверяемой.
подход с параметром k=7.
Результатом расчёта KLIC для рядов (4) являют-
6 Отложенный детектор ся значения DP, DS, DN, DV, и DT соответственно.
После расчёта расстояния Кульбака – Лейблера
Второй компонент системы обнаружения сбоев встаёт вопрос: как по найденному значению опреде-
осуществляет оценку набора документов. Оценка лить, произошел сбой или нет? Необходимо задать
осуществляется на основе статистических рядов (4), некоторое пороговое значение K, такое, что наличие
которые можно рассматривать как приближения к сбоя можно определить как
функциям вероятности соответствующих случайных
величин. Идея, лежащая в основе функционирова- (7)
ния отложенного детектора, заключается в следую-
щем: рассматриваемые нами случайные величины, Данный порог не является фиксированной вели-
составляющие вектор (1), подчиняются некоторым чиной, его значение зависит от числа документов в
законам распределения, которые при отсутствии тестовой выборке. Поясним это утверждение на
сбоя остаются неизменными. Изменение же вёрстки примере. Выберем множество наборов до-
с высокой вероятностью повлияет на эти законы кументов различной мощности и вычислим для
распределения. Следовательно, две разных выборки, каждого из них расстояние Кульбака – Лейбле-
состоящие из корректных документов, будут обла- ра от эталонного закона распределения. Сопоста-
дать высокой степенью сходства. Если же одна из вим натуральным числам j, соответствующим мощ-
них будет содержать «плохие» статьи, то различие ностям наборов из множества , числа Kj,
между выборками будет значительно сильнее. Та- определяемые как
ким образом, задача детектора заключается в опре- (8)
делении степени сходства проверяемой выборки и
выборки, состоящей из гарантированно корректных Рассмотрим зависимость максимального рас-
статей, сформированной в процессе обучения (назо- стояния Кульбака – Лейблера от мощности набора.
вём её эталонной). На основе полученного результа- На рис. 6 приведена зависимость для новостей с
та принимается решение о наличии/отсутствии сбоя. kp.ru.
Для примера рассмотрим три выборки случай-
ной величины S (суммарный размер параграфов ста-
тьи), соответствующие наборам новостей с сайта
lenta.ru: эталонную (а); тестовую выборку, состоя-
щую из «хороших» документов (б) и тестовую вы-
борку, содержащую некорректные статьи (в). В ка-
честве последних использовались новости с сайта
cnews.ru.
На рис. 5 показаны гистограммы, соответствую-
щие этим выборкам. Первые две из них обладают
высокой степенью сходства, в то время как третья
значительно от них отличается. Рис. 6. Зависимость максимального значения
KLIC от мощности набора
При этом использовалась оценка характеристики
P, отражающей объем веб-страницы, но аналогичная
зависимость имеет место и для других характери-
стик. При построении зависимости значения j выби-
92
рались равномерно в пределах от 0 до размера обу- ция имеет недостаток: МНК одинаково учитывает
чающей выборки. Наиболее точные результаты мо- отклонение вычисленных данных от эксперимен-
гут быть получены, если в качестве наборов с мощ- тальных для всех узлов аппроксимации. Однако
ностью j рассматривать все возможные j- значения функции в точках с наименьшими и наи-
элементные подмножества документов обучающей большими значениями аргументов могут отличаться
выборки, однако эта задача имеет неполиномиаль- в тысячи раз, и отклонение, несущественное для
ную сложность, поэтому полный перебор возмож- одних узлов, будет недопустимым для других. Это
ных комбинаций элементов был заменен анализом может привести к значительному снижению точно-
наборов, состоящих из j последовательных элемен- сти на больших наборах документов и увеличению
тов выборки. Количество таких наборов равно r-j+1, частоты ложных срабатываний. Для минимизации
где r – размер выборки. числа ложных срабатываний было решено подверг-
Такой вид зависимости легко объясним: чем нуть функцию преобразованию, которое бы обеспе-
больше выборка, тем меньше на неё влияют локаль- чило выполнение условия для всех узлов.
ные колебания значений параметров. Таким обра- Для этого определим величину Δ:
зом, при выборе порогового значения необходимо (10)
учитывать мощность анализируемого набора. Для
этого необходимо определить пороговую функцию Увеличим коэффициент a0 на значение Δ. Те-
K=h(x), устанавливающую соответствие между ко- перь график пороговой функции лежит не ниже всех
личеством документов в наборе и пороговым значе- точек, использованных для аппроксимации. На ри-
нием для этого набора. Для приведенных выше чи- сунке 7 приведены графики пороговой функции до
сел j значение h(j) должно быть максимально близко (пунктирная линия) и после (сплошная линия) кор-
к Kj. Действительно: если h(j)