一种基于IB方法的二分类算法

第 24卷第 4期2013年 8月中原工 学院学报J0URNAL OF ZH0NGYUAN UNIVERSITY OF TECHN0LOGYVo1．24 NO．4Agu．，2013文章编号 ：1671—6906(2013)04—0001—04一 种基于 IB方法的二分类算法杨 晨 ，叶阳东(郑州大学 信息工程学院，郑州 450052)摘 要： 二分类数据中，某些训练样本因其隐私性往往较难获取，致使训练集规模较小，因此分类算法无法学习到较好的数据模式．针对上 述问题 ，本文利用 IB方法 (Information Bottleneck)并结合 该问题特 有 的性 质 ，提 出一种新 的基 于单类的二分类算法——Bc0c～IB算法．该算法的学习阶段使用单类 IB算法学习数据模式 ，分类阶段使用二分类策略对测试数据进行分类．实验结果表明，当训练样本较少的情况下，BCOC-IB算法的分类精度高于对比算法，且时间复杂度较低.

关 键 词： IB方法；单类；二分类；训练样本中图分类号 ： TH124 文献标志码 ： A D0I：10．3969／J．issn．1671—6906．2013．04．001IB 方 法 (Information Bottleneck Method)是Tishby N等人于 1999年提出的一种基于率失真理论的数据分析方法[】 ]．该方法在对数据分析时，将数据对象到“瓶颈”变量 的压缩编码视为 IB方法提取的数据模式．IB方法在模式提取时，力图最大化保存数据中的原有信息，从而使所提取的数据模式可更好地揭示数据中固有的内在结构．IB方法已在众多领域中得到有效的应用，其中包括文本分类_3]、图像聚类 ]、离群点检测[ ]和单类[ ]等.

二分类问题中，某些数据集本身难获取，导致训练样本较少，影响分类算法精度．垃圾邮件(spam)数据集中，因其公开性和易得性，往往很容易获得，而正常邮件(ham)一般都是私人之间的信件，其内容可能牵扯到个人隐私和商业机密等，往往较难获得．若使用分类方法学习数据模式，往往会出现训练样本较少的问题.

一 般来说，对该问题的处理往往使用单类模型[6]和二分类模型Ⅲ7]．单类模型仅采用充足的一类数据参与学习过程 ，使用充足的这类数据模式分类测试数据.

然而，由于已得数据模式并没有学习另一类数据特征，致使最终的分类精度较低．二分类模型则使用两类数据同时加入训练，最终对测试数据进行分类，较为常见的方法有贝叶斯方法[7 和支持向量机方法[7]等．单类模型由于仅有一类训练数据 ，因此学习精度不高 ，而一般的二分类方法并未充分考虑训练数据较少这一问题 ，因此其泛化能力差 ，分类精度较低.

针对上述问题，本文提出一种基于单类的二分类模型(Binary Classification Based on One Class)及对应的 IB算法 BCOC—IB算法．单类 IB算法可在数据集 中搜索到高精度子簇 ，子簇 内的数据对象与原数据集高度相关，因此使用该子簇学习到的数据模式具备高相关的模式结构．本文利用单类 IB算法的这一性质分别采用两类数据训练集中学习模式结构，以期得到强相关数据模式．在分类过程中，本文使用学习过程中得到的两类数据模式对测试数据进行分类，其中以具有充足采样的数据模式为主要分类，以采样不充分的数据模式为辅．由于分别结合了单类在学习过程的优势和二分类在分类过程 的优势 ，因此当训练数据较少时，BCOC～IB算法在 4个垃圾邮件数据集上 F1指标优于 SVM.

本文思路如下 ：(1)提出一种基于单类的二分类模型，该模型使用收 稿 日期 ：2013—05—30基 金项 目：国家 自然科学基金项 目(61170223)作者简介：杨 晨(1987一)，男，河南平顶山人 ，硕士生，研究方向为机器学习.

中原工学院学报 2013年 第 24卷单类算法分别学习两类数据模式，并使用二分类思想对测试数据进行分类 ；(2)提出一种基于单类的二分类 IB算法 BCOC-IB算法，该算法具有较低的时间复杂度 ，且能得到 目标函数的局部最优解.

1 IB方法及单类 IBIB方法 的基本 思想为 ：在源变量 x和描述 X 模式结构的相关变量y所构成的联合分布P(X，y)已知的情 况下 ，IB方 法试 图找到源 变量 X 的最 优表 示P(T}X)，使得“瓶颈”变量 T能够最大化保存相关变量 y的模式信息．IB模式提取的过程等价于对数据 的划分，因此 丁可视为簇的集合.

F?(P(t l z))一I(X；T)～pi(T；y) (1)其中， ∈[o，。。]，是拉格朗日因子，用于平衡信息源的压缩和相关信息的保存.

文献[6]中提出的单类 IB算法 OCRD-BA算法的主要思想 为 ：数据对 象 oZ" E { ，．z。，?，z )，O一{王 ，-； ，?，主 }为单类集合，且 oC{z ，z ，?，z }，若z EO则失真为d(z l o)，否则 32 E 失真为 0．单类目标函数为：F?(P(0 l z))一 min I(T；X)+( (ol ))卢∑P(z) (o l x)d(x l )(2)2 基于单类的二分类算法基于单类的二分类模型提出BCOC-IB算法，算法描述见表 1.

表 1 BCOC-IB算法Input：train
～
S，train
～
H ，￡ezf一{217l，z2，? ，z }Output：test类标号 test—labelsInitialization：~，W CRD— BA(train
— S ，段)；Wh一0CRD— BA(train
—
H ， )；For i-_1； ≤m；i++If D KJ_(z lI W )≤DKL(z l W )test labels[-／]=1；end算法首先输入训练使用的两类数据集和测试数据集，并分别给 出训练所需参数 和 ，然后运行OCRD— BA 算 法 分别 求 出 train—S的 质心 W 和train
—
H的质心 W ，根据测试数据和两质心 的 KL距离来判定其归属 .

3 实 验3．1 数据集本实验使用表 2中 4个邮件数据集进行实验，其中Ling—spare数据集为邮件列表数据集，trec07p为数据量大的邮件数据集，spambase为 UCI邮件数据集，PU3为加密邮件数据集．对 Ling—spam 和 trec07p进行如下预处理 ：(1)删除附件、邮件头 、标记和图片，只留下邮件主题和正文 ；(2)将所有大写字母变为小写；(3)将所有数字用“digit”标签表示；(4)忽略非字母 、非数字的字符；(5)删除所有的停止词以及仅出现小于 3次的单词；(6)使用信息增益保留贡献最大的前 2 000个单词作为特征值.

由于 PU3是加密邮件数据集，只进行(5)、(6)步操作 ，而 spambase是 UCI中处理过的数据集 ，不进行预处理操作，且其特征值维度为 58.

表 2 数据集上述 4个数据集 在垃圾邮件过滤领域都使用较多，如 Androutsopoulos使用朴素 贝叶斯分类器 7¨ 时使用了 Ling—spare和 PU3数据集 ，Sculey在文献E8]中使用了 trec07p和 spambase数据集.

3．2 对比实验为了验证本文的方法对于训练集较少时垃圾邮件过滤的有效性，以 SVM 作为对比算法．SVM 使用libsvm库 中的C—SVC算法和 RBF核函数 ，参数采用十字交叉选取的最优参数 ，数据 向量进行归一化操0 D D 作．使用 F (F 一 l~q
-
P，其中R为召回率，P为精度)第 4期 杨 晨，等：一种基于 IB方法的二分类算法度量作为分类精度．实验中依次增加训练数据的个数，分别运行 1O次本文方法 和 SVM 求实验结果 的平均值 ，直到 90 的数据参 与训 练为止，最小训练集个数选为 100．由于 trec07p数据集规模较大 ，最小训练集个数选为 500．为了凸显本文算法的优势 ，训练集的增幅在开始时比较小，随着训练集规模增大，增幅也呈跳跃性变化.

图 1给出了 BCOC-IB算法和 SVM 在 4个数据集不同训练数据规模下 F 指标 的大小 ，其 中坐标 系中的横坐标表示训练集规模 ，最后一个刻度为数据集总规模 ，倒数第二个刻度表示 90 的数据参与训练时1∞ 200 30o 500 700l000 20Oo260o 2893训练数据个数l00 20o 350 500 700 1000 2000 3000 4C00 4610训练数据个数训练集规模 ，纵坐标为两算法 的 F 指标．从 图 1可 以看出，当训练集规模很小时，BCOC—IB算法在 F 指标上优于 SVM，随着训练数据集规模 的增加 ，两算法性能相当．在训练数据增加的整个过程中本文 的方法较 SVM 更为稳定 ，这种情况在 spambase数据集上表现的非常明显．因为 spambase数据集 的特征词过少 ，SVM在整个实验过程中分类精度抖动很大．为了提高分类精度，SVM 要求数据向量进行归一化操作，而BCOC-IB算法并无此要求．归一化操作在处理大数据集(例如trec07p)时非常慢，因此本方法在整体的运行时问上 比 SVM 要短.

(b)图 1 BCOC—IB与 SVM 对 比结果通 过 上述 实验 结果 可 知，当训 练 样本 较 少 时，BCOC-IB算法的分类能力要优于 SVM 算法 ，这是因为 BCOC-IB算 法在小训练样本下学 习到 的模 型泛化能力更强．随着训练数据集规模的增大，更多的训练数据不能为 BCOC-IB算法提供更多有用信息，导l0o 200 300 50o 80o 10001500 2000 3000 3700 4139训练数据个数(d)致 F 度 量增 长趋 于平 缓，而更 多 的训 练数 据可 为SVM算法提供更多的支持向量，因此学习到的模式特征更有利于得到高精度的分类结果．综上所述 ，本文提出的 BCOC-IB算法性能稳定，且在训练数据较少情况下优于 SVM 算法.

0 O O O 0 0 0 0 0 0 0 0 0 0 0 0 · 4 · 中原工学院学报 2013年 第 24卷4 结 语当训练数据集较少时，单类过滤模型和二分类模型的精度较低．针对该问题 ，本文提出一种基于单类的二分类过滤模型及优化算法 BCOC-IB算法．基于单参考文献 ：类的二分类模型利用单类 IB算法优势可在训练数据较少的情况下提取强相关数据模式，且使用二分思想能保证分类过程的性能．BCOC-IB算法可快速收敛 ，且时间复杂度较低．通过实验表明，在训练数据集较少的情况下 ，BCOC-IB算法性能优于 SVM 算法.

Eli Tishhy N，Pereira F，Bialek W．The Information Bottleneck Method[c]／／Proceedings of the 37th Alerton Conference onCommunication，Control and Computing．Monticelo，USA，1999：368— 377.

E2]E3]E4][5]E6]E7]E8][9]Slonim N．The Information Bottleneck：Theory and Application[D]．Jerusalem：The Hebrew University of Jerusalem，2002.

Slonim N，Friedman N，Tishby N．Unsupervised Document Classification Using Sequential Information Maximization[C]／／Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieva1.

ACM ，2002：129— 136.

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.

Ando S．Clustering Needles in a Haystack：An Information Theoretic Analysis of Minority and Outlier Detection[c]／／Pro—ceedings of the 7th International Conference on Data Mining．Omaha，USA，2007：13— 22.

Crammer K，Talukdar P P，Pereira F．A Rate—Distortion One-class Mode1 and Its Applications to clustering[c]／／Proceedingsof the 25th International Conference on Machine Learning．Helsinki：ACM ，2008：184 191.

Androuts0poulos I，Koutsias L，Chandrinos K V，et a1．An Evaluation of Naive Bayesian Anti—spam Filtering[C]／／Proceedings of the Workshop on Machine Learning in the New Information Age，1 l th European Conference on Machine Learning．Bar—celona，Spain：ACM ，2000：9— 17.

Sculey D，Wachman G M．Relaxed Online SVMs for Spam Filtering[c]／／Proceedings of the 30th Annual International ACMSIGIR Conference on Research and Development in Information Retrieva1．Switzerland：ACM ，2007：415— 422.

Chang C C，Lin C J．Libsvm：A Library for Support Vector Machines[J]．ACM Transactions on Intelligent Systems and Technology，2011，2(3)：27— 30.

A Binary Classification Algorithm Based on IB M ethodYANG Chen，YE Yang—dong(Zhengzhou University，Zhengzhou 450052，China)Abstract： In two—category data，the privacy of train samples leads to difficult extraction，so the scale oftrain data is small and the classification algorithm can’t learn good data pattern．As to this problem ，this papercombines IB method with the features of the problem ，and proposes a new binary classification algorithm basedon one—class information bottleneck—BCOC—IB．In learning phase of this algorithm，one—class algorithm for datapattern is used；in classification phase，dichotomy strategy is used to classify the test data．Experimental re—suits show that：when training samples become less，BCOC—IB algorithm is more outstanding than comparisonalgorithms，and the time complexity is 1ower than comparison algorithms.

Key words： 1B method；one—class；binary classification；train samples