A Novel Approaches on Clustering Algorithms And it's Applications

Full Text(PDF, ) PP.494499


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 intracluster similarity is maximized while intercluster similarity is minimized. This paper investigates the graph algorithms, graphbased clustering algorithms, and their applications. graph algorithms and graphbased clustering algorithms, we propose novel variants of Star clustering algorithm that use different techniques for identifying centroids, and two novel graphbased clustering algorithms: MSTSim 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, kmember clustering, opinion mining, clustering for partofspeech 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/SpringerVerlag, New York, 1998.
[4] Karger D.R., Klein P.N., and Tarjan R.E., A Randomized
LinearTime Algorithm to Find Minimum Spanning
Trees, Journal of the ACM, Vol. 42, pp. 2:321328, 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:281297, 1967.
[6] Johnson S. C., Hierarchical Clustering Schemes.
Psychometrika, 2:241254, 1967.
[7] Zahn C.T., Graph Theoretical Methods for Detecting and
Describing Gestalt Clusters. IEEE Transactions on
Computers, Vol. C20, 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, 6875, 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.


