[發明專利]一種基于改進文化算法的迭代自組織聚類組合算法

在審

• 申請號: 202110499071.0
• 申請日: 2021-05-08
• 公開（公告）號: CN113191555A
• 公開（公告）日: 2021-07-30
• 發明（設計）人: 韓堅;鄭瓊玲;肖純;李剛;黃華;汪洋;彭翔;劉璇;劉松;黎濤
• 申請（專利權）人: 國網江西省電力有限公司萍鄉供電分公司;國家電網有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/06;G06K9/62;G06N3/00
• 代理公司: 萍鄉益源專利事務所 36119
• 代理人: 胡宜斌

1.一種基于改進文化算法的迭代自組織聚類組合算法，其特征在于：包括如下步驟：

S1、聚類算法可分為監督學習聚類算法和非監督學習聚類算法，其中迭代自組織(ISODATA)算法，不僅可以在聚類過程中根據各類樣本的實際情況動態的調整聚類中心數目，還可以根據自身的需求對對象類別進行“合并”和“分裂”，在速度和精度都得到了極大的提升，從而得到更合理的分類；

步驟1的具體實現：

迭代自組織算法運行前參數設定：聚類數目H，每個聚類樣本最少樣本數量θ_K，樣本標準差(分裂系數)θ_M，若大于它，則繼續分裂；聚類中心距離閾值θ_C(合并系數)，若小于它，則進行合并，迭代總次數l；

步驟1.1：輸入K個樣本數據{x_i＝1,2,..,k}和隨機選出K_c初始聚類中心

步驟1.2：將K個樣本分給最近距離的聚類M_j，采用歐式距離計算樣本和聚類中心距離：

D_j＝min{||x-z_i||,i＝1,2,...,K_c}→x∈S_j。

步驟1.3：判斷S_jθ_K,則樣本子集無效，進行修正聚類中心Z_j，公式：

步驟1.4：判斷分裂運算，當K_c≤H/2,K_c≥2H以及聚類樣本距離標準差向量最大值σ_jmaxθ_S時，進行分裂操作，形成新的聚類中心公式：

Z₁＝Z_i+f_actor×σ_jmax

Z₂＝Z_i-f_actor×σ_jmax

步驟1.5：判斷合并運算，計算各類間距D_ij，當D_ijθ_c或某一類樣本個數小于θ_K時，進行合并操作，形成新的聚類中心公式：

步驟1.6：重復操作，直到達到規定的迭代次數；

S2、文化算法可分為三部分：種群空間、信仰空間和通信渠道；算法實現：種群空間一方面進行基因進化操作，另一方面用適應度函數對個體進行評價，按照適應度的大小選擇優秀個體作為訓練樣本給信仰空間，信仰空間通過Accpet()接受函數輸入其提供的優秀樣本，將樣本的隱藏信息，通過各類知識進行顯性描述存放，再利用influence()影響函數實現各類知識對種群進化的引導并通過Update()更新函數更新，信仰空間則繼續指導種群個體進化，直到獲得最優解，Accpet()和influence()統稱為接口函數，由它構成了文化算法通信渠道；

進一步地，步驟2的具體實現：

步驟2.1：初始化種群空間，隨機產生N個樣本來在聚類前選定聚類數目和聚類中心，并實施編碼；個體由K個聚類中心組成，p是實屬向量，對應的實值碼串K×p，因此適度函數為每個類間距離誤平方和最小值；

步驟2.2：在傳統文化算法的基礎上，將種群空間分成兩個部分，又其中個體樣本的適應度值分成非凡群體和一般群體，前者比后者的適應度值高，對種群的初始值進行優化；

步驟2.3：非凡群體中的個體樣本進化方式：式子中：x_i，x_k是優化方程的一組解，x_i,j是x_i的第j個分量j∈(1,2,...,D)，ε誤差精度，r_j是[0,1]間的隨機數，是[-1，1]間的隨機數；

步驟2.4：一般群體中的個體樣本進化方式：式子中：C_r,i∈[0,1]是交叉率，x_k是整個種群中的隨機解，r_j，同上，r_j是1到D間的整數，其中交叉率越大后代多樣性越多，因此自適應的交叉率為：式子中：f(x_i)是當前個體的適度值，max f是種群個體的最大適度值；

步驟2.5：最后隨著種群多樣性的變少導致交叉率的降低，最終收斂到一個穩定的解即最優個體；

S3、評價種群空間個體，根據給定的取值范圍和初始種群空間的候選解，按照信仰空間的結構，生成初始信仰空間；

步驟3的具體實現：

步驟3.1：信仰空間分為四種知識類型：形勢、標準化、歷史和地形知識，其中文知識類由形勢和標準化組成，將信仰空間定義為S,N；

步驟3.2：形勢知識S＝{S^h₁,S^h₂,...,S^h_m}，表示最優個體的集合，S^h_i表示第h代中第i個最優個體，形勢知識規模為m；

步驟3.3：規范知識N＝X₁,X₂,...,X_n，表示目標函數n個變量的變化區間信息，區間X_j表示I_j,L_j,U_j，其中I_j＝[l,u]＝{l≤x≤u,x∈R}，x為定義域邊界值和給定的初始值上下限u,l，L_j,U_j對應j區間的上下限的適度值，

S4、根據影響函數influence()，對種群空間中每個父代個體進行變異，生成p個相應的子個體；

步驟4的具體實現：

步驟4.1：由規范知識對步長進行調整控制，形勢知識對變化方向進行調整控制，定義為：

其中N(0,1)表示標準正態分布的隨機數，size(I_j)表示信仰空間內變量調整控制區間長度，λ是步長收縮因子；

S4、對于有父子個體共同組成的規模為2p的種群空間中的每一個個體，從中選取c個個體進行比較，如果該個體優于與之比較的個體，則該個體勝利并記錄個體勝利次數，選擇前p個勝利次數多的個體作為下一代的父個體；

S5、設定Accpet()接收函數，并用Update()更新函數更新信仰空間；

步驟5的具體實現：

步驟5.1：Accpet()函數是文化算大中的通信函數，傳遞當前種群空間15％的優秀個體；

步驟5.2：信仰空間更新，由Accpet()函數傳遞m個最優個體m_j,j＝1,2,...,n到信仰空間，根據適應度從大到小排列，有m_jm_j+1，那么更新形勢知識的過程為：

步驟5.3：若個體m_j影響規范知識N的下限，個體m_k影響規范知識N的上限，則N可用以下規則更新：

S6、若不滿足終止條件，重復步驟4，反之結束，得到最優分類。