clustering

clustering(分群)
無中生有:一開始沒有明顯的群,是散亂的資料
unsupserised learning(非監督式學習)
通常先有分群才有分類
ps:
classification(分類)
有中生有:群己經形成及可類
supserised learning(監督式學習)

說明
資料分群能將每筆資料,透過資料的屬性值之相似程度,自動聚集成好幾個群組(cluster),一個群組表示群組內的資料都非常相似,而不同群組的資料都不相似,在資料探勘上,這種只透過資料本身的屬性即能進行運算的方式,也稱為非監督式學習(unsupervised learning)。相對於監督式學習(supervised learning),必須依賴預設的類別與包含類別的訓練資料,像是分類(Classification),必須先定義各群所代表的意義與主要屬性,然後依照資料與各群的相關性進行運算。

應用
資料分群被應用的領域很廣,不管是在商業或生物學等領域,而在異常分析中,可以透過分群的方式找出離異值,協助稽核人員檢測可疑的資料。
 


分群步驟
1.define attribute(定義屬性):此部分與本行高度相關
2.coding(轉碼)
3.similarity measures
4.clustering和explain

分群的品質指標
high intra-class similarity(群內高相似)
low inter-class similarity(群間低相似)
ps:以上兩項取決於similarity measure方式

常見分群方法
distance-based clustering:

分割式分群法(partitional clustering):適合球面形狀資料,不適合複雜形狀
ex:k-mean,k-medoids/pam,clara
階層式分群法(hierarchical clustering):計算成本小但無法修正錯誤,除非用其他方式做修正
ex:birch,cure,rock
密度為基礎的分群法(density-based clustering):適合複雜形狀,
ex:dbscan,optics,denclue,dbclasd,wavecluster 
格狀為基礎的分群法(grid-based clustering):處理時間與資料多寡無關,而是取決於格的數量 ex:sting,qlique,wavecluster
model-based clustering:ex:EM-algorithm,SOM,
high-dimensional data 
clustering:適合大量屬性,可分為子空間分群及頻繁樣式分群 
constraint-based(限制式分群):ex:COD CLARANS
fuzzy clustering:ex:Fuzzy C-Means
[Paquet2004;datamining concepts and techniques2]

hierarchical clustering methods
階層式,可在分為
agglomerative(聚合式),依效率排序如下
 single linkage(單一鏈結),最差
 complete linkage(完全鏈結),
 average linkage(平均鏈結),
 ward's method:最好
divisive(分裂式),先把資料視為同一群,在同中求異
 包括mst 

agglomerative hierarchiaal method
1開始個別物件
2聚集將最相似的物件
3依他們的相似度合併最初的群
4當相似度遞減,所有子群合成一個大群

 


.........................................

similarity measures(相似度計算)
分群對象兩兩之間相似度
分類複雜資料時先測量相似度
需考慮的有
 變數特性,包括discrete(離散),continuous(連續),binary(是或否)
 測量尺度,包括nominal(名目),ordinal(順序),interval(區間),ratio(比率)
 subject matter knowledge(本行事務知識)

ps:
使用distance(距離)描述dissimilarities(相異度)
常見公式有
euclidean distance(歐幾里得距離)
minkowski metric
canberra metric
czekanowski coefficient
ps:以上皆為nonnegative variables(非負變數)


.........................................................

相似度係數計算
1定義屬性
2定義變數
3選取其中2項比較
相同表示0,相異表示1
a=abs(1-1)=0=match
b=abs(1-0)=1=mismatch
c=abs(0-1)=1=mismatch
d=abs(0-0)=0=match
4製作contingence table
 k_1 k_0 total 
i_1
i_0 
a b
c d 
a+b
c+d 
total a+c b+d p=a+b+c+d  

5套入相似度係數
常用的有
(a+d)/p
a/(a+b+c):0-0不考慮,只考慮有出現的狀態
ex
1
定義屬性

item mb flow os
ip1 68mb 1400flow xp
ip2 73mb 1850flow linux
ip3 67mb 1650flow mac
2
定義binary變數

x1={1 mb>=72, 0 mb<72}
x2={1 flow>=1500, 0 flow<1500}
x3={1 os=xp, 0 otherwise}
3
取其中2個item比較

item x1 x2 x3
ip1 0 0 1
ip2 1 1 0
0-1有2個
1-0有1個
4
match和mismatch數量
 ip2_1 ip2_0 total 
ip1_1
ip1_0 
0 1
2 0 
1
total 2 1 3  

5
套入相似度係數
(a+d)/p=(0+0)/3=0/3=0

 

.................................................................................................................................

 

single linkage
1為所有可能成對物件計算相似係數
2從第一個群中選擇2個最像物件
3降低相似程度並形成新群,該新群是包括所有相似係數不低於門檻值的物件
4繼續第3步直到各群漸漸變成一個大群,或己達指定的群數為止

ex:
step1
 
    
   
  
 
11 10 2 

該群中2最小
2在第5列第3行,以d(5,3)表示
第1,2,4行或列,不在2的行列,以此產生新值如下
d(5,3)1 = min{d(5,1),d(3,1)} = min{11,3}=3
d(5,3)2 = min{d(5,2),d(3,2)} = min{10,7}=7
d(5,3)4 = min{d(5,4),d(3,4)} = min{8,9}=8

step2
 (53) 
(53)    
3   
 
該群中3最小
3在第1列第(53)行,以d(1,(53))表示
第2,4行或列,不在3的行列,以此產生新值如下
d(1,(53))2 = min{d(1,2),d((53),2)} = min{9,7}=7
d(1,(53))4 = min{d(1,4),d((53),4)} = min{6,8}=6

step3
 (1(53)) 
(1(53))   
 
5 

該群中5最小
5在第4列第2行,以d(4,2)表示
第(1(53))行或列,不在5的行列,以此產新值如下
d((4,2)(1(53)))=min{d(4,(1(53))),d(2,(1(53)))} = min{6,7} = 6

step4
 (1(53)) (24) 
(1(53))  
(24) 
 

.............................................................


使用工具
minitab

single,average,ward,complete,...等linkage步驟
1先將資料貼到worksheet
依輸入資料形式不同有2種做法
若輸入資料為matrix形式
 2點擊data > copy > copy columns to matrix ,會跳出對話視窗
 2.1將左欄要用到的欄位選取好後按select,則要用到的欄位會出現在右欄copy from columns中
 2.2在store copied data區域中輸入一欄位 ex:d
 2.3點擊ok,copy from columns對話視窗關閉
 3點擊stat > multivariate > cluster variables ,會跳出對話視窗
若輸入資料為一筆筆的形式
 2該步驟可省略
 3點擊stat > multivariate > cluster observation ,會跳出對話視窗
3.1將左欄中在2.2建的欄位選取好後按select,則該欄位會出現在右欄variables or distance matrix中
3.2linkage method可選擇single,ward,complete,average,...等,並勾選show dendgrogram
3.3點擊customize,會跳出對話視窗
3.3.1在label y axis with 選擇distance
3.3.2點擊ok,customize對話視窗關閉
3.4點擊ok,cluster variables對話視窗關閉
4結果顯示

 

2011-06-20 16:49:05發表 2013-01-20 18:36:08修改   

數據分析

程式開發
計算機組織與結構
資料結構與演算法
Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統
數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net