研究生: |
楊正存 Cheng-Tsun Yang |
---|---|
論文名稱: |
在可程式化系統晶片上之Fuzzy C-Means分群演算法設計 SoPC-based Fuzzy C-Means Clustering Algorithm Design |
指導教授: |
黃文吉
Hwang, Wen-Jyi |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2009 |
畢業學年度: | 97 |
語文別: | 中文 |
論文頁數: | 48 |
中文關鍵詞: | 可重組計算 、資料分群 、模糊理論 、現場可程式化閘陣列 、可程式單晶片系統 |
英文關鍵詞: | reconfigurable computing, data clustering, fuzzy system, FPGA, system on programmable chip |
論文種類: | 學術論文 |
相關次數: | 點閱:311 下載:2 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本論文提出一個具平行計算能力的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.