[發明專利]一種基于MapReduce的大型數據集聚類方法

有效

• 申請號: 201811602303.5
• 申請日: 2018-12-26
• 公開（公告）號: CN109858518B
• 公開（公告）日: 2021-07-06
• 發明（設計）人: 程國艮;李欣杰
• 申請（專利權）人: 中譯語通科技股份有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京萬貝專利代理事務所(特殊普通合伙) 11520
• 代理人: 馬紅

1.一種基于MapReduce的大型數據集聚類方法，其特征在于，所述基于MapReduce的大型數據集聚類方法包括：

從分類器中的各訓練子集關系中獲得內聯相似度矩陣，并通過并行Lanczos-QR算法求解矩陣特征值所對應的特征向量實現數據的高維約簡和低維嵌入；

采用并行 AP聚類算法將所有數據點作為潛在的聚類中心，在相似度矩陣的基礎上通過消息傳遞進行聚類，確定聚類中心；

計算外圍數據點與聚類中心距離；首先，按逆時針方向分別建立源數據P和目標數據Q的特征矩陣P_E和Q_E：

P_E ＝[P₁^TP₂^T_…P_2N－1^T P_2N ^T ];

Q_E ＝[Q₁^TQ₂^T_…Q_2N－1^T Q_2N ^T ];

歐式距離公式d(x,y)和夾角余弦公式sim(x,y)如下：

以d(x,y)和為sim(x,y)基礎，重新定義兩個矩陣D和S,使:

；

求出D和S中的最小值；

分別令Eu_e=min{D_ij}, 1≤i≤j=2N;Sim_e=max{S_ij}, 1≤i≤j=2N;

然后再按順序針方向構造數據P和Q的特征矩陣，重復上述計算方法，求出兩特征矩陣中最完備向量間的最小值Eu_c和Sim_c；

最后令Eu=min{Eu_e，Eu_c};

Sim=min{ Sim_e，Sim_c };

Eu和Sim即為P、Q兩數據對應最相似向量的歐式距離和最大相和系數；最終獲得計算外圍數據點與聚類中心的準確距離；

基于MapReduce并行計算的聚類算法重新劃分聚類中心和中心點;具體包括：

步驟A，初始數據處理：對初始數據集進行處理，當數據集為大樣本時，用算法對其進行壓縮，得到新的數據集；

步驟B，數據聚類：對第一步得到的數據集利用算法進行聚類，得到類數據；

步驟C，合并聚類：對聚類好的數據，調用基于距離的過程進行處理，得出分類結果；

輸出聚類結果，建立數據模版；

從分類器中的各訓練子集關系中獲得內聯相似度矩陣前需進行：

從HDFS中讀取原始樣本；

隨機子空間分類器對原始樣本進行訓練，得到多個具有不同特征的訓練子集的分類器；

子空間的選擇是根據均勻分布U隨機抽取m個不同的子集 A={d1 , d2 , …, dm },每個子集的大小為 r, 每個子空間都定義一個映射 P A :Fn ※ F m ,在此基礎上得到每個訓練子集 Di ={(P A (x j ), y j )1 ≤j≤N}；再由分類算法得到待檢樣本的決策 hi ,重復 w次,最后利用擇多投票法得到最終決策.其中 ,子空間維數 r和基分類器的個數 k自動確定；

建立數據模版后，還需進行：

與前次數據模版建立反饋，數據模板自修正，利用規則模板解析信息模塊，根據數據集聚類準確度對臟數據進行清洗并優化信息模板庫。