海量文檔查同或聚類問題 -- Locality Sensitive Hash 算法 - fxjtoday的專欄 - 博客頻道 - CSDN.NET

海量文檔查同或聚類問題 -- Locality Sensitive Hash 算法

分類：
Web Data Mining
Algorithm

2011-02-22 15:56
736人閱讀
評論 (0)
收藏
舉報

?

考慮一下這個場景
,
使用網絡爬蟲高速爬取大量的網頁內容
,
如果想把這些網頁進行實時聚類
,
并從中提取每個網頁聚類的主題
.
我們應該怎么樣去做

對于普通或常見的聚類算法
,
比如
K-means,
或
Hierarchical
聚類
,
無法適用于這個常見
,
對于這些聚類算法無法進行
incremental

聚類
,
即在聚類開始前必須知道整個數據集
,
而這個場景中的數據集是隨著爬蟲不斷增多的
.
而且這些聚類算法的
performance
不夠高
,
比如對于
K-means
需要不斷的
partition
以達到比較好的聚類效果
.
所以向來聚類算法在我的印象中是低效的
,
而面對這樣一個需要實時數據遞增處理的場景
,
我們需要一種
one-shot
的高效算法
,
接收到網頁內容
,
迅速判斷其類別
,
而不用后面不斷地
revisit
或
recluster.

首先介紹下面這個聚類方法



Leader-Follower Clustering (LFC)


The algorithm can be described as follows:

If distance between input and the nearest cluster above threshold, then create
new cluster for the input.

Or else, add input to the cluster and update cluster center.


其實這個聚類方法再簡單不過了
,
我是先想到這個方法
,
然后才發現這個方法有這么個看上去蠻牛比的名字
.


有了這個方法
,
當新網頁來的時候
,
和所有老的網頁形成的聚類算下相似度
,
相似就歸到這類
,
不相似就創建新類

這個過程當中有個經典問題
, KNN

問題

(K-Nearest Neighbor)

.



面

對海量數據
,
而且是高維數據
(
對于文本
feature
一般是選取文本中的
keywords,
文本中的
keywords
一般是很多的
), KNN
問題很難達到線性
search
的
,
即一般是比較低效的
.
這樣也沒辦法達到我們的要求
,
我們需要新的方法來解決這個
KNN
問題

當然該牛人出場了
,
他提出了一種算法



Locality Sensitive Hash(LSH)



這個算法的效果是
,
你可以把高維向量
hash
成一串
n-bit
的數字
,
當兩個向量
cosin
夾角越小的時候
(
即他們越相似
),
那么他們
hash
成的這兩串數字就越相近
.


比較常用的
LSH
算法是下面這個



Charikar's simhash



Moses S. Charikar. 2002. Similarity estimation techniques from rounding
algorithms. In STOC ’02: Proceedings of the thiry-fourth annual ACM symposium
on Theory of computing, pages 380–388, New York, NY, USA. ACM.

用
LSH
算法怎么樣來解決高維數據的
KNN
問題了
,
我們可以參考
Google
在
WWW2007
發表的一篇論文
“Detecting near-duplicates for web crawling”,
這篇文章中是要找到
duplicate
的網頁
,
和我們的問題其實是同一個問題
,
都是怎樣使用
LSH
解決
KNN
問題

分兩步
,


第一步
,
象我們上面說的那樣
,
將文檔這樣的高維數據通過
Charikar's simhash


算法轉化為一串比特位
.
對于
Google
的問題
,

We experimentally validate that for a repository of 8 billion webpages, 64-bit
simhash fingerprints and k = 3 are reasonable.


就是對于
80
億的文檔
,
我們把每個文檔轉化為
64-bit
的
simhash fingerprints,
當兩個
fingerprints
有
k = 3
位不同時
,
我們就認為這兩個文檔不相同
.

Charikar's simhash is a dimensionality reduction
technique
. It maps high-dimensional vectors to small-sized fingerprints.


其實
LSH
算法的基本原理就是
,
把一個多維空間上的點投影到一個平面上
,
當多維空間中的兩個點在平面上的投影之間距離很近的時候
,
我們可以認為這兩個在多維空間中的點之間的實際距離也很近
.
但是
,
你想象一下
,
你把一個三維球體中的兩個點投影到一個隨機平面上
,
當投影很靠近的時候
,
其實那兩個點不一定很靠近
,
也有可能離的很遠
.
所以這兒可以把兩個點投影到多個隨機平面上
,
如果在多個隨機平面上的投影都很靠近的話
,
我們就可以說這兩個多維空間點之間實際距離很近的概率很大
.
這樣就可以達到降維
,
大大的減少了計算量
.

算法過程如下
,
其實挺好理解的



Computation:

Given a set of features extracted from a document and their corresponding
weights, we use simhash to generate an f-bit fingerprint as follows.

We maintain an f-dimensional vector V, each of whose dimensions is initialized
to zero.

A feature is hashed into an f-bit hash value.

These f bits (unique to the feature) increment/decrement the f components of
the vector by the weight of that feature as follows:

ü?? if the i-th bit of the hash value is 1, the i-th component of V
is incremented by the weight of that feature;

ü?? if the i-th bit of the hash value is 0, the i-th component of V
is decremented by the weight of that feature.

When all features have been processed, some components of V are positive while
others are negative. The signs of components determine the corresponding bits
of the final fingerprint.

For our system, we used the original C++ implementation of simhash, done by
Moses Charikar himself.

第二步
, HAMMING DISTANCE PROBLEM

第一步把所有文檔都變成
64-bit
的
fingerprints,
那么面對幾十億的
fingerprints,
怎么樣能快速找到和目標
fingerprint
相差
k
位的所有
fingerprint
了
.


其實這就是個對于
hamming distance
的
KNN
問題
,

Definition: Given a collection of f-bit fingerprints and a query fingerprint F,
identify whether an existing fingerprint differs from F in at most k bits.

漢明距離

(hamming distance)





在信息論中，兩個等長字符串之間的漢明距離是兩個字符串對應位置的不同字符的個數。換句話說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數




可見
,
對于
hamming
距離
,
不是簡單的通過排序索引就可以解決的

說兩個簡單的方法
,
雖然不可行
,
但也是一種思路




耗費時間的方法



Build a sorted table of all existing fingerprints


對于給定的
F,
找出所有
Hamming distance from F is at most k
的
fingerprint
然后去
table
里面搜索
,
看有沒有



For 64-bit _ngerprints and k = 3, we need C ₆₄
³
= 41664
probes.
這樣查找時間太長了
.

耗費空間的方法




還有個辦法就是空間換時間
,
對現有的每個
fingerprints,
先事先算出所有和它
Hamming distance
小于
3
的情況
,
但這種方法預先計算量也太大了
,
如果現有
n
個
fingerprint,
就需要算
41664*n.


可見用傳統的方法是很難高效的解決這個問題的
.

那么怎么辦
,
有什么辦法能夠在海量的
F bit
的向量中
,
迅速找到和查詢向量
F ′
只差
k bit
的向量集合了



We now develop a practical algorithm that lies in between the two approaches
outlined above: it is possible to solve the problem with a small number of
probes and by duplicating the table of fingerprints by a small factor.


我們需要一種介于上面兩種比較極端的情況的方法
,
耗些時間
,
也耗些空間
,
但都不要太多
......

設想一下對于
F bit,
可以表示
2 ^F

個數值
,
如果這兒我們完全隨機產生
2 ^d

個
F bit
的數
,
當
d<<F
時
,
這些隨機數值的高
d
位重復的應該不多
,
為什么
,
這些數值是完全隨機產生的
,
所以應該相對均勻的分布在
2 ^F

大小的空間里
,
如果完全平均生成
2 ^d

個數
,
那么每個數的高
d
位都是不同
.
但是這兒是隨機產生
,
所以會有些數的高
d
位是相同的
,
不過數量不會多
.
所以這邊就可以把高
d
位作為計數器
,
或索引
.
這個假設是這個方法的核心
,
有了這個假設
,
不難想到下面怎么做
...

首先對現有的所有
fingerprints
進行排序
,
生成有序的
fingerprints
表




選擇一個
d ′,
使得
|d ′-d|
的值很小
(
就是說你選擇的這個
d’
和
d
只要差的不多
,
都可以
),
因為表是有序的
,
一次檢測就能夠找出所有和
F ′
在最高的
d ′
位相同的指紋
,
因為
|d ′-d|
的值很小
,
所有符合要求的指紋數目也比較小
,
對于其中的每一個符合要求的指紋
,
我們可以輕易的判斷出它是否和
F
最多有
K
位不同
(
這些不同很自然的限定在低
f-d ′
位
)
。

上面介紹的方法幫我們定位和
F
有
K
位不同的指紋
,
不過不同的位被限定在低
f-d ′
位中。這對大部分情況來說是合適的
,
但你不能保證沒有
k
位不同出現在高
d
位的情況
.
為了覆蓋所有的情況
,
采用的方法就是使用一種排序算法
π,
把當前的
F bit
隨機打亂
,
這樣做的目的是使當前的高位
bit,
在打亂后出現在低位
bit,
然后我們再對打亂后的表排序
,
并把
F ′
用相同的排序算法
π
打亂




再重復我們上面的過程
,
來查找低
f-d ′
位上
k
位不同的情況




這樣當我們多使用幾種排序算法
π,
重復多次上面的過程
,
那么漏掉
’k
位不同出現在高
d
位
’
的情況的概率就會相當的小
,
從而達到覆蓋到所有情況

還有個問題
,
這兒的假設是
, 2 ^d

個數是隨機產生的
.
那么我們這兒的
fingerprints
是基于
hash
算法產生的
,
本身具有很大的隨機性
,
所以是符合這個假設的
.
這點原文
4.2 Distribution of Fingerprints
有相應的實驗數據
.

假設
f=64,k=3,
那么近似網頁的指紋最多有
3
位不同。假設我們有
8B=2 ³⁴

的已有指紋
,
即
d=34
。




我們可以生成
20
個有序排列表
(
即使用
20
種不同的排列算法打亂原
fingerprint,
并生成有序表
),
方法如下
,?


把
64
位分成
6
塊
,
分別是
11,11,11,11,10
和
10
位。共有
C(6,3)=20
種方法從
6
塊中選擇
3
塊。對于每種選擇
,
排列
π
使得選出的塊中的位成為最高位
. d ′
的值就是選出的塊中的位數的總和。因此
d ′=31,32,
或者
33 (
和
d
差的不多
).
平均每次檢測返回最多
2 ^34~31

個排列后的指紋。實際應該不會很多

你也可以用
16
個表
,
或更少
,
但使用的表越少
,
必須
d
的取值也越少
,
這樣最后需要驗證的
fingerprint
就越多
,
這兒就有個時空的平衡
,
時間和空間不可兼得
.

說到這兒大家是不是已經被這個復雜的方法給搞暈
, Google
的這個方法是為了在幾十億篇文章中發現相同的文章
,
相對的精確性要求比較的高
,
如果為了我們的初衷
,
進行文本聚類的話
,
我們不需要用
64-bit
來進行
hash,

也許可以用
16bit,
這個可以通過實驗來選擇
,
為了避免復雜的漢明距離問題
,
只當兩個文章的


fingerprint

完全一致時才認為他們屬于一類
,
隨著用更少的位數來進行
hash,
這個應該是可行的
,
不過需要具體的實驗證明

海量文檔查同或聚類問題 -- Locality Sensitive Hash 算法