簡易檢索 / 詳目顯示

研究生: 楊正存
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.

    中文摘要 i Abstract ii 誌謝 iii 附圖目錄 vi 附表目錄 viii 第一章 緒論 1 1.1研究背景 1 1.2研究動機與目的 4 1.3全文架構 6 第二章 理論基礎與技術背景 7 2.1 Fuzzy C-Means 演算法 7 2.2 SOPC系統整合設計 10 第三章 基礎電路架構介紹 14 3.1簡介 14 3.2 Pre-computation Unit 16 3.3 Membership Coefficients Updating Unit 21 3.4 Centroid Updating Unit 25 3.5 Cost Function Computation Unit 28 第四章 實驗結果與數據探討 30 4.1 開發平台與實驗環境介紹 30 4.2 實驗數據的呈現與討論 37 第五章 結論 46 參考著作 47

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

    下載圖示
    QR CODE