跳到主要內容

臺灣博碩士論文加值系統

(44.200.169.3) 您好!臺灣時間:2022/12/05 20:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:蔡錫震
研究生(外文):Hsi-Chen Tsai
論文名稱:利用最小包含球的支撐向量分群型態之演算法
論文名稱(外文):A Support Vector Clustering Type Algorithm via Minimum Enclosing Balls
指導教授:李育杰李育杰引用關係
指導教授(外文):Yuh-Jye Lee
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:41
中文關鍵詞:支撐向量群聚演算法群聚分配最小包含球
外文關鍵詞:cluster labelingminimum enclosing ballsupport vector clustering
相關次數:
  • 被引用被引用:0
  • 點閱點閱:341
  • 評分評分:
  • 下載下載:33
  • 收藏至我的研究室書目清單書目收藏:0
支撐向量機(support vector machines)在近年來成為最熱門的一種機器學習演算法。支撐向量群聚演算法( support vector clustering )簡稱SVC便是以此為靈感而發展形成。 SVC是一種非監督式學習的演算法。它把要分群的點先映到其它高維度的空間,接著找一最小包含球( minimum enclosing ball )包住這些點,當這在高維度形成的球映回原來的空間變成數個輪廓,每個輪廓中包含個數不一的資料點,同一輪擴的資料點理所當然成為一個群。這是SVC的主要分群概念。

SVC主要的缺點在於其群聚分配( cluster labeling )時間複雜度過高,因此許多的方法被提出來目的在改善這個缺點。 本篇論文結合支撐向量( support vector )的特性、 最小包含球以及k-means演算法, 把這些概念作一適當的分配利用達到降低時間複雜度的目的。 在實驗的部分我們創造一些分布在2維或3維空間的資料集以利可以馬上觀察出各個資料集的群聚分布。並把我們提出的方法跟其他現有的方法作比較,不管是時間花費度跟潔果準確度我們的方法均有較突出且令人滿意的表現。
Clustering analysis which is categorized as unsupervised learning in machine learning means based on speci‾c features creating groups of objects in such a way that the objects grouping into the same clusters are similar and those belonging in diferent clusters are dissimilar. Support vector clustering (SVC) is an unsupervised and kernel-based clustering algorithm. SVC could naturally separate dataset with any shape into diferent clusters. SVC separates the dataset into appropriate clusters by tuning two parameters. Suppose number of data points is n, the time complexity of labeling data points becomes O(n2).
It becomes the bottleneck of SVC and this is the major drawback why SVC always takes more time than other clustering algorithms.
Focus this drawback, this thesis suggests a novel cluster labeling algorithm combining with the concept of minimum enclosing balls (MEBs), the property of support vector and k means to improve the e±ciency. In the later section, we will test our proposed method on synthetic datasets either in R2 and R3 space in order to visualize the clustering results, and demonstrate the e±ciency of our proposed method by comparing with other cluster labeling algorithms. Besides we also find a flaw in the original SVC mathematical programming model, another issue of this thesis is to discuss the flaw and solve it.
1 Introduction 1
1.1 Clustering Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Related Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Hierarchical algorithms . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Partitional algorithms . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 A Novel Clustering Algorithm : Support Vector Clustering . . . . 4
1.4 Organization of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Related Work 6
2.1 Support Vector Machines for Classi‾cation . . . . . . . . . . . . . . 6
2.1.1 Support Vector Classi‾cation . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Idea of Kernel Functions . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 One-Class SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Support Vector Clustering . . . . . . . . . . . . . . . . . . . . . . . .10
I
2.2.1 Introduction of SVC . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Strategies of Cluster Labeling . . . . . . . . . . . . . . . . . . . 15
3 SVC via Minimum Enclosing Balls 19
3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Cluster Labeling via MEBs . . . . . . . . . . . . . . . . . . . . . . . . 20
4 Experiments and Results 27
4.1 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . .27
5 Conclusion and Further Work 32
A SVC Type Algorithm Via MEBs Implementation for Matlab Code 34
[1] P. Baldi, P. Frasconi, and P. Smyth. Modelling the Internet and the Web. Wiley, 2003.
[2] Ben-Dor, A., R. Shamir, and Z.Yakhini. Clustering gene experssion patterns. J. Comp. Bio, 6(3-4):281{97, 1999.
[3] A. Ben-Hur, D. Horn, H. Siegelmann, and V. Vapnik. Support Vector Clustering. Journal of Machine Learning Research, 2:125{137, 2001.
[4] Asa Ben-Hur, David Horn, Hava Siegelmann, and Vladimir Vapnik. A support vector method for hierarchical clustering.
[5] A. Ben-Israel, A. Ben-Tal, and S. Zlobec. Optimality in Nonlinear Programming: A Feasible Directions Approach. John Wiley & Sons, New York, 1981.
[6] D. P. Bertsekas. Nonlinear Programming. Athena Scienti‾c, Belmont, MA, second edition, 1999.
[7] C. J. C. Burges. A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery, 2(2):121{167, 1998.
[8] V. Cherkassky and F. Mulier. Learning from Data - Concepts, Theory and Methods. John Wiley & Sons, New York, 1998.
[9] R. Courant and D. Hilbert. Methods of Mathematical Physics. Interscience Publishers, New York, 1953.
[10] N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge University Press, Cambridge, 2000.
[11] A. Dempster, N. M. Laird, and D. Rubin. Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society B, 39:1{38,
1977.
[12] R. C. Dubes and A. K. Jain. Algorithms for Clustering Data. Prentice Hall, 1988.
[13] P. Hand, D. Mannila, and H. Smyth. Principles of data mining. MIT Press, 2001.
[14] In The Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD). Kernel k-means, spectral clustering and normalized cuts, 2004. 40
[15] Sammon JW Jr. A nonlinear mapping for data structure analysis. IEEE Transactions on Computers, 18, 1969.
[16] L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: an Introduction to Cluster Analysis. John Wiley & Sons, 1990.
[17] J. Lee and D. Lee. An improved Cluster Labeling Method for Support Vector Clustering. IEEE Transactions on pattern analysis and machine intelligence, 27:461{464,
2005.
[18] S. Lee and K Daniels. Cone Cluster Labeling for Support Vector Clustering. In Proceedings of 6th SIAM Conference on Data Mining, pages 484{488, 2006.
[19] Y.-J. Lee and O. L. Mangasarian. RSVM: Reduced Support Vector Machines. Technical Report 00-07, Data Mining Institute, Computer Sciences Department, University
of Wisconsin, Madison, Wisconsin, July 2000. Proceedings of the First SIAM International Conference on Data Mining, Chicago, April 5-7, 2001, CD-ROM Proceedings.
ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/00-07.ps.
[20] Y.-J. Lee and O. L. Mangasarian. SSVM: A Smooth Support Vector Machine. Computational Optimization and Applications, 20:5{22, 2001. Data Mining Institute, Uni-
versity of Wisconsin, Technical Report 99-03. ftp://ftp.cs.wisc.edu/pub/dmi/techreports/99-03.ps.
[21] O. L. Mangasarian. Nonlinear Programming. SIAM, Philadelphia, PA, 1994.
[22] MATLAB. User's Guide. The MathWorks, Inc., Natick, MA 01760, 1994-2001. http://www.mathworks.com.
[23] K. Mehrotra, C. Mohan, and S. Ranka. Elements of Arti‾cial Neural Networks. MIT Press, 1996.
[24] M. L. Overton and R.S. Womersley. Optimality Conditions and Duality Theory for Minimizing Sums of the Largest Eigenvalues of Symmetric Matrices. Mathematical
Programming, 62:321{357, 1993.
[25] J. C. Platt. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. In B. SchÄolkopf, C. J. C. Burges, and A. J. Smola, editors,
Advances in Kernel Methods - Support Vector Learning, pages 185{208. MIT Press,
1999. http://www.research.microsoft.com/»jplatt/smo.html.
[26] B. SchÄolkopf, R. C. Williamson, A.J. Smola, J.Shawe-Taylor, and J.Platt. Support Vector Method for Novelty Detection. In Advances in Neural Information Processing
Systems 12, pages 526{532, 1999.
[27] D. M. J Tax and R. P. W. Duin. Support Vector Domain Description. Pattern Recognition Letters, 20(11-13):1191{1199, 1999.
[28] V. N. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, 1995. 41
[29] A. J. Venables. The international division of industries: clustering and comparative advantage in a multiindustry model. CEPR Discussion Paper, (1961), 1998.
[30] J. T. Wijnen, H. F. A. Vasen, P. M. Khan, A. H. Zwinderman, H. Van Der Klift, A. Mulder, C. Tops, P. Moller, and R. Fodde. Clinical ‾ndings with implications
for genetic testing in families with clustering of colorectal cancer. N. Engl. J. Med., 339:511{518, 1998.
[31] J. Yang, V. Estivill-Castro, and S. Chalup. Support Vector Clustering Through Proximity Graph Modeling. In Proceedings, 9th International Conference on Neural
Information Processing (ICONIP'02), pages 898{903, 2002.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 翁玲玲,〈從陰魂到神明:泉州地區女性神靈信仰初探〉,《佛光人文社會學刊》2,2002.06,頁307-333。
2. 杜正勝,〈形體、精氣與魂魄-中國傳統對「人」認識的形成〉,《新史學》2:3,1991.09,頁1-65。
3. 徐麗霞,〈萬善同歸:「義塚大墓公」〉,《中國語文》483,1997.09頁100-104。
4. 徐麗霞,〈台北縣板橋市厲祠調查(上)〉,《中國語文》502,1999.04,頁105-114。
5. 徐麗霞,〈台北縣板橋市厲祠調查(下)〉,《中國語文》503,1999.05,頁102-111。
6. 林富士,〈台灣的義民廟與義民爺〉,《文化視窗》5,1998年,頁12-19。
7. 李豐楙,〈從成人之道到成神之道-一個台灣民間信仰的結構性思考〉,《東方宗教研究》4,1994.10,頁183-209。
8. 林富士,〈六朝時期民間社會所祀「女性人鬼」初深〉,《新史學》7:4,1996.12,頁95-117。
9. 呂理政,〈鬼的信仰及其相關儀式〉,《民俗曲藝》90,1994.07,頁147-192。
10. 余光弘,〈台灣地區民間宗教的發展-寺廟調查資料之分析〉,《中央研究院民族學研究所集刊》53,1983.06,頁67-103。
11. 王志宇〈台灣的無祀孤魂信仰新論-以竹山地區祠廟為中心的探討〉,《逢甲人文社會學報》6,2003.05,頁183-210。
12. 翁慧雯,〈廖添丁的人格與神格〉,《歷史月刊》139,1999.08,頁98-101。
13. 陳仲玉,〈南中國海諸島上的祠廟〉,《中央研究院民族學研究所集刊》89,2000.03,頁275-295。
14. 陳祥水,〈中國社會結構與祖先崇拜〉,《中華文化復興月刊》11:6,頁32-39。
15. 黃文博,〈台灣民間「有應公信仰」類型分析〉,《民俗曲藝》71,1991,頁212-223。