Final Report for CS5611 (Fuzzy Sets: Theory and Applications):

Fuzzy C-Means and Hard C-Means Clustering: A Comparative Study

高銘鴻 (g843134, 核研一)
何紹傑 (g853104, 核研一)
陳葦霖 (g853123, 核研一)

Table of Contents

Abstract	Problem Definition	Data Set Description	Our Approach
Simulation Results	Conclusions	Computer Programs	Division of labor
References

Abstract

本文利用 Fuzzy C-means 與 Hard C-means 對兩組數據進行聚類分析 (Cluster Analysis)，除利用 Compact 與 Separate 兩個指標來判斷此兩種方法何者較佳之外，且考慮執行的速度。

Problem Definition

本文主要嘗試用 Fuzzy C-means 與 Hard C-means 來對一組人為控制與一組雙相自然對流流譜做 Cluster Analysis。經由兩組固定資料的數據組，我們可以重複進行 Fuzzy C-means 與 Hard C-means 的聚類分析，在比較兩者所得的平均結果，及所需時間，我們可以了解到此兩種方法的主要差異。

在比較 Fuzzy C-means 與 Hard C-means，我們運用了兩個指標：Compact 與 Separate。我們將此兩指標分別定義如下：

Compact：	經聚類分析後的各群組對於其中心的緊密程度。 如果群組各點的分佈越分散，其值越大。
Separate：	經聚類分析後的各群組間，彼此中心的分散程度。 如果各群組的中心點彼此距離越分散，則其值越大。
S ：	Compact / Separate，數值越小，則視為 Cluster Analysis 效果越好。

由上表可知，如果 Cluster Analysis 的各群組對於其中心點越集中、各中心點越分散，則我們認為這樣的 C-means 運算是較好的方式。

藉由對稱的人為控制數據組，我們可以明顯的看出 FCM 與 HCM 的分類是否正確，進而對散亂的雙相流譜組進行 Cluster Analysis。

除利用 Compact 與 Separate 兩個指標外，我們另記錄對同一組數據，FCM 與 HCM 各別做 100 次 Cluster Analysis 運算，記錄其每次運算的次數，以辨別何者的分類速度較快。

Data Set Description

Approach

本文主要探討的重點在於：

1. FCM 與 HCM 的 Cluster Analysis 結果，何者具有較佳的表現。
2. FCM 與 HCM 達到結果所需的時間。

但是值得注意的是，計算次數的多寡並不能直接代表（正比於）執行所需時間。這是由於不同的運算模式，所需一個週期的計算時間並不相同，以本文討論的範圍，HCM 一週期所需的時間比 FCM 所需的時間來得少。因此如果 HCM 所需的計算次數較少，則可以肯定 HCM 所花的時間較少；但是 FCM 次數較少並不一定代表所需的時間較短。

Simulation Results

經過 FCM (Fuzzy C-means) 與 HCM (Hard C-means) 的運算後，我們得到下列結果，並分類加以比較。

人為控制數據組

---

分類結果

HCM



FCM



---

分類中心點移動軌跡圖

HCM



FCM



---

分類中心點分佈 center.gif

HCM



FCM



---

每回運算所需次數

HCM



FCM

雙相流譜數據組

---

分類結果

HCM



FCM



---

分類中心點移動軌跡圖

HCM



FCM



---

分類中心點分佈

HCM



FCM



---

每回運算所需次數

HCM



FCM



---

Compact 與 Separate 指標結果

人為控制數據組 (進行 100 次判別)

	Average epoch	elapsed time, sec	sec/ per epoch	compact index	separate index	validity function S
FCM	59.72	956.48	0.160	0.100118	1.021757	0.097987
HCM	8.80	114.41	0.130	0.149153	0.950883	0.156857

雙相流譜數據組 (進行 100 次判別)

	Average epoch	elapsed time, sec	sec/per epoch	compact index	separate index	validity function S
FCM	159.23	4221.08	0.265	0.004655	0.044222	0.105271
HCM	22.33	465.82	0.209	0.007530	0.047873	0.157298

Conclusion Remarks and Future Work

• Concluding Remarks:

人為控制數據組

1. 無論 separate 與 compact 指標，都可以明顯的看到 FCM 的結果都優於 HCM，因此在 Cluster Analysis 方面，判定使用 Fuzzy C-means 得較佳結果。
2. 在使用時間方面，HCM 跑完一個 circle 的時間已較小於 FCM 使用的時間，且 HCM 僅需 1/7 的次數便可以得到結果，使得 HCM 在執行時間上佔有絕對優勢。

雙相流譜數據組

1. HCM 所得的中心點分布較 FCM 所得的分布來得佳（較分散），但是由於每個群組間的分散程度也相較較大，使得整體的 S 值較 FCM 大。比較 S，發現 Fuzzy C-means 的結果還是比使用 Hard C-means 佳。
2. 由平均運算次數來看，Hard C-means 的運算次數明顯小於 Fuzzy C-means 甚多。
   由於此組數據的分布不再那麼「對稱」，因此 HCM、FCM 每個 circle 所需時間都增加許多，且 FCM 的計算次數平均更高達 159.23 次；不過仍約為 HCM 的七倍左右。

綜合比較

1. 同一數據組，如用 Fuzzy C-means 進行 Cluster Analysis，則每次中心點的位置皆在相同地點；但是如果使用 Hard C-means，則約有十分之一的機會會有第二種分佈產生。
2. 如果一組數據的數量相當的龐大，雖然利用 Fuzzy C-means 可以得到較佳的結果，但是相對的所付出的時間會拉長許多，因此在兩者之間必須做一個平衡取捨，而在不同的情況下有不同的決定，必須視個別情況自行決定。
   
• Future Work:
1. Cluster Analysis 在流譜分析上有極大的作用，一捲兩個小時的錄影帶上具有 216000 張影像，如果能先建立起標準流譜在 「平均值、標準差」平面上的分佈，則在鑑別上速度會增快許多。
2. 目前進行 Cluster Analysis 所得的結果並沒有進行人工鑑別，也就是可能同一相似流譜卻在不同的分類區中。這與流譜的連續變化與簡化為灰階像素分佈模型有關。應在此點加以認證，才能對此工具有更大的信心。

Computer Programs

• 所有的程式皆為 Matlab 格式。
• 本文所使用之程式碼 及說明。
• 執行本文的模擬，需進入 Matlab，切換至模擬程式所在目錄下，執行 fcmtest.m 或 hcmtest.m 即可

Division of Labor

• 高銘鴻: MATLAB coding
• 陳葦霖: DATA BASE, report writing
• 何紹傑: Software collection

References

• 張智星, 孫春在, 水谷英二, "Neuro-Fuzzy and Soft Computing," Prentice-Hall, Inc. , 1997.
• X. Xie and G. Beni, "A Validity for Fuzzy Clustering," IEEE TRans. Pattern Anal. Machine Intell., vol. PAMI-13, no. 8 pp. 841-847, August 1991.