本論文提出一個新的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.

[5] C. Olaru and L. Wehenkel, "Data Mining", IEEE Computer Application in Power, Vol. 12, No. 3, July1999, pp. 19-25.

[6] Alsabti, K., Ranka, S., and Singh,V., "An efficient K-means clustering algorithm," First Workshop on High-Performance Data Mining, 1998.

[7] Elkan, C.,"Using the triangle inequality to accelerate K-Means," Proc. International
Conference on Machine Learning, 2003.

[8] W. J. Hwang, S.S. Jeng and B.Y. Chen, "Fast Codeword Search Algorithm Using Wavelet Transform and Partial Distance Search Techniques," Electronic Letters, pp. 365-366,Vol.33, February 1997.

[9] Estlick, M., Leeser, M., Theiler, J., and Szymanski, J.J., "Algorithmic transformations in the implementation of K- means clustering on reconfigurable hardware," Proceedings of ACM/SIGDA ninth international symposium on Field programmable gate arrays, 2001.

[10] Gokhale, M., Frigo, J., Mccabe, K., Theiler, J., Wolinski, C., and Lavenier, D.,
"Experience with a Hybrid Processor: K-Means Clustering," The Journal of Supercomputing, pp. 131-148, 2003.

[11]Maruyama, T. "Real-time K-Means Clustering for Color Images on Reconfigurable Hardware," Proc. 18th International Conference on Pattern Recognition, 2006.
[12] Filho, A.Gda.S., Frery, A.C., de Araujo, C.C., Alice, H., Cerqueira, J., Loureiro,
J.A., de Lima, M.E., Oliveira, Mdas.G.S., Horta, M.M., "Hyperspectral images
clustering on reconfigurable hardware using the k-means algorithm," Proceedings
of 16th Symposium on Integrated Circuits and Systems Design, pp. 99-104, 8-11
Sept. 2003.

[13] Liu, W.C., Huang , J.L., and Chen, M.S., "KACU: K-means with hardware centroid-updating , " Proc. IEEE Emerging Information Technology Conference, 2005.
[14] Tse-Wei Chen, Chih-Hao Sun, Jiun-Ying Bai, Han-Ru Chen, and Shao-Yi Chien, "Architectural analyses of K-Means silicon intellectual property for image segmentation, " in Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS2008), Seattle, Washington, USA, May 2008, pp. 2578–2581. (4 pages)

[15] ALTERA official web site.
http://www.altera.com

[16] Gersho, A., and Gray, R.M., Vector Quantization and Signal Compression, Kluwer, Norwood, Massachusetts, 1992.