以FPGA實現非監督式Fuzzy c-means分群演算法之硬體架構設計

Hardware Circuit Design of Unsupervised Fuzzy c-means Clustering Algorithm Implemented on FPGA

沈宗懋

指導教授 ： 黃文吉

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2011年)

摘要

Fuzzy c-means演算法是一個非常常見的分群演算法，但是因在計算分群之前必須給定分群數，然而我們不能知道哪個分群結果是最好的，是屬於一種監督式的演算法。基於這個理由本論文提出了一個完全非監督式的Fuzzy c-means分群演算法(Unsupervised Fuzzy c-means Clustering Algorithm)並且實現其硬體電路架構，當Fuzzy c-means運算收斂結束，利用Xie和Beni所提出的群集有效性指標(Cluster Validity Index)來驗證分群的有效性，並且選擇出最佳的分群數目。在對於分群演算法的更新計算質量中心以及更新權重矩陣這兩個步驟在本電路裡整合為單一個更新步驟，來減少使用的儲存空間。並且藉由管線化來實現運作，可利用較低的資源得到更快的計算速度。
最後我們所提出的架構會在以FPGA(Field Programmable Gate Array)為基礎的可程式化晶片設計(System On a Programmable Chip , SOPC)之平台上做實際的驗證測試，經由數據結果的測試與比對可以發現本論文中的架構可以辨認出最適合的分群結果，達到非監督化。

關鍵字

資料分群 ； 可程式化系統晶片 ； 群集有效性指標

並列摘要

無資料

並列關鍵字

Fuzzy c-means ； FPGA

參考文獻

[1] J. B. MacQueen, “Some Methods for classification and Analysis of Multivariate Observations,” Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press, pp. 281–297, 1967.

[3] J. C. Bezdek, “Pattern Recognition with Fuzzy Objective Function Algorithms,” Plenum, New York , 1981.

[4] N. R. Pal , J. C. Bezdek, “On cluster validity for the fuzzy c-means model.” IEEE Transactions on Fuzzy System, Vol. 3, No. 3, p.370-379, 1995.

[7] H. Y. Li, C. T. Yang, W. J. Hwang, “Efficient VLSI Architecture for Fuzzy C-Means Clustering in Reconfigurable Hardware”, Proc. IEEE International conference on Frontier of Computer Science and Technology, pp.168-174, 2009.

[8] Xunali Lisa Xie, Genardo Beni. “A Validity measure for FuzzyClustering”, IEEE Transactions on Pattern Analysis andmachine Intelligence, Vol.13, No4, August 1991.