本論文提出一個具平行計算能力的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.

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

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

[6] Bezdek, J. C., "Fuzzy mathematics in pattern classification," 1973.

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

[8] T.W. Cheng, D, B. Goldgof and L.O. Hall, "Fast Fuzzy Clustering," Fuzzy Sets and Systems, pp.49-56, 1998.

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

[10]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 BiannualWorld Automation Congress, 2002.

[11] Hauck, S., and Dehon, A., " Reconfigurable Computing," Morgan Kaufmann, 2008.

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

[13] J.F. Kolen and T. Hutcheson, "Reducing the Time Complexity of the Fuzzy C-Means Algorithm," IEEE Trans. Fuzzy Systems, pp. 263-267, Vol. 10, 2002.

[14] J. Lazaro, J. Arias, J. L. Martin, C. Cuadrado and A. Astarloa, "Implementation of a Modified Fuzzy C-Means Clustering Algorithm for Realtime Applications," Microprocessorsand Microsystems, pp. 375-380, 2005.

[15] Stratix II Device Handbook, 2008, Altera Corporation.http:// www.altera.com/literature/lit-nio2.jsp.

[16] Cyclone III Device Handbook, 2008, Altera Corporation. http://www.altera.com/ products/devices/cyclone3/cy3-index.jsp

[17] NIOS II Processor Reference Handbook, 2007, Altera Corporation. http://www.altera.com/literature/litnio2.jsp

[18] Vriend. S.P. van Gaans, P.F.M., Middelburg, J. and de Nijs. A. 1988. "The application of fuzzy c-means cluster analysis and nonlinear mapping to geochemical datasets: examples from Portugal." Appl. Geochem., 3: 2 13-224.

[19] Pei Jihong, Yang Xuan, Gao Xinbo, and Xie Weixing, "Weighting exponent m in fuzzy C-means (FCM) clustering algorithm. "Proc. SPIE Vol. 4554, p. 246-251.

[20] Zimmermann, Hans J., 1990. "Fuzzy set theory and its applications." Kluwer Academic Publishers, Boston.

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