Содержание к диссертации
Введение
1 Кластеризация и бикластеризация 16
1.1 Постановка задачи и основные определения 16
1.2 Типы данных 19
1.3 Типы бикластеров 19
1.4 Структура бикластеров 20
1.5 Алгоритмические стратегии поиска 21
1.6 Классификация методов бикластеризации 22
1.7 Программные средства бикластеризации 46
1.8 Прикладные задачи 49
1.9 Обсуждение 53
2 Прикладные задачи и их вычислительные модели 56
2.1 Поиск сходства текстовых документов с помощью частых замкнутых множеств признаков 56
2.1.1 Постановка задачи 56
2.1.2 Описание вычислительной модели 58
2.1.3 Методика оценки качества поиска 63
2.2 Анализ данных о посещаемости сайтов с помощью АФП 63
2.2.1 Постановка задачи и математическая модель 64
2.2.1.1 Пути решения и возникающие проблемы 65
2.2.1.2 Критерии отбора шумоустойчивых и релевантных понятиий 66
2.2.2 Методика оценки качества шумоустойчивых свойств способов отбора релевантных понятий 70
2.3 Формирование бикластеров для рекомендательной системы Интернет-рекламы 72
3 Разработка и исследование методов и алгоритмов бикластеризации на основе замкнутых множеств и их программная реализация 78
3.1 Ассоциативные правила в контексте бикластеризации 78 -
3.1.1 Ассоциативные правила: общий взгляд 78
3.1.2 Связь ассоциативных правил и бикластеризации 79
3.2 Связь опеределения бикластера в моделях бикластеризации для задач генной экспрессии и АФП 81
3.3 Алгоритм бикластеризации на основе объектных и признаковых замыканий 82
3.4 Эмпирический анализ эффективности алгоритма бикластеризации на основе объектных и признаковых замыканий 91
4 Машинные эксперименты и результаты 95
4.1 Поиск сходства Интернет-документов с помощью частых замкнутых
множеств признаков 95
4.1.1 Программная реализация и компьютерные эксперименты 98
4.1.1.1 Оценка результатов с точки зрения полноты и точности поиска 107
4.1.1.2 Сравнение результатов работы метода FPmax с результатами, полученными с помощью системы Cluto 108
4.1.2 Выводы и направления дальнейшей работы 112
4.2 Разработка и апробация системы поиска дубликатов в текстах проектной документации 113
4.2.1 Постановка задачи и актуальность 113
4.2.2 Описание системы 114
4.2.3 Методы поиска дубликатов 115
4.2.4 Реализация поиска дубликатов в системе 119
4.2.4.1 Проведение анализа документов в Системе 120
4.2.5 Подбор параметров и тестирование 121
4.2.6 Направления дальнейшей работы 124
4.3 Построение таксономии групп посетителей сайтов с помощью АФП . 126
4.3.1 Построение таксономии аудиторий веб-сайтов 126
4.3.2 Исследование шумоустойчивых свойств индексов отбора релевантных понятий 127
4.3.3 Выводы 131
4.4 Формирование бикластеров для рекомендательной системы Интернет-рекламы 133
Заключение 141
Литература 143
- Классификация методов бикластеризации
- Критерии отбора шумоустойчивых и релевантных понятиий
- Алгоритм бикластеризации на основе объектных и признаковых замыканий
- Сравнение результатов работы метода FPmax с результатами, полученными с помощью системы Cluto
Введение к работе
Актуальность работы. Существует широкий спектр задач, в которых требуется выявлять кластеры с сохранением объектно-признакового описания данных: выявление групп генов, обладающих общими свойствами; поиск групп посетителей со схожими интересами для рекомендательных систем; выявление сообществ; анализ социальных сетей; автоматическое построение каталогов и рубрикаторов в информационных системах; поиск сходства документов.
При решении подобных задач классический кластерный анализ не предоставляет удобных средств, позволяющих сохранить объектно-признаковое описание кластера. Например, исследователю-биоинформатику требуется выявлять не столько числовое сходство генов, сколько их общие свойства, т.е. то, благодаря чему они были признаны сходными. Подход к разрешению данной проблемы получил название "бикластеризации".
Бикластеризация позволяет отыскивать "бикластеры", включающие, помимо множества объектов, множество их общих признаков (как вещественных и бинарных, так и качественных). Например, для данных генной экспрессии первым компонентом такого кластера является множество генов, а вторым -множество экспериментов в которых они проявляли себя сходным образом. Термин "бикластеризация" впервые упомянут в работе Миркина Б.Г. в 1996 г. Хотя похожие формулировки и методы встречались ранее (например, в работах J.A. Hartigan'a), мы будем использовать это оригинальное название для всей группы методов, которые применяются для построения таких двукомпо-нентных кластеров.
В анализе данных в начале 80-х годов с появлением работ Р. Вилле возникло прикладное алгебраическое направление Анализ Формальных Понятий (АФП), предоставляющий решеточные модели бикластеризации особого вида, позволяющие сохранять объектно-признаковое описание сходства группы объектов внутри кластера и, кроме того, строить иерархии таких кластеров по отношению "быть более общим, чем". Построение таких иерархий дает дополнительные преимущества аналитику, такие как визуализация, эффективный поиск, использование их таксономических свойств и др. В рамках этой области сформулировано математическое определение формального понятия (ФП) и описано построение иерархий ФП. Исходно ФП является парой вида (объем, содержание), где под объемом понимается некоторое множество объектов, а под содержанием — множество их общих признаков. Как видим, это определение напоминает описание бикластера. Исходные данные в АФП представляются в виде объектно-признаковой матрицы, состоящей из нулей и единиц, а ФП является максимальный прямоугольник (с точностью до перестановок столбцов и строк) такой матрицы, заполненный единицами. Это означает, что данное подмножество объектов обладает всеми признаками некоторого подмножества признаков. Множество всех ФП упорядоченно и образует полную решетку, называемую "решеткой формальных понятий".
Существует ряд работ, исследующих возможности "ослабления" требований к определению формального понятия, например, шумоустойчивые поня-
тия (в смысле работ J.-F. Boulicaut). Необходимость такого рода ослаблений вызвана излишне жёсткой структурой ФП, требующей наличия всех признаков из содержания понятия у всех объектов его объема. Однако в случае наличия шума возможны "выпадения" некоторых признаков из содержания понятия. В работах R. Belohlavek'a предложен подход, использующий нечеткие решетки понятий, в котором значения исходных данных лежат в диапазоне [О, 1]. Причина, по которой целесообразно использование нечетких решеток, — возможность передачи вероятностого характера описания исходных данных, например, частоты посещения пользователем веб-сайта. Еще одним желательным требованием является сокращение числа таких бикластеров, т.к. в случае использования АФП их количество растет экспоненциально относительно размера входа. Отчасти проблема порождения большого числа ФП решена путем введения индекса устойчивости формального понятия в работах Кузнецова СО. В этом случае среди множества порожденных ФП отбираются такие, для которых индекс устойчивости превышает некоторый порог. Проблемы отбора релевантных задаче ФП (бикластеров) также обсуждаются в рамках данной работы. Что касается моделей "бокс-кластеризации", описанных Миркиным Б.Г., и шумоустойчивых понятий, то для них характерно наличие сходного подхода. Этот подход допускает наличие перекрытий или пересечений бикластеров, степень которых оказывается существенной при решении ряда задач. В задачах бикластеризации, решаемых в биоинформатике (см. работы S. Barkow'a и др.), используется похожий аппарат, но значения входной матрицы не всегда являются булевыми (в большинстве случаев они положительные вещественные, как в методе OPSM (A. Ben-Dor и др.). Это, в свою очередь, приводит к использованию статистических свойств данных при построении моделей (см. работы А. Тапау и др.). У большинства из этих методов, применяемых в биоинформатике, имеются схожие недостатки: проблема определения числа кластеров, проблема локального оптимума вследствие использования жадной стратегии поиска (см. работы Y. Cheng'a и G.M. Curch'a) др. Особняком стоят методы спектральной кластеризации, которые изначально опираются на спектральные свойства матричного представления графа связей между объектами. В последнее время эти методы активно применяются в Интернет-маркетинге, где связи "рекламодатели-ключевые слова" представлены двудольным графом (например, работы Жукова Л.Е.), и помогают отыскивать потенциальных рекламодателей среди тех, кто не использует некоторые из слов, которые купили их конкуренты. Фактически эти методы искусственно адаптированы для задач бикластеризации, поскольку для найденных кластеров приходится восстанавливать их объектно-признаковую структуру.
Для большинства методов, разработанных вне сообщества АФП, характерно отсутствие иерархии порожденных кластеров, что затрудняет их анализ исследователем. В рамках работы предпринята попытка установить возможность построения для остальных методов бикластеризации такой иерархии, которая носит решеточный характер. Также исследователями в области бикластеризации не используется аппарат ассоциативных правил, являющийся ключевыми в Data Mining при поиске признаковых зависимостей. Ассоциа-
тивные правила можно порождать как на признаковых описаниях бикласте-ров, так и на объектных. Помимо исследователей, использующих аппарат ассоциативных правил в Data Mining, существует сообщество FIMI (Frequent Itemset Mining Implementation), изучающее проблемы поиска частых (замкнутых) множеств признаков в больших базах данных. Отметим, что замкнутые множества признаков являются в точности содержаниями ФП. Поэтому методы FIMI включены в обзор как модель бикластеризации. Поскольку максимальные замкнутые множества признаков составляют только часть замкнутых, постольку их поиск можно рассматривать в качестве альтернативы способам сокращения числа ФП для модели АФП. Другим способом сокращения является использование решеток-айсбергов, предложенных в работах G. Stumme.
Таким образом разработка моделей, методов и эффективных программных средств бикластеризации на основе замкнутых множеств признаков является актуальной и значимой задачей.
Объектом исследования являются модели бикластеризации на основе замкнутых множеств для решения различных задач анализа данных, в которых возможен переход к объектно-признаковому описанию данных.
Предметом исследования являются методы, эффективные алгоритмы и программные средства бикластеризации на основе замкнутых множеств для решения различных задач анализа объектно-признаковых данных.
Цели исследования.
Выявление взаимосвязи существующих моделей и методов бикластеризации, построение их классификации и таксономии.
Разработка оригинальных моделей, методов и алгоритмов бикластеризации на основе решеток замкнутых множеств.
Программная реализация эффективных алгоритмов поиска бикластеров для решения практических задач анализа данных.
Задачи работы. В соответствии с целями диссертационной работы решались (исследовались) следующие задачи.
Анализ существующих подходов кластеризации и бикластеризации.
Построение классификации различных моделей и методов бикластеризации, родственных решеточным, изучение их взаимосвязи.
Разработка оригинальной математической модели и метода бикластеризации на основе решеток замкнутых множеств.
Разработка алгоритмов и программных модулей бикластеризации на основе предложенной модели и метода.
Проведение анализа особенностей разработанного подхода на примере решения задач анализа Интернет-данных (поиск сходства документов, исследование посещаемости сайтов и разработка рекомендательных систем).
б. Разработка методики оценки качества полученных решений в терминах полноты и точности информационного поиска, а также на основе подхода к такой оценке в задачах машинного обучения.
Методы исследования. В диссертации используются методы теории упорядоченных множеств и решеток, анализа формальных понятий,теории графов, математической статистики, разработки данных (Data Mining), машинного обучения и информационного поиска.
Научная новизна работы определяется полученными в ходе решения задач исследования новыми результатами.
Предложены оригинальная математическая модель и метод бикластеризации на основе объектных и признаковых замкнутых множеств, позволяющие сохранить объектно-признаковое описание бикластеров не "потеряв" (в смысле отношения вложения Ц) при этом формальные понятия, построенные по входным данным. Исследованы его полезные свойства, сформулированы и доказаны соответствующие утверждения. Приведена теоретическая оценка сложности алгоритма по времени выполнения и оценен размер выхода.
Впервые формально описана связь между бикластерами и ассоциативными правилами. Даны теоретические оценки мер плотности и разреженности бикластеров, получаемых на основе ассоциативных правил. Выявлена эквивалентность определений бикластера в некоторых методах бикластеризации из биоинформатики и АФП.
Предложена математематическая модель сходства текстовых документов, сформулированная в терминах частых замкнутых множеств признаков и АФП.
Предложена математическая модель построения таксономии групп пользователей веб-сайтов на основе решеток формальных понятий. Указаны наилучшие способы отбора релевантных формальных понятий для построения таких таксономии.
Предложена математическая модель рекомендательной системы на основе использования морфологической структуры словосочетаний (признакового пространтсва). Предложена модель рекомендательной системы на основе бикластеризации и метода ближайшего соседа, а также методика оценки качества результатов таких систем.
Теоретическая значимость работы заключается в 1) установлении взаимосвязей существующих моделей бикластеризации, методов анализа данных на основе теории решеток и поиском ассоциативных правил; 2) построении таксономии существующих методов бикластеризации и её расширении путем включения критериев классификации новых и родственных методов; 3) разработке модели бикластеризации на основе замкнутых множеств объектов и признаков, теоретическом исследовании ее свойств.
Практическая значимость работы состоит в разработке эффективных моделей и методов поиска документов-дубликатов, построения таксономии веб-пользователей и моделей и методов рекомендательных систем на основе бикластеризации. Важным практическим достижением является создание программной реализации метода построения бикластеров, предложенного автором. Количество таких бикластеров сравнимо с числом пар во входной объектно-признаковой таблице, что существенно меньше теоретической оценки размера соответствующей решетки понятий. Два успешных внедрения предложенных методов позволяют говорить о востребованности и пользе полученных результатов. Компания "Спайлог" применяет в задаче исследования аудитории целевого веб-сайта предложенные в работе методы построения решеточных таксономии, а компания "Кварта-ВК" успешно реализовала проект по разработке системы поиска документов-дубликатов в текстах проектной документации на основе предложенного в диссертационной работе подхода и методики настройки и оценки качества такого поиска. Также результаты исследований внедрены и используются автором в учебном процессе при проведении практических и лекционных занятий по анализу данных на факультете бизнес-информатики.
Достоверность и эффективность. Достоверность теоретических результатов подтверждается доказательствами сформулированных утверждений. Достоверность практических результатов подтверждается серией вычислительных экспериментов, демонстрирующих приемлемые значения точности и полноты и других мер качества. Эффективность результатов, помимо эмпирических оценок точности и полноты, подтверждается экспериментами по оценке ресурсной эффективности по времени и пригодности к масштабируемости алгоритмов поиска бикластеров.
Личный вклад диссертанта. Работа продолжает развитие методов объектно-признакового представления данных, на которых сходство, определяемое как алгебраическая операция с некоторыми свойствами, задается через общее признаковое описание объектов. Личный вклад диссертанта состоит в разработке оригинальных методов решения задачи построения приближенного описания объектно-признаковых кластеров (бикластеров) и реализации эффективных программных средств, а также проведении исследований с использованием этих средств.
Результаты работы докладывались на следующих научных семинарах и конференциях:
Научном семинаре Лаборатории анализа и выбора решений, ГУ-ВШЭ, 2010 и научном семинаре "Математические модели информационных технологий" кафедры анализа данных и искусственного интеллекта, ГУ-ВШЭ, 2010
Научно-технической конференции студентов, аспирантов и молодых спе-
циалистов "Информационные технологии в бизнесе", ГУ-ВШЭ, 2006 (доклад отмечен дипломом)
Трижды на национальной конференции по искусственному интеллекту, КИИ-2006, Обнинск; КИИ-2008, Дубна; КИИ-2010, Тверь.
Научно-техническая конференция "25 лет исследований по Д С М-методу: логика, анализ данных, интеллектуальные системы (ДСМ-2006)", РГГУ и ВИНИТИ РАН, Москва, 2006
Четырежды на научно-технической конференции студентов, аспирантов и молодых специалистов "Информационные технологии в экономике, бизнесе, управлении", ГУ-ВШЭ, 2007, 2008, 2009 и 2010;
Второй международная молодежной конференции «Искусственный интеллект: философия, методология и инновации», Санкт-Петербург, СПб-ГУ, 2007 (диплом: лучший доклад)
5-ой международной конференции по Формальному Анализу Понятий, (5th International Conference on Formal Concept Analysis: Clermont-Ferrand, France, February 12-16, 2007) в рамках семинара по анализу социальных сетей (Social Network Analysis and Conceptual Structures: Exploring Opportunities)
1-ой международной конференции по бизнес-информатике, ГУ-ВШЭ, Звенигород, 2007
6-ой международной конференции по решеткам понятий и их приложениям (The Sixth International Conference Concept Lattices and Their Applications (CLA'08)), Olomouc, Czech Republic, 2008
5-й Международной научно-технической конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте", Коломна, 2009
17-й международной конференции по понятийным структурам (The 17th International Conference on Conceptual Structures, (ICCS'09)), Москва, 2009
Летней школе по информатике Reasoning Web 2010: Semantic Technologies for Software Engineering, TU-Dresden, Germany, 2010
Публикации. Основное содержание диссертационной работы изложено в 14 публикациях, среди которых 6 — в трудах российских конференций, 3 — в рецензируемых трудах международных конференций, и 4 — в рецензируемых российских периодических изданиях (из которых 2 статьи опубликованы в журнале из списка ВАК) и 1 статья в международном рецензируемом журнале.
Структура и объем диссертации. Диссертация состоит из четырёх глав, заключения и списка литературы. Общий объем работы — 163 страницы. Список литературы включает 93 названия.
Классификация методов бикластеризации
В этой главе мы опишем проблематику задачи и дадим основные определения, которыми оперирует бикластеризация как метод анализа данных. Помимо это будут приведены основания для классификации методов и алгоритмов бикластеризации. В качестве таких оснований выступают следующие критерии: типы бикластеров, структура бикластеров, получаемых в ходе анализа, а также стратегии поиска, которые используют рассматриваемые алгоритмы. Отметим, что основания для классификации алгоритмов были даны ранее португальским ученым Сарой Мадейра (см. обзор по методам бикластеризации генетических данных [58]). Мы используем выявленные критерии для построения таксономии методов и дополняем существующую классификацию. В частности, мы рассматриваем методы бикластеризации, которые возникли вне области биоинформатики и предназначены для решения других задач, а также теми методами, которые появились позже написания обзора [58] или не вошли в него. По этой же причине мы не рассматриваем подробно те модели, которые описаны в обзорах [58], [13] и [84]. В качестве еще одного критерия классификации возможно использовать область применения метода, но для этого необходимо строго типизировать задачи.
Под термином бикластеризация понимается широкий круг задач и методов, а потому для него в научной литературе существует целый ряд синонимов: совместная кластеризация (simultaneous clustering), кокластеризация (co-clustering), двувходовая кластеризация (two-way clustering), кластеризация подпространства (subspace clustering), двумерная кластеризация (bi-dimensional) и бокс-кластеризация (box-clustering). Повышенный интерес к бикластеризации и выделение ее в самостоятельную область анализа данных возник в связи с задачей анализа массивов генетических данных (microarray data analysis). Поэтому, прежде чем дать основные определения из области бикластеризации, мы опишем задачи анализа генетических данных и то, как бикластеринг оказывается полезен для их решения. Обычно данные генной экспрессии (gene expression data) представляют собой матрицу, в которой строки соответствуют генам, а столбцы — условиям. Каждый элемент такой матрицы отражает уровень экспрессии некоторого гена при заданном условии и представлен действительным числом, как правило логарифмом относительного содержания информационной РНК (mRNA) гена при этом условии. Такие матрицы, как правило, изучают в двух размерностях: в размерности генов или столбцов. Этим способам анализа соответствует выявление экспрессии шаблонов генов посредством сравнения строк или столбцов. Общие задачи такого анализа включают в себя: 1) группировку генов согласно их экспрессии для множества условий; 2) классификацию нового гена по известной экспрессии его и других генов для установленной классификации; 3) группировку условий, основанных на экспрессии конкретного множества генов; 4) классификацию нового образца при известной экспрессии генов и условиях эксперимента. Методы кластеризации могут быть использованы для группирования либо генов, либо условий, а потому явно решают задачи 1 и 3, указанные выше, и неявно — 2 и 4. Но применение методов кластеризации к анализу данных генной экспрессии ведет к значительным сложностям. Активационные образцы образуют группы генов только при определенных экспериментальных условиях. Таким образом, понимание клеточных процессов указывает на то, что необходимо искать множество генов, ведущих себя слаженно и совместно выраженных только при некоторых экспериментальных условиях, и почти независимо при других условиях. А значит, необходимы специальные методы поиска таких локальных образцов, которые могли бы играть ключевую роль в открытии новых генетических взаимодействий [17]. В отличие от методов кластеризации, алгоритмы бикластеризации находят группы генов, проявляющих сходную активность для некоторого подмножества экспериментальных условий. Поэтому подход бикластеризации позволяет успешно решать задачи, в которых возникает одна или сразу несколько таких ситуаций, как: 1) только небольшое множество генов, участвующих в клеточном процессе, представляют интерес; 2) интересующий исследователя клеточный процесс происходит только при некотором подмножестве условий; 3) один ген может участвовать во многих взаимодействиях, которые как могут быть совместно активными, так и не могут для всех условий. Поэтому предлагаемые методы бикластеризации должны следовать требованиям, перечисленным ниже. Кластер генов необходимо определять в соответствии только подмножеству условий. Кластер условий необходимо определять в соответствии только подмножеству генов. Кластеры не должны быть исключающими и \или полными (гены или условия могут принадлежать ко многим кластерам или ни к одному вообще, а также сгруппированы по подмножеству условий или генов, соответственно). В качестве дополнительного требования можно отметить робастность,. понимаемую как наличие мощного (с точки зрения сложности процесса генетической регуляции) инструмента анализа и устойчивость к шуму в исходных данных.
Фактически мы будем работать с матрицей размера п на т, элементы которой в общем случае представляют собой действительные числа. Абстрагируясь от задач анализа генетических данных, мы будем считать, что строкам матрицы соответствуют некоторые объекты, а столбцам множество столбцов. Будем использовать (X, Y) для обозначения матрицы А. Если / С X и J С Y подмножества строк и столбцов, соответственно, то Аи = (I, J) определяет подматрицу AJJ матрицы А. Кластер строк есть подматрица матрицы А вида Ajy — (I, Y), Для которой подмножество строк проявляет "сходное поведение" вдоль всего множества столбцов. Кластер столбцов есть подматрица матрицы А вида Ах j = (X, J), для которой подмножество столбцов проявляет "сходное поведение" вдоль строк. Бикластер есть подматрица матрицы А вида AJJ = (J, J), такая, что ее строки проявляют "сходное поведение" на столбцах и наоборот.
Отметим, что мы дали не достаточно формальное определение бикластера. В рамках представленных в работе моделей требования, предъявляемые к понятию бикластера, отличаются, а потому формальные определения даются нами только для конкретных случаев. Задача, которую решает алгоритм бикластеризации, заключается в нахождении такого множества бикластеров В = {Вк = (Ik,Jk)}, которое удовлетворяет некоторым формально определенным требованиям однородности. Словосочетания "сходное поведение" и "требования однородности" раскрываются в разделе 1.3 в определениях типов бикластеров.
Как уже говорилось выше, исходные данные представляют собой числовую матрицу. Значения этой матрицы в зависимости от необходимого представления данных могут принадлежать множеству действительных чисел или только лишь множеству {0,1}. Значительная часть алгоритмов бикластеризации, например, BiMax, DR-min-ег и все алгоритмы поиска формальных понятий и частых (замкнутых) множеств признаков, работает только с бинарными данными. И хотя существуют техники сведения вещественных и целочисленных данных к бинарным, такие как дискретизация и шкалирование, представляется необходимым четко разделять методы по типу данных.
Критерии отбора шумоустойчивых и релевантных понятиий
Для реальных данных зачастую характерно присутствие шума, в нашем случае это наличие (отсутствие) пары (объект, признак) в исследуемом контексте, при условии, что для описываемого явления данный объект не обладает (обладает) указанным признаком. Помимо этого шум может возникать в виде дополнительных или пропущенных объектов или признаков, описывающих некоторое явление. Шум также можно рассматривать как исключение из правил, например, когда мы рассматриваем некоторую категорию, описанную в терминах объект-признак. Следовательно, мы выделяем два типа шумов: 1) шум первого типа - инверсия значения некоторой ячейки объектно-признаковой таблицы (формального контекста); 2) шум второго типа - добавление (удаление) заданного количества или доли случайных объектов или признаков.
Причиной шумов первого типа могут быть, например, ошибки при формировании исходного набора данных, такие как технические ошибки счетчиков посещаемости, потеря значимых (учет незначимых) посещений при неправильно выбранном пороге посещаемости для шкалирования данных (такой шум могут создавать поисковые роботы). Другой причиной технического характера является невозможность точной идентификации того или иного пользователя, которая осуществляется по IP-адресу, файлам cookie и некоторыми другими способами. Таким образом, информация о посещении пользователем того или иного сайта может оказаться потерянной, т.к. в следующие моменты его активности на том или ином сайте он идентифицируется как другой посетитель.
В первую очередь нас будет интересовать шум первого типа, как наиболее часто встречающийся в исходных данных. Шум второго типа, связанный с добавлением или удалением сайта, как признака формального контекста практически невозможен в силу технических особенностей сбора информации о посещаемости сайтов - счетчик либо установлен на конкретном сайте, либо нет. Шум второго типа, связанный с пропущенными пользователями также отсутствует, пользователь либо посещал сайт, либо нет, но могут возникать дополнительные пользователи по причинам смены его идентификатора в базе данных о посещаемости. Этот тип, шумов сводится к первому типу, т.к. мы можем рассматривать непосещенные пользователем сайты с исходным идентификатором, но посещенные им с новым идентификатом, как пропущенные значения в контексте, и наоборот. Как видим, существует большое количество причин наличия шумов в данных, поэтому мы рассматриваем шум в ином смысле, чем это привыкли делать в математической статистике. По причине огромных размеров исходных данных существуют технические причины для невозможности установления статистических свойств шума. Тем не менее мы осмеливаемся предложить методику для проведения экспериментов с применением некоторого распределения (например, равномерного) для моделирования шумов и проверки шумоустойчивых свойств критериев отбора релевантных понятий для шума первого типа.
Для исходного контекста порождается "зашумленный контекст", в котором каждая ячейка с вероятностью р меняет свое значение на противоположное, т.е. О на 1 и наоборот. Всего порождается к контекстов для значений р от 1 до к с шагом 1. Для каждого контекста, содержащего шум, порождается множество формальных понятий с вычисленными значениями устойчивости и указанием размера объема каждого формального понятия. Далее используется пороговое ограничение на число формальных понятий, отбираются N самых крупных (для случая решеток-айсбергов) или N самых устойчивых (в смысле индекса устойчивости) понятий. Для полученных множеств понятий и понятий исходного, не подвергавшегося воздействию "шума" понятия, вычисляются меры качества. Мы применили две такие меры р и а, которые были использованы в работе [21] для похожей задачи оценки качества способности "шумоустойчивых" понятий восстанавливать понятия исходного контекста.
Мера р служит для оценки степени присутствия множества понятий С\ в Сг. Мера а учитывает степени присутствия множества понятий Сг в Сі, а также показывает, насколько много "лишних" понятий содержится во множестве Сг. Значение р(Сі, Сг) = 1 позволяет говорить о том, что все множество понятий Сі вложено во множество Сг, а т(Сі, Сг) = 1 означает, что эти два множества совпадают.
Одна из разновидностей электронной коммерции — контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы "Яндекс.Директ" и "Бегун". Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В этом разделе мы не будем рассматривать задачу предоставления пользователю наиболее интересной ему поисковой рекламы. Наша задача — выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма F приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила F и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в [97].Цель наших экспериментов — не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание исходного набора данных, постановка задачи, предложены методы для ее решения. Постановка задачи и исходные данные
Данные для экспериментов принадлежат компании US Overture (ныне часть Yahoo) и описаны в работе [97]. Фактически данные представляют собой двумерный массив, в котором строкам соответствуют фирмы (advertisers), а столбцам — рекламные слова (bids). Число фирм — 2000, а число рекламных словосочетаний — 3000. Число ненулевых ячеек 92345, соответственно мера разреженности равна 1 — 6адд0 0,9846. Единица в ячейке означает, что фирма, соответствующая индексу строки, приобрела словосочетание, которое соответствует столбцу. Ноль означает отсутствие такой покупки.
По этим данным требуется построить бикластеры (фирмы, рекламные слова), которые представляют собой сегменты рынка. Далее такие бикластеры можно использовать для создания рекомендаций для фирм, действующих на этом же рынке, но не совершившим покупки слов, входящих в такой бикластер. В случае бикластеризации, допускающей незаполненные ячейки внутри бикластера, рекламные слова, отвечающие таким ячейкам, можно рассматривать в качестве кандидатов для рекомендаций.
Подобные рекомендации можно представлять в виде правил: "если фирма приобрела рекламное словосочетание А, то имеет смысл предложить ей словосочетание В". Такие "если-то" правила хорошо вписываются в парадигму поиска ассоциаций. В существующей научной литературе неоднократно описывались рекомендательные системы, основанные на анализе ассоциативных правил, см. [72] і Эти методы наряду с другими, используемыми в рекомендательных системах, показывают приемлемые результаты. Ниже мы опишем, как можно использовать семантическую и морфологическую информацию, заложенную в описании признаков (рекламных слов), и тем самым улучшить качество рекомендационных правил.
Алгоритм бикластеризации на основе объектных и признаковых замыканий
В качестве экспериментального материала нами использовалась URL-коллекция РОМИП, состоящая из 52 файлов, общего размера 4,04 Гб. Для проведения экспериментов коллекция разбивалась на несколько частей, включающих от трех до двадцати четырех файлов (приблизительно от 5% до 50% от размера всей коллекции). Параметры шинглирования, использовавшиеся в экспериментах: число слов в шингле 10 и 20, отступ между началом соседних шинглов 1. Данное значение отступа означает, что начальное множество шинглов включало все возможные последовательности цепочек слов.
В экспериментах с синтаксическим методом представления исследовались оба способа составления образа документа, описанные в разделе 2.1: "п минимальных элементов в перестановке" и "минимальные элементы в п перестановках". Размеры результирующих образов документов выбирались в пределах от 100 до 200 шинглов.
В качестве порогов, определявших "частые замкнутые множества" (то есть числа общих шинглов в образах документов из одного кластера) нами исследовались различные значения в интервалах, правая часть которых совпадала с числом шинглов в образе документа, например, интервал [85, 100] для образов документов размером 100 шинглов, интервал [135, 150] для образов документов размером 150 шинглов, и т.д. Очевидно, что при выборе в качестве порога верхнего значения из указанных интервалов в кластер дубликатов попадали только те документы, образы которых совпадали полностью. Для значений параметров из указанных интервалов исследовалось соответствие кластеров дубликатов списку дубликатов РОМИП. Для каждой пары из списка дубликатов РОМИП искался кластер "частых замкнутых множеств", в котором содержится данная пара, и обратно, для каждого кластера замкнутых множеств, каждая пара документов из какого-либо кластера частых замкнутых множеств искалась в списке дубликатов РОМИП. Выходом данного модуля являлась таблица с указанием общего числа пар дубликатов HSE (пар дубликатов, имеющихся в списке РОМИП) и число уникальных пар дубликатов ВИНИТИ (то есть пар, не входящих в список дубликатов РОМИП). Эти числа позволяют подсчитывать полноту и точность наших методов относительно списка пар РОМШТ. Замерялось время, затрачиваемое на стадии шинглирования, составления образов документов и порождения кластеров сходных документов.
Очевидно, что когда значение порога на величину сходства равна размеру образа документа, то кластеры будут состоять из документов с идентичными образами. В ходе экспериментов мы исследовали, как соотносятся полученные кластеры со списком дубликатов, предоставленным ROMIP. Сходство каждой пары документов в этом списке было вычислено с помощью меры Левенштейна (Edit Distance), два документа считались дубликатами, если значение меры Левенштейна превышало порог 0,85 [91]. Такое определение понятия быть дубликатом, иногда, как показано ниже, может вести к странным результатам. Однако для большой коллекции данных невозможно установить факт дублирования парными сравнениями, выполняемыми экспертом-человеком, поэтому выявление дубликатов путем попарного вычисления сходства с помощью Edit Distance, хотя и трудоемкая, но технически приемлемая процедура. К сожалению, тестовые коллекции документов (полу)дубликатов отсутствуют даже для таких коллекций, как TREC и Reuters [66]. Для тестирования предложенных методов исследователи создают самостоятельно списки дубликатов, изменяя документы стандартных коллекций.
В нашей работе для каждой пары дубликатов мы искали содержания, в которых присутствуют оба элемента пары, и наоборот, для каждого кластера очень похожих документов (т.е. для каждого соответствующего замкнутого множества документов с более, чем к общими единицами описания) мы брали каждую пару документов в кластере и искали для нее соответствующую пару в коллекции РОМИП. В результате мы получаем таблицу с указанием числа общих пар (полу)дубликатов, найденных нашим методом (обозначенных как HSE) и представленных в коллекции РОМИП, а также числп уникальных пар HSE дубликатов (пар документов, которые встречаются в кластере "очень похожих документов" и отсутствуют в списке дубликатов коллекции РОМИП). Результаты наших экспериментов показывают, что коллекция дубликатов РОМИП, рассматриваемая как эталонная (benchmark) далека от совершенства. Первое, мы обнаружили, что большое число пар ложных дубликатов представлено в этой коллекции документов по причине общей разметки. Например, веб-страницы,
Тем не менее, как и многие другие аналогичные пары ложных дубликатов в РОМИП коллекции, они не принадлежали ни одному из кластеров (максимально частых) содержаний понятий, построенных нашим методом. В рамках нашего исследования мы также искали "кластеры ложных дубликатов" в коллекции РОМИП, появление которых вызвано использованием транзитивного замыкания отношения "X есть дубликат У" (как стандартного определения кластера документов-дубликатов [25]). Т.к. отношение сходства в общем случае не транзитивно, то кластеры, образованные с помощью транзитивного замыкания этого отношения, могут содержать абсолютно разные документы. Отметим, что если кластеры определены как максимально частые множества признаков (подмножества признаков), то не возникает похожих эффектов, потому что документы в этом случае имеют достаточно большое количество общих признаков. Мы проанализировали около 10000 пар дубликатов и обнаружили кластеры ложных дубликатов. Приведем пример кластера из 58 документов, содержащих веб-страницы, адреса которых приведены ннже Блоки 1-6 и 8 реализованы на языке Java, блок 7 позволяет, использовать различные реализации алгоритмов для поиска частых замкнутых множеств признаков на языке C++ из репозитория FIMI. Опишем кратко работу некоторых ключевых блоков с формата входа и выхода для них и некоторых особенностей работы. Блок 5. Составление образа документов путем выбора подмножества (хэш-кодов) шинглов с помощью методов "п минимальных элементов в перестановке" и "минимальные элементы в п перестановках". Класс NElementsPageHandler реализует метод "п минимальных элементов в перестановке". Последовательно обрабатываются данные файлов в формате xml из коллекции ROMIP. Каждый документ, имеющий URL_Id, шинглируется с заданными параметрами (длина_шингла) (смещение) (размер_образа), результаты шинглирования помещаются в выходной файл(ы) {shingles.fps). По умолчанию из множества всех хешей шинглов. данного документа выбирается сто п минимальных (в смысле перестановок) хешей. После выборки в выходной файл в поле Fingerprint записывается выбранный хеш соответствующего шингла. Класс MatrixPageHandler реализует "минимальные элементы в п перестановках".
Последовательно обрабатываются данные файлов в формате xml коллекции ROMIP. Каждый документ, имеющий URL_Id, шинглируется с заданными параметрами (длина_шингла) (смещение) (размер_образа). После разбиения документа на шинглы и хеширования используется техника перестановок, а именно, случайная выборка заданного количества отпечатков для1 конечного представления документа из множества имеющихся отпечатков. Для получения выборки порождаются случайные матрицы определенного вида, на которые затем умножается вектор хешей для каждого документа. Результаты шинглирования помещаются в выходные файлы (shingles.fps). Отпечаток (хеш) данного шингла для документа Docld записывается в выходной файл в поле Fingerprint.
Сравнение результатов работы метода FPmax с результатами, полученными с помощью системы Cluto
На первом этапе, после снятия разметки (например, HTML), документы, как линейные последовательности слов (символов), преобразуются во множества слов, возможно с указанием кратности вхождения. Здесь двумя основными типами методов, определяющими весь возможный спектр смешанных стратегий, являются синтаксические методы (в которых осуществляется выбор последовательностей символов, слов или предложений) и1 лексические (семантические) методы (в которых происходит выбор представительных языковых единиц). Основным синтаксическим методом является шинглирование, когда документ, очищенный от разметки, пробелов и знаков препинания, сперва представляется набором всех подцепочек последовательных слов (символов) определенной длины. Такие цепочки, выбираемые с определенным сдвигом по линейной структуре текста, называют шинглами (от англ. shingle -черепица, чешуйка). Каждой цепочке сопоставляется хеш-код, при выборе которого обеспечиваются следующие важные свойства: равенство цепочек гарантирует равенство кодов (т.е. кодирование есть функция), а равенство кодов говорит о высоком сходстве цепочек. Наиболее распространенными являются хэш-коды SHA1 [63] и Rabin [22]. Необходимым условием является миниальное число коллизий для хеш-функций. Из множества хеш-кодов цепочек, в соответствии с некоторой схемой рандомизации, выбирается подмножество, которое и служит т.н. "отпечатком" (образом) документа. Данный метод используется во многих системах определения сходства документов, а также в таких поисковых системах как Google и AltaVista. Среди способов выбора подцепочек используются следующие методы: выбор подцепочек фиксированной длины, или логарифмической длины от размера текста, выбор каждой fc-й цепочки и т.д. В методах лексического типа реализуется отбор множества представительных слов исходя из показателей значимости этих слов. В множество значимых слов не включаются слова из заранее фиксированного списка стоп-слов. Список стоп-слов для каждого языка является стандартным и включает в себя предлоги, артикли, вводные слова и т.п. Показателями значимости служат частотные характеристики: для дальнейшего анализа отбираются слова, чьи частоты лежат в некотором интервале, так как высокочастотные слова могут быть неинформативными, а низкочастотные -опечатками или случайными словами. В лексических методах, например, в известном методе I-Match [30], используют большой текстовый корпус для порождения лексикона,. то есть набора представительных слов. Документ представляется множеством тех его слов, которые входят в лексикон. При порождении лексикона отбрасываются самые низкочастотные и самые высокочастотные слова. I-Match порождает сигнатуру документа (множество слов-термов), а по ней — хэш-код документа, причем два документа получают один хэш-код с вероятностью равной их мере сходства (по метрике косинуса). I-Match порой неустойчив к изменениям текста [50], например, к рандомизации по существу одних и тех же спамерских сообщений. Для устранения этого недостатка, помимо стандартной сигнатуры, создается еще К сигнатур, каждая из которых получается случайным удалением некоторой доли всех термов из исходной сигнатуры (таким образом, все новые сигнатуры являются подмножествами исходной). Два документа можно считать очень сходными, если их наборы из К + 1 сигнатуры имеют большое пересечение хотя бы по одной из сигнатур. Такой подход сходен с подходом на основе супершинглов (конкатенации шинглов), когда сходство документов определяется как совпадение хотя бы одного супершингла [50]. В лексическом методе [47] большое внимание уделяется построению словаря — набора дескриптивных слов, который должен быть небольшим, но хорошо покрывать коллекцию, а присутствие каждого из слов в образе документа устойчиво по отношению к малым изменениям документов. Проблема автоматического порождения адекватного словаря для анализа сходства документов по определенной теме связана с составлением представительной коллекции документов по данной теме - корпуса текстов, что затрудняет применение лексических методов без постоянной поддержки такого корпуса. На первом этапе можно учесть структуру текста и его шаблонов, представляя исходный текст документа в виде кортежа разделов, определенных шаблонами, и производя шинглирование внутри компонент кортежа. На втором этапе из документа, представленного множеством синтаксических или лексических признаков, выбирается подмножество признаков, образующее краткое описание (образ) документа. В синтаксических методах такого рода отбор чаще всего осуществляется с помощью схем рандомизации [22, 23], в лексических методах - с помощью методов выбора существенных слов, например, на основе заранее созданных словарей [30], или на основе какой-либо меры существенности слова для текста [47]. Техника отбора подстрок, начиная с некоторого определенного места в документе, также позволяет учесть структуру документа с использованием так называемых "якорей" -особых мест документа: начала абзаца, раздела, ключевого слова и т.п [44]. Являясь одной из самых эффективных, эта техника может потребовать много времени для тонкой ручной настройки по каждой коллекции документов. На третьем этапе определяется отношение сходства на документах. Для этого используется определенная числовая мера сходства, сопоставляющая двум документам число в интервале [0, 1], которое характеризует сходство, и некоторый параметр — порог, превышение которого свидетельствует о большом сходстве документов или о том, что документы являются (почти) дубликатами друг друга [22, 23, 24].
На четвертом этапе, на основе отношения сходства документы могут объединяться в кластеры (почти) дубликатов. Определение кластера также может варьироваться. Самый частый используемый на практике подход [22]: если документам сопоставить граф, вершины которого соответствуют самим документам, а ребра - отношению "быть (почти) дубликатом", то кластером объявляется компонента связности такого графа. Достоинством такого определения является эффективность вычислений: компоненту связности можно вычислить за линейное время от числа ребер. Недостаток такого подхода: отношение "быть (почти) дубликатом" не является транзитивным, поэтому в кластер сходных документов могут попасть абсолютно разные документы. Противоположным - "самым сильным" - определением кластера, исходя из отношения "быть (почти) дубликатом", является его определение через клики графа (максимальные по вложению полные подграфы) коллекции документов. При этом каждый документ из кластера должен быть сходным со всеми другими документами того же кластера. Такое определение кластера более адекватно передает представление о групповом сходстве, но может встретить трудности при масштабировании системы поиска документов-дубликатов в силу того, что поиск клик в графе — классическая труднорешаемая задача. Указанные два определения кластера задают спектр промежуточных формулировок, в которых можно находить необходимый баланс между точностью и полнотой определения кластеров, с одной стороны, и сложностью вычисления кластеров, с другой стороны. Другие методы определения кластеров основаны на вариациях стандартных методов кластерного анализа, например, когда при отнесении очередного объекта к кластеру используется расстояние до центров масс кластеров.
