ＴＣＰ連接性能的ＦＣＭ聚類分析

摘要：分析了模糊聚類中的FCM（Fuzzy C-Means）算法，利用該算法對一個TCP連接日志的抽樣數據進行聚類，利用聚類中心對任選的兩組數據集進行分類，并對聚類結果進行了分析。

關鍵詞：模糊聚類；FCM算法；TCP連接

中圖分類號：TN915文獻標識碼：A 文章編號：1009-3044(2008)25-1527-03

Clustering Analysis of TCP Connection Capability Based on FCM

GAO Ai-hua1， LI Chun-fang2， CUI Wei1

(1. HNUST University， Qinhuangdao 066004， China；2 Hebei Institute of Physical Education， Shijiazhuang 050041， China)

Abstract: Analyzed the algorithm of FCM(Fuzzy C-Means)， clustered a sample dataset of TCP log using FCM， classified 2 groups dataset using the center point， and analyzed the clustering's outcome.

Key words: fuzzy clustering; FCM; TCP connection

1 引言

聚類屬于無監督分類，在沒有訓練數據樣本的情況下，依據對象自身的相似性把一組對象劃分成一系列有意義的子集，并使同一類中的數據對象相似度高，不同類中的數據對象相似度低。聚類分析作為統計學的一個分支，已經研究了多年，主要集中于基于距離的聚類分析[1-2]。模糊聚類可以得到樣本對于類別的不確定性描述，更能客觀地反映現實世界，成為聚類研究的主流。

2 FCM 算法

2.1 算法思想

模糊C均值(FCM)聚類法是基于目標函數的模糊聚類算法，由J.C.Bezdek和P.F.Castelaz于1977年提出的，是在傳統C均值算法(K-means)中應用了模糊技術。設被分類對象的集合為U={u1，u2，…，un}，其中每一個ui有m個特征指標，設為ui={ui1，ui2，…，uim}，特征指標矩陣為，如果要把U分成c類(2≤c≤n)，設c個聚類中心向量。為獲得最佳的模糊分類，從Mfc中優選出一個最好的模糊分類，即求出適當的模糊矩陣R及V，使目標函數：

J(R，V)=∑ ∑(rik)q ||uk-Vi||2 (1)

達到極小值，其中q>1(一般q=2)，||uk-Vi||表示對象uk與第i類聚類中心向量Vi的距離。常用的距離有：Chebyshev距離，Hamming距離，Euclid的距離。FCM算法就是采用迭代運算求出目標函數J(R，V)的近似解。

目標函數的物理意義：使用模糊分類矩陣R元素的q次方(rik)q 作為權重對uk與第i類聚類中心向量Vi的距離的求和，rik是uk對第i類的隸屬度，即是一種加權的K-means算法思想。

2.2 算法步驟

1977年，J.C.Bezdek證明了：當q≥1，uk≠Vi 時，該算法是收斂的[3]。求最佳模糊分類矩陣和最佳聚類中心矩陣算法如下：

第1步：選定分類數c，2≤c≤n，任取一初始模糊分類矩陣R(0)∈Mfc，逐步迭代，l=0，1，2，…。

第2步：對于R(l)，計算聚類中心矩陣V(l)=(V1(l) V2(l) …Vc(l) )T，其中

Vi(l)=∑ (rik(l))quk/∑ (rik(l))q (2)

第3步：修正模糊分類矩陣R(l)，取

(3)

第4步：比較R(l)與R(l+1)，若對于給定的精度ε>0，有Max{|rik(l)-rik(l+1)|}≤ε，則R(l+1)和V(l)即為所求，停止迭代；否則，l=l+1，回到第2步，重復進行。

算法解釋：求公式(1)的最小值，用Lagrange數乘法J(R，V，λ)=∑ ∑(rik)q ||uk-Vi||2+∑λk[∑(rik)-1]，對J(R，V，λ)求偏導數并令它們等于0，由于||uk-vi||≥0，q>1，解得式(2)和(3)[4]。

上述算法得到的模糊分類矩陣R(l+1)和聚類中心矩陣V(l)是相對于分類數c，初始模糊分類矩陣R(0)，ε和參數q的局部最優解。

算法要求uk≠Vi ，模糊分類矩陣R(0)要滿足模糊分類矩陣的3個條件外，還要滿足：(1) R(0)不能是每一元素都相同的常數矩陣；(2) R(0)不能是某行元素等值的矩陣；(3) R(0)中對只有一個對象的類，聚類前要去掉，待聚類后再放入。滿足6個條件，才不會在迭代計算過程中造成失真，否則將使聚類分析失效。

2.3 聚類判別

(1)判別原則Ⅰ：利用最佳模糊分類矩陣。設求得的最佳模糊分類矩陣為，?坌uk∈U在 R* 的第k列中，如果rik*=max1≤j≤c(rjk*)，則將對象uk歸于第i類，即按最大隸屬度歸類。

(2)判別原則Ⅱ：利用最佳聚類中心矩陣。設求得最佳聚類中心矩陣為V*=(V1*，V2*，…，Vc*)T，?坌uk∈U，如果||uk-Vj*||=min1≤j≤c(||uk-Vj*||)，則將對象uk歸于第i類，即按與聚類中心距離最近歸類。

2.4 聚類效果檢驗

根據分類系數Fc(R)=2/n ∑ ∑(rik)2和平均模熵Hc(R)=-2/n ∑ ∑(rik)ln(rik)檢驗聚類效果，Fc(R)愈接近于1，Hc(R)越接近于0，聚類效果越好。

3 TCP連接狀態的模糊聚類分析

網絡服務質量QOS，是指網絡服務性能的聚集效應，它決定用戶對特定服務的滿意程度。從網絡提供者的角度說，可以通過控制一些具體的、可度量的參數來提供服務質量，如傳輸延遲、抖動、丟失率、帶寬、吞吐量等指標。從TCP連接歷史數據的聚類分析中取得聚類中心，通過采集的實時數據與聚類中心的比較，可以實時概要描述網絡的服務質量。

3.1 數據清洗

實驗數據是Lawrence Berkeley Laboratory 30天的TCP連接（http://ita.ee.lbl.gov/html/contrib/LBL-CONN-7.htm，簡稱LBL）。采用刪除殘缺數據清洗，532975條數據經清洗得到481513條記錄，平均約每5.3秒產生一條TCP連接。LBI的TCP連接日志數據見表1。

表1 LBL的TCP連接日志數據

在數據集中許多屬性是與挖掘任務無關的或冗余的，對于挖掘網絡服務性能而言，本文選擇研究時間戳（timestamp）、連接時間（duration）和發起請求字節數（bytes_original）、響應字節數（bytes_response）的關系。表1所示為LBL文本數據經數據轉換存入SQL Server數據庫表中，并經清洗后的兩條，內容見字段名。

本文采用取樣法，隨機取20組數據，得到特征指標矩陣U。第一次試驗采用單條數據作為聚類點，由于在ftp，ftpdata等大數據塊傳輸時，回突顯這些大值的作用，使得聚類效果較差；為避免單條大值數據的影響，第二次試驗增大了粒度，合并時間上連續的10條日志作聚類點。由于網絡服務質量一般是平穩漸進變化的，所以此種取樣更符合用戶的主觀感受具有實際意義。待聚類點用向量u=(u1，u2，u3，u4)表示，u1:10次時間連續的duration之和，u2:10次連續的bytes_original之和，u3:10次時間連續的bytes_response之和，u4=(u2+u3)/u1，代表連接速率。

3.2 數據規格化

由于各個特征指標的量綱和數量級不同，在運算中可能突出某數量級特別大的指標的作用，而降低甚至排出了數量級很小的指標的作用，為此，在聚類前要進行數據規格化。常用的方法包括：基于均值和方差的數據標準化、均值規格化、中心規格化、最大值規格化、極差規格化和對數規格化等。本例采用級差規格化，得到特征指標矩陣U'，見表2。

3.3 聚類過程

指定分類數c=3，利用Matlab的fcm()函數聚類，初始模糊分類矩陣R(0)是根據U'自動確定，取q=2，ε=0.001，經過15次迭代運算，得到最佳模糊分類矩陣R*和聚類中心矩陣V*，見表2和表3。

表2 特征矩陣U，格式化矩陣U'，模糊分類矩陣R*

利用判別原則Ⅰ，得到聚類結果見表4。圖1所示為目標函數的迭代收斂曲線，圖2是20組聚類點及聚類中心的散點圖。其中x，y，z軸分別為u1，(u2+u3)和u4規格化后的值，由圖中可以對聚類結果做如下解釋：C1類包含絕大部分元素，它為網絡狀態正常的一類；C2只包含u13， u1'大，(u2'+u3')小，u4'小，表示網絡連接時間長，傳輸的字節數少，網絡速度慢；C3只包含u11，它的u1'小，(u2'+u3')大，u4'大，即連接時間短，傳輸的字節數多，速度快。

經計算，得到分類系數F=0.9645，接近于1，平均模糊熵H=0.0893，接近于0，聚類效果可以接受。

表3 聚類中心V* 表4 聚類結果

圖1 目標函數收斂過程 圖2 20組聚類點及聚類中心的散點圖

3.4兩組數據的時間序列分析

利用聚類中心，將一段時間內的網絡狀態分類。每組50個，第1組為50個時間序列數據點，第2組為500次時間序列10次合并后的數據點。表5是對數據采用Euclid距離計算了聚類點與聚類中心的距離，按距離最近歸類的結果。第一組中u42屬于網絡服務質量差的C2，u18屬于網絡服務質量好的C3，其余是正常的C1。第2組中u8，u31屬于C2，u11，u24屬于C3，其余元素屬于C1。

表5 兩組TCP連接時間序列的分類結果

圖3和圖4為兩組數據的散點圖，圖5和圖6為時間序列速率波形，圖6顯示出大值數據對聚類的干擾較大。

圖3 粒度為1的50個點 圖4 粒度為10的50個點

比較圖5和圖6可見，用粒度為10的數據點的聚類中心，作為衡量此網絡狀態的標準，按照同樣的聚類中心對粒度為10的數據進行分類時效果較好，對粒度為1的數據點分類效果稍差。在尋找聚類中心時，采用粒度為10的聚類點與采用粒度為1的聚類點相比可以有效降低大值數據干擾。

圖5 粒度為1的時間序列速率波形圖6 粒度為10的時間序列速率波形

4 結束語

在各種模糊聚類算法中，FCM是應用最廣泛的方法之一，適用于具有橢球狀分布的數據聚類。將FCM算法應用于TCP連接日志分析，通過聚類中心能合理分類TCP連接狀態，用于實時的網絡性能分析。聚類的中心點可以作為網絡流量控制閾值選擇依據，也可以挖掘異常數據用于入侵檢測。

對TCP連接日志的聚類分析沒有考慮非數值屬性的作用，對混合類型的數據分析及加權系數的FCM算法是下一步研究的重點。

參考文獻：

[1] 陳安，陳寧，周龍驤，等. 數據挖掘技術及應用[M].北京(2006):科學出版社，2006，177-248.

[2] Witten I H， Frank E. 數據挖掘—實用機器學習技術[M]. 董琳，等譯.北京:機械工業出版社，2006.2:241-284.

[3] 陳水利，李敬功，王向公. 模糊集理論及應用[M].北京:科學出版社，2005:59-139.

[4] Wu Yirong， Cao Fang， Hong Wen. An unsupervised classification for fully polarimetric Sar data using span/h/α ihsl transform and the fcm algorithm.journal of electronics (china)[J]. 2007，24(2):145-149.