Автореферат (1137244), страница 6
Текст из файла (страница 6)
Параметры шинглирования, использовавшиесяв экспериментах: число слов в шингле 10 и 20, отступ между началом соседних шинглов 1. Данное значение отступа означает, что начальное множество шинглов включало все возможные последовательности цепочек слов. Вэкспериментах с синтаксическим методом представления исследовались обаспособа составления образа документа, описанные в главе 2: “n минимальныхэлементов в перестановке” и “минимальные элементы в n перестановках”. Размеры результирующих образов документов выбирались в пределах от 100 до200 шинглов. Основные блоки вычислений реализованы на языке Java, блок7 позволяет использовать различные реализации алгоритмов для поиска частых замкнутых множеств признаков на языке С++ из репозитория FIMI.21Эксперименты проводились на персональном компьютере P-IV HT с тактовой частотой 3.0 ГГц, объемом оперативной памяти 1024 Мб и операционнойсистемой Windows XP Professional и Java 2 VM фирмы Sun (версия 1.4.3).
Результаты экспериментов и время, затраченное на их проведение, приводятсяв основном тексте в виде таблиц и графиков.Сравнение полученных нами результатов поиска с тестовой коллекцией РОМИП позволило выявить в ней значительное количество ложныхдокументов-дубликатов. Результаты сравнения с системой кластеризацииCLUTO (одной из лучших для кластеризации документов) показали, что реализованный в ней алгоритм ClusterRB по значению F-меры 0,63 при числекластеров равном 5000 сравним с результатами работы FPmax* на той же коллекции при значении порога 125 (F1=0,61).
При этом время работы ClusterRBсоставило 4 часа, тогда как FPmax* справился с задачей меньше, чем за полсекунды.Эксперименты по построению таксономий веб-пользователей позволяютприйти к выводу, что диаграммы решёток понятий являются удобным средством виузализации аудиторий веб-сайтов и позволяют исследовать их интересы в терминах сайтов других тематик, отличных от целевой. Исследованиешумоустойчивых свойств индексов устойчивости, решеток-айсбергов и минимальных разрезов дают надежные средства борьбы с ошибками в исходныхданных, связанных со спецификой работы интернет-счетчиков.
Индекс устойчивости является наиболее пригодной с точки зрения точности и полнотыпоиска мерой.В качестве данных для проведения экспериментов нам предложена выборка по статистике посещений 10000 сайтов с прилагаемым плоским тематическим каталогом по 59 категориям. Для конкретных экспериментов мыотобрали из них четыре сайта следующих тематик: сайт университета, сайтИнтернет-магазина бытовой техники, сайт крупного банка, сайт автомобильного Интернет-салона.
В качестве языков разработки применялся C# из среды MS Visual Studio 2005 и язык скриптового программирования Pyhton. 1)Для выявления исходных понятий по зашумленным данным необходимо выбирать значение порога (мощность множества самых крупных или самыхустойчивых понятий) примерно равным их числу. При большем значении порога наблюдается появление нерелевантных понятий.
2) Индекс устойчивостиприемлем в задаче выявления исходных понятий по зашумленным даннымдля указанных типов и размеров контекстов при уровне “шума” от 1% до 5%.3) Индекс устойчивости показывает лучшие результаты на контекстах номинальных шкал, т.е. когда наблюдается преобладание несравнимых понятий висходной решетке.Данные для экспериментов по рекомендательным системам принадлежат компании US Overture (ныне часть Yahoo) и описаны в работе [Zhukov,2004]. Фактически данные представляют собой двумерный массив, в которомстрокам соответствуют фирмы (advertisers), а столбцам — рекламные слова(bids).
Число фирм — 2000, а число рекламных словосочетаний — 3000. Единица в ячейке означает, что фирма, соответствующая индексу строки, приоб-22рела словосочетание, которое соответствует столбцу, ноль – отсутствие такойпокупки. Число ненулевых ячеек 92345, соответственно мера разреженности92345равна 1 − 6000000≈ 0, 9846. C помощью АФП и предложенного алгоритмаобъектно-признаковой бикластеризации выявлены крупные рынки рекламныхсловосочетаний. Причем оп-бикластеры более информативны, т.к. число разных тем, приходящихся на один бикластер, примерно в 1,5 раза больше, чемдля случая АФП с ограничениями на размер объема и содержания.
Для проверки результатов, полученных нами с помощью поиска ассоциативных правил, мы применяли предложенную нами модификацию 10-кратного скользящего контроля (10-fold cross validation). Агрегированной мерой качества полученных правил служило среднее значение достоверности для всего порожденного множества, которая на тестовой выборке не сильно снижается по сравнению с минимальной для обучающей, т.е. (0, 9 − 0, 87)/0, 9 ≈ 0, 03.
В качествесредства валидации для метаправил мы также используем меру достоверности. Величина поддержки не играет большой роли, так как мы ищем не столько крупные рынки или наиболее продаваемые словосочетания, а устойчивыезакономерности при покупке. Правила с достоверностью меньше 0.5 нас не таксильно интересуют, потому что они означают, что в половине случаев покупка может произойти, а в половине — нет (своеобразная игра в подбрасываниемонеты). Для метаправил значения поддержки и достоверности необходимовычислить по контексту K = (, , ). Приведем значения этих мер всводной таблице 0.1 для метаправил, построенных с использованием морфологии.Таблица 0.1.
Средние значения и для морфологических метаправил при _ = 0, 5Тип правила −−→ ⋃︀ −−→ ⋃︀ −−→ ( )Среднее значение Среднее значение Числоsuppconfправил150,64454150,6375180,6739321200,700,693922673 −−→ , где ⊆ ⋃︀ −−→ , где ⊆ По таблице 0.1 легко установить, что наиболее достоверными и часто ⋃︀встречающимися являются правила вида −−→ .Полученные результаты показывают, что часть зависимостей в базе данных покупок рекламных слов можно выявлять автоматически, не прибегаяк трудоемким методам, а используя стандартные техники в компьютернойлингвистике. Предложенные подходы вкупе с методами Data Mining помогают23улучшить рекомендации и предлагают хорошее средство частотного ранжирования, что удобно при составлении Top-N рекомендаций.
Еще одно преимущество подхода состоит в возможности выявить связанные рекламные слова, ноне используемые по каким-то причинам рекламодателями. Результаты бикластеризации на основе АФП показывают возможность выявления относительнокрупных рекламных рынков (> 20 участников) в виде бикластеров (фирмыучастники, рекламные слова).Помимо экспериментов для вычислительных моделей из главы 2 автором приводится описание архитектуры программной системы поиска дубликатов в текстах проектной документации, предлагается оригинальная методикаеё настройки и тестирования для коллекций текстовых документов.В заключении приведены основные результаты и перспективы дальнейших исследований.Основные результаты, полученные в данной работе, показывают, чтоприменение предлагаемых автором моделей и методов бикластеризации наоснове замкнутых множеств признаков позволяет эффективно решать различные актуальные задачи анализа данных, как по времени вычислений, таки по качеству результатов, и имеет ряд преимуществ перед классическимиалгоритмами кластеризации.
К основным результатам работы относятся:1. Оригинальная модель и метод бикластеризации на основе объектныхи признаковых замыканий. Исследованы и описаны в виде математических утверждений полезные свойства нового определения бикластера. Теоретические оценки временной сложности и размера выхода алгоритма, реализующего данный метод, полиномиальны от размера входа.Это дает новый эффективный способ сокращения числа бикластеров посравнению с поиском всех формальных понятий, количество и времяпоиска которых в худшем случае экспоненциальны от размера входа.Экспериментально показано, что разработанная оптимизированная (наоснове свойства антимонотонности оператора Галуа) версия алгоритмав среднем в 28 раз превосходит по времени вычислений алгоритм, непосредственно проверяющий условия определения.
Алгоритм позволяетэффективную параллельную реализацию, что дает дополнительные 45%сокращения времени счета на двухядерном процессоре.2. Оригинальная модель поиска сходства текстовых документов и их кластеров на основе частых замкнутых множеств признаков. Эксперименты,проведенные с помощью ее программной реализации на больших коллекциях документов системы показали превосходство по времени вычислений на 3-4 порядка по сравнению с лучшими из известных алгоритмов бикластеризации документов (разработанными в лабораторииJ. Karypis’а), при сохранении такого же качества по точности и полноте поиска.
На основе модели разработан прототип системы поискадокументов-дубликатов в текстах проектной документации.243. Оригинальная модель построения “внешних” и “внутренних” таксономий аудиторий Интернет-сайтов на основе АФП и критериев отбора релевантных понятий. На основе модели создана программная реализация, позволившая провести исследование аудиторий четырех крупныхИнтернет-сайтов и построить их таксономии.4. Модели выявления крупных рынков рекламных словосочетаний для контекстной рекламы и формирования рекомендаций таких словосочетанийна основе ассоциативных метаправил, использующих морфологию.
Созданный прототип рекомендательной системы позволил формироватьвысокодостоверные рекомендации только на основе морфологическогостроения слов в рекламном словосочетании, минуя дорогостоящие вычисления для исходной матрицы покупок рекламы.5. Впервые проведенное исследование связи между ассоциативными правилами, бикластеризацией и решетками понятий. Введено понятие плотности и разреженности бикластера, на основе которого исследованы бикластеры, порождаемые ассоциативными правилами и формальнымипонятиями.25Основное содержание диссертационной работы изложено вследующих публикациях:Публикации в журналах, входящих в перечень ВАК1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
