IJSER Home >> Journal >> IJSER
International Journal of Scientific and Engineering Research
ISSN Online 2229-5518
ISSN Print: 2229-5518 7    
Website: http://www.ijser.org
scirp IJSER >> Volume 3,Issue 7,July 2012
A Novel Approaches on Clustering Algorithms And it's Applications
Full Text(PDF, )  PP.494-499  
Author(s)
B.Venkateshwar Reddy, T. Asha Latha
KEYWORDS
Clustering algorithms, graph based clustering algorithms,
ABSTRACT
Graph clustering algorithms are Random walk and minimum spanning tree algorithms. Random walk has been used to identify significant vertices in the graph that receive maximum flow while minimum spanning tree algorithm has been used to identify significant edges in the graph .We believe these two graph algorithms have useful applications in clustering, namely for identifying centroids and for identifying edges to merge or split clusters such that intra-cluster similarity is maximized while inter-cluster similarity is minimized. This paper investigates the graph algorithms, graph-based clustering algorithms, and their applications. graph algorithms and graph-based clustering algorithms, we propose novel variants of Star clustering algorithm that use different techniques for identifying centroids, and two novel graph-based clustering algorithms: MST-Sim and Ricochet. The variant graph algorithms and graph based clustering algorithms achieve higher performance in terms of effectiveness and efficiency for the applications of document clustering, k-member clustering, opinion mining, clustering for part-of-speech tagging.
References
[1] Kruskal J. B., On the shortest spanning subtree and the traveling salesman problem. In Proceedings of the American Mathematical Society. 7, pp. 48–50, 1956.

[2] Boruvka O., ‚O jistém problému minim{lním (About a certain minimal problem)‛, Pr{ce mor. prírodoved. spol. v Brne III, pp. 3: 37–58, 1926.

[3] Skiena S. S., The Algorithm Design Manual, Telos/Springer-Verlag, New York, 1998.

[4] Karger D.R., Klein P.N., and Tarjan R.E., A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees, Journal of the ACM, Vol. 42, pp. 2:321-328, 1995.

[5] MacQueen J. B., Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, University of California Press, 1:281-297, 1967.

[6] Johnson S. C., Hierarchical Clustering Schemes. Psychometrika, 2:241-254, 1967.

[7] Zahn C.T., Graph Theoretical Methods for Detecting and Describing Gestalt Clusters. IEEE Transactions on Computers, Vol. C-20, No. 1, January 1971.

[8] Jain A.K., Murty M. N., Flynn, P.J., Data Clustering: A Review, ACM Computing Surveys,Vol. 31, No. 3, September 1999.

[9] Algorithm 479: A Minimal Spanning Tree Clustering Method [Z]. Communications of the ACM, Vol. 17, Issue 6, Pages: 321 – 323, June 1974.

[10] Karypis G., Han E., Kumar V., CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling. IEEE Computer Vol. 32 No. 8, 68-75, 1999.

[11] Van Dongen S.M., Graph clustering by flow simulation - [S.l.]: [s.n.], 2000 - Tekst. -Proefschrift Universiteit Utrecht, 2000.

[12] Nieland H., Fast Graph Clustering Algorithm by Flow Simulation. Research and Development ERCIM News No. 42 - July 2000.

[13] Aslam J., Pelekhov K., and Rus D., the Star Clustering Algorithm. In Journal of Graph Algorithms and Applications, 8(1) 95–129, 2004.

[14] Motwani R. and Raghavan P., Randomized Algorithms, Cambridge University Press, 1995.

[15] King V., A Simpler Minimum Spanning Tree Verification Algorithm, Workshop on Algorithms and Data Structures, 1995.

[16] Aslam J., Pelekhov K., and Rus D., The Star Clustering Algorithm. In Journal of Graph Algorithms and Applications, 8(1) 95–129, 2004.

[17] Kleinberg J., Tardos E., Algorithm Design, Pearson Education Inc., New York, 2006.

[18] Byun J., Kamra A., Bertino E., and Li N., Efficient kanonymity Using Clustering Techniques, Proceedings of International Conference on Database Systems for Advanced Applications (DASFAA), 2007.

Untitled Page