在可程式化系統晶片上之Fuzzy C-Means分群演算法設計

SoPC-based Fuzzy C-Means Clustering Algorithm Design

楊正存(Cheng-Tsun Yang)

指導教授 ： 黃文吉

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

摘要

本論文提出一個具平行計算能力的Fuzzy c-means(FCM)演算法硬體架構，並且使用查表法(lookup table)為基礎的除法器，來減少分群處理及計算質量中心點的硬體資源複雜度和計算複雜度。此外，本硬體架構不需儲存權重矩陣(membership coefficients matrix)，而是將權重值(membership coefficinets)的計算結果直接送入質量中心點的更新計算，達到減少記憶體資源消耗的目的。最後本論文所提出的硬體架構會在以FPGA為基礎的可程式化系統晶片設計(System On a Programmable Chip，SOPC)之平台上作實際的效能測試，由實驗的結果可知，本架構具備較低的計算複雜度與更高的效能。

關鍵字

可重組計算 ； 資料分群 ； 模糊理論 ； 現場可程式化閘陣列 ； 可程式單晶片系統

並列摘要

A cost-effective parallel VLSI architecture for fuzzy c-means clustering is presented. The architecture reduces the area cost and computational complexity for membership coefficients and centroid computation by employing lookup table based dividers. 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.

並列關鍵字

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

參考文獻

[1] 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.

[2] M. Sarkar and B. Yegnanarayana, "A Clustering Algorithm Using Evolutionary Programming," IEEE International Conference on Neural Networks, USA,Vol. 2, 1996, pp. 1162-1167.

[3] D. Lee, S. Back, and K. Sung, "Modified K-means Algorithm for Vector Quantizer Design," IEEE Signal Processing Letters, Vol. 4, No. 1, January 1997, pp.2-4.

[4] K. Krishna and M. N. Murty, "Genetic K-means Algorithm", IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics," Vol. 29, No.3, June 1999, pp. 433-439.

[7] 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.