Метод обнаружения изменений структуры веб-сайтов в системе сбора новостной информации © А.М. Андреев © Д.В. Березкин © И.А. Козлов © К.В. Симаков МГТУ им. Н.Э. Баумана, г. Москва 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)