Автореферат (Модели, алгоритмы и программные средства бикластеризации на основе замкнутых множеств), страница 5

Ниже приведено описание математической модели задачи.Исходный массив данных описывается формальным контекстом K =(, , ), (от firms) — множество компаний-рекламодателей, а (от term)— множество рекламных словосочетаний, — отношение инцидентности, показывающее, что фирма ∈ купила словосочетание ∈ тогда и толькотогда, когда .Для решения задачи мы последовательно применяли следующие подходы:стемы Интернет-рекламы.1. отбор по размеру объема и содержания понятий и объектнопризнаковую бикластеризацию для выявления крупных рынков средствами АФП;2.

поиск ассоциативных правил для построения рекомендаций;3. построение ассоциативных метаправил с помощью морфологическогоанализа;4. построение ассоциативных метаправил с помощью онтологий (тематического каталога).Опишем кратко предложенную нами модель формирования рекомендаций на основе ассоциативных метаправил с помощью морфологического анализа. Рассмотрим в качестве дополнительного знания имеющееся признаковое17пространство, а именно тот факт, что каждый признак является словом илисловосочетанием. Вполне очевидно, что синонимичные словосочетания принадлежат к одному сегменту рынка. Конечно, в штате компаний, занимающихся контекстной рекламой, существуют тематические каталоги, составленныеэкспертами, но ввиду большого количества рекламных слов (несколько тысяч)наполнение каталога “вручную” является сложной задачей.Для построения тематического каталога рекламных словосочетаний могут потребоваться словари синонимов, а учитывая тот факт, что такие словосочетания не всегда слова или сочетания двух слов, такие словари редки.Поэтому в качестве первого приближения для решения такой задачи можноиспользовать стемминг, или выделение основы слова.

Опишем последовательность действий при извлечении знаний с помощью стемминга.Пусть - некое рекламное словосочетание. Представим его в виде множества слов его образующих = {1 , 2 , . . . , }. Основу слова обозначим через = (⋃︀ ), тогда множество основ словосочетания обозначим через () =( ).

Построим формальный контекст K =(, , ), где — множество всех⋃︀словосочетаний, а — множество основвсех словосочетаний из , т.е. = ( ). Тогда будет означать, чтово множество основ словосочетания входит основа .Построим по такому контексту правила вида → для всех ∈ .Тогда такому метаправилу контекста K соответствует −−→ — ассоциативное правило контекста K . Если величина поддержки и достоверноститакого правила в контексте K превышают некоторые пороговые значения,то можно считать ассоциативные правила, построенные по контексту K , нестоль интересными (их можно вывести из описания признаков).В качестве более крупных метаправил мы предлагаем следующие две ⋃︀ возможности.

Во-первых, можно искать правила вида −−→ , т.е. правила, в правую часть которых входят все термы, имеющие хотя бы одно одно⋃︀коренное слово с исходным термом. Во-вторых, правила вида −−→ ( ) ,т.е. правила, термы в правой части которых содержат в своем составе те жеосновы, что и исходный. Довольно очевидно, что первый тип правил можетпривести к объединению различных словосочетаний, например “black jack” —игровой бизнес и “black coat” — одежда. Такое объединение произошло благодаря наличию общего слова “black”.

А второй тип правил относится к болеередким зависимостям, например, { } → { }.Поэтому меры поддержки и достоверности при построении простых метаправил должны служить их мерой пригодности для дальнейшего использования.Мы предлагаем также использовать метаправила вида 1 −−→ 2 , такие что 2 ⊆ 1 . Такие правила имеют простую интерпретацию, из словосочетания2 следует словосочетание множество основ которого вкладывается в множество основ 1 , например, { } → {}, = 14, а = 0, 7.Для указанных выше задач автором предложены методики оценки ка-18чества поиска, основанные на мерах качества, применяемых в информационном поиске (точность, полнота, F-мера), разработке данных (поддержка) всочетании с техниками оценки качества из машинного обучения, такими какскользящий контроль.В третьей главе устанавливается связь между методами поиска ассоциативных правил и бикластеризацией.

Выявляется эквивалентность определения бикластера для исследования данных генной экспрессии и формальногопонятия в АФП. Предлагается новый алгоритм бикластеризации на основеобъектных и признаковых замыканий.Рассмотрим алгоритм для предложенного нами определения бикластера. Предварительно введем определения объектного и признакового понятия.Объектным понятием формального контекста K = (, , ) называется формальное понятие вида ( ′′ , ′ ), где ∈ , а признаковым понятиемформального контекста K = (, , ) называется формальное понятие вида(′ , ′′ ), где ∈ .Для краткости записи будем писать ′′ и ′ вместо {}′′ и {}′ соответственно, аналогично поступим с записью оператора Галуа на признаках.Обозначим множество всех объектных понятий формального контекста K =(, , ) как = {( ′′ , ′ )|∀ ∈ }, а множество всех признаковых понятийкак = {(′ , ′′ )|∀ ∈ }.Для формального контекста K = (, , ) и любой пары объектных ипризнаковых понятий ( ′′ , ′ ) ∈ и (′ , ′′ ) ∈ , связанных отношением вложения ( ′′ , ′ ) ≤ (′ , ′′ ), назовем объектно-признаковым бикластером′ ′(оп-бикластером) пару вида ( , ).g'mm'gg''m''Рис.

1. Бикластер на основе объектных и признаковых замыканий19Требование вложения объектного понятия ( ′′ , ′ ) в признаковое (′ , ′′ ) объясняется тем фактом, что объектные понятия имеют самые большие по размеру содержания (среди других понятий, имеющих в объеме объект , кроме,быть может, верхнего понятия в решетке), а признаковые – самые большиеобъемы (среди других понятий, имеющих в содержании признак , кроме,быть может, нижнего понятия в решетке).Плотностью бикластера (, ) формального контекста K = (, , )|∩×|назовем величину (, ) = |||| .Свойство 1.1.

Если (′ , ′ ) oп-бикластер, то ( ′′ , ′ ) ≤ (′ , ′′ ).2. Для произвольного бикластера (, ) справедливо соотношение 0 ≤ ≤ 1.3. Пусть (, ) – формальное понятие, тогда (, ) = 1Пусть дан бикластер (, ) ∈ 2 × 2 и положительное целое число , такое что 0 ≤ ≤ 1 , тогда (, ) называется плотным в том и только том случае, когда он удовлетворяет ограничению ( , (, )) ≡((, ) ≥ )Ограничение ( , (, )) ≡ ((, ) ≥ ) не является ни монотонным, ни антимонотонным.Свойство 2.Пусть = 0, тогда верноДля любого формального понятия ( , )B(, , ) существует ( , ) ∈ B, такой что ( , ) ⊑ ( , ).Утверждение1.∈Тот факт, что оп-бикластер представим в виде (′ , ′ ) наводит на мысль о том,что возможно избежать дорогостоящего вычисления оператора замыкания –(.)′′ (в худшем случае (||| |)).

Поэтому автором предложен алгоритм,который является улучшенной версией действующего по определению “наивного” алгоритма, и использует свойство антимонотонности оператора (.)′ дляоптимизации. Доказано утверждение об эквивалентности выходов этих алгоритмов.При достаточно больших значениях не все формальные понятиямогут оказаться вложенными в некоторый бикластер, построенный по формальному контексту K = (, , ).При некотором > 0 существует K = (, , ),такой что существует формальное понятие ( , ) ∈ B(, , ), длякоторого верно, что не существует бикластера ( , ) ∈ B, такого что( , ) ⊑ ( , ).Утверждение 2.Оценим теоретически ресурсную временную и емкостную сложность алгоритма 1.Число объектно-признаковых бикластеров контекста может быть гораздо меньше числа формальных понятий (в худшем случае экспоненциальноеколичество от размера || + | |), что подтверждается следующими утверждениями.20Улучшенный алгоритм поиска бикластеровData: = (, , ) – формальный контекст, – порог назначение плотности оп-бикластераResult: = {( , )|( , ) – оп-бикластер}Algorithm 1:123456789101112begin.

= ||. = | | ←− ∅for ∈ do[] = ′for ∈ do[] = ′for ← 0 to || dofor ∈ [] doif ([], []) ≥ then.(([], []))Для данного формального контекста K = (, , ) и = 0 наибольшее число оп-бикластеров равно ||, а все оп-бикластерыпорождаются за время (|| · (|| + | |)).Утверждение 3.Для данного формального контекста K = (, , ) и > 0 наибольшее число оп-бикластеров равно ||, а все оп-бикластерыпорождаются за время (|| · || · | |).Утверждение 4.В четвёртой главе предлагаемые модели и методы бикластеризации использовались в серии экспериментов в нескольких предметных областях.В качестве экспериментального материала нами использовалась URLколлекция РОМИП, состоящая из 52 файлов, общего размера 4,04 Гб. Дляпроведения экспериментов коллекция разбивалась на несколько частей, включающих от трех до двадцати четырех файлов (приблизительно от 5% до 50%от размера всей коллекции).