[發(fā)明專利]一種基于改進(jìn)ABC算法與DE變異策略的自適應(yīng)聚類方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510766519.5
• 申請(qǐng)日: 2015-11-11
• 公開（公告）號(hào): CN105426910B
• 公開（公告）日: 2018-11-27
• 發(fā)明（設(shè)計(jì)）人: 蔣炯明;薛羽
• 申請(qǐng)（專利權(quán)）人: 南京信息工程大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 許方

本發(fā)明公開了一種基于改進(jìn)ABC算法與DE變異策略的自適應(yīng)聚類方法，該方法采用變異和交叉兩個(gè)操作代替原算法ABC中單一的搜索操作，采用自適應(yīng)的DE變異策略和新的概率選擇值方法代替原方法。本發(fā)明在一定程度上解決了傳統(tǒng)聚類算法后期容易陷入局部最優(yōu)的缺點(diǎn)，且搜索速度相對(duì)較慢的缺陷，將改進(jìn)ABC算法與DE結(jié)合，重新定義人工蜂位置更新公式，使算法盡可能的跳出局部最優(yōu)，從而找到全局最優(yōu)解。該方法的聚類結(jié)果更具多樣性和準(zhǔn)確性，且算法速度及效率都具有一定的優(yōu)勢(shì)。

技術(shù)領(lǐng)域

本發(fā)明涉及一種聚類方法，特別是涉及一種基于改進(jìn)ABC算法與DE變異策略的自適應(yīng)聚類方法，屬于數(shù)據(jù)挖掘技術(shù)領(lǐng)域。

背景技術(shù)

群體智能進(jìn)化算法從20世紀(jì)90年代發(fā)展至今，以其對(duì)函數(shù)要求低、進(jìn)化過程與初始值無關(guān)、搜索速度快等優(yōu)點(diǎn)，迅速成為進(jìn)化算法的一個(gè)重要分支，并成為新的學(xué)術(shù)研究熱點(diǎn)。其中比較成熟的算法有Dorgo等人提出的蟻群算法(Ant Colony Optimization)和Kennedy等人提出的粒子群算法(Particle Swarm Optimization)。近年來，人工蜂群(Artificial Bee Colony，ABC)算法也越來越多地受到人們的關(guān)注。Karaboga于2005年提出人工蜂群算法，該算法是基于蜜蜂群體智能的優(yōu)化算法，通過模擬蜂群依各自分工不同智能采蜜，交換蜜源信息找到最優(yōu)蜜源。相比于其他經(jīng)典的進(jìn)化算法，ABC算法更簡單易用。

聚類是指將多個(gè)具有類似特性的對(duì)象組成多個(gè)類的過程，聚類的目的就是在相似的基礎(chǔ)上收集數(shù)據(jù)來分類。聚類目前在很多不同領(lǐng)域都得到非常廣泛的應(yīng)用并且得到了相應(yīng)的發(fā)展，包括計(jì)算機(jī)科學(xué)與技術(shù)、統(tǒng)計(jì)學(xué)、生物學(xué)等。最常見的聚類算法是k-means算法，它具有優(yōu)秀的局部搜索能力，能很好的解決一些聚類問題，但是自身還存在一定的缺陷，其中比較嚴(yán)重的缺點(diǎn)就是容易陷入“早熟”，即非常容易陷入局部最優(yōu)的缺點(diǎn)。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是：提供一種基于改進(jìn)ABC算法與DE變異策略的自適應(yīng)聚類方法，通過改進(jìn)ABC的變異策略，并增加了自適應(yīng)機(jī)制，在一定程度上解決了容易陷入局部最優(yōu)的缺點(diǎn)。

本發(fā)明為解決上述技術(shù)問題采用以下技術(shù)方案：

一種基于改進(jìn)ABC算法與DE變異策略的自適應(yīng)聚類方法，包括如下步驟：

步驟1，初始化自適應(yīng)聚類的各參數(shù)，包括：聚類數(shù)目、蜜蜂種群數(shù)目、開采極限以及最大迭代次數(shù)；根據(jù)聚類數(shù)目隨機(jī)對(duì)待聚類樣本進(jìn)行聚類劃分，且聚類劃分次數(shù)等于蜜蜂種群數(shù)目，得到蜜蜂種群數(shù)目的聚類劃分；計(jì)算各聚類劃分的適應(yīng)度，并找出最優(yōu)適應(yīng)度及其對(duì)應(yīng)的聚類劃分；

步驟2，對(duì)于步驟1得到的聚類劃分，從第一個(gè)聚類劃分開始，采用變異和交叉兩個(gè)過程產(chǎn)生新的聚類劃分，計(jì)算新的聚類劃分的適應(yīng)度，并與當(dāng)前最優(yōu)適應(yīng)度比較，若新的適應(yīng)度優(yōu)于當(dāng)前最優(yōu)適應(yīng)度，則用新的聚類劃分替換第一個(gè)聚類劃分，且新的聚類劃分的開采次數(shù)置為0，否則，第一個(gè)聚類劃分的開采次數(shù)加1；重復(fù)上述過程，直至最后一個(gè)聚類劃分結(jié)束；

步驟3，對(duì)于步驟2迭代之后的聚類劃分，計(jì)算各聚類劃分的概率值，計(jì)算公式為prob＝(0.9*Fitness/max(Fitness))+0.1，其中，prob表示各聚類劃分的概率值，F(xiàn)itness表示當(dāng)前計(jì)算的聚類劃分的適應(yīng)度，max(Fitness)表示迭代之后的聚類劃分適應(yīng)度的最大值；

步驟4，隨機(jī)產(chǎn)生一0-1之間的隨機(jī)數(shù)，并與步驟3得到的概率值比較，對(duì)概率值大于隨機(jī)數(shù)的聚類劃分重復(fù)步驟2的迭代過程；重復(fù)上述過程，且產(chǎn)生隨機(jī)數(shù)的次數(shù)等于蜜蜂種群數(shù)目；

步驟5，對(duì)于步驟4迭代之后的聚類劃分，判斷各聚類劃分的開采次數(shù)是否大于開采極限，若大于開采極限，則隨機(jī)生成一新的聚類劃分替換開采次數(shù)大于開采極限的聚類劃分，且將新的聚類劃分的開采次數(shù)置為0；

步驟6，重復(fù)步驟2-步驟5，直至達(dá)到步驟1的最大迭代次數(shù)，輸出最優(yōu)的聚類劃分。