簡易檢索 / 詳目顯示

研究生: 楊政諺
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.

    中文摘要 i Abstract ii 誌謝 iii 附圖目錄 vi 附表目錄 viii 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機 4 1.3 研究目的 5 1.4 全文架構 6 第二章 理論基礎與技術背景 7 2.1 Fuzzy C-Means 演算法 7 2.2 SOPC系統整合設計 11 第三章 基礎電路架構介紹 15 3.1 簡介 15 3.2 Pre-computation unit 17 3.3 Membership coefficients updating unit 21 3.4 Centroid updating unit 24 3.5 Cost function computation unit 30 3.6 On-Chip Centroid RAM 32 3.7 Control Unit 34 第四章 實驗結果與數據探討 39 4.1 開發平台與實驗環境介紹 39 4.2 實驗數據的呈現與討論 46 第五章 結論 57 參考著作 58

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

    下載圖示
    QR CODE