研究生: |
楊政諺 Cheng-Yen Yang |
---|---|
論文名稱: |
適於多叢集Fuzzy C-Means分群演算法之硬體架構設計 Fuzzy C-Means Hardware Architecture for Applications Having Large Number of Clusters |
指導教授: |
黃文吉
Hwang, Wen-Jyi |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2010 |
畢業學年度: | 98 |
語文別: | 中文 |
論文頁數: | 60 |
中文關鍵詞: | 現場可程式邏輯陣列 、可重組化計算 、資料分群 、模糊系統 、可程式化系統晶片 |
英文關鍵詞: | FPGA, reconfigurable computing, data clustering, fuzzy system, system on programmable chip |
論文種類: | 學術論文 |
相關次數: | 點閱:126 下載:4 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本論文提出一個適合在高叢集的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.
[1] ALTERA official web site
http://www.altera.com
[2] J. C. Bezdek,” Fuzzy Mathematics in Pattern Classification,” Ph.D Thesis, Cornell University, 1973.
[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.
[4] T. W. Cheng, D. B. Goldgof and L. O. Hall, “Fast Fuzzy Clustering,” Fuzzy Sets and Systems, pp. 49-56, 1998.
[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.
[6] Cyclone III Device Handbook, 2010, Altera Corporation.
http://www.altera.com/products/devices/cyclone3/cy3-index.jsp.
[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.
[9] S. Hauck, and A. Dehon, “Reconfigurable Computing,” Morgan Kaufmann, 2008.
[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.
[11] Integer Arithmetic Megafunctions User Guide, Altera Corporation.
http://www.altera.com/literature/ug/ug_lpm_alt_mfug.pdf
[12] 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.
[13] 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.
[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,” Microprocessors and Microsystems, pp. 375-380, 2005.
[15] 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.
[16] H. Y. Li, C. T. Yang, W. J. Hwang, “Efficient VLSI Architecture for Fuzzy C-Means Clustering in Reconfigurable Hardware”, Proc. IEEE International conference on Frontier of Computer Science and Technology, 2009, pp.168-174.
[17] J. B. MacQueen, "Some Methods for classification and Analysis of Multivariate Observations". Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press.1967, pp. 281–297.
[18] NIOS II Processor Reference Handbook, 2007, Altera Corporation.
http://www.altera.com/literature/lit-nios2.jsp.
[19] C. Olaru and L. Wehenkel, "Data Mining", IEEE Computer Application in Power, Vol. 12, No. 3, July1999, pp. 19-25.
[20] N. R. Pal , J. C. Bezdek, 1995. “On cluster validity for the fuzzy c-means model.” IEEE Transactions on Fuzzy System, Vol. 3, No. 3, p.370-379.
[21] J. Pei, X. Yang, X. Gao, and W. Xie, “Weighting exponent m in fuzzy C-means(FCM) clustering algorithm.” Proc. SPIE Vol. 4554, p.246-251.
[22] M. Sarkar and B. Yegnanarayana, "A Clustering Algorithm Using Evolutionary Programming", IEEE International Conference on Neural Networks, USA,Vol. 2, 1996, pp. 1162-1167.
[23] S.P. Vriend, P.F.M. van Gaans, J. Middelburg and A. de Nijs, “The application of fuzzy c-means cluster analysis and nonlinear mapping to geochemical datasets: examples from Portugal.” Appl. Geochem. 3, pp. 213-224, 1988.
[24] Hans J. Zimmermann, 1990. “Fuzzy set theory and its applications.” Kluwer Academic Publishers, Boston.