臺灣博碩士論文加值系統

圖是一種用來說明目標間之關聯性與相似性的工具，圖的拉普拉斯矩陣可用於進一步探討其相似性。在本研究中，我們將探究拉普拉斯矩陣的特徵向量來對高度相關的資料點進行聚類，其中一個應用為將圖像的像素聚類。這樣利用拉普拉斯矩陣輔助聚類的技術在文獻中稱為譜聚類。

Graphs are tools which illustrate connections and similarities between objects. A graph''s Laplacian can be used to further explore these similarities. In this thesis, we will explore the use of the Laplacian''s eigenvectors to cluster datapoints which are highly related. Particularly, we will relate pixels within an image and use this clustering to discern objects within the image. This technique is called spectral clustering.

Contents
論文審定書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .i
摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .ii
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .iii
圖次 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .vi
1 Introduction 1
2 Graphs and Drawings 2
3 Similarity and Weights 3
3.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
3.2 Creating Weights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
3.3 Putting Them Together . . . . . . . . . . . . . . . . . . . . . . . . . . .5
4 The Laplacian Matrix 8
5 Degree-Normalized Eigenvectors 10
6 Drawing Graphs with Eigenvectors 11
7 Implementation 13
8 Defining Clusters 18
8.1 K-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18
8.2 Hierarchical Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . .19
9 Final Thoughts 20
參考文獻 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21

[1] A. Ng, M. Jordan, and Y. Weiss (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems.
[2] G. James, D. Witten, T. Hastie, and R. Tibshirani. An Introduction to Statistical Learning : with Applications in R. New York: Springer, 2013.
[3] J. Shi and J. Malik (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.22, No.8.
[4] P. D. Jarvis, B. R. Holland, and J. G. Sumner (2013). Phylogenetic Invariants. Brenner’s Encyclopedia of Genetics (Second Edition)
[5] U. von Luxburg (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17.
[6] W. Fleshman (2019). Spectral Clustering: Foundation and Application. Towards Data Science available online at https://towardsdatascience.com/spectralclustering-
aba2640c0d5b.
[7] Y. Koren (2004-2005). Drawing Graphs by Eigenvectors: Theory and Practice. Computers and Mathematics with Applications 49. 1867-1888.