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

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

　　《網絡空間安全》(原：信息安全與技術)(月刊)創(chuàng)刊于2010年，是由中國電子信息產業(yè)發(fā)展研究院與迪賽工業(yè)和信息化研究院有限公司主辦的，是我國信息安全和信息技術領域集學術性、技術性、專業(yè)性和權威性為一體的國家級月刊。

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

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

　　2.2 BP神經網絡

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

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

　　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聚類規(guī)則，當前聚類結果設為R(t)，t=t+l。如果R[t-1]的效果相比于R[t]更好，算法結束并輸出R[t]，衡量聚類效果的標準是所有聚類之間的距離差異概率。

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