一种特征加权的顺序IB算法

，

(郑州大学 信息工程学院，郑州 450052)

IB方法(Information Bottleneck)是Tishby等人在1999年提出的一种基于信息论的数据分析方法[1]，该方法通过最小化源数据与聚类之间的互信息来实现对数据的压缩，最大化聚类结果与相关信息的互信息来达到对相关信息保存的目的[2]，从而有效地发现数据中隐含的模式。这种算法在文本聚类[3-4]、图像聚类[5]、星系光谱分析[6]、基因表达式分析[7]等领域都得到了有效的应用。

顺序IB算法(sIB)是Slonim于2002年提出的[3]，该算法主要是对待分析数据对象按其与另一数据对象的相关性进行“硬”划分，使划分在一起的对象体现出源数据对象所蕴含的某个特征模式。sIB是较好的IB算法，但是它假定样本中各维特征对分类的贡献是均匀的，事实上，由于数据集中，特征矢量的各维特征来自不同的传感器，存在量纲、精度及可靠性的差异。为了考虑特征矢量中各维特征对聚类结果的不同贡献，本文提出了一种基于特征加权的顺序IB算法，该算法利用特征加权技术ReliefF对特征进行加权，即给特征集中每一个特征赋予一定的权重，并迭代更新权值，然后根据权值大小变化特征集。特征加权后再对其进行聚类分析，不仅使聚类效果优于传统聚类算法，同时可以分析各维特征对聚类的贡献程度。

1 IB和sIB算法

1.1 IB算法

IB算法是在率失真定理基础上扩展的一种新的数据分析方法。对于率失真定理，失真度量的选择是一大难题。因为对于数据资源分布p(x)，不同的率失真函数会产生不同的结果。

在IB理论中，引入一个与源变量相关的目标变量X～p(x)，达到压缩X与维持相关信息平衡的目的，这个相关随机变量称为Y。通过寻找X的压缩变量T(最大化维持了X与相关变量Y的互信息)来确定x,y的联合分布。其中，T形成了从X到Y信息压缩的“瓶颈”。该理论可表示为：

(1)

其中，d(x,t)是失真度量函数；I(T;X)表示T与X的互信息。IB理论通过失真度量函数来度量信息压缩过程产生的失真，使该失真小于预先制定的值D[8]。

IB理论中，压缩变量T只与源变量X有关，与相关变量Y无关，因此有概率分布为

p(x,y,t)=p(x,y)p(t|x,y)

(2)

在率失真中，引入拉格朗日乘数来实现聚类的最优划分。则IB的目标函数表示为

L[p(t|x)]=I(T;X)-βI(T;Y)

(3)

乘数β用来控制压缩和失真的平衡。p(t|x)为随机映射函数。IB理论克服了率失真的缺点，不用考虑如何选取失真度量的问题。

1.2 sIB算法

相对于其他IB算法，sIB算法可以保证能够及时得到一个固定的解，而且有较为理想的时间复杂度和空间复杂度。是一个将已知自凝聚算法映射到类似“顺序KMeans算法”的算法。

sIB算法先将x随机地划分为M个簇(M保持不变)，再在每一步中将每个x从簇t(x)中提取出来，再将x合并到tnew中去，从而得到新的tnew划分[9]。

tnew=arg mint∈Tcost({x},t)

(4)

cost({x},t)=(p(x)+p(t))×JSπ1,π2(p(y|x),p(y|t)),其中π1和π2满足

通过不同的初始值T，可以得到不同的结果，以此来降低局部最优解潜在的不稳定性。因此sIB算法适于实际应用，而且可以得到局部稳定解。

2 特征加权的顺序IB算法(wsIB算法)

特征加权是从原始特征集中，按照某一评价标准,对具有不同区分特性的特征子集进行加权的方法，是提高聚类质量的有效方法[10]。基本的Relief算法是Kira等在1992 年提出的，它可以检测那些与目标属性不相关的特征[11]，当时仅局限于解决两类问题。1994年Kononenko扩展了Relief算法得出一种新的算法，即ReliefF算法，其可以解决多类问题、回归问题以及数据缺失问题[12]。该算法的基本思想是根据每个属性对聚类结果影响程度的不同给每一特征项赋予不同的权重，并迭代更新权值，然后根据权值大小对特征子集做相应的加权变换，使得好的特征聚集同类样本，离散异类样本。

数据集X中，xi=[xi1,xi2,…,xiN]T表示第i个样本的N个特征值。对于任意一个样本xi，首先找出R个与xi同类的最邻近的样本hi,i=1,2，…，R。设diff-hit是N×1的矩阵，表示最邻近样本hi与xi在特征上的差异。

(5)

然后在与xi不同类的子集中找到R个最邻近的样本mli，i=1,2,…，R,l≠class(xi)。设diff-miss是N×1的矩阵，表示mli与xi在特征上的差异，则

(6)

式中：p(l)为第l类数据出现的概率;p(class(xi))是xi在类中出现的概率。

sIB算法以循环的方式遍历所有的数据点，对每个点检查是否要把它从当前簇中取出并放到另一个簇中，这个循环过程迭代至局部最优。将ReliefF算法融入到sIB算法中，在顺序聚类算法的基础上对特征值进行加权。令λ=[λ1,λ2,…，λi]T表示每个特征的权值。将目标函数改写为

tnew←arg mint∈T∑icost({λix},t)

(7)

λ更新式为

λ=λ-(diff-hit)/R+(diff-miss)/R

(8)

当目标函数循环至最小值，就得到了最优的聚类结果。改进后的wsIB算法描述如下：

wsIB算法执行过程：

输入:数据集X,X具有联合分布p(x,y)；

平衡参数β;簇数k.

输出:

X到k簇的随机划分T.

初始化：

T←将X随机划分为k个簇.

主循环：

Done=False;

While not Done

Done←TRUE；

λ=λ-(diff-hit)/R+(diff-miss)/R

For everyx∈X

将x从其归属的t中取出，形成单元素集合{x}

tnew←arg mint∈T∑icost({λix},t)

iftnew≠t

done←FALSE

将x合并到tnew中；

End For

End While

对目标函数tnew的加权,改变了多维数据集中数据项之间在欧式空间中的距离，聚类中循环更新簇的分配将权值计算在内，进而影响了算法迭代过程中不同特征值对聚类结果的影响。

3 实 验

3.1 实验数据

实验数据为在经典数据集UCI中随机选取的8组数据集，包括：Cancer(医学乳肿瘤记录)、Car(汽车评估资料库)、Diabetes(比马族人糖尿病数据记录)、Hepatitis(医学肝炎记录数据)、Iris(鸢尾花数据记录)、Kr_vs_kp(国际象棋残局数据)、Votes(1984美国国会选举记录)、Credit_a(信用记录数据)。用传统sIB算法和加权改进后的wsIB算法分别对其聚类，得出的聚类结果用精度、召回率和准确率进行评估。实验数据描述如表1所示。

表1 UCI数据集

3.2 实验结果

对于数据集Cancer，本文得到的加权矩阵为：λ= [2.633 3，1.322 2，1.477 8，2.055 6，1.066 7，2.666 7，1.855 6，2.522 2，0.071 1]。从这个矩阵来看，第六维特征的贡献最大，第九维特征的贡献最小。由此可见，对于Cancer数据集来说，加权之后特征值从均匀贡献变为第一维特征值最高的不均匀贡献。

表2 sIB算法和wsIB聚类结果对比

实验结果对比如表2所示，对于Car数据集，加权后的聚类结果准确率提高了6.77%、精度提高了2.39%、召回率提高了5.55%。

3.3 实验结果分析

实验所选取的数据从150到319 6个不等，数据的特征个数从4到36个不等。对实验结果分析可得出：

(1)较传统sIB算法，wsIB算法中数据集的3种评价指标(准确率、精度、召回率)均得到不同程度的提高。

(2)wsIB算法对于特征个数少、特征个数多以及数据样本个数少、数据样本个数多的数据集均有效。

(3)wsIB算法不仅改善了聚类的性能，还有助于分析各维特征对聚类的贡献度。

wsIB算法对各个聚类成员的先进性进行了划分，利用权重改变了数据项之间的相对距离，降低了劣质聚类成员的影响，提升了优质聚类成员的影响，使聚类质量大大提高。因此，该算法在精确度方面优于传统IB聚类算法。

4 结 语

本文提出的wsIB方法可以很容易地扩展到其他聚类算法中。因此，将特征加权应用到其他协同学习方法上是未来的一个研究方向。另外，可以对本文提出的方法进行进一步的理论分析，并将它应用到其他领域之中。

参考文献：

[1] Tishby N, Pereira F, Bialek W.The Information Bottleneck Method[C]//Proceeding of the 37th Allerton Conference on Communication.USA:Control and Computing，1999: 368-377.

[2] 朱真峰, 叶阳东.基于变异的迭代 sIB 算法[J].计算机研究与发展, 2008, 44(11): 1832-1838.

[3] Slonim N, Friedman N, Tishby N.Unsupervised Document Classification Using Sequential Information Maximization[C]//Proceeding of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Finland:ACM, 2002: 129-136.

[4] Slonim N, Tishby N.Document Clustering Using Word Clusters via the Information Bottleneck Method[C]// Proceeding of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Greece:ACM, 2000: 208-215.

[5] Goldberger J, Gordon S, Greenspan H.Unsupervised Image-set Clustering Using an Information Theoretic Framework[J].IEEE Transactions on Image Processing, 2006, 15(2): 449-458.

[6] Slonim N, Somerville R, Tishby N, et al.Objective Classification of Galaxy Spectra Using the Information Bottleneck Method[J].Monthly Notices of the Royal Astronomical Society, 2001, 323(2): 270-284.

[7] Tishby N, Slonim N.Data Clustering by Markovian Relaxation and the Information Bottleneck Method[C]// Proceeding of the 13th Annual Conference on Neural Information Processing Systems.Colorado, USA：NIPS，2000: 640-646.

[8] 叶阳东, 刘东, 贾利民.一种自动确定参数的 sIB 算法[J].计算机学报, 2007, 30(6): 969-978.

[9] Ye Y D, Ren Y, Li G.Using Local Density Information

to Improve IB Algorithms[J].Pattern Recognition Ietters, 2011, 32(2): 310-320.

[10] Ji B, Ye Y D, Xiao Y.Mutual Information Evaluation: a Way to Predict the Performance of Feature Weighting on Clustering[J].Intelligent Data Analysis, 2013, 17(6): 1001-1021.

[11] Kira K, Rendell L A.A Practical Approach to Feature Selection[C]//Proceeding of the 9th International Workshop on Machine Learning.Britain: Morgan Kaufmann Publishers Inc., 1992: 249-256.

[12] Lim S C, Jang S J, Lee S P.Music Genre/Mood Classification Using a Feature-based Modulation Spectrum[C]//International Conference on Mobile IT Convergence(ICMIC)．Washington: Procceeding of IEEE Computer Society, 2011:133-136.