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 2
total	2 1	3

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

…………………………………………………………………………………………………………………

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

ex:
step1

	1	2	3	4	5
1	0
2	9	0
3	3	7	0
4	6	5	9	0
5	11	10	2	8	0

該群中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)	1	2	4
(53)	0
1	3	0
2	7	9	0
4	8	6	5	0

該群中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))	2	4
(1(53))	0
2	7	0
4	6	5	0

該群中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))	0
(24)	6	0

…………………………………………………….

使用工具
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結果顯示