[發明專利]基于Spark的快速尋找聚類中心的方法和系統

在審

• 申請號: 201710693112.3
• 申請日: 2017-08-14
• 公開（公告）號: CN109389140A
• 公開（公告）日: 2019-02-26
• 發明（設計）人: 李學兵;莊福振;敖翔;何清
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國;梁揮

本發明涉及一種基于Spark的快速尋找聚類中心的方法，涉及計算機信息獲取和處理技術。本發明實現了基于Spark的并行CFSFDP聚類算法，利用內存并行計算框架解決了CFSFDP聚類算法處理數據規模小、效率低的問題。基于Spark的并行CFSFDP聚類算法首先通過把兩點距離計算分成完全獨立的子部分，再將計算結果在匯總服務器上處理分析，然后繼續將一系列計算任務切割成獨立子任務，匯總到一臺服務器上，最終并行計算得到聚類中心，在得到聚類中心后串行計算得到所有數據點的類別。本發明在處理數據中充分發揮了CFSFDP算法的優點，彌補一些常用并行聚類算法的不足。

技術領域

本發明涉及一種基于Spark的快速尋找聚類中心的方法和系統，涉及計算機信息獲取和處理技術。

背景技術

本發明致力于解決大數據背景下高效解決聚類問題，基于Spark分布式平臺實現CFSFDP(Clustering by fast search and find ofdensity peaks)算法的并行化，使得這個優秀的聚類算法可以應用于大數據環境下。

在無監督學習中，訓練樣本的標記信息是未知的，目標是通過無標記訓練樣本的學習來揭示數據的內在性質及規律，為進一步的數據分析提供基礎。聚類在這類研究中扮演著重要角色，聚類是通過將數據劃分為若干個不相關的簇來探索數據中固有的規律和分布結構，在數據劃分過程中基于物以類聚的原則，盡可能將類似的數據分到同一類簇，將不同的數據組織成不同的類簇。聚類應用領域廣泛，如圖像處理、網絡安全、模式識別、生物信息學、蛋白質分析和社交網絡等。目前有多種聚類算法，大致可分為原型聚類、層次化聚類、劃分式聚類、基于密度和網格的聚類算法和其他聚類算法。在數據驅動時代的背景下，將聚類算法并行化是聚類算法應用于大數據的有效途徑。目前基于Spark并行化的聚類算法有K-means和混合高斯聚類。

K-means算法是目前應用最廣的算法之一，對于數值屬性的數據，他能很好的體現聚類在幾何和統計學上的意義。K-means算法的基本思想是隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心.對剩余的每個對象,根據其與各個簇中心的距離,將它賦給最近的簇.然后重新計算每個簇的平均值.這個過程不斷重復,直到目標函數收斂.通常定義為公式(1)的目標函數,采用啟發式方法使得目標函數值最小。

其中p對象空間中的一個數據數據對象，m為類C_i的均值，公式(1)在一定程度上刻畫了類簇內樣本圍繞簇均值向量的緊密程度。E值越小則簇內樣本相似度越高。

高斯混合模型(GaussianMixtureModel，簡稱GMM)是最成熟的聚類方法之一，基本思想是假設待聚類的數據集是從多個混合在一起的多元高斯分布，從而用極大似然估計的思想來聚類。GMM是用高斯概率密度函數(正態分布曲線)精確地量化事物，將一個事物分解為若干的基于高斯概率密度函數(正態分布曲線)形成的模型。通俗點講，無論觀測數據集如何分布以及呈現何種規律，都可以通過多個單一高斯模型的混合進行擬合。所以GMM模型就是通過由單一高斯分布混合成的混合高斯分布去擬合數據從而達到聚類的目的。單高斯分布基本定義是：若隨機變量X服從一個數學期望為、方差為σ²的高斯分布，則記為N(μ,σ²)。數學期望μ指的是均值(算術平均值)，σ為方標準差(方差開平方后得到標準差)。一維高斯分布的概率密度函數為：

多維高斯分布模型下的概率密度函數：