基于SOM和BP網絡的K均值聚類算法分析

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

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

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

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

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

1 K均值聚類算法

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

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

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

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

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

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

2 SOM和BP神經網絡

2.1 SOM網絡

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

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

2.2 BP神經網絡

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

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

3 基于BP網絡改進的K均值聚類算法

3.1 BP-K模型簡介

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

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

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

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

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

）作為隱層節點的激勵函數。并初始化隱節點的閾值。

（5）利用（2）中得到的樣本點到聚類中心的距離初始化網絡的權值矩陣：

（6）計算各隱節點的輸出值。

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

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

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

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

3.2 BP-K聚類模型分析

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

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

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

4.1 SOM-K模型介紹

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

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

4.2 SOM-K模型分析

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

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

5 總結與展望

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

參考文獻：

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

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

[3]傅德勝，周辰.基于密度的改進K均值算法及實現[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網絡改進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結合K-均值聚類的軟件定義網絡泛洪攻擊檢測方法[J].計算機應用研究，2019，36（11）：3423-3427.

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

【通聯編輯：唐一東】

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