噪声消除与SMO算法收敛性

噪声消　除与ＳＭＯ算法收敛性　何建兵　何清ｚ史忠植ｚ　（中国科学院研究生院软件学院，北京１０００４９）　（中科院计算技术研究所智能信息处理重点实验室，北京１０００８０）　Ｅ－ｍａｉｌ：ｈｊｂ—ｒｌｈ＠ｓｏｈｕ．ｃｏｍ　摘要近年来，随着序列最小优化分类算法ＳＭＯ等一系列快速算法的推出，支持向量机在自动文本分类研究领域取　得了很大的成功。大多数文本分类问题是线性可分的．使用线性核函数的ＳＭＯ算法能够取得非常好的分类效果。但是文　本向量是一种非常稀疏的向量。采用线性核函数的ＳＭＯ算法对噪声样本非常敏感．容易产生发散的问题。文章分析证明　了噪声如何影响ＳＭＯ算法收敛性。为了解决训练样本中噪声样本影响ＳＭＯ算法收敛的问题，设计了一个消除噪声样本　的算法．取得了非常好的效果。　关键词　文本分类　支持向量机ＳＭ０算法　噪声样本　文章编号１００２—８３３１一（２００６）２４—０１６０—０４　文献标识码Ａ　中图分类号１］Ｐ３０１．６　Ｅｌｉｍｉｎａｔｉｎｇ　Ｎｏｉｓｙ　ａｎｄ　ＳＭＯ　Ａｌｇｏｒｉｔｈｍ　Ｃｏｎｖｅｒｇｅｎｃｅ　Ｈｅ　Ｊｉａｎｂｉｎｇ　Ｈｅ　Ｑｉｎｇ２　Ｓｈｉ　Ｚｈｏｎｇｚｈｉ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｇｒａｄｕａｔｅ　Ｓｃｈｏｏｌ　ｏｆ　ｔｈｅ　Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，　Ｂｅｉｌｉｎｇ　ｌ００Ｏ４９　１　（Ｔｈｅ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ，Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ，　Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１０００８０）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｒｅｃｅｎｔ　ｙｅａｒｓ，ａｃｃｏｍｐａｎｙ　ｗｉｔｈ　ｔｈｅ　ａｐｐｅａｒａｎｃｅ　ｏｆ　ａ　ｓｅｒｉｅｓ　ｏｆ　ｒａｐｉｄ　ｔｒａｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ａｓ　Ｓｅｑｕｅｎｔｉａｌ　Ｍｉｎｉｍａｌ　Ｏｐｔｉｍｉｚａｔｉｏｎ（ＳＭＯ），ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅｓ　ａｃｈｉｅｖｅｄ　ｇｒｅａｔ　ｓｕｃｃｅｓｓ　ｉｎ　ｔｅｘｔ　ｃａｔｅｇｏｒｉｚａｔｉｏｎ．Ｍｏｓｔ　ｔｅｘｔ　ｃａｔｅｇｏｒｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ　ａｒｅ　ｌｉｎｅａｒｌｙ　ｓｅｐａｒａｂｌｅ，ａｎｄ　ＳＭＯ　ａｌｇｏｒｉｔｈｍ　ｕｓｉｎｇ　ｌｉｎｅａｒ　ｋｅｒｎｅｌ－ｉｎｄｕｃｅｄ　ｃａｎ　ｐｅｒｆｏｒｍ　ｗｅｌｌ　ｆｏｒ　ｔｅｘｔ　ｃａｔｅｇｏｒｉｚａｔｉｏｎ．　Ｈｏｗｅｖｅｒ，ｔｅｘｔ　ｖｅｃｔｏｒｓ　ａｒｅ　ａ　ｋｉｎｄ　ｏｆ　ｅｘｔｒｅｍｅｌｙ　ｓｐａｒｓｅ　ｖｅｃｔｏｒ，ａｎｄ　ＳＭＯ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｌｉｎｅａｒ　ｋｅｒｎｅｌ　ｏｒ　ｐｏｌｙｎｏｍｉｌ　ｋｅｒａｎｅｌ　ｉｓ　ｖｅｒｙ　ｓｅｎｓｉｔｉｖｅ　ｔｏ　ｔｈｅ　ｅｘｔｒｅｍｅｌｙ　ｓｐａｒｓｅ　ｎｏｉｓｙ　ｅｘａｍｐｌｅ，ｗｈｉｃｈ　ｉｓ　ｅａｓｙ　ｔｏ　ｂｒｉｎｇ　ｏｎ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｔｈａｔ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｎｏｔ　ｃｏｎｖｅｒｇｅ．Ｉｔ　ｉｓ　ｂｅｅｎ　ｐｒｏｖｅｄ　ｔｈａｔ　ｔｈｅ　ｎｏｉｓｙ　ｅｘａｍｐｌｅ　ｈｏｗ　ｔｏ　ｉｎｆｌｕｅｎｃｅ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｏｆ　ＳＭＯ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｔｈｅ　ｐａｐｅｒ．Ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｔｈａｔ　ｎｏｉｓｙ　ｓａｍｐｌｅ　ｉｎ　ｔｒａｉｎｉｎｇ　ｓａｍｐｌｅｓ　ａｆｆｅｃｔ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｏｆ　ＳＭＯ　ａｌｇｏｒｉｔｈｍ，ｔｈｉｓ　ｐａｐｅｒ　ｄｅｓｉｇｎｓ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｔｈａｔ　ｃａｎ　ｅｌｉｍｉｎａｔｅ　ｎｏｉｓｙ　ｓａｍｐｌｅｓ，ａｎｄ　ｇｏｏｄ　ｒｅｓｕｌｔｓ　ｉｓ　ａｃｈｉｅｖｅｄ．　Ｋｅｙｗｏｒｄｓ：ｔｅｘｔ　ｃａｔｅｇｏｒｉｚａｔｉｏｎ，ＳＶＭ，ＳＭＯ　ａｌｇｏｒｉｔｈｍ，ｎｏｉｓｙ　ｓａｍｐｌｅ　ｌ　引言　文本分类通常采用向量空间模型将文本表示成空间中的　向量，向量空间的维数为词的总数．每维对应一个词。一般文本　向量的维数很高（大于１０　０００），相对而言，学习样本就显得不　足。传统的分类算法在文本特征项的数目比训练数目大时．可　能会出现在高维空间泛化能力差的情况…。由于支持向量机　（ＳＶＭ）算法解决的是一个凸优化问题，局部最优解一定是全局　最优解，这种高维小样本的情况很适合采用ＳＶＭ技术【１】。近年　来．随着ＳＭＯ等一系列快速算法的推出，ＳＶＭ在自动文本分　类研究领域取得了很大的成功。　因，在第四节中提出了消除噪声样本的算法，取得了很好的效　果。　２支持向量机　２．１最大间隔分类器　支持向量机中最早提出的模型是最大间隔分类器，由　Ｂｏｓｅｒ，Ｇｕｙｏｎ和Ｖａｐｎｉｋ发明［３１。假设有，个样本训练点（　１，Ｙ１），　（Ｘ２，Ｙ２），…，（轨，Ｙ，）ＥＲ　×｛±１｝，学习得到线性分类超平面：Ｗ・　＋　ｂ＝Ｏ，将样本分成两类：ｙｉ（ｗ・　＋６）＞０和ｙｉ（　・　６）＜０。　显然，超平面中的Ｗ和ｂ乘以系数后仍能满足方程，不失　一大多数文本分类问题是线性可分的　，使用线性核函数的　ＳＭＯ（Ｓｅｑｕｅｎｔｉａｌ　Ｍｉｎｉｍａｌ　Ｏｐｔｉｍｉｚａｔｉｏｎ）算法能够取得非常好的　分类效果。但是文本向量是一种极度稀疏的向量．向量中很多　维的权值用０表示．采用线性核和多项式核的ＳＭＯ算法对这　样的噪声样本非常敏感．容易产生不能收敛的问题。本文第三　节通过推导解释了ＳＭ０算法为什么对噪声样本非常敏感的原　般性．对于所有的样本．适当调整Ｗ和ｂ，使１　・ｘ＋ｂＩ的最小值　为１。经过归一化处理得到：ｙｉ（　・　『卜６）≥１。因。此，两类样本到超　平面最小距离之和为＿厂（　）＝　１　ｌ　ｌＷ　ｌ　ｌ２０如果两类到该超平面的　二　间隔最大，则该超平面为最优超平面。通过优化函数ｆ（ｗ），求　解最优超平面：　基金项目：国家自然科学基金资助项目（编号：６０４３５０１０）；国家８６３高技术研究发展计划资助项目（编号：２００３ＡＡ１１５２２０）；中澳科技合作特别基金　项目；北京市自然科学基金资助项目（编号：４０５２０２５）　１６０　２００６．２４计算机工程与应用　维普资讯 http://www.cqvip.com

Ｍｉｎ　ｉｍｉｓ。　１　．ｏｌｄ　ｏｌｄ　ｎ删　ｎｅｌｏ　ａ１＋ｓａ２　＋ｓａ２＝ｒ　ｏ，，（７）　，　０　二　Ｓｕｂｊｅｃｔ　ｔｏ　ｙｉ（ｗ・ｘｉ＋ｂ）≥１（１≤ｉ≤　考虑到可能存在一些样本不能被超平面严格地正确分类。　其中ｓ＝ｙ　，ｒ为常数，Ⅱｏｌ　ｄⅡｌｄ为　Ｏｔ２变化前的值，Ⅱｎｅ　”：Ⅱ２ｎｅｗ为变化后的值。将（７）代入（４）并优化目标函数可以得到：　—　Ｙ２（Ｅ２一Ｅ１）　Ⅱ２＝ａ２　—　（８）　１９９５年Ｃｏｎｅｓ和Ｖａｐｎｉｋｔ４１￣ｌ入了ＳＶＭ的软间隔版本，使用松　弛变量喜≥０，使点　满足Ｙｌ（　・　＋６）≥１　条件。这样原函数　，　变成　）＝—　１　ｌｌ　ｌ：＋ｃ∑　，其中Ｃ是一个正常数，函数中第　厶　＝１　一其中，ｋ＝２ＫｌｒＫｌ厂如，Ｅ１　１）一Ｙ１，Ｅ２＝ｆ（ｘ：）－ｙ２。求得Ⅱ２ｎｅｗ的　项使样本到超平面的距离尽量大，从而提高泛化能力，第２　值后，由（７）求解Ⅱ＿　。　项则使误差尽量小。原优化问题变为：　Ｍｉｎｉｍｉｓｅ　１０　　ｌ　ｌＷ　ｌｌ　＋ｃ　１．１　・口　ｉ＝１　Ｓｕｂｊｅｃｔ　ｔｏ　ｙｉ（ｗ・　６）≥１　，基≥０（１≤ｉ≤　（１）　利用拉格朗日乘子法．得到拉格朗日函数：　，　，Ｊ（Ｗ　ｙｂ，　ｒ）：　１　ｃ∑　二　Ｅ＝１　，　，　∑　Ｊｊ，　（　＋６）一１　卜∑ｒ春　（２）　１　ｉ＝１　，　，　分别对Ｗ，ｂ，毒求偏导置零得：　＝　Ｏ１．１　ｔｆＹ　，　１．１　Ｏｔ　ｙ￣－－Ｏ，ｃ—　广　＝１　ｉ：１　ｒｉ－０。代入（２）式中，得到拉格朗日函数的对偶目标函数：　，　，　Ｌ　∑　广　∑　ｉＹｉＯｔｊＹｊ（　）　（３）　１　厶ｉ．ｊ＝ｌ　设Ｗ是原函数的一个可行解，是Ｏｔ目标函数的一个可行　解，根据上面的推导可知　（　）≤，Ｊ（　，ｂ，　，Ｏｔ，ｒ）≤＿厂（　），即对偶　问题的值的上界由原问题的值给出。而原函数和目标函数都是　凸二次函数，在鞍点处有Ｌ。（　）＿厂（　）。所以，原函数的优化问题　变成目标函数的优化问题：　，　，　Ｍａｘｍｉｓｅ　Ｌ　∑　广　∑　ｙｉＯＺｆｊ（Ｘｉ＂　）　“　Ｉ＝Ｉ　ｉ．，　Ｉ　Ｓｕｂｊｅｃｔ　ｔｏ∑ＯｔｉＹｉ＝０，０≤　≤ｃ（１≤　≤　（４）　ｌ　目标函数的最优解必须满足ＫＫＴｔ￣互补条件：　，　Ｏｔｉ　（∑嘞（　・规）＋６）一１　Ｊ＝０　ｌ　ｆ＝０，ｉ＝１，…，　（５）　根据该条件，仅仅最靠近超平面的点对应的Ｏｔ　非０。而在　超平面的权重Ｗ表达式中，只有Ｏｔ　非０的点才包括在内，因此　这些点被称为支持向量。通过优化目标函数，寻找支持向量，从　而训练得到一个ＳＶＭ的分类规则函数：　，　）＝ｓｇｎ（∑Ｏｔｉｙ　（规．　）＋６）　（６）　＝ｌ　２．２　ＳＭ０算法　ＳＭＯ优化（４）时使用了块与分解技术，并将分解算法思想　推向极致，每次迭代仅优化两个点的最小子集，其威力在于两　个数据点的优化问题可以获得解析解，从而不需要将二次规划　优化算法作为算法一部分。尽管需要更多的迭代才收敛，但每　个迭代需要很少的操作，因此算法在整体速度上有数量级的提　，　高。不失一般性优化　。，　：，其他Ｏｔｉ固定，由线性约束条件∑Ｏｔ　ｉ＝１　ｙｉ＝Ｏ可知：　ＳＭＯ算法从初始值为０的Ｏｔ　开始优化（４），相应地巨的　初始值为Ｙ　。每次变更后Ｏｔ１，Ｏｔ２要对Ｅ　进行修改，Ｅ　（　）　＝　，　１Ｋ１ｆ＋　＋　ａｙｊ（ｘ　，　）＋６－ｙ　，假设偏置ｂ保持不变，则Ｅ　，＝３　的变化量为：　ＡＥｆ＝Ａａ￣ｒ１Ｋ１，＋Ａａｚｙ￣　（９）　ＳＭＯ每次迭代时，从训练集中启发式地选择最可能违反　ＫＫＴ条件的两点进行优化，加快算法的收敛速度。根据拉格朗　日乘子取值范围（０≤　≤Ｃ）分析ＫＫＴ条件，当Ｏｔ　＜Ｃ时，ｙ五≥　０；Ｏｔ　＞０时，，，　ｆ≤０。因此，最可能违反ＫＫＴ条件的点是：当　ｌ＜Ｃ　时，ｙ五为最小的点；当Ｏｔ　＞０时，ｙ　为最大的点　所以ＳＭＯ算　法根据当前点的Ｅ　启发式地选择优化的两点。　３　噪声样本影响ＳＭＯ算法收敛的原因　噪声样本是指向量相同或相似（相似度达９０％以上），而分　类标签相反的训练样本。如果ＳＭＯ通过启发式选择算法选择　了两对相互矛盾的两点，由于文本向量是极度稀疏的向量，大　量的属性权值以０表示。在计算噪声样本的线性核函数或多项　式核函数时．个别有差异的属性权值乘以其他向量的属性权　值，而其他向量在这个属性的权值为０的概率：　常大，就可能　会得到相同核函数的结果。其Ｅ在迭代时出现反复振荡，导致　ＳＭＯ算法在两对相互矛盾的两点上反复迭代，无法收敛，这也　说明ＳＭＯ算法对这样的噪声是非常敏感的。因此，在训练前应　该设法消除这样的样本向量。下面的推导进一步说明了噪声样　本导致ＳＭ０算法无法收敛的原因。　假设训练集中存在两对相互矛盾的向量Ｓ。，Ｓ：，Ｓ３，Ｓ　，其中　。，　是一对噪声样本，　：，　是另一对噪声样本。为简化推导，　只考虑向量相同，而分类标签相反的情况。不妨设　。，　３相同，　２，　相同，且ｙｌ＝１，ｙ２＝一１，ｙ３＝一１，ｙ４＝１。假设在对　ｌ，　２，　３，　４向　量优化之前，　。，　：，　３，　向量的Ｅ　分别为Ｅ。，Ｅ　，Ｅ３，Ｅ　。训练活　动集经过一定次数迭代后，如果ＳＭＯ算法第一次启发式地选　择了　。，　：两点，对它们进行优化。根据（８），Ｏｔｔ，Ｏｔ：本次迭代的　变化量分别为：　△　兰　（１０）　△　，：　兰！　（１１）　ｋ　根据（９），Ｅ。，Ｅ：，　，臣本次迭代的变化量分别为：　△巨＝△　ｌｙ１Ｋ１ｌ＋Ａ　　ｌ—（Ｅ￣－Ｅ２）　（ＫＨ－Ｋ１２）　（１２）　—ＡＥｚ＝Ａ　肌Ｋ１２＋Ａ　：　１二２　（１３）　３＝Ａａ￣ｙ，Ｋ１３－１－ｍ　ｚｙ￣２３：—（Ｅ，－Ｅ２）（ＫＩ３－Ｋ２３）　（１４）　—－—／ｌ：　计算机工程与应用２０ｏ６．２４　１６１　维普资讯 http://www.cqvip.com

ＡＥ　△　１　１４＋△　２Ｋ　＝—（Ｅｌ－Ｅ２（Ｋ１４－Ｋ￣）　（１５）　———）一了这里ｋ＝２Ｋ　－Ｋ　１－Ｋ　。由于Ｓ１，Ｓ３是相同的向量；　，　是相　同的向量，则Ｋ１３＝　ｌｌ’Ｋ∞＝　１２；　１４＝　ｌ２’　２４＝　。所以ＡＧ＝ＡＥ１，　Ｅ　Ｅ　然后ＳＭＯ算法启发式地选择　，，　两点，对它们进行优　化。根据（８），　，　本次迭代的变化量分别为：　…　２Ｋ３　４－Ｋ　３３一　“　２Ｋｓ４－Ｋ３３－Ｋ４４　．　Ｅ　坷　＋（１３）一（１２）　Ｅ４坷３幅，坷２　衄　—～’　２Ｋ３４－Ｋ—３３－Ｋ４４　—２Ｋ３４－Ｋ　３３一　Ｋ４４　同样道理，　３４＝　ｌ２，Ｋ３３＝　ｌｌ，Ｋ４：Ｋ　；而且，Ｓｌ’Ｓ２，Ｓ３，Ｓ４向量　在第一次优化之前，ｙｌＥ１＝　３，ｙ２Ｅ２＝ｙ，Ｅ４。所以　３，　４本次迭代的　变化量可分别表示为：　Ａａ３＝２ｙ３　—　喜　（１６）　Ａｏｔ４－２　里喜　（１７）　同样根据（９），Ｅ。，Ｅ　，Ｅ，，Ｅ４本次迭代的变化量分别为：　衄１＝△　３＋△　４＝　学　［　（１８）　衄　△　２４＝　（１９）　△　３＝△　３３＋△　—　３４＝△　Ｉ　ＡＥ４＝Ａｏｔ３ｙｆｌ（￣＋Ａａ４ｙ４Ｋ４４＝ＡＥ２　经过两次迭代之后，Ｅ　，Ｅ２，Ｅ３，Ｅ４的变化量分别为：　衄１＝（１２）＋（１８）：　！　！　！　（２０）　衄　（１３）＋（１９）：　！　二　（２１）　衄　衄１，衄４＝衄　紧接下来．ＳＭＯ又启发式地选择Ｓ　，Ｓ　两点进行优化，同　理可推导出　。。　，本次迭代的变化量分别为：　Ａｏｑ＝２ｙ１—Ｅ　｜－Ｅ２　（２２）　Ａｏ￣２＝２ｙ２里粤　（２３）　Ｅ　，Ｅ２，Ｅ，，Ｅ４本次迭代的变化量分别为：　衄　２　！　（２４）　后　衄，＝２　１皇　！　！　二　望　（２５）　后　衄　衄．．衄ｄ＝衄，　经过三次迭代之后，　，　２，Ｅ　，Ｅ２，Ｅ３，Ｅ４的变化量分别为：　Ａｏｈ＝（１０）＋（２２）＝３　丁ＥｌｓＥ２　（２６）　ＡＯ￣２＝（１１）＋（２３）＝３ｙ２—　Ｅ，一Ｅ　（２７）　衄ｌ＝（２０）＋（２４）：！皇　二　．和（１２）相同　衄　（２１）＋（２５）：　丝　，和（１３）相同　ＡＥ３＝ＡＥｌ，△　＝ＡＥ２　１６２　２０ｏ６．２４计算机工程与应用　然后再启发式地选择Ｓ，，Ｓ　两点，对它们进行优化。经过四　次迭代之后，　３，　，Ｅ１，Ｅ　，Ｅ３，Ｅ４的变化量分别为：　＝　，△　学　２０）相同　ＡＥ，＝！　丝　．ｋ　和（２１）相同　ＡＥ３＝ＡＥｌ，△　４＝△　２　依此类推，每迭代两次，　，　的拉格朗日乘子　，　的系　数按２ｎ一１（ｎ＞０）顺序增加，　，，　的拉格朗日乘子　，　的系数　按２ｎ（ｎ＞０）顺序增加。而噪声样本　，　３的Ｅ　（　１，３）在（１２）和　（２０）式之间反复振荡；　，　的Ｅ　（　２，４）在（１３）和（２１）式之间　反复振荡。从而导致ＳＭＯ算法在两对相互矛盾的两点上反复　迭代．无法收敛。　４消除噪声样本算法　为消除训练样本中可能存在的噪声样本，遍历训练样本文　件中所有向量．比较分析正负样本向量的相似度，如果相似度　大于或等于９０％。我们认为正负样本向量对是相互矛盾的。相　似度计算公式如下：　Ｍａｘ（面正向量非零属性数．　鬻　负向量非零属性数）　‘、　２８　设训练样本数为　，算法执行的步骤描述如下：　步骤１按１到　哽序从训练样本集中取一个样本Ｓ　如果　取完样本集所有样本．则算法结束。　步骤２按ｉ＋１到　顺序取训练样本集中另一个样本Ｓ　如　果取完样本。则转步骤１。　步骤３比较Ｓ　和Ｓ，的类标。如果Ｙｉ和　相同，Ｓ　和Ｓ不　可能是相互矛盾的向量，转步骤２。　步骤４根据公式（２８）计算Ｓ　和Ｓ，的相似度。如果Ｓ　和ｓ｜　的相似度大于或等于９０％，则Ｓ　和Ｓ，是相互矛盾的向量，从训　练集中去掉Ｓ　和Ｓ　转步骤１；否则，转步骤２。　５实验结果　本文实验系统训练使用了１３个训练集样本文件：从文件　Ｓ１．ｔｍ到文件Ｓ１３．ｔｍ，训练１３个分类，每类对应一个超平面。　在采用线性核和多项式核执行ＳＭ０算法训练时．发现训练文　件Ｓ１．ｔｍ．Ｓ３．ｔｍ．Ｓ８．ｔｍ无法收敛。分析发现这三个训练文件中　表１　消除噪声样本数统计　维普资讯 http://www.cqvip.com

存在比较多的噪声样本，即相同（或相似）的两个向量的类标相　反。对Ｓ１，Ｓ３和Ｓ８文件进行除噪声处理后，训练收敛了，并得　到了模型文件。我们继续对其他文件也进行了训练前的除噪声　优化算法计算线性核或多项式核时，相互矛盾的向量的核函数　计算结果非常容易一致．当训练集中噪声样本比较多时，容易　引发ＳＭＯ训练算法不能收敛．出现收敛前振荡　使用本文提供　处理，发现这些文件也或多或少的存在相互矛盾的向量．结果　如表ｌ所示。随后我们又使用了９８４个测试数据，对训练得到　的预处理算法能够消除训练集中的噪声样本，很好地解决　ＳＭ０对训练集中噪声样本敏感的问题。　（收稿日期：２００６年３月）　的分类器进行了测试，相应测试准确率见表２。　表２　基于ＳＭ０的文本分类测试结果表　参考文献　１．Ｔｈｏｒｓｔｅｎ　Ｊｏａｃｈｉｍｓ．Ｔｅｘｔ　Ｃａｔｅｇｏｒｉｚａｔｉｏｎ　ｗｉｔｈ　Ｓｕｐｐｏｒｔ’Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅｓ：　Ｌｅａｒｎｉｎｇ　ｗｉｔｈ　Ｍａｎｙ　Ｒｅｌｅｖａｎｔ　Ｆｅａｔｕｒｅｓ［Ｃ］．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｅｕｒｏｐｅａｎ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｃｈｉｎｅ　Ｅｅａｍｉｎｇ，１９９８　２．Ｔｈｏｒｓｔｅｎ　Ｊｏａｃｈｉｍｓ．Ｍａｋｉｎｇ　ｌａｒｇｅ－ｓｃａｌｅ　ＳＶＭ　ｌｅａｍｉ１１ｇ　ｐｌａｃｔｉｃａ１．Ｉｎ：Ｂ　Ｓｃｈｓｌｋｏｐｆ，Ｃ　Ｊ　Ｃ　Ｂａｒｇｅｓ，Ａ　Ｊ　Ｓｍｏｌａ　ｅｄｓ．Ａｄｖａｎｃｅｓ　ｉｎ　Ｋｅｒｎｅｌ　Ｍｅｔｈｏｄｓ—　Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｌｅａｒｎｉｎｇ，ＭＩＴ　Ｐｒｅｓｓ，１９９９：１６９～１８４　３．Ｂ　Ｅ　Ｂｏｓｅｒ．Ｉ　Ｍ　Ｇｕｙｏｎ．Ｖ　Ｎ　Ｖａｐｎｉｋ．Ａ　ｔｒａｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｏｐｔｉｍａｌ　ｍａｒｇｉｎ　ｃｌａｓｓｉｆｉｅｒｓ［Ｃ］．Ｉｎ：Ｄ　Ｈａｕｓｓｌｅｒ　ｅｄｓ．Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　５ｔｈ　Ａｎｎｕａｌ　ＡＣＭ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｅｅａｍｉｎｇ　ＴｈｅｏｒｙＡＣＭ　Ｐｒｅｓｓ，１９９２：　，，１４４～１５２　４．Ｃ　Ｃｏｒｔｅｓ，Ｖ　Ｖａｐｎｉｋ．Ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｎｅｔｗｏｒｋｓｌ　Ｊ１．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９９５；　２０：２７３～２９７　５．Ｈ　Ｋｕｈｎ．Ａ　Ｔｕｃｈｅｒ．Ｎｏｎｌｉｎｅａｒ　ｐｒｏｇｒａｍｍｉｎｇ［Ｃ］．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　２ｎｄ　Ｂｅｒｋｌｅｙ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｍａｔｈｅｍａｔｉｃａｌ　Ｓｔａｔｉｓｔｉｃｓ　ａｎｄ　Ｐｒｏｂａｂｉｌｉｓｔｉｃｓ，　６　结论　在文本自动分类巾．文本分类通常采用向量空间模型将文　本表示成空间巾的向量。向最空『口】的维数为词的总数，每维对　应一个词．向量的维数很高，而一篇文章中出现的词占总词数　巾的词比例很低，这样导致文本ｒ口】量是一种极度稀疏的向量，　向茸叶１很的权值用０表示。侄计算向量的内积时，只有两　两向量不为０的乘积才有非０值。　此，使用ＳＭＯ这样的两点　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃａｌｉｆｏｍｉａ　Ｐｒｅｓｓ，１　９５　１　６．Ｊ　Ｐｌａｔｔ．Ｆａｓｔ　ｔｒａｉｎｉｎｇ　ｏｆ　ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅｓ　ｕｓｉｎｇ　ｓｅｑｕｅｎｔｉａｌ　ｍｉｎｉｍａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］．Ｉｎ：Ｂ　Ｓｃｈｏｌｋｏｐｆ．Ｃ　Ｂｕｒｇｅｓ，Ａ　Ｓｍｏｌａ　ｅｄｓ．Ａｄ—　ｖａｎｃｅｓ　ｉｎ　Ｋｅｒｎｅｌ　Ｍｅｔｈｏｄｓ—Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｌｅａｒｎｉｎｇ，ＭＩＴ　Ｐｒｅｓｓ，１９９８　７．Ｋ　Ａａｓ．Ｌ　Ｅｉｋｖｉｌ．Ｔｅｘｔ　ｃａｔｅｇｏｒｉｚａｔｉｏｎ：ａ　ｓｕｉｗｅｙ［Ｒ］Ｔｅｃｈ，ｌｉｃａｌ　ｒｅｐｏｒｔ，Ｎｏｒ—　ｗｅｇｉａｎ　Ｃｏｍｐｕｔｉｎｇ　Ｃｅｎｔｅｒ．１９９９一Ｏ６　８．史忠植知识发现ＩＭｌ＿清华大学出版社，２００２　（上接６７页）　引入的背景颜色　这种情况可能存Ｂａｙｅｓ　ｍａｔｔｉｎｇ巾发生，因为　通过与当前交互式分割算法的对比可以看出Ｇｒａｂ　ｃｕｔ分割算　法有较强的优势。笔者结合自己的研究课题，将该分割算法应　用到了医学图像器官分割巾．得到了较好的实际效果。　（收稿日期：２００５年ｌ１月）　采用的概率函数斌图取消背景影响，但是做的又不够准确，就　现为前景颜色的流失。这里通过从前景７１ｆ里取像素来避免　这种情况。首先采用Ｂａｙｅｓ　ｍａｔｔｉｎｇ算法获得像素ｎ（ｎ∈Ｔｆ）的　前景颜色估计　。然后在邻域　素来形成前景颜色　。　里面找到与　．颜色相近的像　参考文献　１．Ｒｕｚｏｎ　Ｍ，Ｔｏｍａｓｉ　Ｃ　Ａｌｐｈａ　ｅｓｔｉｎｍｔｉｏｎ　ｉｎ　ｎａｔｕｒａｌ　ｉｍａｇｅｓ［Ｃ］，Ｉｎ：Ｐｒｏ（：　１ＥＥＥ　Ｃｏｎｆ　Ｃｏｍｐ　Ｖｉｓｉｏｎ　ａｎｄ　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，２０００　２．Ｃａｒｓｔｅｎ　Ｒｏｔｈｅｒ．Ｖｌａｄｉｍｉｒ　Ｋｏｌｍｏｇｏｒｏｖ，Ａｎｄｒｅｓ　Ｂｌａｋｅ“Ｇｒａｂｃｕｔ”一ｉｎｔｅｒ—　圈　盈　（ａ）头部横切网　（ｂ）脑室的分　割结果　图５　Ｇｒａｂ　ｃｕｔ医学图像分割结果　ａｃｔｉｖｅ　Ｆｏｒｅｇｒｏｕｎｄ　Ｅｘｔｒａｃｔｉｏｎ　ｕｓｉｎｇ　ｉｔｅｒａｔｅｄ　Ｇｒａｐｈ　ＣＵｔｓ［Ｃ｝．Ｉｎ：Ｍｉｃｒｏｓｏｆｔ　Ｒｅｓｅａｒｃｈ　Ｃａｍｂｒｉｄｇｅ，ＵＫ，２００４　３．Ｃｈｕａｎｇ　ｙ－ｙ，Ｃｕｒｌｅｓｓ　Ｂ，Ｓａｌｅｓｉｎ　Ｄ　ｅｔ　ａ１．Ａ　Ｂａｙｅｓｉａｎ　ａｐｐｒｏａｃｈ　ｔｏ　（Ｃ）腹部横切罔　（ｄ）肝脏分　割结果　ｄｉｇｉｔａｌ　ｍａｔｔｉｎｇ［Ｃ］．Ｉｎ：Ｐｒｏｃ　ＩＥＥＥ　Ｃｏｎｆ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ　ａｎｄ　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇ，ＣＤ—ＲＯＭ，２００１　４．Ｂｏｙｋｏｖ　Ｙ．Ｊｏｌｌｙ　Ｍ－Ｐ．Ｉｎｔｅｒａｃｔｉｖｅ　ｇｒａｐｈ　ｃｕｔｓ　ｆｏｒ　ｏｐｔｉｍａｌ　ｂｏｕｎｄａｒｙ　ａｎｄ　注：图中的试验罔片均来自重庆第三军医大学的人体切片数据库　ｒｅｇｉｏｎ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｏｆ　ｏｂｊｅｃｔｓ　ｉｎ　Ｎ—Ｄ　ｉｍａｇｅｓ［Ｃ］．Ｉｎ：Ｐｒｏｃ　ＩＥＥＥ　Ｉｎｔ　Ｃｏｎｆ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ，ＣＤ－ＲＯＭ，２００　１　５．Ｋｏｌｍｏｇｏｒｏｖ　Ｖ．Ｚａｂｉｈ　Ｒ．Ｗｈａｔ　ｅｎｅｒｇｙ　ｆｕｎｃｔｉｏｎｓ　ｃａｎ　ｂｅ　ｎｌｉｎｉｍｉｚｅｄ　ｖｉａ　５结论与试验结果　本文详细的阐述了一种新的交互式目标分割方法Ｇｒａｂ　ｃｕｔ．并演示了其分割效果图。该方法能在难度适度的图像中通　过相对较少的交　互工作得到满意的分割效果，并获得了高质量　的前景ａｌｐｈａ值。整个算法结合基于Ｇｒａｐｈ　ｃｕｔｓ的优化迭代和　Ｂ０ｒｄｅｒ　ｍａｔｔｉｎｇ来处理目标边界处图像模糊和像素重叠问题。　ｒａｐｈ　ｃｕｔｇｓ［Ｃ］．Ｉｎ：Ｐｒｏｃ　ＥＣＣＶ　ＣＤ—ＲＯＭ，２００２　６．Ｍｏｒｔｅｎｓｅｎ　Ｅ，Ｂａｒｒｅｔｔ　Ｗ．Ｔｏｂｏｇａｎ—ｂａｓｅｄ　ｉｎｔｅｌｌｉｇｅｎｔ　ｓｃｉｓｓｏｒｓ　ｗｉｔｈ　ａ　ｆｏｕｒ　ｐａｒａｍｅｔｅｒ　ｅｄｇｅ　ｍｏｄｅｌ［Ｃ］．Ｉｎ：Ｐｒｏｃ　ＩＥＥＥ　Ｃｏｎｆ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ　ａｎｄ　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇ，１９９９；２：４５２￣４５８　７．Ｒｕｃｋｌｉｄｇｅ　Ｗ　Ｊ．Ｅｆｆｉｃｉｅｎｔ　ｖｉｓｕａｌ　ｒｅｃｏｇｎｉｔｉｏｎ　ｕｓｉｎｇ　ｔｈｅ　Ｈａｕｓｄｏｒｆｆ　ｄｉｓ—　ｔａｎｃｅ［Ｍ］．ＬＮＣＳ，Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，ＮＹ，１９９６　计算机工程与应用：２００６．２４　１６３