基于代价敏感的图分类算法

引入图的误分类代价矩阵,选取以最小误分类代价为目标的加权子图作为图样本的特征属性,建立起图的决策树桩分类器,进行集成学习,得到一个对新图进行分类的判别函数.在生成候选子图时,利用子图的超图增益值具有上界的性质来裁剪增益值比较小的候选子图,从而减少候选子图数量,提高算法效率.实验结果表明,所提算法比其他图分类算法的误分类代价更小.

Graph classification algorithm based on cost sensitivity

Introduce cost-matrix of graph misclassification,select the weighted sub-graph based on the least misclassification cost as the attribute of graph,then build up decision stump classifier and ensemble learning,finally obtain a classify critical function to classify a new graph.And use the upper bound of super graph for reducing the number of candidate sub-graphs.Experimental results show that our algorithm performs better than another graph classification algorithm in reducing misclassification cost.