代价敏感的GEP分类算法实现

在数据挖掘领域中，通常以分类精度作为分类算法效果的评估标准。这一标准是建立在假设任意一实例被误分类为任意类时都具备同样代价的基础上的。当此假设不成立时，直接使用传统分类方法就无法取得良好的分类和预测效果。针对这一问题，通过改进编解码方法以及在适应度函数中集成样本的不同误分类代价，提出了一种基于基因表达式程序设计的代价敏感分类算法(CSC-GEP)，并在三个UCI数据集上对该算法进行了测试，实验结果表明CSC-GEP是一种有效的代价敏感分类算法。
关 键 词 分类; 代价敏感; 误分类代价; 基因表达式程序设计

In data mining reseach, the classification algorithms generally pursue more highly accuracy. It is based on the assumption that all misclassifications have the same cost. However, the assumption is not correct in the real world, so that the normal classification algorithms do not perform well. By improving the encode/decode methods and taking different misclassification cost into account, this paper concerns a new cost-sensitive algorithm called CSC-GEP based on Gene Expression Programming (GEP). The experimental results show that the new algorithm is effective.
Key words classification; cost-sensitive; cost of misclassification; gene expression programming

在数据挖掘中，分类的任务通常是建立一个期望误分类数量最小的分类器，比较典型的例子如C4.5的决策树算法，在传统上都是基于分类错误具有相同的代价的假定上的。而在现实中，不同的分类错误通常会导致不同的代价。以UCI数据集中的Heart disease数据集为例，错误地将健康的人分类为患病的代价仅仅是使健康的人接受更多的检查，但如果将患病的人分类为健康，则有可能延误病人的治疗。很明显，第二种错误分类会令使用者付出远比第一种错误分类更大的代价。仍以Heart disease数据集为例，在这一数据集上建立分类器的目的是为了检测出患病的就诊者。对某一特定疾病而言，可能存在的情况是全部就诊者中仅有极少数是患病者，则在最糟糕的情况下，使用传统分类方法产生的分类器只需要牺牲全部患病者的实例作为误分类即可获得一个在传统意义上的高精度分类结果。但此时这个分类器也就丧失了存在的意义。因此在处理误分类代价不统一的数据集时，单纯地以分类精度作为分类器的评估标准就变得不恰当了。一种合理的解决方法是以代价敏感(Cost Sensitive Classification，CSC)的分类取代精度敏感的分类。
本文通过在GEP的适应度函数中加入代价矩阵，提出了基于基因表达式编程的代价敏感分类算法CSC-GEP。通过在UCI数据集中的Heart disease数据集、Sick数据集和Credit数据集上的分类算法与传统算法进行实验对比，结果证明CSC-GEP是一种有效的代价敏感分类算法。