臺灣博碩士論文加值系統

所謂切割式叢集法先給予一組初始值，再使用循環式重新配置，讓成員能在各群中互相轉移，以達到區域或整體最佳解。當使用切割式叢集法處理資料的過程中，常常會發現某一群的成員，在演算法未收斂前就不再更動。此時若我們此部份適時加以剔除，將可減少計算次數，節省運算時間。因此本論文將利用獨立率的機制來找出這些不再變動的部分，並加以剔除，如此不僅減少所有成員與各質心交互運算的次數，更加快收斂的速度，但必須花費部分時間去計算各中心間的關係。而所謂獨立率是指每一群的中心兩兩比較的距離，再除以各自的標準差。從實驗分析，在不同測試資料集的表現上，本論文所提出運用獨立率的演算法，均比傳統的切割式叢集法，節省計算時間並降低時間複雜度。

Partition clustering methods are given a set of initial centers, it uses an iterative realocation technique that attempts to improve the partitioning by moving objects from one group to another and to achieve global optimality. There is a phenomenon in using partition clustering method to deal with data, the member in someone cluster will no change before the whole iterative stop. This time if we can skin to compute the partition that will save much time. Therefore, in this thesis, we modify the traditional partition clustering methods by applying the isolation ratio, where the isolation ratio is the distance between two clusters, divided by its own standard deviation. Our method is to use the isolation ratio to find the unmove parts and skip them, which can reduces the number of data to calculate with each center point, so it can save much of this time, but some computational time must be spent to calculate the relation of the distance between each center point. From the simulation results by testing some datasets, our method is faster than traditional partition clustering methods.

第一章 緒論 1
第一節 研究背景與動機 2
第二節 研究目的 2
第三節 論文架構 3
第二章 相關研究 4
第一節 不同基礎的分群法 4
第二節 K-means及其變化的演算法 5
第三章 獨立率在部分分群法的應用 10
第一節 獨立率 10
第二節 獨立率在K-means的應用 12
第三節 獨立率在PAM、CLARAN的應用 21
第四章 獨立率在動態資料的應用 31
第一節 獨立率在動態資料的方法 31
第二節 數學式推導 32
第三節 實作與討論 34
第五章 結論與未來研究方向 38
第一節 結論 38
第二節 未來研究方向 38
參考文獻 40

Anderberg, M.R. (1973). Cluster Analysis for Applications. Academic Press.
Dan Judd, Philip K.McKinley, Anil K.Jain. (1998). Large-Scale Parallel Data Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence.
Dan Pelleg and Andrew Moore. (1999）. Accelerating Exact k-means Algorithms with Geometric Reasoning. In KDD-99.
Huang, Z. (1997). A fast clustering algorithm to cluster very large categorical data sets in data mining. Proceedings of the SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery, Dept. of ComputerScience, The University of British Columbia, Canada, 1—8.
Han, J. and Kimber, M. (2001). Data Mining: Concepts and Techniques. Morgan-Kaufmann.
J. Coggins and A. Jain. (1985). A Spatial Filtering Approach to Texture Analysis. Pattern Recognition Letters 3, 195-203. .
J. M. Peña, J. A. Lozano, P. Larrañaga. (1999). An empirical comparison of four initialization methods for the k-means algorithm. Pattern Recognition Letters 20, 1027-1040.
James Theiler and Galen Gisler. (1997). A contiguity-enhanced k-means clustering algorithm for unsupervised multispectral image segmentation, Proc SPIE 3159. 108-118.
Khaled Alsabti, Sanjay Ranka, Vineet Singh. (1998). An Efficient K-Means Clustering Algorithm. IPPS: 11th International Parallel Processing Symposium.
L.Kaufman and P.J. Rousseeuw. (1990). Finding Groups in Data: an Introduction to Cluster Analysis. John Wiley & Sons.
MacQueen, J.B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 281—297.
M.B. Al-Daoud and S.A. Roberts. (1996). New methods for the initialisation of clusters, Pattern Recognition Letters, 17, 451-455.
P. S. Bradley, Usama M. Fayyad. (1998). Refining Initial points for K-Means Clustering. Proc. 15th International Conf. on Machine Learning.
Rose H. Turi. (2001). Clustering — Based Colour Image Segmentation.Ph.D.in UNIVERSITY OF MONASH.
Siddheswar Ray and Rose H. Turi. (1998). Determination of Number of Clusters in K-Means Clustering and Application in Colour Image Segmentation. in N R Pal, A K De and J Das (eds), Proceedings of the 4th International Conference on Advances in Pattern Recognition and Digital Techniques (ICAPRDT''99).
T. Kanungu, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu. (2000). The Analysis of a Simple k-Means Clustering Algorithm. Symposium on Computational Geometry.
R. Ng and J. Han. (1994). Efficient and effective clustering methods for spatial data mining. In Proc. of the 20th Int''l Conf. on Very Large Data Bases (VLDB), 144-155, Santiago, Chile.