使用叢集整合技術偵測主曲線之研究

The Study of Principal Curve Detection Using Cluster Ensembles

林昇毅(Sheng-Yi Lin)

指導教授 ： 王才沛

國立交通大學/資訊學院/多媒體工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00850

摘要

主曲線是通過資料中心的一條線，因此找到一個圖形的主曲線即可以得到一個圖形的基本形狀。在過去的研究當中，利用叢集化演算法來找尋主曲線在圖形識別的領域中是一個很熱門的議題，其中大部份的演算法大都分為三個主要的步驟: 叢集化演算法找到分群結果、連接由第一步驟所得到的各個分群獲得一個初始的主曲線、對初始主曲線作平滑化。然而這些過去所提出的演算法中，都因為叢集化演算法先天的一些限制而有所美中不足的地方，例如如何得到適當的分群個數，初始條件以及雜訊量對於叢集化過程的影響，等等。在此我們想引入一種技術--叢集整合技術，利用叢集整合的特性來降低初始件以及雜訊量對於叢集化過程的影響，以此得到更穩定的叢集化後的分群結果，再將此分群結果利用階層聚合演算法來得到最終的分群結果。

關鍵字

叢集整合偵測主曲線

並列摘要

A principal curve is a curve that passes through the middle of the data distribution. As a result, we can obtain the basic shape of a data distribution by detecting its principal curve. The detection of principal curves through clustering algorithms has been a popular topic in past research. Most of these algorithms consist of three main steps: a clustering algorithm to partition the data, the linking of the clusters to obtain an initial principal curve, and the smoothing of the initial principal curve. However, these algorithms all have some limitations due to the underlying clustering algorithms. Examples of such limitations include how to determine a proper number of initial clusters, initializations, and the effect of noise, etc. In this thesis, our goal is to apply the technique of cluster ensembles to principal curve detection. The benefit of cluster ensembles is the reduced effect of initialization and noise, and this leads to more stable clustering results. The final partition into principal curves are obtained using hierarchical agglomeration algorithms.

並列關鍵字

principal curve detection using cluster ensembles

參考文獻

[1] M. Chen, Z. Cheng, and Y. Liu, “A Robust Algorithm of Principal Curve Detection,” Proc. Int’l Conf. Pattern Recognition, Vol. I, pp. 429-432, 2004.

[2] X. Liu, and Y. Jia, “A Bottom-up Algorithm for Finding Principal Curves with Applications to Image Skeletonization”, Pattern Recognition, Vol. 38, pp. 1079-1085, 2005.

[3] D.C. Stanford, A.E. Raftery, “Finding Curvilinear Features in Spatial Point Patterns: Principal Curve Clustering with Noise,” IEEE Trans. Pattern Anal. Mach. Intell., Vol. 22, pp. 601-609, 2000.

[5] J.J. Verbeek, N. Vlassis, and B. Krose, “A K-segments Algorithm for Finding Principal Curves,” Pattern Recognition Lett., Vol. 23, pp. 1009-1017, 2002.

[7] B. Lam and H. Yan, “Complex Curve Tracing Based on A Minimum Spanning Tree Model and Regularized Fuzzy Clustering”, IEEE int’l Conf. on Image Processing, Vol. 3, pp. 2091-2094, 2004.