[發明專利]一種海量數據聚類方法

無效

• 申請號: 201310044976.4
• 申請日: 2013-02-05
• 公開（公告）號: CN103064991A
• 公開（公告）日: 2013-04-24
• 發明（設計）人: 許志興;肖華;邵峰;陳冠雄;樸東國;呂群芳;蔣全璋
• 申請（專利權）人: 杭州易和網絡有限公司;數源科技股份有限公司;西湖電子集團有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州賽科專利代理事務所 33230
• 代理人: 曹紹文

技術領域

本發明涉及一種海量數據聚類方法，尤其涉及一種分布式計算技術、云計算技術、信息系統、數據挖掘技術等領域的在MapReduce分布式計算框架上實現的海量數據聚類方法。

背景技術

海量數據的分析是一個NP問題，一直是數據挖掘技術中的難題，當數據的緯度達到一定高度時，很多對低維數據很有效的聚類方法就不再適用。將原始的海量數據集分割成為許多能夠在單機上快速處理的數據子集，然后在這些數據子集上進行分布式處理是分布式海量數據處理的方法。分割原始數據集的質量對后續進行分布式處理的效果有很深的影響，因為分割后的數據子集中已經遺失了的信息在后續的分布式信息處理中是無法彌補的。

MapReduce是目前云計算中使用得最廣泛的并行編程模式，是Google公司提出的分布式并行計算框架，他讓程序員只需關注數據的處理，而數據的分布式存儲和容錯都交給計算框架來解決。在MapReduce平臺的計算過程中，數據首先被切分到集群的不同節點上，以<Key,Value>的形式存儲在分布式文件系統中。計算過程分為兩個階段：Map階段和Reduce階段，集群中的每臺機器都有幾個Map和Reduce任務。Map過程中指定對各分塊數據進行處理，生成生成中間數據<Key,Value>；Reduce過程中指定如何對分塊數據處理的中間結果進行規約，共享同一個Key的<Key,Value>由同一個Reduce來處理。目前MapReduce及其開源版本Hadoop的研究非常活躍。

雖然MapReduce在并行計算環境中具有一定的優勢，但同時也存在著一定的局限性和缺陷。傳統的MapReduce編程框架只能處理單個數據集，而不能直接支持對多個相關數據集的處理，也不能處理所有的海量數據的問題，比如在面向低維數據的并行計算的效率很高，但是對于海量高維數據進行聚類時常常會出現內存不足、性能不佳等問題。

發明內容

本發明所要解決的技術問題在于提供一種在MapReduce分布式計算框架上實現的海量數據聚類方法。針對海量數據的特點，充分發揮差別矩陣在信息系統中信息約簡方面的優勢，通過差別矩陣對海量高維數據預先進行高效的降維、約簡處理，滿足MapReduce計算框架的計算能力要求。如果一個海量數據的信息系統經過分割后，可以從分割后的信息系統中得到與原始信息系統相同的知識或者規則，則這樣的分割是最佳的分割。

本發明是一種策略性的方法，首先分析海量數據集并通過信息系統和決策表建立對應的差別矩陣，然后對差別矩陣進行稀疏化處理，得到屬性的核和最約簡的決策表。基于這個最約簡的決策表，利用MapReduce分布式并行算法實現動態聚類，從而得到海量數據的最佳聚類。聚類后的數據可以用于各種數據挖掘的分析和應用。

一種海量數據聚類方法，包含如下步驟：

步驟一，根據輸入的海量高維數據，建立一個基于信息系統表達的原始決策表；

步驟二，基于原始決策表建立一個差別矩陣；

步驟三，對差別矩陣進行稀疏化處理，成為一個稀疏化的矩陣；

步驟四，基于稀疏后的差別矩陣，求取屬性的核；

步驟五，基于屬性的核中的屬性形成一個約簡后的決策表，以此決策表作為輸入，實現在MapReduce分布式計算框架上的動態聚類分布式并行算法，實現約簡后的決策表的坐標聚類；

步驟六，基于步驟五中約簡后的決策表的坐標聚類結果，通過MapReduce分布式計算框架轉換為原始的海量高維數據的數據聚類。

優選地，所述的步驟一中，建立一個原始決策表的建立過程如下：

根據輸入的海量高維數據，建立信息系統S=(U,A,V,f)；式中，U為非空有限集，為原始的海量數據；A為非空有限集，為屬性集合；?為屬性a∈A的值域；f:U×A→V為一個單映射，使U中任一個元素在V中有某一個值唯一對應；假設信息系統可以抽象表達為一個d列n行的決策表，其中d為屬性A的個數，n為每個屬性的元素個數；

優選地，所述的步驟二中，建立一個差別矩陣的過程包含如下的操作步驟：

以步驟一中的原始決策表為輸入，建立一個以決策表中的行數分別為行和列的矩陣，決策表中任意兩行的不同的屬性取值的集合作為這個矩陣對應行列位置的元素值，這樣方式得到的矩陣就是屬性A的差別矩陣，記為M(A)，差別矩陣M(A)是一個n×n的對稱矩陣，其中n為每個屬性的元素個數；

優選地，所述的步驟三中，差別矩陣的稀疏化處理過程包含如下的操作步驟：