Методы бикластеризации для анализа интернет-данных
       

Поиск сходства Интернет-документов с помощью частых замкнутых множеств признаков.


У множества документов в Интернете имеются дубликаты, в связи с чем необходимы средства эффективного вычисления кластеров документов-дубликатов [20, 21, 22, 26, 27, 40, 44, 46, 70, 61]. В этом разделе описываются исследования, посвященные применению алгоритмов Data Mining для поиска кластеров дубликатов с использованием синтаксических и лексических методов составления образов документов. На основе экспериментов делаются некоторые выводы о способе выбора параметров методов.

Постановка задачи

У огромного числа документов (по некоторым источникам до 30%) в Интернете имеются дубликаты, и поисковые машины должны обладать эффективными средствами вычисления кластеров дубликатов. Происхождение дубликатов может быть разным — от дублирования компаниями собственной информации на разных серверах (создание зеркал) до злонамеренных — обмана программ индексаторов веб-сайтов, незаконного копирования и спамерских рассылок.

Обычно дубликаты документов определяются на основе отношения сходства на парах документах: два документа сходны, если некоторая числовая мера их сходства превышает некоторый порог [20]. По отношению сходства вычисляются кластеры сходных документов, например, по транзитивному замыканию отношения сходства [20]. Вначале, после снятия HTML-разметки документы, как линейные последовательности слов (символов), преобразуются во множества. Здесь двумя основными схемами (определяющими весь возможный спектр смешанных методов) являются синтаксические и лексические методы. К синтаксическим относится метод шинглирования [22], в котором документ в итоге представляется набором хеш-кодов; этот метод испоьзовался в поисковых системах Google и AltaVista. В лексических методах [44] большое внимание уделяется построению словаря — набора дескриптивных слов; известны его разновидности, такие I-match и метод ключевых слов Ильинского [44].

На втором этапе из документа, представленного множеством синтаксических или лексических признаков, выбирается подмножество признаков, образующее краткое описание (образ) документа. На третьем этапе определяется отношение сходства на документах с помощью некоторой метрики сходства, сопоставляющей двум документам число в интервале [0, 1], и некоторого параметра — порога, выше которого находятся документы-дубликаты.


На основе отношения сходства документы объединяются в кластеры (полу-)дубликатов. Определение кластера также может варьироваться. Одно из возможных определений, часто используемых на практике (например, в компании AltaVista), но наиболее слабых, упоминается в обзоре [20]: если документам Интернета сопоставить граф, вершины которого соответствуют самим документам, а ребра — отношению «быть (почти) дубликатом», то кластером объявляется компонента связности такого графа. Достоинством такого определения является эффективность вычислений. Недостаток такого подхода очевиден: отношение «быть (почти) дубликатом» не является транзитивным, поэтому в кластер сходных документов могут попасть абсолютно разные документы.

В качестве противоположного — «самого сильного» — определения кластера, опирающимся на отношение «быть (почти) дубликатом», можно принять клики графа. При этом каждый документ из кластера должен быть сходным со всеми другими документами того же кластера. Такое определение кластера более адекватно передает представление о групповом сходстве, но, к сожалению, практически не применимо в масштабе Интернета, поскольку поиск клик в графе — классическая труднорешаемая задача.

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

Приводятся результаты экспериментальной проверки данного метода на основе сравнения результатов его применения (для разных значений порогов) со списком дубликатов, составленным на основе результатов применения других методов к тому же множеству документов. Исследовалось влияние на результат следующих параметров модели: использование синтаксических или лексических методов представления документов, использование методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках» [20], параметры шинглирования, величина порога сходства образов документов. Одна из задач проекта заключалась в том, чтобы связать вычисление попарного сходства образов документов с построением кластеров документов, чтобы, с одной стороны, получаемые кластеры были бы независимы от порядка рассмотрения документов (в отличие от методов кластерного анализа), а с другой стороны гарантировали бы наличие реального попарного сходства всех образов документов в кластере.



Описание вычислительной модели

В качестве методов представления документов (создания образа документа) использовались стандартные синтаксические и лексические подходы с разными параметрами.



В рамках синтаксического подхода была реализована схема шинглирования и составление краткого образа (скетча) документов на основе методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках», описание которых можно найти, например, в [21, 22].

Программа shingle с двумя параметрами length и offset порождает для каждого текста набор последовательностей слов (шинглов) длины length, так что отступ от начала одной последовательности до начала другой последовательности в тексте имеет размер offset. Полученное таким образом множество последовательностей хэшируется, так что каждая последовательность получает свой хэш-код.

Далее из множества хэш-кодов, соответствующему документу, выбирается подмножество фиксированного (с помощью параметра) размера с использованием случайных перестановок, описанных в работах [20, 21, 22]. При этом вероятность того, что минимальные элементы в перестановках хэш-кодов на множествах шинглов документов A и B (эти множества обозначаются через


и
соответственно) совпадут, равна мере сходства этих документов sim(A,B):



Основные определения, связанные с частыми замкнутыми множествами, естественно, даются в терминах анализа формальных понятий (ФАП) [33]. Мы рассматриваем формальный контекст
, где D — множество документов, а F — множество хеш-кодов (fingerprins), отношение


показывает, что некий объект


обладает признаком


в том и только том случае, когда
. Для множества документов


множество их общих признаков


служит описанием их сходства, а замкнутое множество


является кластером сходных объектов (с множеством общих признаков
). Для произвольного


величина


является поддержкой B и обозначается supp(B).

Нетрудно видеть, что множество


замкнуто тогда и только тогда, когда для любого


имеет место
. Именно это свойство используется для определения замкнутости в методах Data Mining.



Множество


называется
-частым, если


(то есть множество признаков B встречается в более чем


объектах), где


— параметр.

Вычисление частых замкнутых множеств признаков (содержаний) приобрело важность в Data Mining благодаря тому, что по этим множествам эффективно вычисляются множества всех ассоциативных правил [59]. Фактически, мы будем вычислять частные замкнутые множества признаков для контекста, дуального к
, т.е. находить такие множества документов-признаков контекста
, для которых размер множества их общих шинглов превышает заданный порог сходства.

Хотя теоретически размер множества всех замкнутых множеств признаков (содержаний) может быть экспоненциальным относительно числа признаков, на практике таблицы данных сильно "разрежены" (то есть среднее число признаков на один объект весьма мало), и число замкнутых множеств невелико. Для таких случаев существуют весьма эффективные алгоритмы построения всех наиболее частых замкнутых множеств признаков (см. также обзор по алгоритмам построения всех замкнутых множеств [47]).

В последние годы проводился ряд соревнований по быстродействию таких алгоритмов на серии международных семинаров под общим названием FIMI (Frequent Itemset Mining Implementations). Пока лидером по быстродействию считается алгоритм FPmax* [35], показавший наилучшие результаты по быстродействию в соревновании 2003 года. Мы использовали этот алгоритм для построения сходства документов и кластеров сходных документов. При этом в роли объектов выступали элементы описания (шинглы или слова), а в роли признаков — документы. Для такого представления «частыми замкнутыми множествами» являются замкнутые множества документов, для которых число общих единиц описания в образах документов превышает заданный порог.

Программная реализация и компьютерные эксперименты

Программные средства для проведения экспериментов в случае синтаксических методов включали следующие блоки:

  • парсер формата XML для коллекции ROMIP;


  • снятие html-разметки;




  • нарезка шинглов с заданными параметрами;


  • хэширование шинглов;


  • составление образа документов путем выбора подмножества (хэш-кодов) шинглов с помощью методов «n минимальных элементов в перестановке» и «минимальные элементы n n перестановках»;


  • cоставление по результатам методов 4-5 инвертированной таблицы «список идентификаторов документов—шингл» — подготовка данных к формату программ вычисления замкнутых множеств;


  • вычисление частых замкнутых множеств с заданным порогом общего числа документов, в которое входит данное множество шинглов: программа MyFim (реализующая алгоритм FPmax*);


  • сравнение со списком дубликатов РОМИП – программа Comparator.


    • В качестве экспериментального материала нами использовалась URL-коллекция РОМИП, состоящая из 52 файлов общего размера 4,04 Гб. Для проведения экспериментов коллекция разбивалась на несколько частей, включающих от трех до двадцати четырех файлов (приблизительно от 5% до 50% от размера всей коллекции).

    В экспериментах использовались следующие пПараметры шинглирования: число слов в шингле 10 и 20, отступ между началом соседних шинглов 1. Данное значение отступа означает, что начальное множество шинглов включало все возможные последовательности цепочек слов.

    Эксперименты проводились на персональном компьютере P-IV HT с тактовой частотой 3.0 ГГц, оперативной памятью объемом в 1024 Мб и операционной системой Windows XP Professional. Результаты экспериментов и время, затраченное на их проведение, частично приводятся в следующих таблицах и рисунках.

    (1) Результаты работы метода “


    минимальных элементов в перестановке”



    FPmax    		 All Pairs of Duplicates Unique pairs of duplicates Common pairs


    Input     		Threshold ROMIP Test ROMIP Test


    b_1_20_s_100_n1-6.txt     		100 33267 7829 28897 3459 4370
    b_1_20_s_100_n1-6.txt 95 33267 11452 26729 4914 6538
    b_1_20_s_100_n1-6.txt 90 33267 17553 22717 7003 10550
    b_1_20_s_100_n1-6.txt 85 33267 22052 21087 9872 12180


    b_1_20_s_100_n1-12.txt     		100 105570 15072 97055 6557 8515
    b_1_20_s_100_n1-12.txt 95 105570 20434 93982 8846 11588
    b_1_20_s_100_n1-12.txt 90 105570 30858 87863 13151 17707
    b_1_20_s_100_n1-12.txt 85 105570 41158 83150 18738 22420


    b_1_20_s_100_n1-24.txt     		100 191834 41938 175876 25980 15958
    b_1_20_s_100_n1-24.txt 95 191834 55643 169024 32833 22810
    b_1_20_s_100_n1-24.txt 90 191834 84012 155138 47316 36696
    b_1_20_s_100_n1-24.txt 85 191834 113100 136534 57800 55300


    b_1_10_s_120_n1-6.txt     		120 33267 7725 29065 523 4202
    b_1_10_s_120_n1-6.txt 115 33267 11763 26586 5082 6681
    b_1_10_s_120_n1-6.txt 110 33267 11352 26547 4632 6720


    b_1_10_s_150_n1-6.txt     		150 33267 6905 28813 2451 4454
    b_1_10_s_150_n1-6.txt 145 33267 9543 27153 3429 6114
    b_1_10_s_150_n1-6.txt 140 33267 13827 24579 5139 8688
    b_1_10_s_150_n1-6.txt 135 33267 17958 21744 6435 11523
    b_1_10_s_150_n1-6.txt 130 33267 21384 19927 8044 13340
    b_1_10_s_150_n1-6.txt 125 33267 24490 19236 10459 14031


    b_1_10_s_180_n1-6.txt     		170 33267 9834 27457 4024 5810
    b_1_10_s_180_n1-6.txt 130 33267 38402 20142 25277 13125
    b_1_10_s_180_n1-6.txt 120 33267 55779 19966 42478 13301


    b_1_10_s_200_n1-6.txt     		200 33267 5083 29798 1614 3469
    b_1_10_s_200_n1-6.txt 195 33267 6700 28661 2094 4606
    b_1_10_s_200_n1-6.txt 190 33267 8827 27516 3076 5751
    b_1_10_s_200_n1-6.txt 170 33267 12593 25866 5192 7401
    b_1_10_s_200_n1-6.txt 135 33267 48787 19987 35507 13280
    b_1_10_s_200_n1-6.txt 130 33267 57787 19994 44514 13273
    <


    (2) Результаты работы метода “минимальные элементы в n перестановках”.

    FPmax All Pairs of Duplicates Unique pairs of duplicates Common pairs
    Input Threshold ROMIP Test ROMIP Test
    m_1_20_s_100_n1-3.txt 100 16666 4409 14616 2359 2050
    m_1_20_s_100_n1-3.txt 95 16666 5764 13887 2985 2779
    m_1_20_s_100_n1-3.txt 90 16666 7601 12790 3725 3876
    m_1_20_s_100_n1-3.txt 85 16666 9802 11763 4899 4903
    m_1_20_s_100_n1-6.txt 100 33267 13266 28089 8088 5178
    m_1_20_s_100_n1-6.txt 95 33267 15439 26802 8974 6465
    m_1_20_s_100_n1-6.txt 90 33267 19393 24216 10342 9051
    m_1_20_s_100_n1-12.txt 100 105570 21866 95223 11519 10347
    m_1_20_s_100_n1-12.txt 95 105570 25457 93000 12887 12570
    (3) Вычисление образов документов для методов "


    минимальных элементов в перестановке" и метода "минимальные элементы в


    перестановках".

    Subcollection Number of documents Method Time elapsed, sec Shingling parameter
    length of shingle image size
    narod.1-3.xml 26077 n-min 312 20 100
    narod.1-6.xml 53539 n-min 622 20 100
    narod.1-12.xml 110997 n-min 1360 20 100
    narod.1-24.xml 223804 n-min 2435 20 100
    narod.1-3.xml 26077 min in n 924 20 100
    narod.1-6.xml 53539 min in n 1905 20 100
    narod.1-12.xml 110997 min in n 3617 20 100
    narod.1-24.xml 223804 min in n 7501 20 100
    narod.1-3.xml 26077 n-min 277 10 100
    narod.1-6.xml 53539 n-min 563 10 100
    narod.1-12.xml 110997 n-min 1118 10 100
    narod.1-24.xml 223804 n-min 2348 10 100
    narod.1-3.xml 110997 n-min 315 10 120
    narod.1-6.xml 223804 n-min 622 10 120
    narod.1-3.xml 110997 n-min 388 10 150
    narod.1-6.xml 223804 n-min 745 10 150
    narod.1-6.xml 223804 n-min 1312 10 180
    narod.1-6.xml 223804 n-min 2585 10 200
    narod.1-6.xml 223804 n-min 541 5 100
    narod.1-6.xml 223804 n-min 611 15 100
    narod.1-6.xml 223804 min in n 2101 10 200
    <


    (3) Время работы FPmax* для метода “


    минимальных элементов в перестановке”.

    Input Threshold Time elapsed,
    sec
    b_1_20_s_100_n1-6.txt 100 1,2
    b_1_20_s_100_n1-6.txt 95 2,0
    b_1_20_s_100_n1-6.txt 90 3,1
    b_1_20_s_100_n1-6.txt 85 5,3
    b_1_20_s_100_n1-12.txt 100 3,0
    b_1_20_s_100_n1-12.txt 95 9,0
    b_1_20_s_100_n1-12.txt 90 14,2
    b_1_20_s_100_n1-12.txt 85 25,7
    b_1_20_s_100_n1-24.txt 100 16,1
    b_1_20_s_100_n1-24.txt 95 120,0
    b_1_20_s_100_n1-24.txt 90 590,4
    b_1_20_s_100_n1-24.txt 85 1710,6
    b_1_10_s_150_n1-6.txt 150 1,75
    b_1_10_s_150_n1-6.txt 145 3,265
    b_1_10_s_150_n1-6.txt 140 19,609
    b_1_10_s_150_n1-6.txt 135 97,046
    b_1_10_s_150_n1-6.txt 130 36,609
    b_1_10_s_150_n1-6.txt 125 11,75
    Рис. 5.1. Время работы алгоритма FPmax* для размера образа документа n=100

    Рис. 5.2. Время работы алгоритма FPmax* для размера образа документа n=150

    (4) Время работы FPmax* для метода “минимальные элементы в


    перестановках”.

    Input Threshold Time elapsed,
    sec
    m_1_20_s_n1-3.txt 100 3,4
    m_1_20_s_n1-3.txt 95 3,9
    m_1_20_s_n1-3.txt 90 7,0
    m_1_20_s_n1-6.txt 100 16,4
    m_1_20_s_n1-6.txt 95 4479,6
    m_1_20_s_n1-6.txt 90 7439,4
    m_1_20_s_n1-12.txt 100 291,36
    m_1_20_s_n1-12.txt 95 40418,796
    Рис. 5.3. Время работы алгоритма FPmax*

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

    (5) Сравнение эффективности алгоритмов поиска максимальных замкнутых множеств.

    Рис. 5.4. Время работы алгоритмов FIM и AddIntent

    По диаграмме видно, что наилучшие результаты показали алгоритмы Fpmax* и Afopt. А алгоритм AddIntent* из сообщества FCA-алгоритмов даже превзошел Mafia из FIMI, что является неплохим результатом для, как правило, более ресурсоемких алгоритмов первой группы.

    Выводы и направление дальнейшей работы

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



  • Методы порождения частых замкнутых множеств представляют эффективный способ определения сходства документов одновременно с порождением кластеров сходных документов.


  • На результаты синтаксических методов определения дубликатов значительное влияние оказывает параметр «длина шингла». Так, в наших экспериментах результаты для длины шингла, равной 10, были существенно ближе к списку дублей РОМИП, чем для длины шингла, равной 20, 15 и 5.


  • В экспериментах для всех значений параметров не было обнаружено существенного влияния использования метода «минимальные элементы в n перестановках» на качество результатов. По-видимому, на практике достаточно случайности, задаваемой отбором шинглов с помощью метода «n минимальных элементов в перестановке».


    • Необходимы дальнейшие эксперименты с использованием различных значений параметров синтаксических методов и сравнение результатов с результатами применения лексических методов, в которых используются инвертированные индексы коллекций. Необходимо сравнение методов кластеризации, в которых применяются замкнутые множества признаков, с алгоритмами, основанными на поиске минимальных разрезов вершин (cut) в двудольных графах, в которых множества вершин соответствуют множествам документов и множествам признаков [29, 87]. Эти методы родственны, поскольку замкнутые множества документов естественным образом выражаются через минимальные разрезы такого рода двудольных графов.

    Назад Содержание Вперёд


    Содержание раздела