基于局部加权的Citation-kNN算法

黄剑华 丁建睿 刘家锋 张英涛

(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)

1 引言

1997年，Dietterich等人[1]在对药物活性预测问题的研究中，提出了多示例学习(Multi-Instance Learning, MIL)的概念。在传统学习框架中，一个样本代表一个示例，即样本和示例是一一对应的关系，同时示例的标签全部已知或者全部未知；而在多示例学习中，一个样本被定义为一个包，其中包含了多个示例，即样本和示例是一对多的对应关系，同时样本(包)的标签已知但是示例的标签未知。所以多示例学习中的训练样本的歧义性与传统学习中样本的歧义性完全不同，这使得传统学习方法难以解决多示例问题[2]。

文献[1]提出了APR(Axis-Parallel Rectangle)学习算法来解决多示例药物活性预测问题；Maron等人[3]提出了多样性密度(Diverse Density, DD)算法；Wang等人[4]提出了Bayesian-kNN 和 Citation-kNN两种算法；Zhang等人[5]将 DD 算法与 EM算法相结合提出了 EM-DD算法；Andrews 等人[6]对支持向量机进行了扩展，得到了多示例算法Bag-SVM和Inst-SVM。

在多示例学习概念和算法提出以后，已经在多个领域得到了成功应用，如：药物预测[1]；图像分类、标注[7]、图像分割[8]；视频中人的识别[9]，股票选择[10]；索引网页推荐[11]；显微镜下的肺癌细胞图像识别[12]等。

Citation-kNN算法通过结合惰性学习(lazy learning)和 Hausdorff距离，对 k-近邻算法进行了扩展，使其能够处理多示例学习问题，并在标准测试数据集MUSK上取得了良好的结果。但其所采用的 0-1投票决策方式在实际应用中存在着一定的缺陷。因为在实际分类系统中样本库并不是分布在连续的空间中，并且样本也并不能均匀分布在包空间的任何一个角落，所以实际样本库缺乏足够的样本来表示完整的包空间。在这种不完全库所能表达的特征空间中，样本分布会表现出密集与稀疏，散乱与聚集等特征，同时样本也可能在一个聚集的中心位置或不同聚集的交界处，而Citation-kNN的决策方式无法很好地解决这些特殊情况。

本文针对 Citation-kNN算法的不足进行了改进，提出了基于局部加权的 Citation-kNN算法(Locally Weighted Citation-kNN, LWCitationkNN)。实验证明，该方法在标准库MUSK1上的分类效果较Citation-kNN算法有明显提高，同时，该方法在超声乳腺肿瘤良恶性分类问题中也得到了很好的效果。

2 局部加权的 Citation-kNN(LW.CitationkNN)算法

本文提出的局部加权的 Citation-kNN算法(LWCitation-kNN)主要针对 Citation-kNN 算法中决策部分的不足进行了改进，将包特征空间的分布形式进行细分，得到两种分布特征：距离分布和散乱分布。算法根据以上分布特征的具体情况设置相应的权值和决策准则。

LWCitation-kNN和Citation-kNN的算法流程如图1所示。

图1 LWCitation-kNN和Citation-kNN算法流程图

不同于 Citation-kNN中的 0-1决策方式，在LWCitation-kNN中，根据样本的分布情况，分别提出了基于距离权值、基于离散度权值以及综合这两种分布的决策方式。

2.1 基于距离权值的算法改进

图2是一种可能存在的包分布情况。

图中中心位置的白色方块为测试样本，周围的圆点为训练样本，颜色代表其类别，数量分别为nb和nw。在图中所示的分布情况中，nb/nw=1，若采用Citation-kNN的0-1投票方式，则很难确定测试样本的类别。

基于距离加权的类别决策函数定义为

图2 距离权值解决的情况

本文所采用的距离加权函数为

其中dmax和dmin分别为训练样本到测试样本的最大和最小距离，该距离可以细分为局部形式和全局形式，采用局部形式时，dmax和dmin为投票集合中的最大和最小距离；采用全局形式时，dmax和dmin为所有训练样本到测试样本的最大和最小距离。

2.2 基于离散度权值的算法改进

离散度是用于描述特征空间中局部范围内的不同标签类别的样本点相互掺杂程度，离散度反映了样本局部范围内的可分程度。若在一个区域中心的样本点的可分性很差，则说明这个区域的散乱程度高，同时这个区域的样本点作为训练样本(投票者)的投票可信度就小，即权值要小。

图3是一种可能存在的包分布情况。

图3中的测试样本难以用Citation-kNN和基于距离权值的方法正确分类，但从离散度来看，上方白色训练样本的离散度更低，其权值应该更大，即测试样本判为白色更加合理。

基于离散度加权的决策函数为

图3 离散度权值所解决的情况

其中X为测试示例包，Ti为X投票集合中的训练示例包，其标签ci用+1或-1来表示，S(Ti)为训练示例包的离散度权值，其定义为

其中Ti为训练示例包，将Ti作为待测示例包，可以得到它的投票集合，Tk为Ti投票集合中的训练示例包，其标签ck用+1或-1来表示，W(·)为根据式(2)所得到的Ti投票集合中的训练示例包的距离加权值。

训练样本中可能存在噪声，在图4所示的情况中，采用式(4)计算的离散度是相同的，但在图4(b)中心的训练样本修正为黑色更为合理。

图4 训练样本中存在噪声的情况

为解决这类问题，可以采用带有类别信息的离散度权值，对于不合理的训练样本可以采用式(5)进行修正：

2.3 综合加权算法

综合考虑上面两种分布情况，将基于距离权值和基于离散度权值的方法相结合，得到基于综合加权的Citation-kNN改进算法，算法描述如表1所示。

3 实验结果

本文的实验样本库分别采用标准数据集MUSK1和MUSK2和由哈尔滨医科大学第二附属医院提供的乳腺超声图像库。实验分为两部分，第1部分是针对MUSK1和MUSK2标准数据集进行实验，主要比较本文方法与标准Citation-kNN算法在该数据集上的分类效果；第2部分是针对超声乳腺肿瘤图像库进行实验，分别对比分析不同的加权方法下的分类效果，同时选择适合于此类库的最佳参数组合。

实验中采用交叉验证的方法，将数据集随机分为10组，依次将其中1组作为测试样本，其他9组作为训练样本，在该训练样本上选取参数cn,rn，并在测试样本上进行测试，最终结果取10次测试的平均值。实验采用准确率(ACC)来评价不同算法在数据集上的分类性能，其中参数TP(True Positive)和FN(False Negative)是被正确和错误判别的正例样本数，而TN(True Negative)和FP(False Positive)是被正确以及错误判别的反例样本数，准确率定义为式(6)：通过对前面局部加权方法进行组合，可以得到8种加权方法，如表2所示。

3.1 MUSK库的实验结果

MUSK库包含MUSK1和MUSK2两个分子构造数据集，每个数据集中包含多个示例包，每个示例包包含多个示例，每个示例代表一种分子构造方法，其特点如表3所示。

表2 加权方式的组合

表3 MUSK库

实验中选择reference集合大小取值范围为2～10, citer集合大小取值范围为0～10，在MUSK1和MUSK2上的实验结果如表4所示。

表4 MUSK1和MUSK2上的实验准确率(%)

本文所采用的方法与其他多示例学习算法在MUSK1和MUSK2库上的性能比较结果如表5所示。

表5 与其他算法的准确率比较(%)

结果表明本文的权值设置方法在 MUSK库上有较好的效果，在综合加权方式下(W8)达到最佳性能。本文方法同样具有较好的表现，准确率要高于Bayesian-kNN和Diverse Density算法，但略低于iterated-discrim APR算法，由于该算法针对MUSK数据集进行了优化[13]，因此并不具有代表性；另外一个原因是 MUSK数据集符合多示例学习的标准定义，即：正例包中的正例数大于 1，负例包中所有示例均为负例，而Citation-kNN算法以及本文改进的算法，属于示例包级的算法，并没有考虑包中示例的正负问题，因此针对MUSK数据集的性能提高不大。

3.2 超声乳腺肿瘤良恶性分类实验

本文主要针对116幅乳腺超声图像(58例良性，58例恶性)进行分类，用以验证本文方法的效果。这些乳腺超声图像来源于哈尔滨医科大学第二附属医院的乳腺超声图像库，图像通过GE VIVID7超声影像系统和5.6-14 MHz, 38 mm线性探头采集。诊断结果均得到临床手术证实。

在传统超声乳腺肿瘤分类系统中，每个图像的特征信息需要在肿瘤感兴趣区域(Region Of Interest, ROI)部分提取，为了避免非肿瘤ROI区域信息对最终分类的干扰，应尽量提取出精准的ROI区域，但是现有超声肿瘤分割仍然是医疗图像领域的一个难题，并没有得到很好的解决[14]。同时在一些分类以及分割算法中，需要有医生手动提取的训练样本作为系统的初始条件，手画ROI边界在训练样本大量存在的时候是一项繁琐的工作。为避免ROI区域的分割误差对分类性能的影响，减轻医生的工作负担，本文将超声图像的分类问题转为多示例学习问题来进行处理。

将每幅超声图像划分为等大小的子区域，每个子区域作为示例，整幅图像作为示例包，提取每个子区域的纹理特征(灰度共生矩阵)[15]作为示例特征，如图5所示。

区域大小反映了所提取特征的分辨率，区域越小，则特征分辨率越高，不同区域之间的特征差异越小；区域越大，则特征分辨率越低，极端情况下，当区域大小为图像大小时，则多示例学习问题被还原为传统有监督学习问题，在区域大小的选择上，存在着既能够反映图像的局部特征，又能够使得区域之间的可分性较好的一些划分，对于不同的图像和不同的样本库，该划分不尽相同。

图5 示例包的构建

实验中选择的子区域大小从 50×50～155×155(步长为15)，reference集合大小取值范围为2～10,citer集合大小取值范围为0～10。表6中给出了对图像进行不同划分时，采用不同加权方式时的分类准确率与Citation-kNN, iterated-discrim APR方法准确率的比较。

从实验结果来看，本文所采用的方法在不同的包构建方式下要普遍高于Citation-kNN和iterateddiscrim APR的分类效果，在采用W8(全局距离加权+具有修正功能的离散度加权)加权方式时，效果最佳，同时也说明iterated-discrim APR算法在其他数据集上表现并不理想。

通过对实验结果进行分析，发现被错误分类的样本大部分集中在恶性样本集合内，这说明库中恶性样本之间的差异性较良性样本之间较大，使得恶性样本不如良性样本聚集，分布散乱，造成分类错误。

4 结束语

本文针对Citation-kNN算法进行了改进，充分考虑了样本的分布特征，提出了基于样本距离加权、基于样本离散度加权的方法，并对多种组合方式进行了实验。在标准数据集和乳腺超声图像数据集上的实验结果表明，该方法要明显优于Citation-kNN算法，具有良好的适应性。同时，在超声图像库上的实验结果表明，在医学图像分类中可以采用多示例学习方法，减少对感兴趣区域(ROI)准确定位的依赖，避免由于分割不准确所带来的特征提取误差。在今后的工作中，将进一步针对医学图像的特点，提取更为有效的特征，并探讨扩展传统的多示例学习方法，使之符合医学图像结构复杂，良恶性特征相互重叠等特性。

表6 不同加权方式时的分类准确率(%)

[1]Dietterich T G, Lathrop R H, and Lozano-Pérez T. Solving the multiple-instance problem with axis-parallel rectangles[J].Artificial Intelligence, 1997, 89(1-2): 31-71.

[2]Foulds J and Frank E. A review of multi-instance learning assumptions[J].Knowledge Engineering Review, 2010, 25(1):1-25.

[3]Maron O and Lozano-Pérez T. A framework for multipleinstance learning[J].Advances in Neural Information Processing Systems, 1998,(10): 570-576.

[4]Wang J and Zucker J D. Solving the multiple-instance problem: a lazy learning approach[C]. Proceedings of the 17th International Conference on Machine Learning, San Francisco,CA, 2000: 1119-1125.

[5]Zhang Q and Goldman S A. EM-DD: an improved multipleinstance learning technique[J].Advances in Neural Information Processing Systems, 2002,(14): 1073-1080.

[6]Andrews S, Hofmann T, and Tsochantaridis I. Multiple instance learning with generalized support vector machines[C]. Proceedings of the National Conference on Artificial Intelligence, Edmonton, Alta., Canada, 2002: 943-944.

[7]Katsamanis A, Gibson J, Black M P,et al.. Multiple instance learning for classification of human behavior observations [C].Proceedings of Affective Computing and Intelligent Interaction, Memphis, TN, USA, 2011: 145-154.

[8]Vezhnevets A and Buhmann J. Towards weakly supervised semantic segmentation by means of multiple instance and multitask learning[C]. Proceedings of Computer Vision and Pattern Recognition, San Francisco, CA, United States, 2010:3249-3256.

[9]Guillaumin M, Verbeek J, and Schmid C. Multiple instance metric learning from automatically labeled bags of faces[C].Proceedings of European Conference on Computer Vision,Heraklion, Crete, Greece, 2010: 634-647.

[10]Tsoumakas G, Katakis I, and Vlahavas I. Mining Multi-Label Data, Data Mining and Knowledge Discovery Handbook[M].Berlin: Springer, 2010: 667-686.

[11]Zhou Z H, Jiang K, and Li M. Multi-instance learning based web mining[J].Applied Intelligence, 2005, 22(2): 135-147.

[12]Zhu Liang, Zhao Bo, and Gao Yang. Multi-class multiinstance learning for lung cancer image classification based on bag feature selection[C]. Fifth International Conference on Fuzzy Systems and Knowledge Discovery, FSKD, Jinan,China, 2008, 2: 487-492.

[13]Zhou Z H. Multi-instance learning from supervised view[J].Journal Computer Science and Technology, 2006, 21(5):800-809.

[14]Cheng H D, Shan Juan, Ju Wen,et al.. Automated breast cancer detection and classification using ultrasound images: a survey[J].Pattern Recognition, 2010, 43(1): 299-317.

[15]Liu B, Cheng H D, Huang J,et al.. Fully automatic and segmentation-robust classification of breast tumors based on local texture analysis of ultrasound images[J].Pattern Recognition, 2010, 43(1): 280-298.