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

Abstract

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

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.