簡易檢索 / 詳目顯示

回結果列表
研究生： 沈宗懋
論文名稱： 以FPGA實現非監督式Fuzzy c-means分群演算法之硬體架構設計
Hardware Circuit Design of Unsupervised Fuzzy c-means Clustering Algorithm Implemented on FPGA
指導教授： 黃文吉
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2011
畢業學年度： 99
語文別： 中文
論文頁數： 62
中文關鍵詞： 資料分群 、可程式化系統晶片 、群集有效性指標
英文關鍵詞： Fuzzy c-means, FPGA
論文種類： 學術論文
相關次數： 點閱：185  下載：7 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • Fuzzy c-means演算法是一個非常常見的分群演算法，但是因在計算分群之前必須給定分群數，然而我們不能知道哪個分群結果是最好的，是屬於一種監督式的演算法。基於這個理由本論文提出了一個完全非監督式的Fuzzy c-means分群演算法(Unsupervised Fuzzy c-means Clustering Algorithm)並且實現其硬體電路架構，當Fuzzy c-means運算收斂結束，利用Xie和Beni所提出的群集有效性指標(Cluster Validity Index)來驗證分群的有效性，並且選擇出最佳的分群數目。在對於分群演算法的更新計算質量中心以及更新權重矩陣這兩個步驟在本電路裡整合為單一個更新步驟，來減少使用的儲存空間。並且藉由管線化來實現運作，可利用較低的資源得到更快的計算速度。
    最後我們所提出的架構會在以FPGA(Field Programmable Gate Array)為基礎的可程式化晶片設計(System On a Programmable Chip , SOPC)之平台上做實際的驗證測試，經由數據結果的測試與比對可以發現本論文中的架構可以辨認出最適合的分群結果，達到非監督化。

    附圖目錄 ............................................................................................v 附表目錄 .........................................................................................viii 第一章 緒論 ....................................................................................1 1.1 研究背景 ....................................................................................1 1.2 研究動機與目的 ....................................................................3 1.3 全文架構 ....................................................................................5 第二章 基礎理論與技術背景 ............................................................6 2.1 Fuzzy c-means分群演算法 ....................................................6 2.2 Xie and Beni分群有效性指標 ............................................10 2.3 FPGA系統整合設計 ................................................................12 第三章 基礎電路架構介紹 ..........................................................14 3.1 架構介紹 ..........................................................................14 3.2 電路單元：Pre-Computation Unit ..........................16 3.3 電路單元：Membership Coefficients Updating Unit ..18 3.4 電路單元：Centroid Updating Unit ..................................20 3.5 電路單元：Cost Function Computation Unit ..................23 3.6 電路單元：On-Chip Centroid RAM ..................................24 3.7 電路單元：Xie-Beni Index Computation Unit ............25 3.8 電路單元：Control Unit ..................................................34 第四章 實驗結果與數據探討 ..........................................................37 4.1 開發平台與實驗環境介紹 ..................................................37 4.2 實驗數據的呈現與討論 ..........................................................41 4.2.1 影像分割效果比較與驗證 ..................................................41 4.2.2 硬體架構與軟體演算法效能之量測 ..................................53 第五章 結論 ..................................................................................60 參考著作 ..........................................................................................61

    [1] 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, pp. 281–297, 1967.

    [2] J. C. Bezdek, “Fuzzy Mathematics in Pattern Classification,” Ph.D Thesis, Cornell University, 1973.

    [3] J. C. Bezdek, “Pattern Recognition with Fuzzy Objective Function Algorithms,” Plenum, New York , 1981.

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

    [5] “Fuzzy partition entropies and entropy constrained fuzzy clustering algorithms,” J. Intell. Fuzzy Syst., vol. 5, no. 2, pp. 103–111, 1997.

    [6] Fukuyama, Y., and Sugeno, M., “A new method of choosing the number of clusters for the fuzzy c-means method,” Proc. 5thFuzzy Syst. Symp., pp. 247-250, 1989.

    [7] 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, pp.168-174, 2009.

    [8] Xunali Lisa Xie, Genardo Beni. “A Validity measure for FuzzyClustering”, IEEE Transactions on Pattern Analysis andmachine Intelligence, Vol.13, No4, August 1991.
    [9] Hathaway, R., and Bezdek, J., “Fuzzy c-means clustering of incomplete data,” IEEE Trans. Syst., Man, Cybern., vol. 31, no. 5,pp. 735–744, 2001.

    [10] 楊政諺 “適用於多叢集Fuzzy c-means分群演算法之硬體架構設計” 碩士論文,國立臺灣師範大學資訊工程學系,民國九十九年。

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

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

    [14] Hans J. Zimmermann, “Fuzzy set theory and its applications.” Kluwer Academic Publishers, Boston, 1990.

    [15] J. C. Dunn, “Well separated clusters and optimal fuzzy partitions,” J. Cybern., vol. 4, pp. 95-104, 1974.

    [16] K. Krishna and M. N. Murty, “Genertic K-means Algorithm”, IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, Vol. 29, No.3, pp. 433-439, 1999.

    [17] Bezdek and Pal, J.C. Bezdek and N.R. Pal, “Some new indexes of cluster validity”, IEEE Trans. Systems Man Cybernet., pp. 301–315, 1998

    [18] Qiu, W.-L. and Joe, H. ,”Separation Index and Partial Membership for Clustering.” Computational Statistics and Data Analysis, 50, 585–603 , 2006.

    [19] D. L. Davies and D. W. Bouldin, “A cluster separation measure.”IEEE Trans. Pattern Anal. Mach. Intelligence ,Vol.1, 224–227,1979.

    [20] J.C. Bezdek, “Cluster validity with fuzzy sets,” J. Cybernet, vol.3, pp.58-73,1973

    [21] C. H. Chou and M. C. Su and E. Lai, “A new cluster validity measure and its application to image compression.” Pattern Anal Applic 7: 205–220, 2004.

    下載圖示
    QR CODE