分群技術是以物件與物件之間彼此的”相似度”來進行分類，讓相似度相同的儘量聚集在同一群的一種方法。而相似度定義通常是以物件間的距離為基礎，如:歐幾里得距離。但在基因分群的應用中，傳統以距離為相似度計算依據的方式並不適合，因為有時基因與基因間並不具有相近的物理距離，但卻存在有相似的一致性樣式，因此一種新的分群模型-樣式為基礎的分群(Pattern-Based clustering)簡稱為”pCluster”被提出來解決此一問題。所謂兩個物件是否同屬一pCluster，取決於它們屬性中的子集是否有一致性的樣式，這樣兩兩比對找出pCluster的過程，必須耗費大量的計算時間。然而如何在大量資料中，準確且有效率地找出這些pCluster，便成了一個非常值得探究的議題。目前的方法在處理大型資料集或是資料集中群與群間重疊很嚴重時，效能表現並不好。因此，在本篇論文中，將提出一個新的演算法: 稱之為PCP (pCluster plus)，主要的做法是藉由減少計算不必要比對的物件，使得處理pCluster的問題更為快速。此外，也提出考量資料位移(Shift)及資料量新增(Incremental)時能有效找出pCluser的方法。經過實驗証明，我們所提出的方法的確有更好的效能。

Clustering, a method which makes similar objects gather in the same cluster, is done by means of the similarity between objects. And the definition of similarity is mostly based on the distance between objects such as Euclid’s distance. However, for clustering genes objects, the traditional method that worked out the similarity by distance is not so proper because sometimes there doesn’t exist approximate distance but a coherent pattern. Therefore, a brand-new clustering model – Pattern-Based Clustering, called pCluster, was proposed to slove this problem. Two objects in the same cluster is decided whether the subsets they belong to share a coherent pattern. The way to find the pClusters by compare their objects will waste time, nevertheless, how to find out these clusters precisely and efficiently in considerable data becomes a question worthy of inquiry. Although some have brought up solutions to pCluster, bad efficiency is found when there is huge overlap of the large volumn of objects. For this reason, our purposed PCP, a method more efficient and precise method which mainly serves to reduce some unnecessary objects is provided. Besides, the the problem of data shift and incremental are considered as well. Through the experiment, our purposed method have better efficiency than others.

中文摘要 ……………………………………………………………… I
英文摘要 ……………………………………………………………… II
誌 謝 ……………………………………………………………… III
目 次 ……………………………………………………………… IV
圖 次 ……………………………………………………………… V
第一章 緒論………………………………………………………… 1
第一節 研究背景…………………………………………………… 1
第二節 研究動機…………………………………………………… 3
第三節 論文架構…………………………………………………… 4
第二章 相關研究…………………………………………………… 5
第一節 Bicluster及δ-cluster ……………………………………… 5
第二節 pClustering ………………………………………………… 5
第三節 Maple ……………………………………………………… 10
第三章 更有效的pCluster方法: PCP法 ………………………… 13
第一節 MDSc ……………………………………………………… 13
第二節 對MDSc進行分析與砍除 ……………………………… 14
第三節 產生pCluster ……………………………………………… 16
第四節 效能分析…………………………………………………… 18
第四章 改良PCP法: PCP-II……………………………………… 22
第一節 MDSc ……………………………………………………… 22
第二節 Prune MDSc – Global prune ……………………………… 22
第三節 產生pCluster……………………………………………… 23
第四節 效能分析…………………………………………………… 25
第五章 Shift pCluster方法 : Shift pCluster plus……………… 31
第一節 何謂Shift pCluster………………………………………… 31
第二節 Maximum Interval of Dimension Set (MIDS)……………… 32
第三節 產生Shift pCluster ………………………………………… 35
第四節 效能分析…………………………………………………… 36
第六章 Incremental pCluster方法: Incremental pCluster plus 40
第一節 I_MDS pattern ……………………………………………… 40
第二節 產生新增資料的pCluster ………………………………… 41
第三節 效能分析…………………………………………………… 42
第七章 結論與未來研究方向……………………………………… 46
第一節 結論………………………………………………………… 46
第二節 未來研究方向……………………………………………… 46
參考文獻 ……………………………………………………………… 48

[1] A.D. Gordon, “Classification 2nd Edition”, In Chapman & Hall/CRC, 1999.
[2] A.K. Jain and R.C. Dubes, “Algorithms for Clustering Data”, In Prentice Hall, 1988.
[3] C. C. Aggarwal, C. Procopiuc, J. Wolf, P. S. Yu, and J. S. Park. “Fast algorithms for projected clustering”. In SIGMOD, Philadelphia, Pennsylvania, 1999.
[4] C. C. Aggarwal and P. S. Yu. “Finding generalized projected clusters in high dimensional spaces.” In SIGMOD, Dallas, Texas, pages 70-81, 2000.
[5] C. H. Cheng, A. W. Fu, and Y. Zhang. “Entropy-based subspace clustering for mining numerical data”. In SIGKDD San Diego, CA, pages 84-93, 1999.
[6] D. Fasulo, “An analysis of recent work on clustering algorithm”, In Tech. report, 1999.
[7] H. V. Jagadish, J. Madar, and R. Ng. “Semantic compression and pattern extraction with fascicles”. In VLDB, Edinburgh, Scotland, pages 186-196, 1999.
[8] H.Wang, W.Wang, J.Yang, and P.Yu “Clustering by Pattern Similarity in Large Data Sets.” In ACM SIGMOD, Madison, Wisconsin, 2002.
[9] Jian Pei, Xiaoling Zhang, Moonjung Cho, Haixun Wang, Philip S. Yu: “MaPle: A Fast Algorithm for Maximal Pattern-based Clustering”, In ICDM, Melbourne, Florida, pages 259-266, 2003.
[10] J. Han and M. Kamber, Data Mining : “Concepts and Techniques”, In Morgan Kaufmann, 2000.
[11] J. Yang, W. Wang, H. Wang, and P. S. Yu. “δ-clusters: Capturing subspace correlation in a large data set”. In ICDE, San Jose, California, 2002.
[12] J. Riedl and J.Konstan. “Movielens dataset.” In http://www.cs.umn.edu/Research/GroupLens
[13] K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft. “When is nearest neighbors meaningful.” In Proc. of the Int. Conf. Database Theories, pages 217–235, 1999.
[14] P. Arabie, L.J. Hubert and G.D Soete, “Clustering and Classification”, In World Scientific Pub Co, 1996.
[15] R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. “Authomatic subspace clustering of high dimensional data for data mining applications.” In SIGMOD, Seattle, Washington , 1998.
[16] R. Sharan, R. Elkon and R. Shamir, “Cluster Analysis and its Applications to Gene Expression Data”, In Ernst Schering workshop on Bioinformatics and Genome Analysis Springer Verlag, 2001.
[17] S.Tavazoie, J.Hughes, M.Campbell, R.Cho, and G.Church. “Yeast micro data set.” In http://arep.med.harvard.edu/biclustering/yeast.matrix, 2000.
[18] Y. Cheng and G. Church. “Biclustering of expression data.” In Proc. of 8th International Conference on Intelligent System for Molecular Biology, La Jolla / San Diego, CA, 2000.
[19] Rich J. Roiger, Michael W. Gealz. “Data Mining – A Tutorial-Based Primer”, Published by Addison Wesley Professional.