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

Именно это свойство используется для определения замкнутости в методах Data Mining. Множество ⊆ называется -частым, если | ′ | > (то есть множество признаков B встречается в более чем объектах), где — параметр. Фактическимы будем вычислять частные замкнутые множества признаков для дуальногок K контекста, т.е. находить такие множества документов-признаков контекста K = (, , ), для которых размер множества их общих шингловпревышает заданный порог сходства. Хотя теоретически размер множествавсех замкнутых множеств признаков (содержаний) может быть экспоненциальным относительно числа признаков, на практике таблицы данных сильно“разрежены” (то есть среднее число признаков на один объект весьма мало) ичисло замкнутых множеств невелико. Для таких случаев существуют весьмаэффективные алгоритмы построения всех наиболее частых замкнутых множеств признаков (см.

также обзор по алгоритмам построения всех замкнутыхмножеств [Kuznetsov, 2002]). В последние годы проводился ряд соревнованийпо быстродействию таких алгоритмов на серии международных семинаров14под общим названием FIMI (Frequent Itemset Mining Implementations). Однимиз лидеров по быстродействию считается алгоритм FPmax* [Grahne, 2003],показавший наилучшие результаты по быстродействию в соревновании 2003года. Мы использовали этот алгоритм для построения сходства документов икластеров сходных документов.С момента создания сайта для его владельцев и возможно потенциальных рекламодателейвстает вопрос учета количества посещений с целью определения популярности ресурса и выявления целевой аудитории.

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

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

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

Ей будет в точности соответствовать решетка формальныx понятий, построенная по такому контексту K = (, , ),где – множество всех посетителей целевого сайта, – множество всехсайтов выборки исключая целевой, – отношение инцидентности , имеющее место для ∈ , ∈ , тогда и только тогда, когда посетитель “ходил” на сайт . Под “внутренней” таксономией будем понимать иерархическую структуру аудитории целевого сайта, построенную по данным посещенийего собственных страниц (возможно, сгруппированных по разделам). Соответствующий контекст определяется сходным образом K = (, , ), где – множество всех посетителей целевого сайта, – множество всех собственных страниц целевого сайта, — отношение инцидентности , имеющее место для ∈ , ∈ , тогда и только тогда, когда посетитель “ходил” на сайт . Понятию такого контекста соответствует пара (, ), такая что ′ = { множество сайтов ∈ , которые посещали все посетители15 ∈ } = , а ′ = {множество посетителей ∈ , которые посещали всесайты ∈ } = .Остановимся подробнее на понятии индекса устойчивости формальногопонятия, предложенного в работах С.О.

Кузнецова, который мы используемдля отбора интересных групп посетителей при построении таксономий. Индексустойчивости ФП служит показателем независимости содержания от частныхобъектов объема (наличие которых в контексте зависит от случайных факторов).Пусть K = (, , ) — формальный контекст, (, ) – некоторое формальное понятие , тогда индекс устойчивости понятия (, ) определяется выражением|{ ⊆ | ′ = }|.(, ) =2||Очевидно, что 0 ≤ (, ) ≤ 1.Даже если описание данных зашумлено, то понятия с индексом устойчивости близким к 1, вероятно, объективно отражают реальное положениедел.

Индекс устойчивости показывает, насколько стабильны интересы групппосетителей, даже если некоторые из них более не активны.Пусть (, ) – некоторое ФП контекста K = (, , ), его поддержка||определяется выражением (, ) = || , и дано минимальное значениеподдержки ∈ [0, 1], тогда решеткой-айсбергом назовем множество{(, )|() ≥ }.Использование решеток-айсбергов позволяет выявлять крупные понятия, соответствующие аудиториям наиболее посещаемых сайтов. К сожалению, размер аудитории не гарантирует того, что данная аудитория возниклане в результате влияния шума.

Поэтому мы исследовали и некоторые другиекритерии отбора релевантных ФП, например, минимальные разрезы из теории графов. Применение таких критериев возможно потому, что формальномуконтексту K = (, , ) соответствует неориентированный двудольный графΓ = ( ∪ , ), где для ∈ и ∈ выполнено {, } ∈ ⇔ .Формальному понятию (, ) контекста K будет соответствовать биклика, двудольного графа Γ. В этом случае разрезом для формального понятия (, ) будет число ребер графа Γ, имеющих одну вершину в или , адругую в ∖ или ∖ соответственно.Для формального контекста K = (, , ) разрез ФП (, ) определяется выражением⋃︁⋃︁(, ) = |( ′ ) ∖ | + |(′ ) ∖ |.∈∈Такой индекс показывает степень связи объектов и признаков ФПс другими признаками и объектами контекста.

Если говорить в терминах“пользователи-сайты”, то чем меньше значение для некоторого понятия,тем легче отделить аудиторию (объем понятия) от пользователей других сай-16тов, не входящих в содержание этого понятия. Аналогично, легче выделитьтематику сайтов, предпочитаемую этой аудиторией, как вполне самостоятельную, т.к. меньшее количество людей с другими интересами их посещает.Формирование бикластеров и рекомендаций для рекомендательной си-Одна из разновидностей электронной коммерции— контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама.

Для России репрезентативнымипримерами служат рекламные Интернет-сервисы “Яндекс.Директ” и “Бегун”.Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставленияпользователю наиболее интересной ему поисковой рекламы, наша задача —выявление рекламных слов, которые могут быть интересны рекламодателю.Предположим, что некая фирма приобрела ряд рекламных слов, которыеописывают предоставляемые услуги. Как правило, на рынке уже существуюткомпании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они.

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