The week's pick
Random Articles
Reseach Article
Article:Minimum Spanning Tree-based Structural Similarity Clustering for Image Mining with Local Region Outliers
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 8 - Number 6 |
| Year of Publication: 2010 |
| Authors: S. John Peter |
10.5120/1211-1737
|
S. John Peter . Article:Minimum Spanning Tree-based Structural Similarity Clustering for Image Mining with Local Region Outliers. International Journal of Computer Applications. 8, 6 ( October 2010), 33-40. DOI=10.5120/1211-1737
Abstract
Image mining is more than just an extension of data mining to image domain. Image mining is a technique commonly used to extract knowledge directly from image. Image segmentation is the first step in image mining. We treat image segmentation as graph partitioning problem. In this paper we propose a novel algorithm, Minimum Spanning Tree based Structural Similarity Clustering for Image Mining with Local Region Outliers (MSTSSCIMLRO) to segment the given image and to detect anomalous pattern (outliers). In MSTSSCIMLRO algorithm we use weighted Euclidean distance for edges, which is key element in building the graph from image. MST-based image segmentation is fast and efficient method of generating a set of segments from an image. The algorithm uses a new cluster validation criterion based on the geometric property of data partition of the data set in order to find the proper number of segments. The algorithm works in two phases. The first phase of the algorithm creates optimal number of clusters/segments, where as the second phase of the algorithm further segments the optimal number of clusters/segments and detect local region outliers
References
- T. Asano, B. Bhattacharya, M.Keil and F.Yao. “Clustering Algorithms based on minimum and maximum spanning trees”. In Proceedings of the 4th Annual Symposium on ComputationalGeometry,Pages252-257,1988.
- V.Barnett and T.Lewis, “Outliers in Statistical Data”, John Wiley, 1994.
- M. Breunig, H.Kriegel, R.Ng and J.Sander, Lof: “Identifying density-based local outliers”. In Proceedings of 2000 ACM SIGMOD International Conference on Management of Data. ACM Press, pp 93-104, 2000.
- M. R. Brito, E. L. Chavez, A. J. Quiroz, and J. E. Yukich. “Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection”. Statistics & Probability Letters, 35(1):33-42, 1997.
- Deepthi Narayan, Srikanta Murthy K., and Hemantha Kumar G “Image Segmentation Based On Graph Theoretical Approach to Improve the Quality of Image Segmentation”, World Academy of Science, Engineering and Technology 42, 2008.
- C. Ding, X. He, H. Zha, M. Gu, and H. Simon, “A min-max cut algorithm for graph partitioning and data clustering”, Proc. of ICDM 2001.
- M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise". In Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD'96), Portland, OR, pages 291-316. AAAI Press, 1996.
- Feng Luo,Latifur Kahn, Farokh Bastani, I-Ling Yen, and Jizhong Zhou, “A dynamically growing self-organizing tree(DGOST) for hierarchical gene expression profile” Bioinformatics,Vol 20,no 16, pp 2605-2617, 2004.
- Felzenszwalb P.F and Huttenlocher, 2004. “Efficient Graph-Based Image Segmentation”, International Journal of Computer Vision, vol 59.
- M. Fredman and D. Willard. “Trans-dichotomous algorithms for minimum spanning trees and shortest paths”. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science,pages 719-725, 1990.
- Gath and A.Geva, “Fuzzy Clustering for the estimation of the Parameters of the components of Mixtures of Normal distribution”, Pattern Recognition letters, 9, pp.77-86, 1989.
- Gary Chartrand and Ping Zhang “Introduction to Graph Theory”, Tata MgrawwHill, Paperback-2008.
- S. Guha, R. Rastogi, and K. Shim. “CURE an efficient clustering algorithm for large databases”. In Proceeding of the 1998 ACM SIGMOD Int. Conf. on Management of Data , pp 73-84, Seattle, Washington, 1998.
- A. Hardy, “On the number of clusters”, Computational Statistics and Data Analysis, 23, pp. 83–96, 1996.
- D.Hawkins, “Identifications of Outliers”, Chapman and Hall, London, ,1980.
- Z. He, X. Xu and S. Deng, “Discovering cluster-based Local Outliers”, Pattern Recognition Letters, Volume 24, Issue 9-10, pp 1641 – 1650, June 2003.
- H.Gabow, T.Spencer and R.Rarjan. “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs”, Combinatorica, 6(2):pp 109-122, 1986.
- M. Jaing, S. Tseng and C. Su, “Two-phase Clustering Process for Outlier Detection”, Pattern Recognition Letters, Volume 22, Issue 6 – 7, pp 691 – 700, May 2001.
- Jundi Ding, SongCan Chen , RuNing Ma and Bo Wang, “A Fast Directed Tree Based Neighborhood Clustering Algorithm for Image Segmantation”, Neural Information Processing , Lecture Notes in Computer Science, Vol 4233,pp 369-378, 2006.
- D. Karger, P. Klein and R. Tarjan, “A randomized linear-time algorithm to find minimum spanning trees”, Journal of the ACM, 42(2):321-328, 1995.
- E. Knorr and R. Ng, “A Unified Notion of Outliers: Properties and Computation”. In Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, pages 219 – 222, August 1997.
- E..Knorr and R.Ng, “Algorithms for Mining Distance-based Outliers in Large Data sets”, Proc.the 24th International Conference on Very Large Databases(VLDB),pp.392-403, 1998.
- E.Knorr, R.Ng and V.Tucakov, “Distance- Based Outliers: Algorithms and Applications”, VLDB Journal, 8(3-4):237-253, 2000.
- J. Kruskal, “On the shortest spanning subtree and the travelling salesman problem”, In Proceedings of the American Mathematical Society, pp 48-50, 1956.
- A.Loureiro, L.Torgo and C.Soares, “Outlier detection using Clustering methods: A data cleaning Application”, in Proceedings of KDNet Symposium on Knowledge-based systems for the Public Sector. Bonn, Germany, 2004.
- Ming Zhang , Reda Alhajj “Improving the Graph Based Image Segmentation Method”, Proceedings of the 18 th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’06), IEEE,2006.
- R. Prim. “Shortest connection networks and some generalization”. Bell systems Technical Journal,36:1389-1401, 1957.
- S. Salvador and P. Chan, “Determining the number of clusters/segments in hierarchical clustering/segmentation algorithms”, in Proceedings Sixteenth IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2004, Los Alamitos, CA, USA, IEEE Computer Society, pp. 576–584 , 2004.
- J. Shi and J. Malik, “Normalized cuts and image segmentation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 22, No. 8, 2000.
- Stefan Wuchty and Peter F. Stadler. “Centers of Complex Networks”. 2006
- S. Still and W. Bialek, “How many clusters? , An information-theoretic perspective”, Neural Computation, 16, pp. 2483–2506, 2004.
- Thiadmer Riemersma, “Color Metric” Available at http://www.compuphase.com/ cmetric.htm
- Xiaowei Xu, Nurcan Yuruk Zhidan Feng and Thomas A.J. Schweiger, “ SCAN: A Structural Clustering Algorithm for Networks”, SIGKDD, San Jose, CA, US, 2007.
- C. Zahn. “Graph-theoretical methods for detecting and describing gestalt clusters”, IEEE Transactions on Computers, C-20:68-86, 1971
- J. Zhang and N. Wang, “Detecting outlying subspaces for high-dimensional data: the new task, Algorithms and Performance”, Knowledge and Information Systems, 10(3):333-555, 2006.
- Zhou, S., Zhao, J.: A Neighborhood-Based Clustering Algorithm. PAKD 2005, LNAI 3518 (1982) 361-371
Index Terms
Keywords