[發明專利]一種兩階段混合粒子群優化聚類方法

有效

• 申請號: 201210109141.8
• 申請日: 2012-04-13
• 公開（公告）號: CN102663100A
• 公開（公告）日: 2012-09-12
• 發明（設計）人: 劉志鏡;王縱虎;王韋樺;陳東輝;屈鑒銘;賀文驊;王靜;姚勇;熊靜;唐國良;袁通;劉慧
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

1.一種兩階段混合粒子群優化聚類方法，包括如下步驟：

(1)讀入數據集和聚類個數K；

(2)統計維度信息

計算機遍歷數據集所有樣本，統計數據集各維的取值范圍信息，獲得數據集各維屬性取值范圍的最大值與最小值；

(3)維度規范化

對數據樣本各維屬性值采用規范化公式進行處理，將數據集所有樣本各維屬性值映射到[0，1]區間；

(4)計算相似度矩陣

對所有樣本采用歐式距離公式計算兩兩之間的相異度值，生成數據集各樣本之間的相異度矩陣；

(5)生成候選初始聚類中心

5a)將所有樣本看作一個子簇，加入當前輪子簇列表中，根據步驟(4)中獲得的相互之間的相異度降序排序；

5b)按照平均相異度公式計算當前輪子簇列表中每個子簇與數據集其他子簇之間的平均相異度值；

5c)對排序后的子簇對進行合并，若子簇對之間的相異度同時小于子簇對中兩個子簇的平均相異度值，則將這兩個子簇進行合并，加入到新一輪子簇列表中，否則將這兩個子簇加入新一輪子簇列表中；

5d)判斷新一輪子簇列表中子簇的數目是否小于等于預定數目，若是，則停止迭代，輸出生成的新一輪子簇列表中的子簇作為候選初始聚類中心；否則返回5b)繼續進行層次凝聚聚類；

(6)粒子群K均值劃分聚類

6a)采用粒子編碼方式對選擇的新一輪子簇列表中的子簇中的候選初始聚類中心子簇進行編碼；

6b)設定粒子種群中粒子的數目及最大迭代次數、整個粒子種群的位置和速度的搜索空間范圍，設定每個粒子的初始位置和速度；

6c)根據當前粒子編碼位置各維的值獲得初始聚類中心子簇的序號，采用K均值劃分方法對數據集進行劃分聚類，獲得數據集的聚類結果；

6d)根據適應度值公式，對數據集聚類結果計算粒子的適應度值；

6e)判斷當前粒子適應度值與該粒子的最優適應度值的大小，若小于則將該粒子最優適應度值用當前粒子適應度值替換，將該粒子最優位置用當前粒子位置替換，否則不變；

6f)判斷當前粒子適應度值與粒子種群的最優適應度值的大小，若小于則將粒子種群最優適應度值用當前粒子適應度值替換，將粒子種群最優位置用當前粒子位置替換，否則不變；

6g)根據粒子速度更新公式更新粒子速度；

6h)根據粒子位置更新公式更新粒子位置；

6i)判斷粒子群優化迭代次數是否到達預設的最大迭代次數，若是，則停止迭代，執行步驟(7)；否則，返回6c)繼續進行計算；

(7)輸出粒子種群最優適應度值和對應的數據集類簇劃分結果。

2.根據權利1所述的一種兩階段混合粒子群優化聚類方法，其特征在于，步驟(3)所述的規范化公式如下：

f′=f-minfmaxf-minf]]>

其中，f′為樣本某一維屬性經過規范化后映射到[0，1]范圍內的值，f為樣本某一維屬性原始值，min_f為數據集中樣本某一維屬性f的最小值，max_f為數據集中樣本某一維屬性f的最大值。