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

SoPC-based C-Means Clustering Algorithm Design

許智傑(Chih Chieh Hsu)

指導教授 ： 黃文吉

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

摘要

本論文提出一個新的c-means演算法硬體架構，在做分群處理與質量中心點的計算皆為管線化的運作，因此可以同時處理多筆訓練向量。我們計算質量中心點的除法器是由查表法、乘法器與位移運作所組成，可以大大的降低硬體複雜度且一個時脈週期即可完成除法的運算。最後我們所提出的架構會在以FPGA為基礎的可程式化系統晶片設計(System On a Programmable Chip，SOPC)之平台上作實際的效能測試，經由數據分析可以發現我們的架構會比軟體有更高的效能。

關鍵字

可程式化系統晶片 ； 分群演算法

並列摘要

A novel hardware architecture for c-means clustering is presented in this paper. Our architecture is fully pipelined for both the partitioning and centroid computation operations so that multiple training vectors can be concurrently processed. A simple divider circuit based on table lookup, multiplication and shift operations is employed for reducing both the area cost and latency for centroid computation. The proposed architecture is used as a hardware accelerator for a softcore NIOS CPU implemented on a FPGA device for physical performance measurement.Numerical results reveal that our design is an effective solution with low hardware complexity and high computation performance for c-means design.

參考文獻

[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, "Genertic K-means Algorithm", IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, Vol. 29, No.3, June 1999, pp. 433-439.

[7] Elkan, C.,"Using the triangle inequality to accelerate K-Means," Proc. International