[發(fā)明專利]一種局部加權(quán)的不完整數(shù)據(jù)混雜聚類方法

在審

• 申請?zhí)枺?/td>: 201710993558.8
• 申請日: 2017-10-23
• 公開（公告）號: CN107766887A
• 公開（公告）日: 2018-03-06
• 發(fā)明（設(shè)計）人: 張利;牛明航;孫穎;石振桔;郭煒儒;孫軍;王軍;趙中洲
• 申請（專利權(quán)）人: 遼寧大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/12
• 代理公司: 沈陽杰克知識產(chǎn)權(quán)代理有限公司21207
• 代理人: 羅瑩

1.一種局部加權(quán)的不完整數(shù)據(jù)混雜聚類方法，其步驟如下：

(1)收集數(shù)據(jù)：所使用的數(shù)據(jù)為UCI標準測試數(shù)據(jù)集包括：Iris、Bupa、Wine和Breast；

(2)數(shù)據(jù)處理：隨機使部分數(shù)據(jù)缺少部分屬性，變成不完整數(shù)據(jù)；

(3)數(shù)據(jù)估算：利用改進的遺傳算法中的個體對不完整數(shù)據(jù)的缺失屬性進行估算；

(4)聚類分析：基于matlab軟件對估算的數(shù)據(jù)進行模糊聚類分析.

2.根據(jù)權(quán)利要求1所述的一種局部加權(quán)的不完整數(shù)據(jù)混雜聚類方法，其特征在于：所述步驟(3)利用改進的遺傳算法中的個體對不完整數(shù)據(jù)的缺失屬性進行估算的過程如下：

(1)問題編碼：由臨近樣本對缺失數(shù)據(jù)的屬性進行估算，對要處理的問題：優(yōu)化最近鄰樣本個數(shù)、模糊化參數(shù)和函數(shù)寬度參數(shù)進行編碼處理；

(2)初始化參數(shù)：設(shè)定模糊聚類算法中聚類類別數(shù)c，迭代收斂閾值ε，遺傳種群規(guī)模為M，遺傳算法的選擇概率P_s，染色體交叉概率P_c，自主學(xué)習(xí)的混雜變異概率常量P_m1和P_m2，初始設(shè)置個體E_p(1)(p＝1,2,...,M)，最大迭代數(shù)量G；

(3)搜索臨近樣本:當遺傳迭代次數(shù)為t(t＝1,2,...,G)，每一個個體表示為E_p(t)(1≤p≤M)，根據(jù)相似度公式，搜索出缺失數(shù)據(jù)的q個最鄰近樣本；相似度公式如下：

Dkp=sΣj=1sIjΣj=1s(x~jk-x~jp)2Ij---(1)]]>

其中和分別表示樣本和的第j個屬性值，且

(4)估算缺失屬性，獲取新的數(shù)據(jù)集：通過結(jié)合高斯核函數(shù)確定的權(quán)系數(shù)對缺失值得估值獲得新的數(shù)據(jù)集，公式如下：

缺失屬性可以表示為：

x~jk=Σp∈wkwkpx~jp---(3)]]>

其中：W_k表示為不完整數(shù)據(jù)樣本的q個最近鄰樣本的相對應(yīng)屬性值的域；是q個最近鄰域樣本中相對應(yīng)屬性值之一；w_kp(p∈W_k)表示權(quán)值，滿足限制條件0≤w_kp≤1，權(quán)值的大小將取決于樣本與最近鄰樣本的相似度；權(quán)值w_kp計算公式表示為：

wkp=1δkexp(-||x~k-x~p||22/(2σ)2)---(4)]]>

其中：表示為采用高斯核函數(shù)定義的不完整數(shù)據(jù)樣本和最近鄰樣本之間的距離；σ表示函數(shù)寬度參數(shù)，它將掌控著權(quán)值函數(shù)w_kp的衰減程度；計算不完整的樣本與最近鄰域中的樣本的距離得到較合理的加權(quán)系數(shù)，相鄰樣本與缺失樣本距離越大，相應(yīng)權(quán)值越小，該方法能夠更好的考慮數(shù)據(jù)集的鄰域結(jié)構(gòu)信息；δ_k表示歸一化常數(shù)，計算公式表示為：

δk=Σexp(-||x~k-x~p||22/(2σ)2)---(5)]]>

(5)聚類原型和劃分矩陣更新：當?shù)螖?shù)取值為l＝(1，2...)時，結(jié)合劃分矩陣U^l-1，利用聚類原型計算公式更新聚類原型V^l；劃分矩陣更新：按照聚類原型V^l，利用隸屬度計算公式更新劃分矩陣U^l；若出現(xiàn)的結(jié)果，則算法進行下一步，輸出劃分矩陣U和聚類原型V；否則將繼續(xù)下次尋優(yōu)過程l＝l+1,重新聚類原型和劃分矩陣更新；聚類原型公式如下：

vi=Σk=1nuikmx~kΣk=1nuikm,i=1,2,...,c---(6)]]>

隸屬度計算公式如下：

uik=[Σi=1c(||x~k-vi||22||x~k-vt||22)1m-1]-1---(7)]]>

(6)適應(yīng)度值確定：通過公式(計算每個個體E_p(t)(1≤p≤M)的適應(yīng)度值，采取升序排列染色體的適應(yīng)度值；按照適應(yīng)度值的大小判斷個體的優(yōu)劣性；適應(yīng)度公式如下：

F(Ep(t))=1Σi=1cΣk=1nuikm||xk-vi||22---(8)]]>

其中v_i表示為第i類的聚類原型,u_ik被用來表示樣本數(shù)據(jù)x_k隸屬于模糊子類第i類的程度，對于條件滿足下式:

Σi=1cuik=1,k=1,2,...,n]]>

記U＝[u_ik]∈R^c×n為模糊劃分矩陣；m∈(1,∞)表示模糊化參數(shù)，它將決定聚類分析結(jié)果的模糊程度，其中一般經(jīng)典取值為m＝2；

(7)修正的輪盤賭策略：在種群中選擇父代，種群前期時候，當適應(yīng)度比較分散的時候，采用適應(yīng)度進行一定程度的縮小，而且適應(yīng)度越是高的個體，縮小的幅度越大；在種群后期，當適應(yīng)度相對集中的時候，對其進行擴大，適應(yīng)度越大的個體，放大幅度也相對大；采用修正的輪盤賭的選擇策略公式，第t代個體的E_p(t)的被選擇概率如下：

a=(c-1)FavgFmax-Favg---(9)]]>

b=Favg(Fmax-c*Favg)Fmax-Favg---(10)]]>

F(Ep(t))=a*F(Ep(t))+b---(11)Ps(Ep(t))=F(Ep(t))Σj=1MF(Ej(t))---(12)]]>

其中：F_max表示適應(yīng)度最大值；F_avg表示適應(yīng)度平均值；F為適應(yīng)度值；c表示調(diào)節(jié)參數(shù)；E_j(t)表示種群規(guī)模M中的個體；

(8)交叉操作：算法的交叉操作將父代優(yōu)良基因遺傳到子代，一對父代個體交叉操作后會產(chǎn)生多個子代個體，所以子代個體之間存有角逐現(xiàn)象；設(shè)E_p(t)和E_f(t)(p≠f)分別作為第t代的父代染色體，為增加競爭性，產(chǎn)生四個子代個體:

overl1=Ep(t)+Ef(t)2overl2=(Emin+Emax)(1-β)+(Ep(t)+Ef(t))β2overl3=Emin(1-β)+min(Ep(t),Ef(t))βoverl4=Emax(1-β)+max(Ep(t),Ef(t))β---(13)]]>

其中，我們把交叉算子的定義為β∈[0,1]；min(E_p(t),E_f(t))和max(E_p(t),E_f(t))的每個元素分量取E_p(t)和E_f(t)(p≠f)相對應(yīng)的極小值和極大值；上面有4種交叉方式產(chǎn)生的子代方法個體勢必會好于傳統(tǒng)單一的算術(shù)或兩點式交叉方式，再按照產(chǎn)生的子代個體中挑選出適應(yīng)度值最優(yōu)的兩個個體，以此作為交叉操作產(chǎn)生的子代；

(9)變異操作：為免染早熟、基因變異位置的隨機性和一成不變的變異概率，于任意個體的適應(yīng)度值大于所有個體適應(yīng)度平均值的個體應(yīng)用較小變異概率進行變異引導(dǎo)，這樣的做法有利于保證算法變異方向的正確性，較優(yōu)質(zhì)量的染色體得以遺傳給子代；對于任意個體的適應(yīng)度值小于所有染色體適應(yīng)度平均值的個體應(yīng)用較大變異概率進行變異引導(dǎo)，這樣可以使得劣質(zhì)的個體被淘汰,自主學(xué)習(xí)的混雜變異概率為：

Pm=Pm1(Fmax-Favg)(1+t0.5)(F-Favg),F≥Fmaxpm2,F<Fmax---(14)]]>

其中：F_max表示適應(yīng)度最大值；F_avg表示適應(yīng)度平均值，F(xiàn)表示適應(yīng)度；t表示遺傳優(yōu)化算法的迭代次數(shù)；P_m1和P_m2分別為自主學(xué)習(xí)的混雜變異概率常量且P_m1<P_m2；

(10)根據(jù)選擇算子從候選中間代Em(t)個體生成子代個體E(t+1)個體；

(11).如果遺傳更新次數(shù)為t＝G或遺傳優(yōu)化結(jié)果連續(xù)8代不發(fā)生變化，則停止尋優(yōu)運算并獲得適當?shù)膮?shù)，并進行相應(yīng)的聚類分析；否則，設(shè)置t＝t+1并且返回3)。