基于邻域粗糙集的主动学习方法

2017-12-20胡峰，周耀，王蕾

重庆邮电大学学报(自然科学版) 2017年6期

关键词：粗糙集邻域分类器

胡峰，周耀，王蕾

(重庆邮电大学计算智能重庆市重点实验室，重庆 400065)

基于邻域粗糙集的主动学习方法

胡峰，周耀，王蕾

(重庆邮电大学计算智能重庆市重点实验室，重庆 400065)

主动学习是机器学习领域的重要研究方向。现有主动学习方法通常选择不确定性的或具有代表性的样本供专家打标，然后添加到已标记的数据集中供分类器学习，但没能充分利用数据的分布信息，并且在野点采集问题上有待改进。结合邻域粗糙集理论，提出了一种基于邻域粗糙集的主动学习方法(neighhbor rough set active learning，NRS-AL)。实验结果表明，在加州大学数据集(university of CaliforniaIrvine，UCI)上，该算法充分利用了数据的分布信息，同时结合样本的不确定性和代表性计算，处理了野点的选择，是一种能有效解决主动学习样本选择问题的算法，在accuracy，受试者工作特征(receiver operating characteristic curve，ROC)曲线下面的面积(area under curve，AUC)指标上优于文献中的主动学习算法。

邻域粗糙集；主动学习；基于池的样本选择

0 引言

在传统监督学习问题中，通常给定有标记的样本作为训练集，学习算法以此训练出分类模型。在真实的数据分析场景下，虽然我们可以轻松获得海量的数据，但是这些数据都是没有标注过的数据，很多经典分类算法并不能直接应用，对数据进行一一标记不仅需要时间和精力还要有专业的知识，这代价显然是比较昂贵的，实行起来也是比较困难。如果算法可以主动对原始数据进行筛选，只将含有信息量较高的数据交给专家标注，那么就可以解决上述问题。半监督学习(semi-supervised learning)和主动学习(active Learning)算法在这种情况下应运而生，并且得到了快速发展。主动学习最初是由耶鲁大学的Angluin教授[1]提出，该方法选择部分最值得标记的样本进行标记添加到训练集，之后利用新的分类器模型对无标记样本进行再次选择，通过标记部分样本扩大训练集和迭代训练的方式使得学习模型的泛化能力得到提高。主动学习可以高效利用专家标注并且适用性广泛，在机器学习领域占有举足轻重的地位。

目前，主动学习的处理方法可以分为2种：基于流(stream-based)的处理方法和基于池(pool-based)的处理方法。在基于流的主动学习[2]中，设定一个阈值，所有未标记的样本逐个提交给选择引擎，由选择引擎根据计算结果和阈值对比，来决定是否标记当前提交的样本。在基于池的主动学习[3]中，设立一个未标注样本集合，由选择引擎在该集合中选择当前值得标注的样本。目前研究比较充分的是基于池的主动学习样本选择方法，按照选择标准可分为：基于不确定性缩减的方法[4-6]、基于版本空间缩减的方法[7-9]、基于未来泛化错误率缩减的方法[10-12]等。

在基于不确定性缩减的方法中，由于在计算样本重要性时需要考虑到样本本身的不确定性，我们需要借助数学工具来表达和处理这些不确定性问题。Rough集[13-18]理论是一种有效的不确定信息处理方法，可以根据数据分布，自动将样本空间划分为正区域、边界域和负区域。迄今为止，不少学者结合粗糙集开展了主动学习算法的研究。Wang等[19]提出结合模糊粗糙集选择样本的主动学习方法，通过计算样本在条件特征和决策标签之间的不一致性来选择样本。此外，Wang等[20]还提出了基于模糊粗糙集做流式选择的主动学习方法，通过模糊粗糙集考虑特征和决策标签之间的不一致性来计算样本的不确定性。

本文结合邻域粗糙集[21]理论，通过对边界区域内的样本计算样本重要性，提出了一种基于邻域粗糙集的主动学习样本选择方法(neighhbor rough set active learning，NRS-AL)，并结合J48基分类器，对无标签数据进行标记并添加到训练集。实验结果表明，文中提出的算法是一种有效的解决主动学习样本选择问题的算法，在accuracy，受试者工作特征(receiver operating characteristic curve，ROC)曲线下面的面积(area under curve，AUC)等指标上优于文献中的主动学习算法。

1 相关概念

1.1 基于不确定性的主动学习方法

主动学习方法的工作过程是维护一个迭代训练的分类器的过程，一般可以分为2个部分：学习引擎和选择引擎。学习引擎负责维护一个基分类器，根据提供的训练集和新增的标记样本，利用监督学习算法进行迭代学习，从而使该分类器性能提高；选择引擎负责运行样本选择算法，选择新的样本交给人类专家进行标记，之后将标记的样本添加到训练集中。学习引擎和选择引擎交替工作，通过不断的迭代使得基分类器性能不断提高，当达到迭代次数或者预定精度等预定条件时，算法终止。主动学习算法伪代码描述如下。

输入：已标记的训练集L，未标记的数据集U，测试集T，学习引擎LE，选择引擎SE

当今社会的就业竞争非常激烈，用人单位在选择毕业生的时候都会着重考虑他们的综合素质和实用的技术能力。随着社会国际化进程发展的需要，对毕业生提出了更高的要求，不仅需要他们掌握专业技能，还需要他们能够使用英语对外进行交际。因此，高职院校英语教学的重点是要加强学生使用英语对外进行沟通的能力。高职英语教学可以在课堂上模拟各种真实工作场景，锻炼学生在实践中解决各种问题。“实践出真知”，这种任务型教学模式将会大大提高学生实际生活中用英语解决各种问题的能力，从而提高高职院校学生的就业水平。

输出：学习引擎LE

step1:train(LE，L) //训练基分类器模型

result=test(LE，T)//测试样本

案例3：在“均值不等式的定理”一节中，可用“某商店在节前进行商品降价酬宾销售活动，拟分两次降价，有三种降价方案：甲方案是第一次打A折销售，第二次打B折销售；乙方案是第一次打B折销售，第二次打A折销售；丙方案是两次都打—样折销售，问哪一种方案降价较多？”

if 算法精度或者迭次次数到达预设条件

return LE算法结束

step2：S=select(SE，U)//使用样本选择算法从无标记样本中选择最值得标记的样本

step3：label(S)//将选择的样本交给人类专家进行标记

step4：L=L+S；U=U-S ；return step1;

//更新训练集和无标记数据集，将标记好的样本添加到训练集，同时在未标记数据集中删去所选样本，并返回step1迭代执行

本研究结果提示，B7-H3蛋白除了在免疫调节中发挥作用，还对肿瘤细胞的生物学特性产生影响，同时也提示我们，B7-H3蛋白在不同组织细胞中可能发挥不同的作用。这些实验数据可以为进一步研究B7-H3的功能奠定实验基础，同时也将为乳腺癌的治疗提供新的靶点。

(1)

1.2 邻域粗糙集

1988年，T.Y Lin[24]提出了邻域模型，该模型通过空间点的邻域来粒化论域空间。把邻域理解成基本信息粒子，空间中的其他概念可借此进行描述。

胡清华等[25]利用邻域模型对经典粗糙集理论进行拓展，提出了邻域粗糙集模型。在该模型中，实数空间中的点形成一个δ邻域，所以空间中任意概念的基本信息粒子由δ邻域族描述。

定义1[25]给定任意xi∈U，B⊆C,xi在属性子集B上的邻域δB(xi)定义为

δB(xi)={xj|xj∈U,ΔB(xi,xj)≤δ}

(2)

δ为度量函数。定义x1，x2为2个N维空间样本，A={a1,a2,…,aN}，f(x,ai)表示x在属性ai上值，则2个样本的Minkowsky距离可定义为

(3)

当p=2时，即欧拉距离(euclidean distance)。

ASet=random(ASet)

(4)

(4)式中：C1为总体样本中属性值为V1的个数，C1i为其中类别为i的个数；C2是总体样本中该属性值为V2的个数，C2i为其中类别为i个数；K取常数，通常设为1。

定义2[25]邻域近似空间定义如下，给定数据集U，N是U的邻域关系，邻域粒族可表示为{δ(xi)|xi∈U}，则表示为邻域近似空间。

之后，新的海底往两边均匀地推开山脊上密度较大的现有岩块，在地球表面的海洋板块之间漂离得越来越远，直到最终被海沟吞没或撞到海岸上。当板块相撞之时，一个板块会滑动到另一个板块下面，熔化成地球内部的物质。科学家认为，自从侏罗纪时代，一片相当于太平洋大小的水域独自潜没于美洲大陆之下，这也是那里的海底较为年轻的原因。

定义3[25]对于任意X⊆U，在邻域空间下，X在邻域关系N中的上近似，下近似和边界域定义为

(6)式中：min(dis(xi,s))表示距离其最近样本的距离；range(dis(xi,s))表示在指定数据集中其距离的取值范围；w表示权重。将邻域内的样本划分为负域，边界上的样本划分为边界域，邻域外的样本划分为正域，算法对边界域和负域的样本进行处理。

做人要实，就是要清清白白做人，老老实实干事。为人处世要表里如一、知行合一，仰不愧天，俯不愧地，内不愧心，打牢修身做人的根基，夯实为官从政的基础，做官要经得起道德良知的拷问，要经得起历史后人的评说，做一个高尚的人和有益于人民的人。

牙隐裂是牙体牙髓科的常见病，根据隐裂程度不同我们采取的治疗方法也不尽相同，对于伴发牙髓炎或者根尖周炎隐裂牙通常会采取根管治疗后冠修复来保存患牙。根管治疗是目前治愈牙髓炎和根尖周炎的有效方法，常规的根管治疗包括根管预备，根管消毒和根管充填，因此疗程较长，患者需要多次到医院接受治疗，伴发牙髓炎或者根尖周炎的隐裂牙因其特殊性需要的治疗时间越短患牙的保存几率就会越高。近年来一次性根管治疗技术的疗效得到了肯定，为了节省患者就诊时间和提高患牙的保存率，我院对伴发牙髓炎或根尖周炎的患牙采取了一次性根管治疗技术，其临床疗效值得肯定，现将本次研究结果进行如下报道。

(5)

2 基于邻域粗糙集的主动学习方法

2.1 算法思路

主动学习方法一般考虑信息含量高的和具有代表性的无标记样本进行标记，信息含量高也就是不确定性大，适合使用粗糙集来处理这类不确定性问题。一般主动学习算法在计算代表性时使用的是聚类算法，但是聚类仅利用无标记样本的分布信息，而本文提出的算法不仅利用无标记样本的分布信息，还利用有标记样本的分布信息。同时在预处理阶段，对无标记样本在邻域内缩减样本，有效地控制了野点的采集。

2.1.1 计算训练集样本和无标签样本的两两距离

考虑是计算数据集中所有样本之间的两两距离，本算法大部分时间在距离计算，所以考虑多线程并行的方式，用公式(3)进行计算。

2.1.2 确定样本的邻域半径

δ=min(dis(xi,s))+w×range(dis(xi,s)), 0≤w≤1

(6)

∅,xi∈U},

2.1.3 计算待标记样本的信息量

考虑信息熵的计算方式

(7)

待标记样本邻域信息量定义如下

(8)

(9)

邻域内的无标记样本信息量原理如图1所示，在有标记样本集中计算无标记样本A和B的信息量，在A的邻域中，含有更多类别的样本，所以无标记样本A的信息量大于B，样本A更容易被选中。

1)积极引进国内外知名MOOCs课程体系，并重点建设本专业自己的MOOCs课程和翻转课堂教学模式，并应用于课程教学中，目前已完成3门专业课程的MOOCS建设和3门专业课程的“翻转课堂”教学模式的建设，并都应用于相关课程教学改革的实施中。

图1 邻域内的无标记样本信息量原理图Fig.1 Principle of calculating the information quantity of the non labeled samples in the neighborhood

2.1.4 计算待标记样本的泛化量

考虑样本的泛化性能，也就是需要待标记样本处于训练集的低密度区域，并且处于无标签数据集的高密度区域。无标签样本邻域泛化性定义如下

gene(x)=dens_u(x)p/dens_l(x)q

(10)

(10)式中：dens_1表示样本在训练集中的邻域密度；dens_u表示样本在无标签数据集中的邻域密度；q,p为权重。无标记样本在有标记样本邻域和无标记样本邻域计算泛化量原理如图2所示，在所有样本集中计算无标记样本A和B的泛化量，在A的邻域中，A处于无标记样本集的高密度区域，有标记样本集的低密度区域，而B样本处于有标记样本的高密度区域，所以,A的泛化量大于B，样本A会更容易被选中。

2.1.5 计算待标记样本的重要性

为了避免信息量和泛化量过大过小，所以考虑取p泛数，省去了调参过程。

随着“大众创业、万众创新”的发展浪潮，大学生自主创业成为解决大学生就业困难问题的有效手段，正引起社会的广泛关注和重视。面对高校毕业生日益严峻的就业形势，大学生无疑是创业界的中流砥柱及重点培育对象，对于为社会注入新鲜的活力颇为重要。但尽管如此，比起社会平均水平，大学生创业成功的概率仍较低。本文通过对200份广东大学生创业融资情况问卷的数据研究发现，41%的大学生认为资金短缺是创业路上的最大障碍。

imp(x)=(info(x)p+gene(x)p)1/p

(11)

将样本按照重要性排序，取TopK添加到训练集，并从无标签样本中删除这部分样本

与蒙特卡洛仿真类似，利用重要抽样策略进行失效概率梯度计算时，随机样本与式(7)中失效概率计算的样本一致，即利用重要抽样策略计算失效概率梯度时不会增加额外的计算成本。

2.1.6 基于邻域样本缩减解决采集野点的问题

在无标记样本集中指定一个较小的邻域半径权重w，在预处理阶段删除邻域内的样本即可，即可达到去除野点的目的。

图2 无标记样本在有标记样本邻域和无标记样本邻域计算泛化量原理Fig.2 Non labeled samples are calculated from the neighborhood of labeled samples and the neighborhood of unlabeled samples

2.2 算法描述

基于邻域粗糙集的主动学习方法的具体步骤。

1)根据指定参数划分数据集，输入训练集占比，无标签样本占比，剩余数据为测试集，算法如下。

算法1数据集划分算法

输入：全部数据集ASet，训练集比重t，无标签数据比重u。

输出：训练集TSet，无标签数据集USet，测试集TestSet。

毫无疑问，数学史融入数学教学实践会对学生的数学学习产生影响，此方面的研究大都依托于具体的教学主题，通常附属于HPM教学实践，在数学史融入数学教学实践后对融入效果进行测评，以此看对学生数学学习的影响．例如报告11在数学史融入对数教学实践后，研究者用学生课上对工作单的作答、小组及全体讨论的录音及课后两份匿名的问卷来评估学生知识的获得及学生对使用数学史的意见等．报告17中，研究者用前后测、田野观察及最后的问卷来评估实践效果．

TSet=∅;USet=∅;

TestSet=∅

4.并购后组织机构整合的纳税筹划。并购后组织机构整合的纳税筹划主要是考虑应该设立子公司还是分公司，但无论设立哪种，都应该从总体利益出发。企业若是设立子公司，对于享受税收优惠的被并购企业，并购企业应该设立子公司，延续该优惠政策，母子公司之间的利润可以进行合理转移，各种费用容易形成合理列支，使母子公司之间的税收筹划空间更大。企业若是设立分公司，因为分公司不具有独立法人资格，需要总公司汇总收支进行纳税，所以总公司的盈利可以冲减分公司的亏损，降低总体税负。

良好的开端是成功的一半，新班主任在开学工作伊始，就要在班级工作上打好第一战，吃好“开头奶”，在新接班级工作开展的每一个“第一次”上下功夫，让每一个“第一次”化为一种坚守，多管齐下，力争文明之花随之绽放。那么，班主任要从哪几个方面快速投入班级建设呢？笔者结合自己的经验浅谈中途新接班级的几点方略。

步骤2：(打乱数据)

欧拉距离只适用于属性是连续型的情况，不能处理分类型属性。Stanfill和Waltz[26]提出的不同属性度量 (value difference metric，VDM)可用来处理分类型属性。假设样本x1，x2有分类型属性的2个值V1，V2，他们之间的距离定义为

步骤3：(划分数据)

TSet=ASet[0,size(ASet)×t]

USet=ADet[size(ASet)×t,size(ASet)×(u+t)]

TestSet=ASet[size(ASet)×(u+t),size(ASet)]

步骤4：将训练集，无标签数据集和测试集分别输出。

2)根据算法1划分的数据集，对无标签样本进行计算信息量和泛化量，然后对重要性排序对topk的样本进行询问(query)操作，将新打标的样本添加到训练集，并重复此过程，直到无标签样本被选择完，训练集不再更新，算法如下。

算法2基于邻域粗糙集的主动学习算法(NRS-AL)

输入：训练集TSet，无标签数据集USet，测试集TestSet，邻域半径参数w，重要性计算的参数泛数p，每次选择询问的样本数k。

forxiin USet do

步骤1：(计算TSet和USet中样本间距离)

利用公式(3)和(4)计算distance(x,y)

步骤2：(计算无标记样本的邻域)

forxiin USet do

利用公式(5)计算样本xi在TSet和USet中的邻域半径δ。计算xi的邻域δ1(xi)和δu(xi)，将邻域内的样本划分为负域，边界上的样本划分为边界域，邻域外的样本划分为正域，算法对边界域和负域的样本进行处理。

步骤1：(初始化)

δ1(xi)={x|x∈TSet,Δ(x,xi)≤δli}

这项研究还表明，通过额外的机制，小农户可以整合入新的供应链。在超市供应链中，先锋农民对于鼓励其他农民的参与是非常重要的，例如，通过“卫星”农场实现。尽管农民愿意通过正规的农民组织参与集体行动加入超市供应链，但是还有些农民可能是通过其他的机制参与。政策不应仅仅因为社会的原因而促进组织的发展，也要根据农民的条件和喜好去探索其他机制。

δu(xi)={x|x∈USet,Δ(x,xi)≤δui}

end for

步骤3：(计算无标签样本的重要性)

输出：分类器ActiveClassifier

利用公式(7)计算info(x)，

利用公式(9)计算gene(x)，

利用公式(10)计imp(x)。

end for

QuerySet=topk(rank(X))

TSet={x|x∈TSet,x∈QuerySet}

USet={x|x∈USet,x∉QuerySet}

步骤4：(更新分类器并输出测试集结果)

if TrainSet is updated then

ActiveClassifier=train(TSet)

TestResult=test(TSet)

else return ActiveClassifier

重复步骤2—步骤4直到训练集不再更新。

3 实验评价

3.1 数据集及评价指标

本次试验所使用的15个数据集为公开数据集，如表1所示，其中字母识别来自加州大学数据集(University of CaliforniaIrvine，UCI)[27]，选择其中比较难分辨的DP，EB，EF，IJ，MN，RK构建二分类数据集。其中数字手写体识别数据集来自Kaggle[28]中较难分辨的17，35，69，89作为本次实验的数据集。austra，cortex_nuclear，occupancy，vehicle，wdbc均来自UCI公开数据集。其中多分类评价指标为准确率accuracy，二分类评估指标为受试者工作特征(receiver operating characteristic curve，ROC)曲线下面的面积(area under curve，AUC)。其中,AUC被定义为ROC曲线下的面积，由于ROC曲线一般都位于y=x这条线的上方，所以AUC的取值在[0.5，1]。因为在很多时候，ROC曲线并不能清晰地说明哪个分类器效果更好，通常考虑到数据集分布有可能是不平衡数据，所以,本质是对分类器排序性能评估的AUC指标在二分类中获得更广泛的使用。

表1 实验数据集Tab.1 Experimental data set

3.2 实验方法

本次实验采用随机方法将1%的数据划分为初始训练集，69%的数据划分为无标签数据集，30%的数据划分为测试集。无标签数据均分成50次添加到训练集，基分类器采用开源工具Weka中的J48，使用默认参数。对每个数据集运行10次取均值作为最终实验结果。

3.3 实验评估结果

本次实验采用AUC和accuracy作为评估指标。AUC表示ROC曲线下的面积，介于0和1之间，AUC作为数值可以直观的评价分类器的好坏，AUC值越大表示当前分类算法越有可能将正样本排在负样本前面。accuracy表示分类准确率，二分类采用AUC评估，多分类采用accuracy评估。采用5种主动学习方法，基于不确定性的主动学习方法[29](uncertainty)，主要采用基于SVM为基分类模型的一种基于超平面度量样本不确定性的方法；基于代表性的主动学习方法[30](representative)，主要采用了基于层次聚类来度量样本代表性的方法；委员会投票主动学习方法[7](QBC)，采用了训练多个模型来投票度量样本信息量的方法；随机选择的主动学习方法(random)，保持新样本的较大泛化性能的方法。Huang[31]等提出的主动学习算法中，实验结果表明，部分主动学习算法性能并不如随机选择效果好，所以本文也将随机选择的方法加入对比。本文所使用的基于粗糙集的主动学习方法(NRS-AL)。在本次实验中，分别使用20%，40%，60%，80%，100%无标记数据，实验结果如表2-表6所示，对于5种算法重复10次试验取平均结果，评估指标为10次试验的均值，二分类数据采用AUC评估，多分类数据采用accuracy。

表2 使用20%无标记数据时算法性能对比Tab.2 Performance comparison of algorithms using 20% unlabeled data

表3 使用40%无标记数据时算法性能对比Tab.3 Performance comparison of algorithms using 40% unlabeled data

表4 使用60%无标记数据时算法性能对比Tab.4 Performance comparison of algorithms using 60% unlabeled data

表5 使用80%无标记数据时算法性能对比Tab.5 Performance comparison of algorithms using 80% unlabeled data

表6 使用100%无标记数据时算法性能对比Tab.6 Performance comparison of algorithms using 100% unlabeled data

续表6

在15个数据集上，对比5种算法在无标签数据添加过程的性能表现，在不同无标签数据量时，其中本文提出的NRS-AL算法在75次比较中45次获得领先，明显优于其他算法。representative和QBC其次，分别是基于代表性主动学习算法和不确定性主动学习算法中效果较好的算法，本文提出的NRS-AL算法吸取了2种算法的优点，同时考虑了样本的代表性和不确定性，并且处理了野点，使得算法选择到的样本更重要，对模型的性能提升更大。random算法效果最差，虽然该算法选择的样本泛化性能较好，但是过于盲目，细节因素并未考虑。

另外NRS-AL算法在digit 4个数据集中表现并不如意，因为该数据集在实验数据中特征数明显大幅多过其他数据集，包含784个特征，其余数据集特征数在5-81之间，特征过多时可能包含的噪声特征也变多，导致NRS-AL算法性能下降。

在所有数据集上不同数据量时算法性能平均表现如表7所示。无标记数据量在20%-40%的时候，本文提出的NRS-AL算法性能明显领先于其他算法，甚至超过100%无标记数据作为训练集的性能，当数据量逐渐增加的时候，所有算法性能均保持提升并趋于稳定。

表7 在所有数据集上不同数据量时算法性能平均表现Tab.7 Algorithm performance with average performance in all data sets with different data volumes

4 结束语

本文提出了一种基于邻域粗糙集的主动学习方法，用于解决主动学习算法中无标签样本的选择问题。首先根据邻域粗糙集模型从样本分布来定义正域样本、边界域样本和负域样本；然后对负域和边界域样本进行计算无标签样本的不确定性和泛化性，以此来衡量该无标签样本的重要性。一方面该算法充分地利用了有标签数据和无标签数据的分布，另一方面，还在预处理阶段过滤掉部分无标签样本，减少计算量，同时计算了样本的泛化性能，有效地解决了野点采集问题。在15个UCI数据集上的实验结果表明，相较于其他主动学习算法，文中提出的方法对样本选择的效率明显提高，在相同样本选择数量上，精度和AUC指标也明显提高。在20%-40%无标记数据使用量时，本文提出的算法性能甚至超过100%无标记数据使用量性能，起到了缩减样本的功能。本文所提出方法适合在大规模集群上并行实现，研究更高效的并行算法将是今后的研究重点。

[1] ANGLUIN D. Queries and concept learning[J]. Machine Learning, 1988, 2(4):319-342.

[2] FREUND Y, SEUNG H S, SHAMIR E, et al. Selective Sampling Using the Query by Committee Algorithm[J]. Machine Learning, 1997, 28(2):133-168.

[3] MUSLEA I A. Active Learning with Multiple Views.[J]. Journal of Artificial Intelligence Research, 2011, 27(1):203-233.

[4] WROBEL S. Active Learning of Partially Hidden Markov Models[J]. Data Mining and Knowledge Discovery, 2001, 15(2):102-107.

[5] VLACHOS A. Active Learning with Support Vector Machines[J]. Wiley Interdisciplinary Reviews Data Mining & Knowledge Discovery, 2004, 4(4):313-326.

[6] CAMPBELL C, CRISTIANINI N, SMOLA A. A Query learning with large margin classifiers[C]//DAN R.17th International Conference On Machine Learning (ICML). CA: JMLR, 2000:111-118.

[7] SEUNG H S, OPPER M. Query by Committee[J]. Acm conference on Computational Learning Theory, 1992, 28(4):287-294.

[8] ABE N, MAMITSUKA H. Query Learning Strategies Using Boosting and Bagging [C]//JUDE W. Fifteenth International Conference on Machine Learning. San Francisco: Morgan Kaufmann, 1998:1-9.

[9] MELVILLE P, MOONEY R J. Diverse ensembles for active learning[C]//DAN R, International Conference on Machine Learning.CA: JMLR, 2004:74.

[10] ROY N, MCCALLUM A. Toward Optimal Active Learning through Sampling Estimation of Error Reduction[C]// Richard N, Eighteenth International Conference on Machine Learning. San Francisco: Morgan Kaufmann, 2001:441-448.

[11] TONG S, KOLLER D. Active Learning for Parameter Estimation in Bayesian Networks[J]. Nips, 2001,1(1):647-653.

[12] LINDENBAUM M, MARKOVITCH S, RUSAKOV D. Selective Sampling for Nearest Neighbor Classifiers[J]. Machine Learning, 2004, 54(2):125-152.

[13] PAWLAK Z. Rough sets[J]. International Journal of Parallel Programming, 1982, 38(5):88-95.

[14] PAWLAK Z, SKOWRON A. Rudiments of rough sets[J]. Information Sciences, 2007, 177(1):3-27.

[15] PAWLAK Z, SKOWRON A. Rough sets: Some extensions[J]. Information Sciences, 2007, 177(1):28-40.

[16] PAWLAK Z, SKOWRON A. Rough sets and Boolean reasoning[J]. Information Sciences, 2007, 177(1):41-73.

[17] 王国胤,苗夺谦,吴伟志,等.不确定信息的粗糙集表示和处理[J].重庆邮电大学学报:自然科学版, 2010, 22(5):541-544..

WANG Guoyin, MIAO Duoqian, WU Weizhi, et al. Uncertain knowledge representation and processingbased on rough set. rough set representation and processing of uncertain information[J].Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition,2010, 22(5):541-544.

[18] 李华雄,刘盾,周献中.决策粗糙集模型研究综述[J].重庆邮电大学学报：自然科学版，2010, 22(5):624-630.

LI Huaxiong,LIU Dun,ZHOU Xianzhong.A survey of rough set model[J]. Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition, 2010, 22(5):624-630.

[19] WANG R, CHEN D, KWONG S. Fuzzy-Rough-Set-Based Active Learning[J]. IEEE Transactions on Fuzzy Systems, 2014, 22(6):1699-1704.

[20] WANG R, KWONG S, CHEN D, et al. Fuzzy rough sets based uncertainty measuring for stream based active learning[J]. Machine Learning and Cybernetics(ICMLC), 2012, 1:282-288.

[21] HU Q, YU D, XIE Z. Neighborhood classifiers[J]. Expert systems with applications, 2008, 34(2): 866-876.

[22] LEWIS D D, CATLETT J. Heterogeneous Uncertainty Sampling for Supervised Learning[J]. Machine Learning Proceedings, 1994, 7(4):148-156.

[23] VLACHOS A. Active Learning with Support Vector Machines[J]. Wiley Interdisciplinary Reviews Data Mining and Knowledge Discovery,2004, 4(4):313-326.

[24] LIN T Y. Neighborhood Systems and Approximation in Relational Databases and Knowledge Bases[J]. Proceedings of International Symposium on Methodologies of Intelligent Systems, 1988, 12(5):132-155.

[25] HU Q, YU D, XIE Z. Neighborhood classifiers[J]. Expert Systems with Applications An International Journal, 2008, 34(2):866-876.

[26] STANFILL C. Toward memory-based reasoning[J]. Communications of the Acm, 1986, 29(12):1213-1228.

[27] MEILA M, JORDAN M I. Learning with Mixtures of Trees[J]. Journal of Machine Learning Research, 1999, 1(1):1-48.

[28] KAGGLE.Digit Recongnizer[EB/OL]. (2012-03-01)[2016-10-15].https://www.kaggle.com/c/digit-recognizer/data.

[29] TONG S, KOLLER D. Support vector machine active learning with applications to text classification[J]. Journal of Machine Learning Research, 2001, 2(1):45-66.

[30] DASGUPTA S, HSU D. Hierarchical sampling for active learning[C]// Daniel Hsu. International Conference on Machine Learning. Helsinki: Pattern Analysis, 2008:208-215.

[31] HUANG S J, JIN R, ZHOU Z H. Active Learning by Querying Informative and Representative Examples[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2014, 36(10):892-900.

s：The National Natural Science Fundation of China(61309014)；The Ministry of Education Humanities and Social Sciences Program(15XJA630003)；The Science and Technology Research Project of Chongqing Municipal Education Commission(KJ1500416)；The Chongqing Basic and Frontier Research Program(cstc2013jcyjA40063)

Algorithmforactivelearningbasedonneighborroughsettheory

HU Feng, ZHOU Yao,WANG Lei

Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, P. R. China)

Active learning is one of the major research directions of machine learning. Most active learning approaches select uncertain or representative unlabeled samples to query their labels, and then add them into labeled data sets for classifier learning. However, these approaches have not fully utilized data distribution information, and not processed outlier acquisition problem well enough, too. With neighbor rough set theory, an algorithm named NRS-AL is proposed. The experiment results have shown that in UCI data set, combined with uncertainty and representative calculation of samples, the proposed algorithm in this paper has solved the previous problems, and is effective in solving sample choosing problems in active learning, which shows better accuracy and AUC performances than others in the literatures.

neighborhood rough set; active learning; pool-based sample selection

10.3979/j.issn.1673-825X.2017.06.011

2016-11-10

2017-09-15

周耀 384375530@qq.com

国家自然科学基金(61309014)；教育部人文社科规划项目(15XJA630003)；重庆市教委科学技术研究项目(KJ1500416)；重庆市基础与前沿研究计划项目(cstc2013jcyjA40063)

TP183

1673-825X(2017)06-0776-09