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


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


  • нарезка шинглов с заданными параметрами;
  • хэширование шинглов;
  • составление образа документов путем выбора подмножества (хэш-кодов) шинглов с помощью методов «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
    <


    - Начало -  - Назад -  - Вперед -



    Книжный магазин