滕少華，洪 源，李日貴，張 巍，劉冬寧

(廣東工業(yè)大學 計算機學院，廣東 廣州510006)

0 引 言

數據庫技術的快速發(fā)展和數據庫管理系統(tǒng)的廣泛應用，使得各種組織結構積累了海量數據。人們迫切希望從海量數據中找到有用的知識和信息，從而在市場競爭中搶占先機。面對這種挑戰(zhàn)，數據挖掘技術獲得了迅速發(fā)展，不僅在理論上有眾多成果［1，2］，且已廣泛走向工業(yè)應用。聚類分析是數據挖掘的主要方法之一［2］，它是分析數據并從中發(fā)現(xiàn)信息和知識的一種手段。對聚類分析，人們取得了一系列研究成果。K-Means 算法［3］是經典的聚類算法之一，但需要預先給定聚類個數和初始值，開銷大且對數據輸入順序敏感;文獻［4］提到的Rock 算法是一種經典的層次聚類算法，針對包含分類屬性的數據集使用鏈接(兩個對象間共同的近鄰數目)，不但考慮了對象間的相似度，還考慮了鄰域信息;改進的DBSCAN 算法［5］是一種基于高密度聯(lián)通區(qū)域的基于密度的聚類方法，可以有效地找出任意形狀的簇。

無線網絡傳感器［6］作為一種檢測裝置，能夠獲得周圍的信息，并將這些信息按照一定的規(guī)律轉換為其他需要形式的信息，滿足傳輸、存儲等功能。通過無線傳感器收集的信息，這里成為無線網絡數據集，本文在提出了自適應的多趟聚類分析方法，并將其運用到無線數據中，發(fā)現(xiàn)數據特征，尋找離群信息，對于一般的離群點，往往有重要研究價值，可以用于研究無線傳感器節(jié)點的安全信息［7］。

1 KSummary 算法

1.1 KSummary 算法與相關概念

KSummary 算法［8］能夠處理分類屬性與混合屬性數據，提出使用聚類摘要信息(cluster summary information，CSI)來表示一個簇，算法給出了自己的相似度計算方法。

設D 為數據集合，D 中任意一條記錄有m 個屬性，其中有mc個分類屬性和mN個數值屬性，顯然滿足m=mc+mN。用Di表示第i 個屬性取值的集合，x=2。下面給出KSummary 算法的定義［9］:

定義1 給定簇C，a∈Di，a 在C 中關于Di的頻度定義為C 在Di上的投影中包含a 的個數

定義2 給定簇C，n=|C|表示C 的大小，C 的CSI 定義為CSI={n，summary}，由數值型屬性的質心和分類屬性中不同取值的頻度信息兩部分組成，即

定義3 設C，C1，C2為數據集合D 劃分的簇，p=［p1，p2，…，pm］，q=［q1，q2，…，qm］表示兩個對象，x ＞0。

1)對象p 到簇C 的距離d(p，C)定義為p 與簇C 的摘要之間的距離

對于dif(pi，Ci)，當Di表示分類屬性時，該值定義為p與C 中每個對象在屬性Di上的距離的算術平均值，即

當Di是數值屬性時，定義為

2)簇C1和簇C2間的距離d(C1，C2)定義為兩個簇的摘要間的距離

若Di為數值屬性，則該值定義為

3)dif(pi，qi)表示兩個對象p，q 在屬性Di上距離，dif(p，q)表示對象p，q 之間的距離

a.若Di是二值屬性或分類屬性或:

當pi=qi，dif(pi，qi)=0;

當pi≠qi，dif(pi，qi)=1 .

b.若Di是順序屬性或連續(xù)數值屬性

c.兩個對象p，q 間的距離為

1.2 KSummary 算法的不足

KSummary 算法能夠很好地處理混合型數據集［9］，但需要解決下列問題:1)預先給定聚類個數k 值，k 的取值直接影響聚類結果;2)需要隨機選擇k 個初始聚類中心，記為集合Q，但是KSummary 算法的聚類結果對Q 存在依賴關系。

2 自適應多趟聚類分析方法

2.1 體系結構

本文提出自適應多趟聚類分析方法，采用層次聚類、基于密度聚類和KSummary 聚類算法相結合的思想，對數據集進行多趟聚類。多趟聚類體系結構如圖1 所示。

2.2 自適應層次聚類

本階段在層次聚類的基礎上，使用自適應［10］層次聚類算法。實施時，對于數據集，根據公式(11)，給出閾值R，R值會選擇的相對大些，這樣在調整閾值時可以直接減小該值。通過計算簇內和簇間對象的相似度，得到一個評價函數。

若評價函數偏高，則減小閾值R，繼續(xù)剛才的聚類，得到新的層次聚類，直到評價函數［2］的值達到理想條件為止，這樣獲得聚類結果依賴于具體的數據集，使得算法更實用和可靠。

算法閾值［11，12］R 定義為

其中，total(D)為數據集D 中對象間的距離之和，n 為指對象個數，α 為閾值調節(jié)系數。對于不熟悉的數據集，α值一般都是要通過經驗值來獲得。

文中使用均衡化的評價函數［11，12］，對于聚類C 計算類內相似度D(C)和類間相似度L(C)，獲得了評價函數為

當滿足距離代價最小時，可以得到最優(yōu)的空間聚類結果。自適應層次聚類的流程圖圖2。

2.3 密度聚類與迭代過程

本文使用的密度聚類［2］方法是在已經有一組聚類基礎上進行的。用D 來表示數據集，Ci(i=1，2，..，k)表示簇。本階段通過計算各個簇中對象密度，選擇簇中密度相對較大的點作為該簇的代表點，并選為下一步算法的初始聚類中心。將簇Ci中的任意對象pi的密度定義為density(pi)［11，12］

圖2 自適應層次聚類流程Fig 2 Flow chart of adaptive hierarchical clustering

其中，x 為pi所在簇中的對象個數，pj為該簇內對pi有影響的的任一對象，d(pi，pj)為pi到pj的距離，?為對象之間可以相互影響的閾值。對象pi密度是在該對象所在的簇內計算，因而，閾值?僅和該簇內對象有關，不同簇中的?值也是不同的。

獲得初始聚類個數k 和初始聚類中心Q 以后，運用KSummary 算法，重復迭代，不斷更新簇的摘要信息和對象所屬的簇，直到每個對象所屬的簇不再發(fā)生變化時，算法終止。

2.4 傳感器數據集

使用無線傳感器收集手機通信信息，從傳感器收集的信息要經過多重處理，包括數據壓縮和融合等［13，14］，這樣在經過處理后會產生能夠使用的數據集，這樣的數據集適用于自適應多趟聚類算法。數據集的主要屬性包括:移動信號強度(MSPOWER)、上行接收信號(RXLEV)、時間延遲量(TA)等。數據集的每條記錄，都有標記其來源的若干屬性，這樣在聚類后，記錄位置變化后，仍能找到獲得該記錄的傳感器設備，這樣的數據特征有助于分析實驗結果。

數據集經過數據預處理［15］后，能夠獲得切合實際并且適合聚類方法的數據集，部分數據如下

3 實驗結果和分析

3.1 實驗環(huán)境

本文使用了無線傳感器收集數據，用于接收手機發(fā)出的無線電信號。數據處理和聚類算法使用在機器為:CPU:Inter Core(TM)T5800，RAM:2GB，32 位操作系統(tǒng)。工具為Weka 3.7，Vs 2010.使用精度、平均評價函數、統(tǒng)計方法［16，17］等來對實驗結果分析。

3.2 實驗和結果

聚類分析的統(tǒng)計結果見圖3、表2 和圖4。

圖3 兩種方法在不同聚類個數下的精度Fig 3 Precision of the two methods under different number of clustering

表1 實驗結果統(tǒng)計Tab 1 Statistics of experimental results

表1 記錄了實驗過程的計算結果，結合圖3 可以看到:本文算法得到的評價函數、平均評價函數都比原算法低，而最高精度和平均精度也優(yōu)于原算法的處理結果。圖3 也說明自適應多趟聚類算法可以找到在無線網絡數據集上的最佳聚類個數，聚類的精度也達到了比較理想的數值。

圖4 簇中對象的個數Fig 4 Number of objects in each cluster

圖4 給出了聚類后的數據分布，給出了簇中數據對象的個數，容易發(fā)現(xiàn)第2，10 簇中數據比其他簇少很多，所以，這些對象就很大概率是要找的離群點，通過對這些對象的分析，可以定位到收集這些信息的無線傳感器，進一步研究可以分析出該傳感器某個節(jié)點的安全狀況。

4 結束語

自適應多趟聚類分析方法相比傳統(tǒng)KSummary 算法，從平均評價函數和平均精度都有更好的效果。自適應多趟聚類算法是將整個過程分為三趟聚類，三趟之間屬于串行。與KSummary 算法相比，確實增加了一定的時間開銷，但是在數量級與指數級上都沒有增加，而且聚類的效果要好于原算法。

使用自適應多趟聚類算法，應用于傳感器收集的無線網絡數據中，離群點表現(xiàn)出來的信息與其他信息會有較大差異，這在本算法中會有明顯的體現(xiàn)，實驗結果也說明了這個問題。對聚類后找到的可疑離群點進行分析，定位到收集該信息的傳感器，就能夠知道該設備的節(jié)點是否處于安全的工作狀態(tài)。

［1］ 王令劍，滕少華.聚類和時間序列分析在入侵檢測中的應用［J］.計算機應用，2010，30(3):699-701.

［2］ Han Jianwei，Micheline Kamber，Pei Jian.數據挖掘概念與技術［M］.范 明，孟小峰，譯.3 版.北京:機械工業(yè)出版社，2012.

［3］ Kanungo T，Mount D，Netanyahu N，et al.An efficient k-means clustering algorithm:Analysis and implementation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(7):881-992.

［4］ Dutta M，Kakoti A Mahanta，Arun Pujari K.QROCK:A quick version of the ROCK algorithm for clustering of categorical data［J］.Pattern Recognition Letters，2005，26(15):2364-2373.

［5］ 周水庚，周傲英，金 文，等.FDBSCAN:一種快速DBSCAN算法［J］.軟件學報，2000，11(6):735-744.

［6］ 馬華東，陶 丹.多媒體傳感器網絡及其研究進展［J］.軟件學報，2006，17(9):2013-2028.

［7］ 陳 娟，張宏莉.無線傳感網絡安全研究綜述［J］.哈爾濱工業(yè)大學學報，2011，43(7):90-95.

［8］ 蔣盛益，李 霞，鄭 琪.數據挖掘原理與實踐［M］.北京:電子工業(yè)出版社，2011.

［9］ 蔣盛益，李慶華.一種增強的K-Means 聚類算法［J］.計算機工程與科學，2006，28(11):56-59.

［10］馬 力，焦李成，白 琳，等.自適應多克隆聚類算法及收斂性分析［J］.模式識別與人工智能，2008，21(1):72-83.

［11］汪 中，劉貴全，陳恩紅.一種優(yōu)化初始中心點的K-Means 算法［J］.模式識別與人工智能，2009，22(2):299-305.

［12］袁 方，周志勇，宋 鑫.初始聚類中心點優(yōu)化的K-Means 算法［J］.計算機工程，2007，33(3):65-69.

［13］尹亞光，貴 廣.無線傳感器網絡中的數據壓縮技術研究［J］.計算機應用與軟件，2010，27(7):1-4.

［14］張 軍，楊子晨.多傳感器數據采集系統(tǒng)中的數據融合研究［J］.傳感器與微系統(tǒng)，2014，33(3):52-57.

［15］趙 偉，何丕廉，陳 霞，等.Web 日志挖掘中的數據預處理技術研究［J］.計算機應用，2003，23(5):62-67.

［16］Yosr N，Kaouther B S.Interpretability-based validity methods for clustering results evaluation［J］.Journal of Intelligent Information Systems，2012，39(1):109-139.

［17］Peter T，Jana H.Mathematical tools of cluster analysis［J］.Applied Mathematics，2003，4(5):814-816.

［18］古 平，劉海波，羅志恒.一種基于多重聚類的離群點檢測算法［J］.計算機應用研究，2013，30(3):751-756.