Extended Self-Organizing Map on Transactional Data

延伸自組映射圖探勘交易型資料

10.6382/JIM.201201.0185

廖文忠(Wen-Chung Liao)；許中川(Chung-Chian Hsu)

交易型資料 ； 自組映射圖 ； 概念階層 ； 交易型資料距離函數 ； 概念樹 ； transactional data ； self-organizing map ； concept hierarchy ； distance function on transactions ； concept tree

資訊管理學報

19卷1期（2012 / 01 / 01）

185 - 216

英文

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

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 in 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. Experiments on synthetic and real datasets were conducted, and the results demonstrated the SetSOM outperforms other SOM models in execution time, and the qualities of visualization, mapping and clustering.

1. Chen, D. R.,Chang, R. F.,Huang, Y. L.(2000).Breast cancer diagnosis using self-organizing map for sonography.Ultrasound in Medicine and Biology,1(26),405-411.
2. Flanagan, J. A.(2003).Unsupervised clustering of symbol strings.Proceedings of the Int. Joint Conference on Neural Networks (IJCNN 2003)
3. Guha, S.,Rastogi, R.,Shim, K.(2000).ROCK: a robust clustering algorithm for categorical attributes.Information Science,25(5),345-366.
4. Günter, S.,Bunke, H.(2002).Self-organizing map for clustering in the graph domain.Pattern Recognition Letters,23,405-417.
5. Hammer, B.,Micheli, A.,Neubauer, N.,Sperduti, A.,Strickert, M.(2005).Self-Organizing Maps for Time Series.Proceedings of the Workshop on Self-Organizing Maps (WSOM 2005),Paris:
6. Han, J.,Kamber, M.(2001).Data Mining Concepts and Techniques.San Francisco:Morgan Kaufmann.
7. He, Z.,Xu, X.,Deng, S.(2005).TCSOM: clustering transactions using self-organizing map.Neural Processing Letters,22,249-262.
8. Himberg, J.,Flanagan, J. A.,Mantyjarvi, J.(2003).Towards context awareness using Symbol Clustering Map.Proceeding of WSOM (WSOM 2003)
9. Hsu, C. C.(2006).Generalizing self-organizing map for categorical data.IEEE Transactions on Neural Networks,17,294-304.
10. Hsu, C. C.,Wang, K. M.,Wang, S. H.(2006).GViSOM for multivariate mixed data projection and structure visualization.Proceedings of the Int. Joint Conference on Neural Networks (IJCNN 2006)
11. Hua Yan, H.,Chen, K.,Liu, L.,Bae, J.(2009).Determining the best K for clustering transactional datasets: A coverage density-based approach.Data & Knowledge Engineering,68,28-48.
12. Kaski, S.,Nikkila, J.,Oja, M.,Venna, J.,Toronen, J.,Castren, E.(2003).Trustworthiness and metrics in visualizing similarity of gene expression.BMC Bioinformatics,4(48)
13. Kohonen, T.(2001).Self-organizing maps.Berlin:Springer.
14. Kohonen, T.(1996).Technical Report A42Technical Report A42,Finland:Laboratory of Computer and Information Science, Helsinki University of Technology.
15. Kohonen, T.(1982).Self-organized formation of topologically correct feature maps.Biological Cybernetics,43,59-63.
16. Kohonen, T.,Hynninen, J.,Kangas, J.,Laaksonen, J.(1996).Report A31Report A31,Helsinki University of Technology.
17. Kohonen, T.,Kaski, S.,Lagus, K.,Salojarvi, J.,Honkela, J.,Paatero, V.,Saarela, A.(2000).Self-organization of a massive document collection.IEEE Transactions on Neural Networks,11(3),574-585.
18. Kohonen, T.,Oja, O. E.,Simula, A.,Visa, S. A.,Kangas, J.(1996).Engineering applications of the self-organizing map.Proceedings of the IEEE (IEEE 1996),84(10),1358-1384.
19. Kohonen, T.,Somervuo, P.(2002).How to make large self-organizing maps for nonvectorial data.Neural Networks,15,945-952.
20. Kohonen, T.,Somervuo, P.(1998).Self-organizing maps on symbol strings.Neurocomputing,21,19-30.
21. Lampinen, J.,Oja, E.(1992).Clustering properties of hierarchical self-organizing maps.Journal of Mathematical Imaging and Vision,2,261-272.
22. Somervuo, P.(2004).Online algorithm for the self-organizing map of symbol strings.Neural Networks,17,1231-1239.
23. Ultsch, A.(2003).Maps for the visualization of high-dimensional data spaces.Proceedings of the 4th Workshop on Self-Organizing Maps (WSOM 2003),Kitakyushu, Japan:
24. Vathy-Fogarassy, A.,Abonyi, J.(2009).Local and global mappings of topology representing networks.Information Sciences,179,3791-3803.
25. Venna, J.,Kaski, S.(2005).Local multidimensional scaling with controlled tradeoff between trustworthiness and continuity.Proceedings of the Workshop on Self-Organizing Maps (WSOM 2005)
26. Vesanto, J.,Himberg, J.,Alhoniemi, E.,Parhankangas, J.(2000).Report A57Report A57,Helsinki University of Technology.
27. Wang, K.,Xu, C.,Liu, B.(1999).Clustering transactions using large items.Proceedings of the ACM Conference on Information and Knowledge Management (CIKM 1999)
28. Yang, Y.,Guan, S.,You, J.(2002).CLOPE: a fast and effective clustering algorithm for transactional data.Proceedings of KDD (KDD 2002)
29. Yeh, M. F.,Chang, K. C.(2006).A self-organizing CMAC network with gray credit assignment.IEEE Transactions on Systems, Man, and Cybernetics-Part B Cybernetics,36(3),623-635.
30. Zhang, B,Xiang, Q.,Lu, H.,Shen, J.,Wang, Y.(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 (MM2009)