close

Вход

Забыли?

вход по аккаунту

?

Информационный поиск. Лекция 5

код для вставкиСкачать
Современныеметодыисредства
построениясистеминформационного
поиска
ЛЕКЦИЯ5:ПоискдубликатоввWeb(часть1)
Москва,Mail.ru 2016
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Планлекции
•
•
•
•
•
•
Видыдубликатов
Shingling
Ура! Каникулы Практика!
Minhashing
Алгоритмдляколлекций
ДЗ
2
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Сравнениедокументов
• Чтоделаетдокументы“похожими”?
• Вырожденныеслучаи
• Почтидубликаты
3
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Пример: точныедубликаты
Пример: почтидубликаты
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Пример: почтидубликаты
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Пример: версиядляпечатиВерсиядляпечати
Полнаяверсия
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Пример: неточныедубликаты
Частыеслучаивweb
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Приложения
МногоDataMining проблемможетбыть
выраженочерезпоискпохожихобъектов:
– определениеплагиата
– поисксайтов-зеркал
– пользователиспохожимимнениями
10
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Приложениявweb
– Сайты-зеркалаили«почти»зеркала
– Плагиат,включаябольшиечастицитирования
– Сегментыsoft404
– Похожиеновостинановостныхсайтах
• Кластерновостейнаоднутему
• Можетотражатьважностьсамойновости
– Дубликатыизображений
11
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Триосновныхэтападля
определенияпохожихдокументов
• Shingling :преобразованиедокументов во
множества(sets)
• Minhashing :преобразованиебольших
множестввкороткиесигнатуры,сохраняя
степеньпохожести
• Приемыдлямасштабирования
12
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Основнаясхема
Грубое
Разделение
Доку
мент
Множество
строкдлиной
k которые есть
вдокументе.
Сигнатуры:
Небольшие
векторачисел,
которыепредставляют
множества
иотражаютих
похожесть.
Пары
кандидатов:
Тепары
кандидатов
которыемы
должныпроверитьна
похожесть.
13
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Shingles
14
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Shingles (Шинглы)
• k-shingle (или k-gram)длядокументаесть
последовательностьизk символов,которые
встречаютсявдокументе.
• Пример:k=2;doc=abcab.Множество из 2shingles={ab,bc,ca}.
– Опционально:рассматриватьшинглы как«мешок»
исчитать ab дважды.
• Представитьдокументкакмножествоkshingles.
15
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Shingles& Similarity
• Документы,которыеимеютмногоодинаковых
шинглов,содержатпохожийтекст. Даже,если
текстовыефрагментынаходятсявдругомпорядке.
• Изменениесловаменяютk-шинглы толькона
расстоянииkотслова
• Внимание:выдолжнывыбрать k довольно
большим,иначебольшинстводокументовбудут
содержатьбольшинствошинглов.
– k=5длякороткихдокументов;k =10длябольших
16
Основнаямодельданных:
Множества
•
•
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Многиезадачиопределенияпохожестимогут
бытьсформулированыкакпоиск
подмножествнекоторогоуниверсального
множества,которыеимеетбольшуюстепень
пересечения.
Примеры включают:
1. Документы,представленныекакихмножества
шинглов
2. Похожиеклиентыилитовары
17
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
ОтМножествк БулевойМатрице
• Строки =элементыуниверсального
множества.
• Напр.,множествовсехk-шинглов
• Колонки =множества.
• 1встрокедляэлементаe идляколонки
множества S тогдаитолькотогда,когда e
являетсячленоммножестваS.
18
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Ввидематрицы
a
b
c
d
e
f
g
h
S
1
1
1
0
1
1
0
0
T
1
0
0
1
0
1
1
1
U
0
1
0
0
1
0
0
0
V
1
1
1
0
0
1
1
1
W
0
0
0
1
1
1
1
0
S={a,b,c,e,f}T={a,d,f,g,h}U={b,e}
V={a,b,c,f,g,h}W={d,e,f,g}
19
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Документыввидематрицы
• Строки =шинглы
• Колонки =документы
• 1встроке r,колонке c ттт документы c
содержитшингл r
• Ожидается,чтоматрицабудетразреженная
20
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Чутьвсторону…
• Необязательнопредставлятьданныекак
бинарнуюматрицу
• Разреженныематрицыобычнолучше
представлятькакспискиэлементов,где
значениянеравны0
– Напр.,фильмы,которыесмотрел
пользователь
• Носточкизрениявизуального
представленияматрицыболеенаглядны
21
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Похожестьколонок
• Помним:колонкаэтомножествострок,в
которыхвыставленозначение1
• Jaccard similarity колонок C1 и C2 =Sim (C1,C2)
=отношениеразмеровпересеченияи
объединенияC1 и C2.
– Sim (C1,C2)=|C1∩C2|/|C1∪C2|.
22
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Пример:КоэффициентЖаккара
C1
0
1
1
0
1
0
C2
1
*
0
*
1 **
0
1 **
*
1
Sim (C1,C2)=
2/5=0.4
23
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Ура!Практика
24
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
ПоискдубликатовHTML-документов
• Дано: множествоHTML-документов
• https://cloud.mail.ru/public/67wf/xZcb39udo
• seminar.tgz
• Необходимонайтидубликатыметодомшинглов
html2text:
$ sudo pip install html2text
25
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
ПоискдубликатовHTML-документов
1.
2.
3.
4.
Получаемтекст(src/htmlparse.py)
Извлекаемслова
Считаемшинглы
Сверяеммеждусобойнаходякоэфф.Жаккара
1. порог=60%
26
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Продолжим!
•
•
•
•
•
•
Видыдубликатов
Shingling
Ура! Каникулы Практика!
Minhashing
Алгоритмдляколлекций
ДЗ
27
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Shingles:Опциясжатия
• Длясжатиядлинныхшинглов мыможем
хешировать их,напр.,в 4байта.
• Представимдокументовкакмножество
значений-хешей отk-shingles.
• Двадокументамогут(редко)иметь
якобы общиешинглы,хотяпофакту
совпадаюттолькохеши.
28
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Shingles:почемухэши?
•
•
•
•
Множествосочетанийбуквязыкамало
Хэш увеличивает «плотность»информации
Счисламиработатьпроще
murmurhash
– Python:mmh3
29
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
План:Поискпохожихколонок
1. Посчитатьсигнатурывсехколонок.
2. Проверитьпарысигнатурчтобынайти
похожие.
– Важно:корреляциямеждупохожестью
сигнатуриколонок.
3. Опционально:проверить,чтоколонкис
похожимисигнатурамидействительно
похожимеждусобой.
30
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Сигнатуры
•
Основнаяидея:хешироватькаждую
колонку C внебольшую сигнатуру Sig
(C)так,что:
1. Sig(C)достаточномалачтобымымогли
разместитьсигнатурувОЗУдлякаждой
колонки.
2. Sim (C1,C2)естьтоже,чтои“похожесть”
между Sig (C1)и Sig (C2).
31
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Иэтоидея,котораянеработает
• Выбрать100произвольныхстрокипусть
сигнатураколонкиC будет100бит из C вэтих
строках.
• Т.к.матрицаразреженная,томногоколонок
будутиметьвид 00...0вкачествесигнатуры,
чтоприведетк Коэф.Жаккара= 0,потомучто
их‘1’ будутвразныхстроках.
32
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Четыретипастрок
• Дляданныхколонок C1 и C2,строкимогут
следующими:
C1
a 1
b 1
c 0
d 0
C2
1
0
1
0
• Также,A =#строктипа a ит.д.
• Заметим,что Sim (C1,C2)=A /(A +B +C )
33
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Minhashing
34
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Minhashing
• Представим,чтострокислучайно
переставлены
• Определим “hash”функцию h (C )=индекс
первой(впереставленномпорядке)строкигде
C равно 1
• Используемнесколько(напр.100)
независимыхhash-функцийчтобысоздать
сигнатуру
35
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Minhashing, пример
Входнаяматрица
Матрицасигнатуры M
1 4 3
1
0
1
0
2
1
2
1
3 2 4
1
0
0
1
7 1 7
0
1
0
1
2
1
4
1
6 3 6
0
1
0
1
1
2
1
2
2 6 1
0
1
0
1
5 7 2
1
0
1
0
4 5 5
1
0
1
0
36
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Неожиданноесвойство
• Вероятностьтого (средивсех
перестановокстрок), что h (C1)= h (C2)–
этотожесамое,чтоиSim (C1,C2).
• Дляобеих A /(A +B +C )!
• Почему?
– Просматриваемсверхувнизколонки C1 и C2
поканеувидим1.
– Еслиэтастрокатипаa,значитh (C1)=h (C2).
Еслистрокатипаb или c,тонет.
37
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Похожестьсигнатур
• Степеньпохожестисигнатуресть долястрок,
гдеонисовпадают.
– Помним,чтокаждаястрокасоответствует
перестановкеили“hash-функции”.
– Т.о.ожидаемаясхожестьдвухсигнатурравнакоэфф.
Жаккара колонокилимножествупредствленных
сигнатур
– Ичемдлиннеесигнатура,темменьшебудет
ошибка
38
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
MinHashing – Пример
Входнаяматрица
Матрицасигнатур M
1 4 3
1
0
1
0
2
1
2
1
3 2 4
1
0
0
1
7 1 7
0
1
0
1
2
1
4
1
6 3 6
0
1
0
1
1
2
1
2
2 6 1
0
1
0
1
5 7 2
1
0
1
0
4 5 5
1
0
1
0
Similarities:
1-32-41-23-4
Col/Col 0.750.7500
Sig/Sig 0.671.0000
39
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
СигнатурыMinhash
• Выбрать,скажем, 100произвольных
перестановокстрок.
• РассматриватьSig (C)каквектор
колонки.
• Пусть Sig (C)[i]=
согласноi-й перестановке,индекспервой
строкигдеесть1вколонкеC.
40
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Реализация– (1)
• Пустьунасесть1Млрд.строк
• Сложновыбратьслучайную
перестановкудля1Млрд
• Представлениеслучайнойперестановки
требуетеще1Млрд.записей
• Доступкстрокамвслучайномпорядке
ведетдеградациипроизводительности
41
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Ксловуодеградации
Необходимопосчитатьсуммучиселв1Gb
Каковаразницамеждуподходами?
• Линейно
• Блокамипо1Mb
• По4байта
• А на SSD?
42
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Ксловуодеградации
Обычновсенетакплохо
1. Pagecache
2. Чтениевсегдаидетблоками
• Блокамиустройства
• readahead драйвера
• …можносимулироватьсO_DIRECT
43
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Реализация– (2)
•
•
Хорошаяаппроксимациядляперестановки
строк:выбрать “100”hash-функций
Длякаждойколонкиc икаждойhashфункции hi ,записать “слот”M(i,c)дляэтого
значенияminhash
44
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Реализация– (3)
for eachrowr
for eachhashfunctionhi do
computehi(r)
for eachcolumnc
if chas1inrowr
for eachhashfunctionhi do
if hi(r)isasmallervaluethanM(i,c)
then
M(i,c):=hi(r );
45
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Пример
Row
1
2
3
4
5
C1
1
0
1
1
0
C2
0
1
1
0
1
h(x)=x mod5
g(x)=2x+1mod5
Sig1
Sig2
h(1)=1
g(1)=3
1
3
-
h(2)=2
g(2)=0
1
3
2
0
h(3)=3
g(3)=2
1
2
2
0
h(4)=4
g(4)=4
1
2
2
0
h(5)=0
g(5)=1
1
2
0
0
46
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Реализация– (4)
• Еслиданныехранятсяrow-by-row,тогданужен
толькоодинпроход.
• Еслиданныехранятся column-by-column
– Напр. Данныеэтопослед-тьдокументов
топредставитьих какпарыrow-column и
отсортироватьпостроке.
– Уменьшимстоимостьзатратнарасчетhi (r )
множествораз.
47
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Доп.примеры:Использование
Minhashing
• Обычныйпаттерн:поискмножествс
относительнобольшимпересечением.
• Напр.пользователькино-сайта,укоторого
естьсписокфильмов,которыеонсмотрел.
• Пользователиспохожимивкусамибудут
иметьдовольнобольшуюобщуюдолю
такихжефильмов.
48
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Minhashing дляшинглов
Эскизкакстабильнаявыборкашинглов
Длямножествашинглов W
  ,   ≥ 
MINs  = #
, ℎ
MODs(W)– наборэлементовW,такихчто0mods
s– размер«эскизадокументов»
49
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Minhashing дляшинглов (2)
W1
W2
W3
W4
W5
W6
…
sorted
Wi%N
W1
W6
W2
W3
…
50
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Алгоритмдляколлекций
• Реализациясравнения«влоб»обладает
O(n2)затратамиповремени
• Применимадляфинальныхстадийпосле
содания кластеров
51
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
АлгоритмБродера
1. Считаем«эскизы»документов
2. Сортируемпары<шингл,docid>
3. Генерируемпарыпересечений:
1. ID,ID,1
2. УпорядоченыпоID
4. Подсчитываемсумму:
1. ID,ID,count
2. count>threshold?
52
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Многообщихшинглов
Из-заобщихшинглов этап3->4можетбыть
O(n2) попамяти/диску
Локальныйхарактер
53
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Многообщихшинглов
Можем
пренебречь
такимислучаями
54
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Подведемитог
1.
2.
3.
4.
Видыдубликатов
Shingling
Minhashing
Алгоритмдляработысколлекциями
55
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Чтоосталосьзакадром
1. Уточнениеконтента:
1. Вырезание обвязки
2. Вычленениесодержимого
2. Нормализациядокументов
3. Другиеподходы длябольшогоweb
4. Вопросыполнотыиточностиалгоритмов
56
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
ДЗ:поискдубликатовпоколлекции
• ДаноКоллекциядокументов HTML
– чтение– zcat …|src/docreader.py
• Необходимонайтидубликатыалгоритмом
Бродера
• Результат:
– Списокпардокументов(u1 u2 similarity)stdout
• Полноевремя:20мин
• Ограничениепамяти:4Gb
– Анализрезультата (всвободнойформе)
57
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
ДЗ:формат
• Сроксдачи:до23марта
• Письмо:
– To:ir-ts@ml.corp.mail.ru
– Subject:[Ir-ts]ДЗ№2,ИванИванов BD-22
• Будетпроверятся:
– Автоматически навыборкеx5..x10
– Сверяетсяколичество дубликатов(~)
– Проверяетсясхожестьдокументов
58
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
ДЗ:формат(2)
• ./preinstall.sh
– считайтечтоестьroot
– Беспарольный sudo
• ./run.sh path/to/dataset/*.gz
• Ужеесть:
– Linuxx86_64,Python2.7
– html2text,mmh3
– Googleprotocolbuffers
59
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Литература:
1.
2.
3.
4.
5.
6.
7.
JureLeskovec,Anand Rajaraman,JeffreyD.Ullman,Mining ofMassiveDatasets,
pages73-83 2010
A.Broder.Ontheresemblanceandcontainmentofdocuments.Compression
andComplexityofSequences(SEQUENCES'97),pages21-29.IEEEComputer
Society,1998
N.Heintze.Scalabledocument fingerprinting. InProc.ofthe2ndUSENIX
Workshop onElectronicCommerce,Nov.1996
A.Broder, S.Glassman,M.Manasse andG.Zweig.Syntacticclusteringofthe
Web.Proc.of the6thInternationalWorld WideWebConference, April1997
Manber U.Finding SimilarFilesinaLargeFileSystem,TR93-33,October1993
Google protocol bufferforPython, https://developers.google.com/protocolbuffers/docs/pythontutorial
Perfomance testingwithO_DIRECTinLinux.Emailarchive@
http://yarchive.net/comp/linux/o_direct.html
60
ЛЕКЦИЯ5:ПОИСКДУБЛИКАТОВВWEB
Спасибо!
Вопросы?
Автор
tekhnostrim
Документ
Категория
Презентации
Просмотров
40
Размер файла
3 951 Кб
Теги
лекция
1/--страниц
Пожаловаться на содержимое документа