ABSTRACT
Automatic classification of data items, based on training samples, can be boosted by considering the neighborhood of data items in a graph structure (e.g., neighboring documents in a hyperlink environment or co-authors and their publications for bibliographic data entries). This paper presents a new method for graph-based classification, with particular emphasis on hyperlinked text documents but broader applicability. Our approach is based on iterative relaxation labeling and can be combined with either Bayesian or SVM classifiers on the feature spaces of the given data items. The graph neighborhood is taken into consideration to exploit locality patterns while at the same time avoiding overfitting. In contrast to prior work along these lines, our approach employs a number of novel techniques: dynamically inferring the link/class pattern in the graph in the run of the iterative relaxation labeling, judicious pruning of edges from the neighborhood graph based on node dissimilarities and node degrees, weighting the influence of edges based on a distance metric between the classification labels of interest and weighting edges by content similarity measures. Our techniques considerably improve the robustness and accuracy of the classification outcome, as shown in systematic experimental comparisons with previously published methods on three different real-world datasets.
- S. Chakrabarti. Mining the Web: Discovering Know- ledge from Hypertext Data. Morgan-Kauffman, 2002. Google ScholarDigital Library
- S. Chakrabarti. Breaking through the syntax barrier: Searching with entities and relations. In ECML, 9--16, 2004. Google ScholarDigital Library
- S. Chakrabarti, B. E. Dom, and P. Indyk. Enhanced hypertext categorization using hyperlinks. In SIGMOD'98, 307--318 Google ScholarDigital Library
- C.-C. Chang, C.-J. Lin. Libsvm: a Library for Support Vector Machines. 2001. Google ScholarDigital Library
- W. W. Cohen, S. Sarawagi. Exploiting dictionaries in named entity extraction: combining semi-markov extraction processes and data integration methods. In KDD, 89--98, 2004 Google ScholarDigital Library
- D. Cohn and T. Hofmann. The missing link - a probabilistic model of document content and hypertext connectivity. In NIPS 13, 2001.Google Scholar
- P. Domingos and M. Richardson. Mining the network value of customers. In KDD, 57--66, 2001. Google ScholarDigital Library
- D. Eppstein. Finding the k shortest paths. In IEEE Symp. on Foundations of Computer Science, 154--165, 1994.Google Scholar
- R. Feldman and H. Shatkay. Link analysis for bioinformatics: Current state of the art, PSB Tutorial, 2003.Google Scholar
- L. Getoor. Link mining: a new data mining challenge. SIGKDD Explor. Newsl., 5(1):84--89, 2003. Google ScholarDigital Library
- J. Han and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, September 2000. Google ScholarDigital Library
- J. Kleinberg, E. Tardos. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. In FOCS, 1999. Google ScholarDigital Library
- J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. of ICML, 282--289, 2001. Google ScholarDigital Library
- S. Z. Li. Markov random field modeling in image analysis. Springer-Verlag New York, Inc., 2001. Google ScholarDigital Library
- Q. Lu, L. Getoor. Link-based classification. ICML, 2003.Google ScholarDigital Library
- H.-J. Oh, S. H. Myaeng, and M.-H. Lee. A practical hypertext catergorization method using links and incrementally available class information. SIGIR, 264--271, 2000. Google ScholarDigital Library
- L. Pelkowitz. A continuous relaxation labeling algorithm for markov random fields. ACM Press, 20:709--715, 1990.Google Scholar
- T. Washio and H. Motoda. State of the art of graph - based data mining. SIGKDD Explor. Newsl., 5(1):59--68, 2003. Google ScholarDigital Library
- T.-F. Wu, C.-J. Lin, and R. C. Weng. Probability estimates for multi-class classification by pairwise coupling. J. of Machine Learning Research, 5:975--1005, 2004. Google ScholarDigital Library
Index Terms
- Graph-based text classification: learn from your neighbors
Recommendations
Passage detection using text classification
Passages can be hidden within a text to circumvent their disallowed transfer. Such release of compartmentalized information is of concern to all corporate and governmental organizations. Passage retrieval is well studied; we posit, however, that passage ...
A Machine Learning Based Ensemble Method for Automatic Multiclass Classification of Decisions
EASE '21: Proceedings of the 25th International Conference on Evaluation and Assessment in Software EngineeringStakeholders make various types of decisions with respect to requirements, design, management, and so on during the software development life cycle. Nevertheless, these decisions are typically not well documented and classified due to limited human ...
Text classification using graph mining-based feature extraction
A graph-based approach to document classification is described in this paper. The graph representation offers the advantage that it allows for a much more expressive document encoding than the more standard bag of words/phrases approach, and ...
Comments