基于排序互信息的无监督特征选择

李纯果，张春琴，李海峰

(1.河北大学 数学与信息科学学院，河北 保定 071002；2.河北省机器学习与计算智能重点实验室，河北 保定 071002；3.河北大学 计算机教学部，河北 保定 071002)

无监督排序学习旨在根据评价对象在多个指标上的观测数据，提出一种合理的综合排序模型，得到每个评价对象的综合分值并据此排序.无监督学习问题的首要任务是建立一套合理的评价准则，即无监督排序模型构造面临一个主要的挑战[1]：在没有真实排序结果的情况下，如何保证排序模型的合理性.

目前，由于大多数无监督排序模型的应用背景是信息检索问题中搜索引擎对网页、图像或学术文章的排序[2-4]，排序模型的合理性仍然采用了监督排序学习的评价标准[1]，例如应用NDCG(normalized discounted cumulative gain)、MAP(mean average precision)在人工标注数据集上评价排序模型.如果排序对象不同，例如世界国家经济水平排名、世界大学排名，排序方法不仅不适用，而且也无法标注排序对象.原因在于，应用于综合评价的排序问题不同于网页搜索，是一类静态问题，当排序对象被标注后，排序学习就失去了学习的意义[5].随着深度学习的发展，虽然无监督学习的学习效果有了很大的进步[6]，但是深度模型的训练需要亿万级的训练数据，并不适用于综合评价问题.

在实际应用的学习模型构建中，应用领域知识会影响到模型的选择.在机器学习领域，已经有大量的工作将领域知识嵌入到学习模型中，形成“数据”与“知识”共同驱动的学习模型[7-8]，增加了模型的透明度(transparency)和可理解性[9].无监督排序问题也可以充分利用排序的领域知识，作为观测数据的先验知识和选择排序模型的参考，从而对排序对象做出合理的排序.胡清华等[10]针对序分类问题提出了观测属性与序类标的排序互信息的概念，刻画更抗噪的排序一致性，作为序分类模型的选择标准和训练精度指标.同时，定义的排序互信息在序分类问题上可以进行很有效的特征选择，对分类效果也有很大的提高[10-11].但是，无监督排序问题由于没有序类标的存在[10],定义的排序互信息并不适用于无监督排序模型的学习标准和特征选择的标准.

1 预备知识

给定n个排序对象集合A={a1,a2,…，an},V={v1,v2,…,vd}是观测属性集合.由于每个排序对象在所有观测属性上的观测数据为一个n维实向量x∈Rd，从而对n个排序对象的排序，也即对Rd的n个数据点进行排序.

定义1给定v∈V，如果对于∀x,y∈A，都有v(x)≤v(y),则称x≼vy.

上述定义中，v(x)表示对象x在属性v上的观测值，“≼”表示一种偏序关系，具备自反性、反对称性和传递性.

定义2给定U⊆V，如果对于∀u∈U和∀x,y∈A，都有u(x)≤u(y),则称x≼Uy.

定义 3[12]在属性集U⊆V条件下，优于对象xi的所有对象集合，定义

称之为对象xi的优势类.定义

称之为对象xi的劣势类.

定义4[10]设U1⊆V，U2⊆V，定义U1和U2之间的排序互信息为

(1)

特别地，两属性之间的排序互信息定义为

(2)

设f为排序规则，是根据观测数据对排序对象给出的综合评价分值，是观测属性V到实值的映射.排序规则需要满足单调性，才可以作为观测基础上的综合评价函数，得到排序对象的全序排列.

定义5如果排序规则满足

x≼y⟹f(x)≤f(y),x,y∈A,

(3)

则称f是单调的.

综合评价函数的结果也可以看成是决策属性D，是排序对象的序的量化属性.在序分类问题中，D是学习目标，使得综合评价函数f产生的决策尽可能与排序目标一致.为了反应观测属性与决策属性之间的关联程度，在观测属性间的排序互信息的基础上，Hu等[11]定义了观测属性与决策属性间的排序互信息.

定义6设U⊆V，定义U和D之间的排序互信息为

(4)

根据定义6中的公式(4)，Hu等针对序分类学习问题，计算了表1中数据的2个观测属性分别与决策属性之间的排序互信息为

RMI≼(a1,D)=0.428 1，RMI≼(a2,D)=0.503 9.

2 无监督排序互信息

决策属性是监督学习的重要学习目标，也是评价监督学习模型的重要指标.然而，无监督学习问题中没有真实的决策属性，评价排序学习的模型就需要独立于决策属性.此时，由于决策属性的缺失，公式(4)中定义的排序互信息不适用于无监督排序模型的排序互信息计算.对于表1中的数据，2个属性都与决策属性呈单调增加关系.如果其中一个属性与决策属性呈单调增加关系，而另一个属性与决策属性呈单调减少关系，例如表2中的数据，属性与决策属性呈单调增加关系，而属性与决策属性呈单调减少关系.此时，排序互信息的计算公式(4)不再适用.因此，需要提出一个新的排序互信息的计算公式，独立于决策属性，且能同时反应不同属性体现的不同单调关系.

表2 单增/单减混合序分类数据

由于排序问题中涉及到的排序对象之间的序关系，面向聚类的无监督特征选择方法并不适用.对于无监督排序学习来说，由于没有排序真值，需要根据排序的先验知识对原始多指标观测数据进行特征选择.排序对象之间的序关系满足单调性，在实数意义上，参与排序对象进行观测的属性或特征，与对象的最终排名成单调增加或单调减少关系，即属性值越大，排名越靠前，或越靠后.假设属性u和属性v与排序结果都是单调增加的关系，则u与v之间也是单调增加的关系；而如果属性与排序结果是单调增加的关系，属性却与排序结果是单调减少的关系，那么u与v之间就是单调减少的关系.但是对于给定的观测数据来说，由于未知各属性与排序结果之间的单调关系，当利用在优势关系下定义的排序互信息来衡量两属性之间的单调特征时，不能单独根据两属性之间的RMI≼(u,v)或RMI(u,v)来定义排序互信息.此时，两属性之间的排序互信息定义为

(5)

本文用公式(5)来进行计算无监督排序问题中两两属性间的互信息.对表2中2个属性与决策属性之间的排序互信息根据公式(5)进行计算，结果与公式(4)保持一致，说明该公式可以涵盖原排序互信息的公式，但公式(5)更具有实际的应用适应性.

3 无监督特征选择

在实际无监督排序特征选择问题中，依据最小冗余最大相关(mRMR,minimum redundancy and maximum relevance)原则进行特征选择.对计算的两属性间的排序互信息进行排序，选择具有最大排序互信息的属性对作为无监督排序最相关的属性集合.在这些属性集中，如果一个属性与其他属性都具有最小的互信息，说明该属性不是单调属性，与评价结果无关，该属性为冗余属性，需要从属性集中排除.上述初步进行特征选择的方法为filter方法，在模型训练之前进行，独立于无监督排序模型.

基于排序互信息的无监督排序学习中的特征选择算法为

输入：排序对象的基于d个属性的观测数据.

输出：最相关的属性集合.

1)根据公式(5)计算属性两两之间的排序互信息；

2)计算每个属性的平均互信息；

3)把平均排序互信息进行从大到小的排序；

4)选择排序互信息最大的k个属性.

构建一组模拟数据检验算法的可行性，模拟数据的散点图如图1所示.从图1中可以看出，a2与a4两个属性间有明确的单调函数关系，而a1与a2、a4也有比较明显的单调关系，而a5与其他属性间的单调关系不明显，不是排序的影响因素，为冗余属性，应从排序属性中删除，以免影响决策.根据公式(5)计算的各属性平均互信息如表3所示.可以看出，属性与其他属性具有最小的平均排序互信息，从而与排序无关，可以从特征集中排除.

图1 2-维数据散点分布Fig.1 2-dimensional data spots distribution

表3 各属性平均互信息

4 结论

在无监督排序学习中，由于没有决策属性做参考，已有的基于排序互信息的特征选择方法不再适用.基于属性与潜在的决策属性之间的单调传递关系，本文提出用每个属性与其他属性之间的平均互信息，来衡量每个属性与排序学习结果的相关程度.根据新的排序互信息的定义能够选出基于不同单调关系的评价属性，这是对已有排序互信息定义的推广.虽然本文提出的无监督排序互信息的定义在模拟数据上的特征选择效果更具有广适性，但是对真实数据的效果有待于进一步验证.