郑碧如，吴广潮

(华南理工大学数学学院，广东 广州 510641)

0 引 言

在机器学习算法中，两实例间距离或者相似性度量扮演着重要的角色，广泛地应用于分类、聚类和奇异值检测和特征学习[1-2]等算法中。常用的距离度量方法，如闵可夫斯基距离、马氏距离等，通常只适用于数值型数据。而对于分类数据，其属性为分类属性(如颜色、形状等)，其值具有离散、无序和取值有限的特点，因此，不能直接对2个不同属性值进行比较，通常是利用数据驱动的方法，通过数据的分布情况等信息来对其进行度量。

对已提出的分类数据的度量方法，可分为不相似性和相似性这2大类。不相似性的方法包括Xie等人[3]提出的方法将分类数据映射到实数域，并以此度量不相似性，通过基于最近邻分类错误率最小化来更新值；Cheng等人[4]使用自适应相异矩阵评估分类属性值之间的差异，用梯度下降法优化误差；Le等人[5]则考虑给定2个值与其他属性的条件概率分布差异的组合进行度量，但随数据维度的增大，其复杂度也大大增加。Alamuri等人在文献[6]中介绍了对分类数据的距离或相似性度量的方法，而Boriah等人在文献[2]则侧重介绍了数据驱动的分类数据相似性度量方法，并根据方法所基于的理论对其做如下分类：基于频数的方法有OF(Occurrence Frequency)，IOF(Inverse Occurrence Frequency)，其中IOF与信息检索的逆文档频率的概念相关[7]，Wang等人[8]将其应用到中文文本分析。基于概率的方法有Goodall，Smirnov和Anderberg，其中Goodall提出的度量使得不频繁属性值对整体相似性的贡献大于频繁属性值；……