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

在審

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

1.一種基于分形技術的分布式聚類方法，其特征在于：該方法的步驟如下：

步驟1：數據預處理；

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

步驟3：全局聚類；

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

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

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

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

2.根據權利要求1所述一種基于分形技術的分布式聚類方法，其特征在于：

步驟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：各子節點上本地數據中的各屬性值按照屬性的全局取值范圍進行標準化；

步驟1.5：各子節點上本地數據的抽樣概率初始化為1/n_i。

3.根據權利要求1所述一種基于分形技術的分布式聚類方法，其特征在于：

步驟2：抽樣聚類包括如下步驟；

步驟2.1：子節點按照比例抽樣方式獨立抽取本地數據并上傳至中心節點，具體來說，子節點J_i將依據各數據點的抽樣概率抽取總數為(n_i/n)N的數據；

步驟2.2：中心節點J₀匯總各子節點的抽樣數據，并對抽樣數據進行聚類，形成k個聚類中心；

步驟2.3：中心節點J₀按照k個聚類中心將抽樣數據集數據劃分到各個聚類，計算每個聚類的局部分形維數，具體來說，第i個聚類分形維數表示為其中i＝1，2...，k；

步驟2.4：中心節點J₀計算全局聚類分形質量指數和第i個聚類的局部聚類分形質量指數

步驟2.5：將k個聚類中心及其分形維數、全局與局部聚類分形質量指數廣播至各個子節點。

4.根據權利要求1所述一種基于分形技術的分布式聚類方法，其特征在于：

步驟3：全局聚類包括如下步驟；

步驟3.1：各個子節點遍歷本地數據集，計算各個數據點與k個聚類中心的距離，將各個數據點標記為距離最近的那個聚類中心成員，具體來說，第i個子節點的第j個數據點所屬聚類用表示；

步驟3.2：子節點更新本地數據集中各聚類數據的抽樣概率：其中

5.根據權利要求1所述一種基于分形技術的分布式聚類方法，其特征在于：

步驟5包括如下步驟；

步驟5.1：計算全局抽樣聚類質量指數Ω＝∑_i，j|Qⁱ-Q^j|和第r次抽樣的局部抽樣聚類質量指數Ω^r＝∑_j|Q^r-Q^j|，其中r＝1，...，L；

步驟5.2：L次抽樣聚類共產生了L×k個聚類，每個聚類的分形維數為其中i＝1，2，...，k，r＝1，2，...，L；我們將這L×k個分形維數進行k-means聚類，產生k個分形聚類中心；

步驟5.3：將新的k各分形聚類中心以及Ω和Ω^r廣播到各子節點。