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

　　關(guān)鍵詞：K-means;SOM;BP;聚類算法

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

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

　　1 K均值聚類算法

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

　　(1)從輸入樣本集中任意選擇K個(gè)對(duì)象作為初始聚類中心;

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

　　(3)對(duì)距離較大的重新計(jì)算每個(gè)聚類的聚類中心;

　　(4)計(jì)算標(biāo)準(zhǔn)測(cè)度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時(shí)，則算法終止;如果條件不滿足則回到步驟(2)。

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

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

　　2.1 SOM網(wǎng)絡(luò)

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

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

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

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

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

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

　　3.1 BP-K模型簡(jiǎn)介

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

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

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

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