適於多叢集Fuzzy C-Means分群演算法之硬體架構設計

Fuzzy C-Means Hardware Architecture for Applications Having Large Number of Clusters

楊政諺(Cheng-Yen Yang)

指導教授 ： 黃文吉

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

摘要

本論文提出一個適合在高叢集的Fuzzy c-means分群演算法硬體架構，同時對分群質量中心點和訓練向量作管線化架構(pipeline)，可以獲得更低的硬體資源消耗和更高的計算速度。此外，合併以往迭代更新權重矩陣(membership coefficient matrix)以及質量中心成為單一的更新步驟，可以避免使用大量的儲存空間。

最後本論文所提出的硬體架構會在以FPGA為基礎的可程式化系統晶片設計(System On a Programmable Chip，SOPC)之平台上作實際的效能測試。由實驗的結果可知，本架構具備較低的計算複雜度、較低的硬體資源複雜度以及更高的效能。

關鍵字

現場可程式邏輯陣列 ； 可重組化計算 ； 資料分群 ； 模糊系統 ； 可程式化系統晶片

並列摘要

This paper presents a novel low-cost and high-performance VLSI architecture for fuzzy c-means clustering. In the architecture, the operations at both the centroid and data levels are pipelined to attain high computational speed while consuming low hardware resources. In addition, the usual iterative operations for updating the membership matrix and cluster centroid are merged into one single updating process to evade the large storage requirement. Experimental results show that the proposed solution is an effective alternative for cluster analysis with low computational cost and high performance.

並列關鍵字

FPGA ； reconfigurable computing ； data clustering ； fuzzy system ； system on programmable chip

參考文獻

[3] R. Cannon, J. Dave, J. Bezdek, “Efficient Implementation of the Fuzzy C-Means Clustering Algorithm,” IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 248-255, 1986.

[5] C. Chinrungrueng and C. H. Sequin, "Optimal Adaptive K-means Algorithm with Dynamic Adjustment of Learning Rate", IEEE Transactions on Neural Networks, Vol. 6, No. 1, January 1995, pp.157-169.

[7] S. Eschrich, J. Ke, L. O. Hall, and D. B. Goldgof, “Fast Accurate Fuzzy Clustering Through Data Reduction,” IEEE Trans. Fuzzy Systems, pp. 262-270, 2003.

[8] J. Garcia-Lamont, L. M. Flores-Nava, F. Gomez-Castaneda, J. A. Moreno-Cadenas, ”CMOS Analog Circuit for Fuzzy C-Means Clustering,” IEEE Proc. 5th Biannual World Automation Congress, 2002.

[10] P. Hung, H. Fahmy, O. Mencer, and M. J. Flynn, “Fast Division Algorithm with a Small Lookup Table,” IEEE Asilomar Conference on Signals, Systems, and Computers, pp. 1465-1468, 1999.