[發明專利]一種基于分形技術的分布式聚類方法

在審

• 申請號: 201611257250.9
• 申請日: 2016-12-30
• 公開（公告）號: CN106777298A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 張巖龍;鄧軍;幸勇
• 申請（專利權）人: 成都數聯易康科技有限公司;西南交通大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 成都中亞專利代理有限公司51126
• 代理人: 王崗

技術領域

本發明涉及聚類處理相關領域，尤其是一種基于分形技術的分布式聚類方法。

背景技術

聚類分析是數據挖掘領域的一項重要研究內容，聚類算法在金融業務員、保險業、市場營銷、網絡安全、科學決策等方面的應用越來越廣泛。目前已有的聚類算法大多只適用于集中式數據的聚類。而實際中的數據卻是分布在不同的站上，如果使用傳統的聚類算法從這些分布式數據中提取信息，就必須把這些數據合并到一個中心站點上。由于傳輸速度和安全因素的限制，把各站點的數據合部集中到某一個中心站點上是十分困難的。而且所有站點數據集中在一起，數據量會非常龐大，聚類效率會顯著降低。

經過檢索發現專利號CN200710156189.3的發明公開了一種面向互聯網微內容的分布式聚類方法。本發明采用多機分布式聚類的方法，主控機器把要處理的微內容切分成多個小文件，并把這些小文件分配給多臺聚類機器進行聚類操作。單臺聚類機器對分配到的各個小文件循環進行元聚類，接著合并這些元聚類結果文件，得到相應的單機聚類合并文件，然后把它發送給主控機器。主控機器在接收到各個聚類機器發送過來的單機聚類合并文件后，從各個單機聚類合并文件中抽取微內容代表點，對這些微內容代表點進行再次元聚類，生成新的聚類項，并將對應的類別合并，得到最后的聚類結果。

專利號CN201510747122.1的發明公開了一種海量負荷曲線的分布式聚類方法，其通過將受聚類區域內所有用戶劃分為M個用戶子集，并對應每一個用戶子集設置一個局部數據中心，用各個局部數據中心分別對各自處理得到的歸一化日負荷曲線進行自適應局部聚類，以減少待分析的用電數據，再對應所述受聚類區域設置一個全局數據中心，并全局數據中心對接收到的所有局部典型曲線進行全局的聚類分析，從而使得每一個局部數據中心的每一條原始日負荷曲線能夠歸屬到相應的全局聚類。

傳統聚類方法的一個前提是數據集中在一個站點,需要一次性載入內存。然而,在許多環境中,局域網、廣域網、Internet網將多個數據源連成一個大型分布式異構數據庫,用戶需要處理大量、多計算節點、不同地理分布的數據,并需要保護數據的隱私和安全。集中式聚類算法不能很好地應用到分布式環境中,以往的分布式聚類算法其通信量和中心節點的計算工作量均較大，即使允許集中執行大量的數據,要么算法崩潰,要么執行效率太低,其長時間的執行,讓用戶難以接受。數據存儲方式的變化對聚類算法的并行性和分布化都提出了要求。

發明內容

本發明的目的在于克服現有技術的不足，在此提供一種基于分形技術的分布式聚類方法。解決了以往的分布式聚類算法其通信量和中心節點的計算工作量大的難題，該算法比以往的分布式聚類算法減少了通信量和中心節點的計算工作量，該算法充分利用分形維度作為相似性衡量的標準，使得簇之間分形維度變化最大，簇內分形維度變化最小。通過將分析維度引入到聚類算法，利用分形維度固有的自相似性來提高聚類算法的適應性。

本發明是這樣實現的，構造一種基于分形技術的分布式聚類方法，其特征在于：該方法的步驟如下：

步驟1：數據預處理；

步驟2：抽樣聚類：中心節點從各子節點抽取總數量為N的數據并聚類；

步驟3：全局聚類；

步驟4:迭代完成步驟2-步驟3，直到達到最大抽樣次數L；

步驟5：中心節點J0經過L次抽樣聚類后；

步驟6：各子節點計算本地數據點的平均分形維數；

步驟7：各子節點計算本地數據點的平均分形維數與k個分形聚類中心的距離，將其劃分為最近的那個聚類，即為最終聚類結果。

根據本發明所述一種基于分形技術的分布式聚類方法，其特征在于：

步驟1：數據預處理包括如下步驟；

步驟1.1：中心節點J₀發出指令獲取各子節點本地數據集的分布情況；

步驟1.2：各子節點計算本地數據集中的記錄數n_i及各屬性的取值范圍(A_min與A_max)，并將數據上傳至中心節點J₀；

步驟1.3：中心節點J₀合并各子節點數據集中各屬性的取值范圍，得到全局數據集中各屬性的取值范圍(A′_min與A′_max)，然后將全局數據量n、A′_min與A′_max廣播至各子節點；

步驟1.4：各子節點上本地數據中的各屬性值按照屬性的全局取值范圍進行標準化；