[發明專利]一種針對大數據的分解組合聚類方法

有效

• 申請號: 201410334542.2
• 申請日: 2014-07-14
• 公開（公告）號: CN104063518B
• 公開（公告）日: 2017-06-09
• 發明（設計）人: 吳俊杰;伍之昂;曹杰
• 申請（專利權）人: 南京弘數信息科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京匯盛專利商標事務所(普通合伙)32238
• 代理人: 陳揚

技術領域

本發明屬于數據挖掘領域，涉及一種數據劃分的聚類方法，具體的說是一種針對大數據的組合聚類方法。

背景技術

大數據給人們帶來了前所未有的沖擊和挑戰，大數據的特點：Volume(大量)、Velocity(高速)、Variety(多樣)、veracity(真實性)。如何挖掘大數據中蘊含的潛在價值信息成為工業界和學術界的熱點問題。大數據具有數據量大，維度高的特點，這使得傳統的數據分析方法在大數據面前束手無策，力不從心；并且大數據中存在噪聲屬性和噪聲樣本點也讓挖掘大數據的內在模式難上加難。

發明內容

鑒于大數據聚類中的海量高維難題，本發明的目的是提供一種針對大數據的分解組合聚類方法，本發明采用“分解-組合”的方法，首先將大數據分別進行橫向和縱向切分，得到若干數據子集，再利用快速聚類法獲得數據子集的類別標簽，再利用組合聚類法將若干數據子集的類別標簽進行組合，得到完整的數據類別標簽。

本發明的目的是通過以下技術方案來實現的：

一種針對大數據的分解組合聚類方法，其特征在于：該方法首先將大數據分解，針對每個數據子集聚類，再使用組合聚類的方法求得最后的完整類別標簽，具體步驟如下：

1)對大數據的樣本點進行隨機抽樣,得到若干橫向數據子集；

進一步：將大數據D進行橫向切分，獲得r個數據子集D_i，1≤i≤r，使得r個數據子集的全集為D，r個數據子集的樣本總數為D的樣本數量的5倍以上。

進一步：利用隨機抽樣的方式，對大數據進行橫向切分，隨機抽取10％的樣本量獲得數據子集D_i，有放回的重復抽樣r＝100次，使得100個數據子集的全集為D。

2)對得到的橫向數據子集的屬性進行隨機抽樣,得到若干規模較小的縱向數據子集；

進一步：對每個數據子集D_i進行縱向切分，獲得c個數據子集D_ij，1≤j≤c，使得c個數據子集的全集為D_i，c個數據子集的屬性總數為D_i的屬性數量的5倍以上。

進一步：利用隨機抽樣的方式，對每個數據子集D_i進行縱向切分，隨機抽取10％的屬性獲得數據子集D_ij，有放回的重復抽樣c＝100次，使得100個數據子集D_ij的全集為D_i。

3)對得到的縱向數據子集,進行基礎聚類,得到若干基礎聚類結果；

利用K均值對每個數據集子集D_ij進行聚類，得到π_ij；K均值算法如下，其中K均值聚類距離函數為平方歐式距離或者余弦相似度；只需要運行K均值算法一次即可：

(31)選擇K個點作為初始中心；

(32)重復；

(33)將每個點指派到最近的中心，形成K個簇；

(34)重新計算每個簇的中心；

(35)直到中心不發生變化。

4)對縱向數據子集的基礎聚類結果進行組合聚類,得到橫向數據子集的類別標簽；

進一步：利用基于K均值的一致性聚類方法對c個π_ij進行組合聚類，得到π_i作為D_i的類別標簽。

利用基于K均值的組合聚類方法對100個π_ij，1≤j≤c進行組合聚類，得到π_i作為D_i的類別標簽；基于K均值的組合聚類方法如下：

(41)將100個基礎聚類結果π_ij，轉化為0-1矩陣，其轉換方式如下：

用表示由上述基礎聚類結果得到的0-1二元矩陣，n_i為D_i樣本個數，其生成方式如下所示：

其中

因此，是一個的矩陣，其中K_i為的π_ij簇個數，并且

(42)選擇組合聚類效用函數U，并從中分解

如果效用函數U可以進行如下所示的分解，則可利用基于快速一致性聚類的框架進行求解；

其中，p_k表示第k個類占所有數據的比例，m_k,j表示π_ij的第k個類的中心，且上式中為凸函數；

(43)基于生成快速聚類法的距離函數，利用K均值聚類法的距離范式，