research-article

Clustering Documents using the 3-Gram Graph Representation Model

Authors:

John Violos,

Konstantinos Tserpes,

Athanasios Papaoikonomou,

Magdalini Kardara,

Theodora VarvarigouAuthors Info & Claims

PCI '14: Proceedings of the 18th Panhellenic Conference on Informatics

Pages 1 - 5

https://doi.org/10.1145/2645791.2645812

Published: 02 October 2014 Publication History

Get Access

Abstract

In this paper we illustrate an innovative clustering method of documents using the 3-Gram graphs representation model and deducing the problem of document clustering to graph partitioning. For the latter we employ the kernel k-means algorithm. We evaluated the proposed method using the Test Collections of Reuters-21578, and compared the results using the Latent Dirichlet Allocation (LDA) Algorithm. The results are encouraging demonstrating that the 3-Gram graph method has much better Recall and F1 score but worse Precision. Further changes that will further improve the results are identified.

References

[1]

Aisopos, F. et al. 2012. Content vs. Context for Sentiment Analysis: A Comparative Analysis over Microblogs. Proceedings of the 23rd ACM Conference on Hypertext and Social Media (New York, NY, USA, 2012), 187--196.

Digital Library

Google Scholar

[2]

Amigó, E. et al. 2009. A comparison of extrinsic clustering evaluation metrics based on formal constraints. Information Retrieval. 12, 4 (Aug. 2009), 461--486.

Digital Library

Google Scholar

[3]

Blei, D.M. et al. 2003. Latent Dirichlet Allocation. J. Mach. Learn. Res. 3, (Mar. 2003), 993--1022.

Digital Library

Google Scholar

[4]

Dhillon, I. et al. 2005. A Fast Kernel-based Multilevel Algorithm for Graph Clustering. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (New York, NY, USA, 2005), 629--634.

Digital Library

Google Scholar

[5]

Dhillon, I. et al. 2004. A unified view of kernel k-means, spectral clustering and graph cuts.

Google Scholar

[6]

Dhillon, I.S. et al. 2004. Kernel K-means: Spectral Clustering and Normalized Cuts. Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, NY, USA, 2004), 551--556.

Digital Library

Google Scholar

[7]

Giannakopoulos, G. et al. 2012. Representation models for text classification: a comparative analysis over three web document types. 2nd International Conference on Web Intelligence, Mining and Semantics, WIMS '12, Craiova, Romania, June 6-8, 2012 (2012), 13.

Digital Library

Google Scholar

[8]

Giannakopoulos, G. et al. 2008. Summarization System Evaluation Revisited: N-gram Graphs. ACM Trans. Speech Lang. Process. 5, 3 (Oct. 2008), 5:1--5:39.

Digital Library

Google Scholar

[9]

Hofmann, T. 1999. Probabilistic Latent Semantic Analysis. Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (San Francisco, CA, USA, 1999), 289--296.

Digital Library

Google Scholar

[10]

Kanungo, T. et al. 2002. An efficient k-means clustering algorithm: analysis and implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence. 24, 7 (Jul. 2002), 881--892.

Digital Library

Google Scholar

[11]

Kernighan, B.W. and Lin, S. 1970. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal. 49, 2 (Feb. 1970), 291--307.

Crossref

Google Scholar

[12]

Newman, M.E.J. and Girvan, M. 2004. Finding and evaluating community structure in networks. Physical Review E. 69, 2 (Feb. 2004), 026113.

Crossref

Google Scholar

Cited By

View all

Violos Jde Lira VDazzi PAltmann JAl-Athwari BSchwichtenberg AJung YVarvarigou TTserpes K(2017)User Behavior and Application Modeling in Decentralized Edge Cloud InfrastructuresEconomics of Grids, Clouds, Systems, and Services10.1007/978-3-319-68066-8_15(193-203)Online publication date: 7-Oct-2017
https://doi.org/10.1007/978-3-319-68066-8_15
Violos JTserpes KPsomakelis EPsychas KVarvarigou T(2016)Sentiment Analysis using Word-GraphsProceedings of the 6th International Conference on Web Intelligence, Mining and Semantics10.1145/2912845.2912863(1-9)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2912845.2912863

Recommendations

Partitioning of a graph into induced subgraphs not containing prescribed cliques
Abstract
Let K p be a complete graph of order p ≥ 2. A K p-free k-coloring of a graph H is a partition of V ( H ) into V 1 , V 2 … , V k such that H [ V i ] does not contain K p for each i ≤ k. In 1977 Borodin and Kostochka conjectured that any graph H ...
Fuzzy Clustering of Text Documents Using Naïve Bayesian Concept
ITC '10: Proceedings of the 2010 International Conference on Recent Trends in Information, Telecommunication and Computing

Clustering organizes text in an unsupervised fashion. In this paper, we propose an algorithm for the fuzzy clustering of text documents using the naive Bayesian concept. Fuzzy clustering implies that the text documents are assigned to multiple clusters, ...
An ensemble approach for text document clustering using Wikipedia concepts
DocEng '14: Proceedings of the 2014 ACM symposium on Document engineering

Most text clustering algorithms represent a corpus as a document-term matrix in the bag of words model. The feature values are computed based on term frequencies in documents and no semantic relatedness between terms is considered. Therefore, two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PCI '14: Proceedings of the 18th Panhellenic Conference on Informatics

October 2014

355 pages

ISBN:9781450328975

DOI:10.1145/2645791

General Chairs:
Katsikas Sokratis
Department of Digital Systems, University of Piraeus
,
Hatzopoulos Michael
Department of Informatics and Telecommunications, National and Kapodistrian University of Athens
,
Apostolopoulos Theodoros
Department of Informatics, Athens University of Economics and Business
,
Anagnostopoulos Dimosthenis
Department of Informatics & Telematics, Harokopio University of Athens
,
Program Chairs:
Carayiannis Elias
Department of Systems & Technology Management, School of Business, George Washington University
,
Varvarigou Theodora
School of Electrical and Computer Engineering, National Technical University of Athens
,
Nikolaidou Mara
Department of Informatics & Telematics, Harokopio University of Athens

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Greek Com Soc: Greek Computer Society
Univ. of Piraeus: University of Piraeus
National and Kapodistrian University of Athens: National and Kapodistrian University of Athens
Athens U of Econ & Business: Athens University of Economics and Business

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 October 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

PCI '14

PCI '14: 18th Panhellenic Conference on Informatics

October 2 - 4, 2014

Athens, Greece

Acceptance Rates

PCI '14 Paper Acceptance Rate 51 of 102 submissions, 50%;

Overall Acceptance Rate 190 of 390 submissions, 49%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
89
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Violos Jde Lira VDazzi PAltmann JAl-Athwari BSchwichtenberg AJung YVarvarigou TTserpes K(2017)User Behavior and Application Modeling in Decentralized Edge Cloud InfrastructuresEconomics of Grids, Clouds, Systems, and Services10.1007/978-3-319-68066-8_15(193-203)Online publication date: 7-Oct-2017
https://doi.org/10.1007/978-3-319-68066-8_15
Violos JTserpes KPsomakelis EPsychas KVarvarigou T(2016)Sentiment Analysis using Word-GraphsProceedings of the 6th International Conference on Web Intelligence, Mining and Semantics10.1145/2912845.2912863(1-9)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2912845.2912863

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Partitioning of a graph into induced subgraphs not containing prescribed cliques

Fuzzy Clustering of Text Documents Using Naïve Bayesian Concept

An ensemble approach for text document clustering using Wikipedia concepts