[發明專利]基于分布式計算平臺的層次聚類改進方法

在審

• 申請號: 201710403380.7
• 申請日: 2017-06-01
• 公開（公告）號: CN107291843A
• 公開（公告）日: 2017-10-24
• 發明（設計）人: 肖甫;劉磊;王少輝;沙樂天;王汝傳
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京知識律師事務所32207
• 代理人: 張芳

技術領域

本發明屬于大數據聚類算法技術領域，特別是基于分布式計算平臺的層次聚類方法。

背景技術

BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)自其產生就受到了廣泛的關注，它克服了凝聚聚類方法所面臨的兩個困難：(1)可伸縮性；(2)不能撤銷先前步驟所做的工作。聚類算法BIRCH來源于Zhang、Ramakrishnan和Livny的工作，他們創建的BIRCH算法的最終結果是建立一棵類似B樹的聚類特征樹。聚類特征CF(Cluster Feature)是BIRCH算法的核心概念。CF正是采用三元組(N，LS，SS)的方式才達到了壓縮數據集的效果，從而使BIRCH算能夠在有限的內存和低IO開銷的情況下得以運行。也正是源于BIRCH算法的這些優勢，越來越多的研究者也將目光投向了BIRCH算法的并行化研究。

隨著大數據技術的快速發展和日漸成熟，目前的BIRCH算法還是無法解決將散列數據聚合成統一的簇，仍依賴于輸入數據的順序，亟待一個良好的算法來解決這個存在的問題。

發明內容

本發明的目的是提供一種適用于對大數據聚類的性能提高的有效執行方法，以實現在當今大數據時代對大數據挖掘聚類進行更精準性的操作，對以前的BIRCH聚類算法輸入數據的處理，保證聚類的準確及離群點處理。

基于分布式計算平臺的層次聚類改進方法，包括，

S1、主節點和從節點上分別安裝有Hadoop和Spark集群，通過HDFS獲取數據；

S2、采用K-均值算法將數據聚類為N個簇，N的范圍為3～5的正整數；

S3、對N個簇進行全排列，形成順序不同的N！個序列，再利用BIRCH算法在Spark平臺上計算，Spark平臺利用分區的調配，并行化進行計算；

S4、對S3的計算結果根據數據簇的緊密性進行篩選，保留數據簇緊密性最好且離群點個數最少的一組數據，所述數據簇的緊密性指計算數據簇的中心點到數據簇各個點的距離和。

S3中所述利用BIRCH算法在Spark平臺上計算的具體過程為：程序被提交到Spark平臺后，為程序分配資源，將程序轉換并執行，程序中有多個任務，每個任務根據數據集的寬依賴關系切分為若干Stage，每個Stage中包含一組Task，每個Task對應一個分區，最后Task被封裝好后放入Executor的線程池中進行并行化計算。

本發明是一種適用于數據挖掘算法中層次聚類算法的改進優化方案，該方案基于K-均值算法和BIRCH算法，首先對聚類數據使用K-均值算法進行聚合分類，然后對處理后的數據進行分簇排序，最后再利用BIRCH算法進行聚合，從而增強數據聚合的質量，提高聚合效率。為大數據聚類再次打下基礎。

附圖說明

圖1為本發明基于分布式計算平臺的層次聚類改進方法流程圖；

圖2為圖1實施例中并行化處理流程圖。

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對本發明進行進一步詳細說明。應當理解，此處所描述的具體實施例僅僅用以解釋本發明，并不用于限定本發明。

該基于Spark平臺的針對于BIRCH算法進行改進的方案，包含在以下具體步驟中：

步驟1、數據來源：平臺包括安裝有Ubuntu系統的虛擬機集群，共三臺主機，一個主節點，兩個從節點。

步驟2、主節點和從節點分別安裝Hadoop和Spark集群，程序從HDFS上獲取給定的實驗數據。

步驟3、針對讀取的數據，首先利用K-均值算法，將數據粗略的聚類為N個簇，其中N為引入的參數，對于N的取值，取3,4,5最合適。

步驟4、針對N個簇，對數據進行全排列，形成順序不同的N！個序列。

步驟5、將N！個序列依次利用BIRCH算法在Spark平臺上計算，Spark平臺利用分區的調配，并行化進行計算。

步驟6、記錄計算后的結果，進行比較篩選。保留聚類效果最好的一組數據。

步驟2-2中對K-均值算法的結果進行全排列，獲取到數據的所有排列序列，最后利用BIRCH算法來處理，總能找到最優的一組數據，有效的提高了聚類的質量。