付康安，王文剑，郭虎升

1.山西大学 计算机与信息技术学院，太原 030006

2.山西大学 计算智能与中文信息处理教育部重点实验室，太原 030006

1 引言

在现实生活中，符号数据（categorical data）[1-2]在实际应用领域普遍存在，例如在生物医学中，构成DNA序列的核苷酸属性由A、T、G和C四种离散的符号编码而成，血型分为A、B、O和AB型等。这类数据的属性取值是一个有限的符号集合，是定性的，仅描述数据的特征，不提供实际的大小和数量，包括标称属性和序数属性。其中，标称属性的属性值彼此之间没有顺序，只有两种状态，即“等”或“不等”，例如“性别”属性，有“男”和“女”之分；而序数属性的属性值彼此之间有顺序，但相互之间的差值是未知的，属性值关系是“大于”“小于”“等于”，如“饮料量”属性有“大杯”“中杯”“小杯”等属性值，很明显，“大杯”和“小杯”之间的差异性要比“大杯”和“中杯”之间的差异性大。尽管在公开的数据集上下载的符号数据集中大多数是1、2、3等数字，但那只是表示不同的属性值，仅仅是为了方便存储等考虑，不能进行定量分析。

由于符号数据缺乏数值数据固有的几何特性，因此对于数值数据分析的理论和算法无法直接应用在符号数据上。目前关于符号数据的分析主要集中在聚类分析方面[3-7]。对于符号数据的分类，较经典的算法有决策树算法、贝叶斯分类器，其中代表性的算法有C4_5决策树算法[8-9]、朴素贝叶斯分类器[1-2]（naive Bayes classifier，NBC），也有采用0-1相异性度量的K-最近邻算法[2,10]（K-nearest neighbor，KNN）。尽管这些算法能够进行符号数据分类，但是这些方法要么简单地假定符号属性之间是相互独立的，而这又与实际情况不符；……