一種基於擾動吸收原理的聚類算法
2024-01-22 20:15:15
一種基於擾動吸收原理的聚類算法
【專利摘要】本發明涉及一種基於擾動吸收原理的聚類算法，其特徵在於依次包括初始聚類中心選擇計算步驟、移動尋優步驟、交叉尋優步驟和類內擾動優化步驟，本發明提出初始聚類中心選擇方法，確保了每組初始聚類中心的對象基本為不同類中的對象並均勻分布在對象集中，提出移動尋優完成全局尋優過程，通過對各聚類中心的局部調整，交叉尋優和類內擾動優化共同完成局部尋優過程，對全局最優結果進行再次改進，避免了整體最優與部分最優不同步的問題。
【專利說明】一種基於擾動吸收原理的聚類算法
【技術領域】
[0001] 本發明涉及數據挖據領域，特別是涉及一種基於擾動吸收原理的聚類算法。
【背景技術】
[0002] 目前，聚類的目標是使同一類對象的相似度儘可能大，不同類對象之間的相似度 儘可能小。聚類在數據挖掘、機器學習領域廣泛的應用價值，在工程學、計算機科學、地球科 學以及社會科學和經濟學等領域起到越來越重要的作用，因此得到了大量研究。當前聚類 算法主要可以分為5大類：基於劃分的聚類算法，代表性方法有K-means、CLARA、PCM等；基 於層次的聚類算法，代表性方法有CURE方法、ROCK方法、BUBBLE方法等；基於密度聚類的 方法，代表性方法有DBSCAN、OPTICC，PDC等；基於網格的聚類算法，STING，WaveCluster， GLIQUE等和基於模型的聚類方法，代表性方法有SOM，AutoClass等。現有的方法各有優缺 點，部分算法速度較快，但精度較低，部分算法在一部分數據上效果好，但在另外的數據上 效果差，不具有普適性，部分算法容易陷入局部最優值等。
[0003] 基於劃分的聚類算法，預先指定聚類數目或聚類中心，通過反覆迭代運算，逐步降 低目標函數的誤差值，當目標函數值收斂時，得到最終的聚類結果。基於該思想，聚類分析 的目的是將個對象根據某種相似性分成》各類，同一類中的對象相似，不同類中的元素 相異。聚類分析形式地描述如下：令Jt維實數空間上的對象集為〇 其中， 巧=*?) €及，i =IAA，，Jfc 為某'~正整數。= =^asl 為畫個聚類中 ;L、，其中，= € JC，，用。右對象兩足 BiPi,Cj} = rail IlOi - C^y〇f - q |ji, ||〇f - C-1|, 則對象Oi屬於聚類中心Cj確定的類，記為Of eg ,其中，U(CkCj) = ||〇f-eg為q 與中間的某一距離測度(或相似性測度)，例如歐幾裡得距離，即
【權利要求】
1. 一種基於擾動吸收原理的聚類算法，其特徵在於依次包括初始聚類中心選擇步驟、 移動尋優步驟、交叉尋優步驟和類內擾動優化步驟， 所述初始聚類中心選擇步驟是指按同類對象距離近， 不同類距離遠來選擇一組初始聚類中心的方式，在對象集 O =權為Λ ,O1J中進行測度； 所述移動尋優步驟是指在全局解空間中尋找最優解，首先在s組聚類中心組中通過計 算適應度函數得到最優聚類中心組，其餘所有聚類中心組向最優聚類中心移動； 所述交叉尋優步驟是指通過在s組聚類中心中進行交叉尋優，除去最優聚類中心組％ 以外的其餘聚類中心組丐中如果存在某個一個聚類中心比嗎中0^/(辦更優，則將二 者交換，完成交叉尋優，得到搜素結果； 所述類內擾動優化步驟是指通過在類內對聚類中心做有指導的擾動，向類中心靠近， 得到優化後的搜索結果。
2. 根據權利要求1所述的一種基於擾動吸收原理的聚類算法，其特徵在於：所述初始 聚類中心選擇步驟包括如下步驟： 步驟1、初始聚類中心個數為》*，聚類中心組數為S ; 步驟2、在[Ojle]上定義《*個模糊集，分別記為ZtZI5Ji?聲·,刻畫m種遠近距離； 步驟3、確定聚類半社r =WtZJl +WyD3 (μ +_w2 =Xwl >〇 )，根據上述分析，在 此聚類半徑下，被中心吸收的對象與該中心基本是同一類的； 步驟 4、$·^ = ·^||碎-cysr}; 步驟5、選擇對象Oi滿足|C4| =_|qyc2p 為某一類的一個初始聚類中心，其 中，M表示集合中元素個數，即集合的基數； 步 驟6、 分 別 詵 檉對象 ?Λ Ο二mm) 滿 足
步驟7、選定一組初始聚類中心為; 步驟8、重複上述過程S次，可選出S組初始聚類中心，記?組初始聚類中心分別為
3.根據權利要求1所述的一種基於擾動吸收原理的聚類算法，其特徵在於：所述移動 尋優步驟包括以下步驟： 步驟1、令s組聚類中心經*次移動尋優後，聚類中心分別調整為
其中，?=1對應上述JT組初始聚類中心； 步驟 2、V?e fULA及/e iUJUrnj ,記 <^切=0*4-說，4-(功 e Λ1 ,則對 於第Y組聚類中心，其第*次的目標函數如下：
其中，W6-=I若Oi eCCCk雜（以為中心的類)，1^- = 0若OJC(OstfO); 步驟3、確定最優聚類中心組A，即
步驟4、其它聚類中心組分別向最優中心組13^? = (象A ?I隨機 移動，即VY e fcUi,第Y組聚類中心劣? = 紙A2(雜為*(攜向最優中心組 紀(0 = {〇￥⑴刀刀_(〇|隨機移動； Ir 令 OvM = (χ^(〇,χ^(〇Λ ,<,(0),貝!J -C^(?)中的 〇々·(0 = 〇4他<.(0Λ，4(0) ||'彳 = 0^·(Ο，（(ΟΛ，<-(0)隨機移動，形式地描述 為：
其中，ff 為一隨機數,= 玖」; 若，二·、",則 VJfc，e ,t}, 〇) - χ$(?) = 〇 ; 因此,V/e ，ι?|, = ,隨機移動不改變最優中心組的目標函數值， 即 Β(Ω^(?+?)) ^ B(Q^it))； 經過隨機移動，得到新聚類中心組，即VYe , ￡^(t+^ = p^{t + ^O^it+T)A ,〇^t+1)}; 步驟5、第f組聚類中心經過隨機移動後的目標函數(第·?+1次的目標函數）如下： DiQ,￡^{thm = 各備β·[ f ? 1卜 =Σ(Σ^/^-4^+1?5 +A +(? -4^+?')， ? J-I 第?+l次最優聚類中心組滿足 I)) =? {d(0,.Q^(M ^χ?)(α〇=(Μ 5)jl ,D(￡?3i^(Ml))} 0
4. 根據權利要求I所述的一種基於擾動吸收原理的聚類算法，其特徵在於：所述交叉 尋優步驟包括如下步驟： 步驟 令 i^-IN -%?ll =?{i%|^ -〇ν?|μ -〇,-?|| 步驟2、若w ~ ,則cy?與〇*#)交叉，s卩〇^ω替換為OsyCo, 〇奪(〇替換為 ，〇￥媯=(χΙ^%χΙ^)Λ1 j 〇々ω 二入 相 I! tm
5. 根據權利要求1所述的一種基於擾動吸收原理的聚類算法，其特徵在於：所述類內 擾動優化步驟包括如下步驟： 步驟 I、 Vj ^tJ0 及 _/e 久，令 = Ipjl |g = ， Olt = χ￥2Λ = (^(?λ^?ΟΛ ； 步驟 2、We(UXAJt),令 ζ(4⑴)=k*y=似，穿且? 〇}, 步驟 3、若 |￡〇?·(0)| =jcSiO+axinatK^ χ￡-^(0 >〇,gf = Χ2Λ ,g\ ； 其中，M表示集合中元素個數，為一設定參數； 步驟 4、若 |￡(^ω)| > >(4(功|,則 xj(/+l) =xJ(〇 +axmax^ -xj(/) <0,^ = Ι2Λ ,g}, 其中，M表示集合中元素個數，e(pj5為一設定參數。
6.根據權利要求2所述的一種基於擾動吸收原理的聚類算法，其特徵在於：所述初始 聚類中心選擇步驟的步驟8中，為避免選出的s組初始聚類中心中出現重複選取的情況，在 重複上述過程$次時，設定每次在未選擇的對象中進行。
【文檔編號】G06F17/30GK104376124SQ201410745070
【公開日】2015年2月25日 申請日期:2014年12月9日 優先權日:2014年12月9日
【發明者】裴崢, 高志升 申請人:西華大學