[發明專利]一種分布式數據流聚類方法及系統

有效

• 申請號: 201210365295.3
• 申請日: 2012-09-26
• 公開（公告）號: CN102915347B
• 公開（公告）日: 2016-10-12
• 發明（設計）人: 吳世忠;曲武;李世賢;王君鶴;偰賡;陳巍
• 申請（專利權）人: 中國信息安全測評中心;北京啟明星辰信息安全技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京安信方達知識產權代理有限公司 11262
• 代理人: 栗若木;曲鵬

1.一種分布式數據流聚類方法，包括：

對數據流進行概要處理，獲得數據流的多個特征向量；

利用位置敏感哈希算法獲得各自包含有至少一個特征向量的多個聚類簇，并從中選取至少一個聚類簇作為候選聚類簇；

周期地使用所述候選聚類簇對新到的數據流的特征向量進行聚類處理。

2.根據權利要求1所述的方法，其中，利用位置敏感哈希算法獲得各自包含有至少一個特征向量的多個聚類簇，并從中選取至少一個聚類簇作為候選聚類簇，包括：

利用所述位置敏感哈希算法對所述多個特征向量進行哈希處理，獲得位置敏感哈希數據結構，得到位置敏感哈希映射值；

對所述位置敏感哈希映射值進行二次哈希，得到一維索引值，落入相應的哈希桶中；

使用Top-k算法從包含有至少一個特征向量的哈希桶中選取包含特征向量最多的前k個哈希桶作為所述候選聚類簇；所述k大于等于1。

3.根據權利要求2所述的方法，利用所述位置敏感哈希算法對所述多個特征向量進行哈希處理，包括：

采用至少一個位置敏感哈希函數族對所述多個特征向量進行所述哈希處理；

其中，每個所述位置敏感哈希函數族由從穩態分布位置敏感哈希函數族中以獨立、一致隨機的方式選擇出的多個位置敏感哈希函數運算構成。

4.根據權利要求1所述的方法，其中，周期地使用所述候選聚類簇對新到的數據流的特征向量進行聚類處理，包括：

獲得所述候選聚類簇各自的質心；

周期地計算所述新到的數據流的特征向量到所有質心的距離范數；

將所述新到的數據流的特征向量歸到所述候選聚類簇的其中一個之中，或者為新到的數據流建立新的聚類簇。

5.根據權利要求4所述的方法，獲得所述候選聚類簇各自的質心，包括：

采用X-median算法獲得所述候選聚類簇各自的質心。

6.根據權利要求4所述的方法，其中，將所述新到的數據流歸到所述候選聚類簇的其中一個之中，或者為新到的數據流建立新的聚類簇，包括：

根據預設的距離閾值將所述新到的數據流的特征向量歸到距離最小的質心所在的候選聚類簇中，或者為所述新到的數據流的特征向量建立新的聚類簇。

7.根據權利要求6所述的方法，根據預設的距離閾值將所述新到的數據流的特征向量歸到距離最小的質心所在的聚類簇中，或者為所述新到的數據流的特征向量建立新的聚類簇，包括：

所述新到的數據流的特征向量到所述候選聚類簇各自的質心的最小距離小于所述預設的距離閾值時，將所述新到的數據流的特征向量歸到所述距離最小的質心所在的聚類簇中，否則為所述新到的數據流的特征向量建立所述新的聚類簇。

8.一種分布式數據流聚類系統，包括：

在線組件，配置為對數據流進行概要處理，獲得數據流的多個特征向量，利用位置敏感哈希算法獲得各自包含有至少一個特征向量的多個聚類簇，并從中選擇至少一個聚類簇作為候選聚類簇；

離線組件，配置為周期地使用所述候選聚類簇對新到的數據流的特征向量進行聚類處理。

9.根據權利要求8所述的系統，其中，所述在線組件包括：

概要處理模塊，配置為對數據流進行概要處理，獲得數據流的多個特征向量；

一次哈希模塊，配置為利用所述位置敏感哈希算法對所述多個特征向量進行哈希處理，獲得位置敏感哈希數據結構，得到位置敏感哈希映射值；

二次哈希模塊，配置為對所述位置敏感哈希映射值進行二次哈希，得到一維索引值，落入相應的哈希桶中；

聚類簇選取模塊，配置為使用Top-k算法從所有哈希桶中選取包含特征向量最多的前k個哈希桶作為所述候選聚類簇；所述k大于等于1。

10.根據權利要求9所述的系統，其中：

所述一次哈希模塊配置為采用至少一個位置敏感哈希函數族對所述多個特征向量進行所述哈希處理；

其中，每個所述位置敏感哈希函數族由從穩態分布位置敏感哈希函數族中以獨立、一致隨機的方式選擇出的多個位置敏感哈希函數運算構成。