Text Categorization Based on Graph Kernel

doi:10.3969/j.issn.1006-2475.2017.11.003

Abstract

Abstract: In text classification, vector space model has the characteristic of simple representation, but only represents frequency information of feature word and ignores the structural information and semantic information of word order between words, which may lead to different documents to be represented as vectors of the same. In view of this problem, this paper uses the graph structure model to represent text, and a text is represented as a directed graph (abbreviated as text graph), which effectively solves the problem of the lack of structured information. In this paper, the graph kernel technique is applied to text classification, and a graph kernel algorithm, which is suitable for the computation of the similarity between text graphs, is proposed. Then support vector machine is used to classify the texts. The experimental results on the text set show that compared with the vector space model, the classification accuracy of interval walk kernel is better than other kernel functions, so it is a good graph structure similarity calculation algorithm and it can be widely used in text classification.

Key words: graph structure, vector space model, gap walk kernel, support vector machine, text categorization

CLC Number:

TP391

JIANG Qiang-rong, SONG Lie-jin. Text Categorization Based on Graph Kernel[J]. Computer and Modernization, 2017, 0(11): 13-16+61.

References

[1] Feng Guozhong, Guo Jianhua, Jing Bingyi, et al. Feature subset selection using naive Bayes for text classification[J]. Pattern Recognition Letters, 2015,65:109-115.

[2] Wajeed M A, Adilakshmi T. Different similarity measures for text classification using KNN[C]// Proceedings of the 2nd International Conference on Computer and Communication Technology. 2011:41-45.

[3] Haddoud M, Mokhtari A, Lecroq T, et al. Combining supervised term-weighting metrics for SVM text classification with extended term representation[J]. Knowledge and Information Systems, 2016,49(3):909-931.

[4] Salton G. The SMART Retrieval System: Experiments in Automatic Document Processing[M]. Prentice-Hall, 1971.

[5] Gee K R, Cook D J. Text classification using graph-encoded linguistic elements[C]// Proceedings of the 18th International Florida Artificial Intelligence Research Society Conference. 2005:487-492.

[6] 周昭涛,卜东波,程学旗. 文本的图表示初探[J]. 中文信息学报, 2005,19(2):36-43.

[7] Schenker A, Last M, Bunke H, et al. Classification of Web documents using a graph model[C]// Proceedings of the 7th International Conference on Document Analysis and Recognition. 2003,1:240-244.

[8] Kondor R I, Lafferty J D. Diffusion kernels on graphs and other discrete input spaces[C]// Proceedings of the 19th International Conference on Machine Learning. 2002:315-322.

[9] 王立鹏,费飞,接标,等. 基于子图选择和图核降维的脑网络分类方法[J]. 计算机科学与探索, 2014,8(10):1246-1253.

[10] Zhao Ruiqi, Martinez A M. Labeled graph kernel for behavior analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016,38(8):1640-1650.

[11] Yang Yiming, Pedersen J O. A comparative study on feature selection in text categorization[C]// Proceedings of the 14th International Conference on Machine Learning. 1997:412-420.

[12] 吴金源,冀俊忠,赵学武,等. 基于特征选择技术的情感词权重计算[J]. 北京工业大学学报, 2016,42(1):142-151.

[13] Quinlan J R. C4.5: Programs for Machine Learning[M]. Morgan Kaufmann Publishers, 1993.

[14] Mladenic D, Grobelnik M. Feature selection for unbalanced class distribution and naive Bayes[C]// Proceedings of the 16th International Conference on Machine Learning. 1999:258-267.

[15] 梅玲,张亚丽. 结构化数据核函数综述[J]. 计算机工程, 2010,36(23):199-201.

[16] Gärtner T. A survey of kernels for structured data[J]. ACM SIGKDD Explorations Newsletter, 2003,5(1):49-58.

[17] Gärtner T, Flach P, Wrobel S. On graph kernels: Hardness results and efficient alternatives[C]// Proceedings of the 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop. 2003:129-143.