摘要：在數(shù)據(jù)挖掘中，K均值聚類算法作為最典型、最常見、實用度最廣的一種聚類算法，具有簡單易操作等優(yōu)點。但K均值聚類算法也存在部分缺點，其在訓練前需要提前設定聚類中心個數(shù)，在訓練過程中容易陷入局部最優(yōu)，面對多維數(shù)據(jù)樣本其效果不佳，得到的聚類結(jié)果受初始聚類中心個數(shù)的設定影響較大。對k均值聚類算法的優(yōu)化方案較多，本文主要針對前人提出的基于BP神經(jīng)網(wǎng)絡的K均值聚類算法和基于SOM網(wǎng)絡改進的K均值聚類算法效果進行分析，為后續(xù)的進一步改進提供基礎。

關鍵詞：K-means;SOM;BP;聚類算法

中圖分類號：TP18 文獻標識碼：A

文章編號：1009-3044（2020）09-0024-03

K均值聚類（K-means）算法是一種經(jīng)典的動態(tài)聚類算法，在聚類分析中常被使用的一種迭代求解的無監(jiān)督學習算法，該算法具有簡單、高效的特點，其對大數(shù)據(jù)效率較高、可伸縮性強，因此常常被用于數(shù)據(jù)挖掘的任務中。但其缺點也較為明顯，其在訓練過程中容易陷入局部最優(yōu)解，其初始聚類中心和聚類個數(shù)需要人為確定，初始聚類中心和聚類個數(shù)對整個K均值聚類的結(jié)果影響較大，針對此問題，許多學者提出了較多的優(yōu)化算法。K均值聚類算法的改進方案主要包含以下三類：一是針對如何選取好的初始聚類中心[1-5];二是在算法中如何確定合適的K值[6-8];三是與其他算法相結(jié)合的用于確定聚類中心和K值[9-13]，其中BP-K模型和SOM-K模型較為突出。本文主要針對這兩種模型進行分析，為后續(xù)的改進提供基礎。

1 K均值聚類算法

K均值聚類（K-means）算法是數(shù)據(jù)挖掘中常用的聚類算法，把N的數(shù)據(jù)對象根據(jù)他們的屬性分為K個簇（K

（1）從輸入樣本集中任意選擇K個對象作為初始聚類中心;

（2）根據(jù)每個聚類樣本的均值，計算每個樣本與這些聚類中心的距離，并根據(jù)最小距離重新對相應對象進行劃分;

（3）對距離較大的重新計算每個聚類的聚類中心;

（4）計算標準測度函數(shù)，當滿足一定條件，如函數(shù)收斂時，則算法終止;如果條件不滿足則回到步驟（2）。

主要局限于平均值被定義的情況下才能使用，不適合部分分類樣本;必須事先給出要生成的聚類中心數(shù)目K，對初值K的選定敏感，對于不同的初始值，可能會導致不同的聚類結(jié)果;樣本集中的少量數(shù)據(jù)能夠?qū)ψ罱K的聚類效果產(chǎn)生極大影響。

2 SOM和BP神經(jīng)網(wǎng)絡

2.1 SOM網(wǎng)絡

自組織映射神經(jīng)網(wǎng)絡是由1981年芬蘭Helsink大學的T.Kohonen教授提出一種自組織特征映射網(wǎng)，縮寫為SOM，又稱Kohonen網(wǎng)。SOM網(wǎng)絡屬于無導師學習網(wǎng)絡，具有良好的自組織性和可視化等特征。SOM神經(jīng)網(wǎng)絡的整體結(jié)構(gòu)由輸入層和競爭層構(gòu)成，輸入層主要負責接受外界信息，將輸入的數(shù)據(jù)向競爭層傳遞，競爭層主要對數(shù)據(jù)進行整理訓練并根據(jù)訓練次數(shù)和鄰域的選擇將數(shù)據(jù)劃分為不同的類。SOM神經(jīng)網(wǎng)絡的典型拓撲結(jié)構(gòu)如圖1所示。

SOM網(wǎng)絡的訓練過程可以概括為：第一步，確定拓撲結(jié)構(gòu)，根據(jù)樣本類型和部分經(jīng)驗確定網(wǎng)絡競爭層維數(shù)、神經(jīng)元個數(shù)和神經(jīng)元的拓撲結(jié)構(gòu)。第二步，樣本歸一化。第三步，初始化網(wǎng)絡參數(shù)，初始化學習率、權(quán)向量和鄰域函數(shù)。第四步，輸入樣本競爭學習，據(jù)歐氏距離相似度或余弦相似度規(guī)則尋找獲勝神經(jīng)元，并對鄰域內(nèi)節(jié)點分配一個更新權(quán)重。第五步，根據(jù)一定的規(guī)則更新節(jié)點參數(shù)。第六部，重復訓練直到收斂。

2.2 BP神經(jīng)網(wǎng)絡

BP神經(jīng)網(wǎng)絡是1986年由Rumelhart和McCelland為首的科研小組提出，BP神經(jīng)網(wǎng)絡是按照誤差逆向傳播的多層網(wǎng)絡。BP神經(jīng)網(wǎng)絡訓練分為兩個過程：第一步是輸入樣本的正向傳播，從輸入層經(jīng)隱藏層到達輸出層;第二步是誤差的反向傳播，計算期望與實際輸出的誤差，將誤差從輸出層傳回隱藏層，再傳回輸入層，根據(jù)代價函數(shù)調(diào)節(jié)隱藏層到輸出層的權(quán)重和偏置，輸入層到隱藏層的權(quán)重和偏置，因此其又被稱為誤差反向傳播網(wǎng)絡。BP網(wǎng)絡為多層網(wǎng)絡，層數(shù)最小三層，其主要由輸入層、隱含層和輸出層構(gòu)成，隱含層可以包含多層網(wǎng)絡，如圖2所示。

BP神經(jīng)網(wǎng)絡學習過程主要包含正向傳播和反向傳播兩個階段，在正向傳播的過程中訓練樣本從輸入層逐層處理傳到輸出層，將輸出結(jié)果與期望值比較計算誤差，若誤差較大將誤差按學習規(guī)則反向逐層分攤到各節(jié)點，訓練過程中正向傳播和誤差反向傳播交替進行，層與層之間存在激勵函數(shù)、權(quán)值矩陣、偏置矩陣、代價函數(shù)和損失函數(shù)，激勵函數(shù)是控制網(wǎng)絡輸出的重要函數(shù)，誤差在反向傳播的過程中，激勵函數(shù)的倒數(shù)是求解誤差梯度的重要參數(shù)。

3 基于BP網(wǎng)絡改進的K均值聚類算法

3.1 BP-K模型簡介

K均值聚類算法的聚類中心和個數(shù)常常結(jié)合其他算法來確定。在文獻[9]中提出了一種基于BP網(wǎng)絡的改進方案，通過對K均值聚類算法初次訓練得到的聚類中心和權(quán)值引入到BP網(wǎng)絡進行訓練從而得到新的聚類中心，由于BP-K模型較為復雜，在結(jié)合實驗后，在這里對該模型的基本步驟整理為：

（1）輸入樣本集P，確定初始簇的聚類中心數(shù)K（K應為一個較大的值，例如：n/5，n為樣本個數(shù)），并隨即選擇初始聚類中心H={Hl，H2，-HK}。

（2）利用K-menas聚類。產(chǎn)生K個簇和各個簇的聚類中心H={H1，H2，-HK}，l司時將各個聚類中心和樣本點到其聚類中心的距離保存下來，得到距離矩陣dpi（p=l，…，n，i=l，…，K）。其聚類結(jié)果滿足K-Means聚類規(guī)則，當前聚類結(jié)果設為R（t），t=t+l。如果R[t-1]的效果相比于R[t]更好，算法結(jié)束并輸出R[t]，衡量聚類效果的標準是所有聚類之間的距離差異概率。

（3）初始化BP網(wǎng)絡的參數(shù)[9]，設置如下：系統(tǒng)誤差為0，學習率為0.01，惰性因子為0.075，訓練次數(shù)為1000，初始化集合S和L為空，循環(huán)次數(shù)為0。

（4）構(gòu)造BP神經(jīng)網(wǎng)絡，主要結(jié)構(gòu)為三層，以樣本集為輸入層，K個聚類中心作為隱藏層節(jié)點，網(wǎng)絡的期望輸出為K-Means劃分結(jié)果。根據(jù)集合H中的節(jié)點序列給每個隱節(jié)點編號，0=（01，02，…，OH}。選擇雙曲線（

）作為隱層節(jié)點的激勵函數(shù)。并初始化隱節(jié)點的閾值。

（5）利用（2）中得到的樣本點到聚類中心的距離初始化網(wǎng)絡的權(quán)值矩陣：

（6）計算各隱節(jié)點的輸出值。

（7）如果隱節(jié)點i和i符合刪除規(guī)則，則刪除i，把i的編號存人集合S中，如過節(jié)點i和j符合合并規(guī)則，則將i和j合并為一個節(jié)點，把i的編號存入集合L中。

（8）重復正向計算、后向傳播、修改權(quán)值直到系統(tǒng)誤差足夠小，如果一次循環(huán)中訓練次數(shù)超過規(guī)定次數(shù)則退出算法并輸出R[t]。

（9）如果一次循環(huán)后集合L不為空，則修改聚類中心：H=H-L， K=K-ILI，如果S非空，則隨機選擇其他中心點C，修改初始聚類中心：H={H-S}uc，ICI=ISI，K不變，如果S和L都為空，則退出并輸出R[t]，否則轉(zhuǎn)向步驟（3）。

在（7）中所提到的刪除規(guī)則定義如下：

3.2 BP-K聚類模型分析

在BP-K-means模型中主要利用BP神經(jīng)網(wǎng)絡對初始聚類中心進行訓練從而得到下一次的聚類中心初始參數(shù)。上述的步驟、相關度和發(fā)散度是在原BP-K模型基礎上結(jié)合實驗f實驗數(shù)據(jù)集為iris數(shù)據(jù)集）的基礎上進行參數(shù)調(diào)整和公式改進的基礎上所得到的。在后面，將會與SOM-K模型進行對比。

在對BP-k的驗證實驗過程中也發(fā)現(xiàn)其模型對BP網(wǎng)絡的依賴性較高，整個模型效率和K均值算法的初始聚類個數(shù)選擇成正相關，選擇的K值越接近最終聚類個數(shù)，模型的時間消耗越低。BP神經(jīng)網(wǎng)絡在BP-K模型中主要對聚類中心進行訓練，BP神經(jīng)網(wǎng)絡的訓練在整個模型中占大部分，其訓練效率較低，在整個BP-K模型中，BP神經(jīng)網(wǎng)絡的誤差反向傳遞過程主要存在于我們的輸入層和隱含層，引入的K均值聚類的初始聚類權(quán)值也主要作用在輸入層和隱含層。BP-K模型在將K均值算法的初步聚類中心和距離矩陣作為BP神經(jīng)網(wǎng)絡輸入和權(quán)值矩陣的做法為后續(xù)的聚類優(yōu)化模型具有一定的啟發(fā)式意義。

4 基于SOM改進的K均值聚類算法分析

4.1 SOM-K模型介紹

在文獻[12-13]中引入SOM網(wǎng)絡對K均值聚類算法進行該進，其思路主要是SOM網(wǎng)絡和K均值聚類算法的串聯(lián)來改進K-means算法。類似的文獻較多，但總體思路如下：第一步，先利用SOM獲得初始聚類中心和中心個數(shù)，第二步，將SOM訓練得到的聚類中心帶人K均值聚類算法。其思路是利用SOM網(wǎng)絡的自組織性來獲取K均值聚類算法的初始聚類中心，模型應用范圍較廣，其效率相較于獨立的兩個網(wǎng)絡確有較大的提升，SOM-K模型步驟如圖3所示。

在圖中可以清楚地看到，SOM-K模型實質(zhì)上是一種利用SOM先聚類，聚類輸出用于K-means二次聚類的串聯(lián)模型。其應用在入侵檢測中可以明顯提高檢測率，降低聚類的誤探率。

4.2 SOM-K模型分析

SOM-K模型只是將SOM網(wǎng)絡與K均值聚類算法簡單的串聯(lián)在一起，雖然在一定程度上優(yōu)化了K均值聚類算法，受限于兩個網(wǎng)絡的簡單串聯(lián)，其模型仍然存在部分缺陷，特別是SOM網(wǎng)絡容易出現(xiàn)死結(jié)點，進行聚類分析時其效率不是很理想、訓練結(jié)果受訓練次數(shù)的影響較大等。

在面對類似于網(wǎng)絡入侵這類在同一時間產(chǎn)生的多種數(shù)據(jù)樣本的環(huán)境中，其更容易陷入死結(jié)點，部分可能出現(xiàn)聚類混亂的情況，此時SOM的改進顯得尤為重要，一定程度上，雖然SOM在SOM-k模型中發(fā)揮了巨大作用，但SOM網(wǎng)絡本身的缺陷也為SOM-K模型帶來了隱患。

5 總結(jié)與展望

在前文中分別分析了基于SOM和基于BP神經(jīng)網(wǎng)絡的K均值聚類算法?？梢园l(fā)現(xiàn)，BP-K模型是對K均值聚類算法的內(nèi)部改進，BP神經(jīng)網(wǎng)絡在模型中主要作用于K均值聚類算法的K值變化中去，初始的K值仍需要提前確定，在面對大量數(shù)據(jù)樣本的情況下，其應用效果不理想。SOM-K模型是在傳統(tǒng)的K均值聚類算法前引入SOM網(wǎng)絡，SOM網(wǎng)絡的主要作用是在K均值聚類算法前確定K值，在一定程度上有利于聚類，但SOM-K模型只是對SOM和K均值聚類算法的簡單串聯(lián)，其無法避免SOM網(wǎng)絡的部分缺陷。文中的BP-K模型具有一定的啟發(fā)式意義，SOM-K模型多數(shù)應用在其他領域中，但在兩類改進方案中，仍然存在著各自網(wǎng)絡的部分缺陷，這是后續(xù)改進的重點。

參考文獻：

[1]邢長征，谷浩，基于平均密度優(yōu)化初始聚類中心的k-means算法[J].計算機工程與應用，2014，50（20）：135-138.

[2]謝娟英，王艷娥.最小方差優(yōu)化初始聚類中心的K-means算法[J].計算機工程，2014，40（8）：205-211，223.

[3]傅德勝，周辰.基于密度的改進K均值算法及實現(xiàn)[J].計算機應用，2011，31（2）：432-434.

[4] Goyal M，Kumar S.Improving the initial centroids of k-meansclustering algorithm to generalize its applicability[J].Journal ofthe Institution of Engineers （lndia）： Series B，2014， 95（4）：345-350+

[5] Zhu M， Wang W， Huang J.Improved initial cluster center se-lection in K-means clustering[Jl. Engineering Computations，2014，31（8）：1661-1667.

[6] Dalal M A.Harale N D，Kulkami U L.An iterative improvedK-means clustering[Jl.lnternational Journal of Network Securi-ty，201 1，2（3）：25-28.

[7]劉廣聰，黃婷婷，陳海南，改進的二分K均值聚類算法[J].計算機應用與軟件，2015，32（2）：261-263，277.

[8] 2alik K R.An efficient k'-means clustering algorithm[J].Pat-tern Recognition Letters，2008，29（9）：1385-1391.

[9]王銀輝，熊忠陽，使用BP網(wǎng)絡改進K-means聚類效果[J].計算機科學，2006，33（3）：194-196.

[10]唐哲.一種基于遺傳算法的k均值聚類分析[D].長沙：長沙理工大學，2014.

[11]寇磊.基于SOM算法改進的K-medoids算法及其研究【Dl.太原：太原理工大學，2017.

[12]袁正，基于SOM及K均值聚類方法的分布式入侵檢測模型的研究[D].天津：天津理工大學，2009.

[13]汪海濤，余松森.分布式SOM結(jié)合K-均值聚類的軟件定義網(wǎng)絡泛洪攻擊檢測方法[J].計算機應用研究，2019，36（11）：3423-3427.

[14]回珥婷，夏懿嘉，陳紫荷，等，基于Synonyms、k-means的短文本聚類算法[Jl-電腦知識與技術(shù)，2019，15（1）：5-6.

【通聯(lián)編輯：唐一東】

作者簡介：趙文均（1994-），男，四川南充人，西華師范大學計算機學院2017屆在讀碩士研究生，研究方向：數(shù)據(jù)挖掘、深度學習。