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

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

0 引 言

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

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

1 KSummary 算法

1.1 KSummary 算法與相關概念

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

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

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

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

定義3 設C，C1，C2為數(shù)據(jù)集合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是數(shù)值屬性時，定義為

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

若Di為數(shù)值屬性，則該值定義為

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ù)數(shù)值屬性

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

1.2 KSummary 算法的不足

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

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

2.1 體系結構

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

2.2 自適應層次聚類

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

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

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

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

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

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

2.3 密度聚類與迭代過程

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

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

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

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

2.4 傳感器數(shù)據(jù)集

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

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

3 實驗結果和分析

3.1 實驗環(huán)境

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

3.2 實驗和結果

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

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

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

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

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

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

4 結束語

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

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

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

［2］ Han Jianwei，Micheline Kamber，Pei Jian.數(shù)據(jù)挖掘概念與技術［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］ 馬華東，陶 丹.多媒體傳感器網(wǎng)絡及其研究進展［J］.軟件學報，2006，17(9):2013-2028.

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

［8］ 蔣盛益，李 霞，鄭 琪.數(shù)據(jù)挖掘原理與實踐［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］尹亞光，貴 廣.無線傳感器網(wǎng)絡中的數(shù)據(jù)壓縮技術研究［J］.計算機應用與軟件，2010，27(7):1-4.

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

［15］趙 偉，何丕廉，陳 霞，等.Web 日志挖掘中的數(shù)據(jù)預處理技術研究［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.