[發明專利]一種異常數據檢測中譜聚類算法并行化方法及系統

在審

• 申請號: 202110325195.7
• 申請日: 2021-03-26
• 公開（公告）號: CN112988693A
• 公開（公告）日: 2021-06-18
• 發明（設計）人: 應時;周慧敏;成海龍;段曉宇
• 申請（專利權）人: 武漢大學
• 主分類號: G06F16/18
• 分類號: G06F16/18;G06F16/182;G06F16/172;G06K9/62
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 肖明洲

1.一種異常數據檢測中譜聚類算法并行化方法，其特征在于，包括以下步驟：

步驟1：將待聚類分析的數據集樣本進行數據分布式存儲；

步驟2：并行化構建數據集樣本的相似矩陣A；

從HDFS中讀取數據集樣本，將數據集樣本進行向量化，并利用開源并行計算框架Spark中的彈性分布式數據集RDD形式將向量化的數據集樣本進行存儲，然后構建數據向量空間，接著通過并行計算數據集樣本之間的相似性，生成數據集樣本的相似矩陣A；

步驟3：并行化計算相似矩陣A的拉普拉斯矩陣；

步驟4：并行化計算拉普拉斯矩陣的特征向量，獲得維度為n×d的特征向量矩陣，其中n表示樣本個數，d表示特征向量的維度；

步驟5：并行化執行K-mean聚類算法。

2.根據權利要求1所述的異常數據檢測中譜聚類算法并行化方法，其特征在于：步驟1中，將待聚類分析的數據集樣本，劃分為若干數據塊，并將這些數據塊抽象為RDD對象，將這些RDD分配給Spark集群中的若干工作節點進行存儲，存入開源分布式文件系統HDFS中。

3.根據權利要求1所述的異常數據檢測中譜聚類算法并行化方法，其特征在于：步驟2中，利用TF-IDF和余弦相似度計算兩數據元素之間的相似性，具體實現包括以下子步驟：

步驟2.1：使用TF-IDF算法的得到各數據元素的關鍵詞；

步驟2.2：選取兩個數據元素的關鍵詞構成關鍵詞集合，計算每個數據元素對于這個關鍵詞集合的詞頻，根據詞頻生成各自詞頻向量；

步驟2.3：計算兩個數據元素中詞頻向量的余弦相似度，獲得兩數據元素之間的相似性。

4.根據權利要求3所述的異常數據檢測中譜聚類算法并行化方法，其特征在于：步驟2.3中，由向量化方法得到各元素的值并構建日志向量數據，對所有數據向量與自身做笛卡爾積得到，得到向量對(v_i，v_j)，構成日志向量空間，將向量對分配到多個節點上使用相似度計算方法來并行計算數據之間的相似度，最終得到相似矩陣A。

5.根據權利要求1-4任意一項所述的異常數據檢測中譜聚類算法并行化方法，其特征在于：步驟2中，利用K最近鄰圖方法，完成對相似矩陣A的稀疏化；即對于每一個數據元素，只保存了與其最近的k個數據元素的相似性，而忽略其他數據元素的相似性；同時使用逆向合并的方法，即從鄰接矩陣中得到鄰接表，進而得知對于任意數據元素x_i與其相鄰點集合{x_j}的邊信息edges[i][j]，從{x_j}集合中每個點出發找出到x_i的邊信息edges[j][i]，綜合edges[i][j]和edges[j][i]，補充因使用k-近鄰圖所缺失的相似度數據，實現相似度矩陣的對稱化。

6.根據權利要求1所述的異常數據檢測中譜聚類算法并行化方法，其特征在于：步驟3中，利用相似矩陣A，構造出包含n個節點的圖G，圖中每個節點表示一個數據元素，每條邊的值對應相似矩陣A的元素值；算出圖G中每個節點的度，并用度矩陣D來保存計算結果；最后由相似矩陣A和度矩陣D經過并行化計算得到拉普拉斯矩陣L＝D-A。