臺灣博碩士論文加值系統

在許多應用領域，交易紀錄反映個人行為上的偏好或習慣，若將交易紀錄適當分群，即可將不同行為類型的個人分到不同群組。交易型資料通常有概念階層伴隨，概念階層反映所有可能交易項目之間的相關性，然而，概念階層卻被大多數的分群演算法忽略，因此，易將相似度高的交易資料分屬不同群組，造成錯誤；除此，分群結果通常不易被使用者觀看。本論文目的在延伸自組映射圖探勘具概念階層的交易資料，此自組映射圖可將交易資料映射至二維平面上，同時保有交易資料在其資料空間上的拓樸關係且可被觀看。除交易型資料外，我們也將此自組映射圖應用至類別型資料及混合型資料。利用人造的資料及真實世界的資料進行實驗，發現此自組映射圖無論在執行時間、視覺觀看品質、映射品質、及分群品質大多優於其他自組映射圖及分群演算法的表現。

In many application domains, transactions are the records of personal activities. Transactions always reveal personal behavior customs, so clustering the transactional data can divide individuals into different segments. Transactional data are often accompanied with a concept hierarchy, which defines the relevancy among all of the possible items in transactional data. However, most of clustering methods for transactional data ignore the existing of the concept hierarchy. Owing to the lack of the relevancy provided by the concept hierarchy, clustering algorithms tend to separate some similar patterns into different clusters. Besides, their clustering results are not easy to be viewed by users. The purpose of this study is to propose an extended SOM model which can handle transactional data accompanied with a concept hierarchy. The new SOM model is named as SetSOM. It can project the transactional data into a two-dimensional map; in the meanwhile, the topological order of the transactional data can be preserved and visualized in the 2-D map. Besides transactional data, we apply the SetSOM to categorical data and mixed data. Experiments on synthetic and real world datasets were conducted, and the results demonstrated the SetSOM outperforms other SOM models and some state-of-art algorithms in execution time, visualization, mapping, and clustering.

摘要 i
Abstract ii
誌謝 iii
Table of Contents iv
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Objectives 3
1.3 Contributions 4
1.4 Organization 4
Chapter 2 Literature review 5
2.1 Similarity/Dissimilarity measures for transactional data 5
2.2 Self-organizing map 7
2.3 SOM on non-vector data 9
2.4 Clustering algorithms for transactional data 12
Chapter 3 Methodology 13
3.1 Preliminaries 13
3.2 Distance between transactions 15
3.3 Operators on concept trees 19
3.4 SetSOM and its algorithms 22
3.4.1 Initialization phase 22
3.4.2 Training phase 22
3.4.3 Adaptation algorithm of SetSOM and its time complexity 26
3.4.4 Visualization of the SetSOM 30
3.5 Applications to the related data types 31
3.5.1 The SetSOM on categorical data 31
3.5.2 The SetSOM on mixed data 33
Chapter 4 Experimental Results 36
4.1 Measures for evaluating mapping and clustering quality 37
4.1.1 Mapping quality 37
4.1.2 Clustering quality 38
4.2 Robustness testing 39
4.3 Experiments on transactional datasets 41
4.3.1 Synthetic dataset: the simulative library checkouts 41
4.3.2 Real dataset: articles of ACM proceedings 46
4.4 Experiment on categorical datasets 51
4.5 Experiment on mixed dataset 56
Chapter 5 Conclusions and Future work 62
References 64
Appendix A 68

1. Agrawal, R. and Srikant, R., 1995, "Mining sequential patterns", Proceedings of the Eleventh International Conference on Data Engineering, 1995, pp. 3-14.
2.Barbará, D., et al., 2002, "COOLCAT: an entropy-based algorithm for categorical clustering", Proceedings of the Eleventh International Conference on Information and Knowledge Management, McLean, Virginia, USA, pp. 582-589.
3.Berkhin, P., 2001, Survey of clustering data mining techniques, Available from http://www.accrue.com/products/rp_cluster_review.pdf.
4.Cesario, E., et al., 2007, "Top-Down Parameter-Free Clustering of High-Dimensional Categorical Data", IEEE Transactions on Knowledge and Data Engineering, vol. 19, issue 12, pp. 1607-1624.
5.Cha, S.-H., et al., 2006, "Enhancing Binary Feature Vector Similarity Measures", Journal of Pattern Recognition Research, vol. 1, pp. 63-77.
6.Chen, D. R., et al., 2000, "Breast cancer diagnosis using self-organizing map for sonography", Ultrasound in Medicine and Biology, vol. 26, issue 3, pp. 405-411.
7.Dantas, A. and Carvalho, F., 2011, "Adaptive Batch SOM for Multiple Dissimilarity Data Tables", IEEE 23rd International Conference on Tools with Artificial Intelligence, Boca Raton, Florida USA, pp. 575-578.
8.Dice, L. R., 1945, "Measures of the amount of ecologic association between species", Ecology, vol. 26, issue, pp. 297-302.
9.Fiannaca, A., et al., 2008, "A New SOM Initialization Algorithm for Nonvectorial Data", Knowledge-Based Intelligent Information and Engineering Systems, (Lovrek, I., Howlett, R. and Jain, L.), Springer Berlin/Heidelberg, vol. 5177, pp. 41-48.
10.Flanagan, J. A., 2003, "Unsupervised clustering of symbol strings", Proceedings of the International Joint Conference on Neural Networks, 2003, pp. 3250-3255.
11.Frank, A. and Asuncion, A., 2010, UCI Machine Learning Repository, Irvine, CA: University of California, School of Information and Computer Science, Available from http://archive.ics.uci.edu/ml.
12.Günter, S. and Bunke, H., 2002, "Self-organizing map for clustering in the graph domain", Pattern Recognition Letters, vol. 23, issue 4, pp. 405-417.
13.Guha, S., et al., 2000, "Rock: A robust clustering algorithm for categorical attributes", Information Systems, vol. 25, issue 5, pp. 345-366.
14.Hammer, B. and Hasenfuss, A., 2010, "Clustering very large dissimilarity data sets", Artificial Neural Networks in Pattern Recognition, (Schwenker, F. and El Gayar, N.), Springer Berlin / Heidelberg, vol. 5998, pp. 259-273.
15.Hammer, B. and Hasenfuss, A., 2010, "Topographic Mapping of Large Dissimilarity Data Sets", Neural Computation, vol. 22, issue 9, pp. 2229-2284.
16.Hammer, B., et al., 2005, "Self-Organizing Maps for Time Series", Proceedings of WSOM, 2005, Paris.
17.Han, J. and Kamber, M., 2001, Data mining: concepts and techniques, San Francisco, Calif.; London, Morgan Kaufmann.
18.He, Z. Y., et al., 2005, "TCSOM: clustering transactions using self-organizing map", Neural Processing Letters, vol. 22, issue 3, pp. 249-262.
19.Himberg, J., et al., 2003, "Towards context awareness using Symbol Clustering Map", Proceedings of WSOM, 2003., Kitakyushu, Japan.
20.Hsu, C.-C., 2006, "Generalizing self-organizing map for categorical data", IEEE Transactions on Neural Networks, vol. 17, issue 2, pp. 294-304.
21.Hsu, C.-C. and Chen, Y.-C., 2007, "Mining of mixed data with application to catalog marketing", Expert Systems with Applications, vol. 32, issue 1, pp. 12-23.
22.Hsu, C. C., et al., 2006, "GViSOM for multivariate mixed data projection and structure visualization", Proceedings of the International Joint Conference on Neural Networks, 2006, pp. 3300-3305.
23.Jaccard, P., 1908, "Nouvelles recherches sur la distribution florale", Bulletin de la Societe Vaudoise de Science Naturelle, vol. 44, pp. 223-270.
24.Kaski, S., et al., 2003, "Trustworthiness and metrics in visualizing similarity of gene expression", BMC Bioinformatics, vol. 4, issue 1, pp. 48.
25.Kohonen, T., 1982, "Self-organized formation of topologically correct feature maps", Biological Cybernetics, vol. 43, issue 1, pp. 59-69.
26.Kohonen, T., 1996, Self-organizing maps of symbol strings, Technical Report A42, Laboratory of Computer and Information Science, Helsinki University of Technology, Finland.
27.Kohonen, T., 2001, Self-Organizing Maps, 3rd, Berlin, Springer.
28.Kohonen, T., et al., 1996, SOM_PAK: the self-organizing map program package, Report A31, Helsinki University of Technology, Available from http://www.cis.hut.fi/research/som_pak/.
29.Kohonen, T., et al., 2000, "Self organization of a massive document collection", IEEE Transactions on Neural Networks, vol. 11, issue 3, pp. 574-585.
30.Kohonen, T. and Somervuo, P., 1998, "Self-organizing maps of symbol strings", Neurocomputing, vol. 21, issue 1-3, pp. 19-30.
31.Kohonen, T. and Somervuo, P., 2002, "How to make large self-organizing maps for nonvectorial data", Neural Networks, vol. 15, issue 8-9, pp. 945-952.
32.Liang, W., et al., 2010, "Enhanced Visual Analysis for Cluster Tendency Assessment and Data Partitioning", IEEE Transactions on Knowledge and Data Engineering, vol. 22, issue 10, pp. 1401-1414.
33.Pelayo, E., et al., 2011, "SO-VAT: Self-Organizing Visual Assessment of cluster Tendency for large data sets", 2011 European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, Bruges (Belgium).
34.Rogers, D. J. and Tanimoto, T. T., 1960, "A computer program for classifying plants", Science, vol. 132, pp. 1115-1118.
35.Rui, X. and Wunsch, D., II, 2005, "Survey of clustering algorithms", IEEE Transactions on Neural Networks, vol. 16, issue 3, pp. 645-678.
36.Somervuo, P. J., 2004, "Online algorithm for the self-organizing map of symbol strings", Neural Networks, vol. 17, issue 8-9, pp. 1231-1239.
37.Ultsch, A., 1993, "Self-Organizing neural networks for visualization and classification", Information and Classification, pp. 307-313.
38.Ultsch, A., 2003, "Maps for the visualization of high-dimensional dataspaces", Proceedings of WSOM, 2003 Kitakyushu, Japan, pp. 225-230.
39.Vathy-Fogarassy, A. and Janos, A., 2009, "Local and global mappings of topology representing networks", Information Sciences, vol. 179, issue 21, pp. 3791-3803.
40.Venna, J. and Kaski, S., 2005, "Local multidimensional scaling with controlled tradeoff between trustworthiness and continuity", Proceedings of the Workshop on Self-Organizing Maps, 2005, pp. 695-702.
41.Vesanto, J., et al., 2000, SOM Toolboxfor Matlab 5, Report A57, Helsinki University of Technology, Available from http://www.cis.hut.fi/projects/somtoolbox/.
42.Wang, K., et al., 1999, "Clustering transactions using large items", Proceedings of the eighth international conference on Information and knowledge management, Kansas City, Missouri, United States, pp. 483-490.
43.Yan, H., et al., 2009, "Determining the best K for clustering transactional datasets: A coverage density-based approach", Data & Knowledge Engineering, vol. 68, issue 1, pp. 28-48.
44.Yan, H., et al., 2010, "SCALE: a scalable framework for efficiently clustering transactional data", Data Mining and Knowledge Discovery, vol. 20, issue 1, pp. 1-27.
45.Yang, Y., et al., 2002, "CLOPE: a fast and effective clustering algorithm for transactional data", Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, Edmonton, Alberta, Canada, pp. 682-687.
46.Yeh, M. F. and Chang, K. C., 2006, "A self-organizing CMAC network with gray credit assignment", IEEE Transactions on Systems Man and Cybernetics Part B-Cybernetics, vol. 36, issue 3, pp. 623-635.
47.Zaki, M. J., et al., 2007, "Clicks: An effective algorithm for mining subspace clusters in categorical datasets", Data & Knowledge Engineering, vol. 60, issue 1, pp. 51-70.
48.Zhang, B., et al., 2009, "Comprehensive query-dependent fusion using regression-on-folksonomies: a case study of multimodal music search", Proceedings of the 17th ACM international conference on Multimedia, Beijing, China, pp. 213-222.