[發明專利]基于數據相似的平衡聚類壓縮方法

有效

• 申請號: 200910095378.3
• 申請日: 2009-01-12
• 公開（公告）號: CN101464910A
• 公開（公告）日: 2009-06-24
• 發明（設計）人: 陳剛;陳珂;余利華;胡天磊;壽黎但
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務所有限公司
• 代理人: 周 烽

1.一種基于數據相似的平衡聚類壓縮方法，其特征在于，包括以下步驟：

(1)文件特征向量提取，從文件數據中提取特征向量用于計算文件相似度；

(2)聚類樣本選取，即從輸入數據集D中選取部分數據作為樣本數據集，即樣本數據集為S；

(3)樣本數據聚類，利用平衡聚類方法聚類樣本數據集S，具體為：

(A)根據樣本數據集S構建相似圖G，并滿足如下條件：(i)V是頂點集，任意v∈V對應到唯一的一個數據d(v)∈S；每個頂點v有一個權重WV(v)，且WV(v)＝d(v).len；(ii)E是邊集，任意(x，y)∈E都有一個權重WE(x，y)，且WE(x，y)＝r(d(x)，d(y))；

(B)調用圖分割方法kmetis分割相似圖G，并為設置kmetis設定兩個約束條件：

約束1：圖分割方法需要刪除相似圖中的一些邊，方法必須最小化刪除邊的權重和，約束1要求分割出來的每個子圖中的數據之間具有高相似度，而跨子圖數據之間只有低相似度；

約束2：分割方法還必須滿足平衡約束條件，即平衡每個子圖的頂點權重和；

(4)剩余數據聚類，按照相似度歸類剩余數據X＝D-S，在滿足負載均衡約束的前提下，把剩余數據歸入到最相似的類；

(5)結果壓縮，對每個類別進行單獨壓縮，默認采用BMCOM壓縮方法，同時亦可采用各種成熟的DELTA壓縮方法。

2.根據權利要求1所述基于數據相似的平衡聚類壓縮方法，其特征在于，所述步驟(1)具體為：

(A)選擇一個窗口長度w和k個整數域上的獨立置換函數{h₁，h₂，…，h_k}，每個置換函數相互獨立；

(B)從前往后逐字節掃描輸入文件f，利用高效的Rabin指紋函數，計算當前滑動窗口內數據的指紋，記該指紋為fp，利用上述k個獨立置換函數作用于指紋fp，得到k個置換指紋h₁(fp)，h₂(fp)，…，h_k(fp)，記文件f的特征向量F(f)為{F₁(f)，F₂(f)，…，F_k(f)}，特征向量的第i維F_i(f)等于第i個置換函數所產生的置換指紋的最小值，即F_i(f)＝MIN(F_i(f)，h_i(fp))；

(C)掃描完整個文件之后，可計算出文件的特征向量F(f)，文件數據相似度r(x，y)根據文件x和y的特征向量定義為|F(x)∩F(y)|/|F(x)∪F(y)|。