[發(fā)明專利]基于多智能體進化的聚類和離群點檢測方法

在審

• 申請?zhí)枺?/td>: 201610846226.2
• 申請日: 2016-09-23
• 公開（公告）號: CN106649456A
• 公開（公告）日: 2017-05-10
• 發(fā)明（設(shè)計）人: 劉靜;焦李成;陳德學
• 申請（專利權(quán)）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 陜西電子工業(yè)專利中心61205
• 代理人: 田文英,王品華

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

本發(fā)明屬于計算機數(shù)據(jù)處理技術(shù)領(lǐng)域，更進一步涉及數(shù)據(jù)聚類和離群點檢測技術(shù)領(lǐng)域中一種基于多智能體進化的聚類和離群點檢測方法。本發(fā)明采用多智能體進化和局部離群點檢測的技術(shù)，有利于提高聚類劃分和離群點檢測精度。本發(fā)明可用于自然數(shù)據(jù)的聚類和離群點檢測。

背景技術(shù)

離群點檢測和聚類分析是數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的一個重要研究領(lǐng)域。在實際應用中，離群點檢測被廣泛地應用到各個領(lǐng)域，如欺騙信用卡檢測、侵入檢測、網(wǎng)絡和視頻監(jiān)控、天氣預報。離群點的本質(zhì)是由不同于一般的機制原理生成的現(xiàn)象，也被叫為異常點、孤立點。離群點檢測在實際用中往往比一般數(shù)據(jù)檢測更有價值，例如在機器故障檢測，醫(yī)療診斷，欺詐檢測，通常出現(xiàn)異常現(xiàn)象的數(shù)據(jù)點較少，正常運行的數(shù)據(jù)點較多。目前，離群點挖掘作為數(shù)據(jù)挖掘的一個熱門研究方向，已經(jīng)引起了很多學者的關(guān)注。

錢光超，賈瑞玉，張然和李龍澍在其發(fā)表的論文“基于遺傳聚類算法的離群點檢測”(工程優(yōu)化與應用1002-833(2008)11-0155-03)中提出了一種基于遺傳聚類的離群點檢測算法。該方法的核心是結(jié)合了遺傳算法全局搜索的優(yōu)點和K-均值方法具有局部收斂速度快的特點。具體的做法是首先聚類所有數(shù)據(jù)點，然后評估每個對象屬于簇的程度，如果刪除一個對象導致該目標的顯著改進，則可將該對象劃為離群點。該方法存在的不足之處是：遺傳算法容易陷入局部最優(yōu)的情況，使得最終的劃分解并不是最優(yōu)解，穩(wěn)定性不高。

張強，王春霞，趙健，武龍舉和李靜永在其發(fā)表的論文“基于聚類和局部信息的離群點檢測算法”(吉林大學學報章編號：1671-5489(2012)06-1214-04)中提出了一種基于聚類和局部信息的兩階段離群點檢測算法。該方法通過定義新的局部離群因子作為判斷數(shù)據(jù)對象是否為離群點的衡量標準。具體的做法是：先采用k-means聚類算法對數(shù)據(jù)集進行聚類的到k個簇；然后對每個簇進行分析，找出離群點。每個離群點的確定方法是先通過計算簇中各關(guān)節(jié)點的局部離群因子，并記錄每個簇中離群因子值最大的一個，再從簇中刪除，然后重新計算直到離群點的個數(shù)達到指定個數(shù)離群點為止。該方法采用k-means聚類算法對數(shù)據(jù)集進行聚類，雖然k-means算法比較簡單，但是，該方法仍然存在的不足之處是，劃分數(shù)據(jù)效率不高，收斂速度慢；一旦某個數(shù)據(jù)點被認為是離群點就不能在下一代執(zhí)行，導致該算法準確率降低。

Lian Duan，Lida Xu，Ying Liu和Jun Lee在其發(fā)表的論文“Cluster-based outlier detection”(Springer Science&Business Media,pp.151-168,2009)中提出了一種基于聚類的離群點檢測算法。該方法采用LDBSCAN算法進行聚類和LOF算法檢測離群點。具體的做法是：先采用LDBSCAN算法進行聚類，然后進行計算每個對象的基于聚類利群因子，一個被認為是一個離群點僅當它偏離它的最近的鄰域點。該方法存在的不足之處是，在算法中，參數(shù)需要有經(jīng)驗的研究者設(shè)置，計算量比較高(N×N)，使得算法執(zhí)行時間長，效率不高。

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

本發(fā)明的目的在于克服上述已有技術(shù)的不足，提出一種基于多智能體進化的聚類和離群點檢測方法，以提高離群點檢測的精度，減少計算時間，同時改善數(shù)據(jù)聚類的效率。

實現(xiàn)本發(fā)明目的的具體思路是：利用多智能體進化算法和K-means聚類算法對輸入數(shù)據(jù)集進行聚類。從多智能體網(wǎng)格中找到最優(yōu)的智能體，根據(jù)最優(yōu)智能體中所分配的類，再利用局部離群程度計算方法計算數(shù)據(jù)點的離群程度值。

實現(xiàn)本發(fā)明目的的具體步驟如下：

(1)初始化：

(1a)從待檢測數(shù)據(jù)集中隨機選擇滿足智能體的聚類個數(shù)，對網(wǎng)格中的每個智能體進行實數(shù)編碼，每個智能體代表一條染色體，每個聚類中心的位置代表一個基因，完成網(wǎng)格的初始化；

(1b)將待檢測數(shù)據(jù)集中的所有點設(shè)定為非離群點；

(1c)將離群點數(shù)據(jù)集設(shè)定為空集；

(1d)將初次迭代次數(shù)設(shè)定為0，最大迭代次數(shù)設(shè)定為100；

(2)對每個智能體執(zhí)行K-means聚類算法：

(2a)從待檢測數(shù)據(jù)集中任選一個點作為待計算點；

(2b)利用歐式距離公式，計算待計算點到每一個聚類中心的距離；

(2c)將每一個待檢測數(shù)據(jù)集中的點，分配到與聚類中心距離最近的類；

(2d)判斷是否選完待檢測數(shù)據(jù)集中所有的點，若是，執(zhí)行步驟(3)，否則，則執(zhí)行步驟(2a)；

(3)計算智能體的能量：