基于集成的非均衡数据分类主动学习算法

第２９卷第６期　２０１２年６月　计算机应用与软件　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｖ０１．２９　Ｎｏ．６　Ｊｕｎ．２０１２　基于集成的非均衡数据分类主动学习算法　李卓然　张　永　（辽宁师范大学计算机与信息技术学院（大连理－１－大学控制科学与工程学院辽宁大连１１６０８１）　辽宁大连１１６０２４）　摘要　当前，处理类别非均衡数据采用的主要方法之一就是预处理，将数据均衡化之后采取传统的方法加以训练。预处理的方　法主要有过取样和欠取样，然而过取样和欠取样都有自己的不足，提出拆分提升主动学习算法ＳＢＡＬ（Ｓｐｌｉｔ—Ｂｏｏｓｔ　Ａｃｔｉｖｅ　Ｌｅａｒｎｉｎｇ），该　算法将大类样本集根据非均衡比例分成多个子集，子集与小类样本集合并，对其采用ＡｄａＢｏｏｓｔ算法训练子分类器，然后集成一个总　分类器，并基于ＱＢＣ（Ｑｕｅｒｙ—ｂｙ・ｃｏｍｍｉｔｔｅｅ）主动学习算法主动选取有效样本进行训练，基本避免了由于增加样本或者减少样本所带　来的不足。实验表明，提出的算法对于非均衡数据具有更高的分类精度。　关键词　中图分类号非均衡数据　集成　主动学习　分类　ＴＰ１８１　文献标识码Ａ　ＩＭＢＡＬＡＮＣＥＤ　ＤＡＴＡ　ＣＬＡＳＳＩＦＩＣＡＴＩｏＮ　ＡＣＴＩＶＥ　ＬＥＡＲＮＩＮＧ　ＡＬＧｏＲＩＴＨＭ　ＢＡＳＥＤ　ｏＮ　ＢｏＯＳＴＩＮＧ　Ｌｉ　Ｚｈｕｏｒａｎ　Ｚｈａｎｇ　Ｙｏｎｇ　・　（Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｌｉａｏｎｉｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｌｉａｎ　１１６０８１，Ｌｉａｏｎｉｎｇ，Ｃｈｉｎａ）　。（Ｓｃｈｏｏｌ　ｏｆＣｏｎｔｒｏｌ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｄａｌｉａｎ　Ａｂｓｔｒａｃｔ　ｆＴｅｃｏｈｎｏｌｏｇｙ，Ｄａｌｉａｎ　１１６０２４，Ｌｉａｏｎｉｎｇ，Ｃｈｉｎａ）　Ａｔ　ｐｒｅｓｅｎｔ，ｏｎｅ　ｏｆ　ｔｈｅ　ｐｏｐｕｌａｒ　ｍｅｔｈｏｄｓ　ｔｏ　ｐｒｏｃｅｓｓ　ｉｍｂａｌａｎｃｅ　ｄａｔａｓｅｔ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ｉｓ　ｒｅｓａｍｐｌｉｎｇ，ｔｏ　ｂａｌａｎｃｅ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｔｒａｉｎｉｎｇ　ｅｘａｍｐｌｅｓ　ａｍｏｎｇ　ｃｌａｓｓｅｓ　ａｎｄ　ｔａｋｅ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｍｅｔｈｏｄ　ｔｏ　ｔｒａｉｎ　ｔｈｅ　ｂａｌａｎｃｅｄ　ｄａｔａｓｅｔ．Ｔｈｅ　ｍａｉｎ　ｗａｙｓ　ｏｆ　ｒｅｓａｍｐｌｉｎｇ　ｉｎｃｌｕｄｅ　ｏｖｅｒ—　ｓａｍｐｌｉｎｇ　ａｎｄ　ｕｎｄｅｒ—ｓａｍｐｌｉｎｇ．Ｈｏｗｅｖｅｒ　ｔｈｅｒｅ　ａｒｅ　ｓｈｏｒｔａｇｅｓ　ｉｎ　ｂｏｔｈ　ｏｖｅｒ—ｓａｍｐｌｉｎｇ　ａｎｄ　ｕｎｄｅｒ－ｓａｍｐｌｉｎｇ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｓｐｌｉｔ－ｂｏｏｓｔ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｃａｌｌｅｄ　ＳＢＡＬ．Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｓｐｌｉｔｓ　ｔｈｅ　ｍａｊｏｒｉｔｙ　ｃｌａｓｓ　ｄａｔａｓｅｔ　ｉｎｔｏ　ｓｕｂｓｅｔｓ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｐｒｏｐｏｒｔｉｏｎ　ｏｆ　ｉｍｂａｌａｎｃｅ　ｓａｍｐｌｅｓ，ｃｏｍｂｉｎｅｓ　ｗｉｔｈ　ｍｉｎｏｒｉｔｙ　ｃｌａｓｓ　ｄａｔａｓｅｔ，ａｎｄ　ｔｒａｉｎｓ　ｔｈｅ　ｃｌａｓｓｉｉｆｅｒｓ　ｂｙ　ＡｄａＢｏｏｓｔ　ａｌｇｏｒｉｔｈｍ，ｔｈｅｎ　ｂｏｏｓｔｓ　ａ　ｔｏｔａｌ　ｃｌａｓｓｉｆｉｅｒ．　ＳＢＡＬ　ａｌｇｏｒｉｔｈｍ　ｓｅｌｅｃｔｓ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅ　ｔｒａｉｎｉｎｇ　ｓａｍｐｌｅｓ　ｔｏ　ｊｏｉｎ　ｔｈｅ　ｌａｓｔ　ｔｒａｉｎｉｎｇ　ｂａｓｅｄ　ｏｎ　ＱＢＣ　Ａｃｔｉｖｅ　Ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍ，ＳＯ　ｉｔ　ａｖｏｉｄｓ　ｔｈｅ　ｓｈｏｒｔａｇｅｓ　ｏｆ　ｔｈｅ　ｏｖｅｒ—ｓａｍｐｌｉｎｇ　ａｎｄ　ｕｎｄｅｒ－ｓａｍｐｌｉｎｇ　ｆｕｎｄａｍｅｎｔａｌｌｙ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｇａｉｎｓ　ｈｉｇｈｅｒ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ａｃｃｕｒａｃｙ　ｗｉｔｈ　ｉｍｂａｌａｎｃｅ　ｄａｔａｓｅｔｓ．　Ｋｅｙｗｏｒｄｓ　Ｉｍｂａｌａｎｃｅｄ　ｄａｔａ　ｓｅｔ　Ｂｏｏｓｔ　Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　当前，许多学者对非均衡数据的分类进行了研究，并在重采　０　引　言　大量数据在各种应用中不断积累，这些数据虽然不能直接　在商业活动中获利，但具有极大的潜在商业价值。在这些应用　中的数据多数类别都是非均衡的，即一个类别的样本数量明显　样、集成学习、代价敏感和特征选择等方面均取得了较大的进　展。但各种方法依然存在各自的不足，例如，虽然重采样方法中　的过取样和欠取样，虽然很多学者已经提出各种合理的改进策　略，如ＳＭＯＴＥ算法，但按此法分类产生的过拟合问题依然存在，　欠取样方法的忽略大类样本潜在有用信息也难以克服。针对以　上不足，本文提出了一个拆分提升主动学习算法ＳＢＡＬ（Ｓｐｌｉｔ－　Ｂｏｏｓｔ　Ａｃｔｉｖｅ　Ｌｅａｒｎｉｎｇ），该算法根据样本非均衡的比例数目，采　大于其他类别样本，而通常，在这些非均衡数据中，较小类别的　数据往往具有较大的价值，如电信管理…、生物信息学　Ｊ、文本　分类方法　Ｊ、语音识别　Ｊ、卫星图像中的石油泄漏　等。　传统的分类算法都是基于处理类别均衡数据的基础之上，　对于非均衡数据，传统算法虽能得到较好的分类准确率，但并不　代表它具有很好的分类精度，实际应用过程中的非均衡数据比　例有可能是１：１０，也有可能是１：１００，甚至１：１　０００，而这个１的　错误往往带来非常大的影响。因此，非均衡数据具有它独特的　用ＡｄａＢｏｏｓｔ算法训练子分类器，然后将子分类器集成为一个总　的分类器，并基于ＱＢＣ主动学习算法投票选取候选集进行训　练，不仅有效利用了样本信息，而且还合理避免了重采样带来的　不足。　收稿日期：２０１１—０９—２０。中国博士后科学基金项目（２０１１０４９１５３０）；　辽宁省科技厅博士启动基金项目（２００８１０７９）；大连市科学技术基金项目　（２０１０Ｊ２１ＤＷ０１９）。李卓然，硕士生，主研领域：机器学习。张永，副教授。　研究特点和非常大的实用价值，针对现实数据的非均衡数据的　数据挖掘越来越引起人们的关注　。　８２　计算机应用与软件　目比例　；　２０１２益　１相关工作　１．１　ＥａｓｙＥｎｓｅｍｂｌｅ算法　在各种不同的非均衡数据分类方法中，欠取样是较常被使　用的　，然而因为欠取样的原理是选取大类的子集进行训练，　步骤２．２根据比例　把大类样本分成［　］个子集，取小　类样本与每个子集结合，其中［　］表示将　取整；　步骤２．３对步骤２．２所得子集进行ＡｄａＢｏｏｓｔ分类，并得　到由［　］个弱分类器　，其中　＝１，２，…，［　］；　步骤２．４将所有步骤２．３所得弱分类器日　看作特征，直　接将其集成为　。　步骤３取剩余样本　到Ⅳｍ，利用步骤２所得到的分类器　Ｈ１，　对其做预测；　所以就导致了包含在被忽略样本中的潜在有用信息被遗漏，这　就是欠取样算法的主要缺陷。ＥａｓｙＥｎｓｅｍｂｌｅ算法　就是针对这　一缺陷提出的一种欠取样算法，该算法将大类样本分为多个独　立的子集，对于每一个子集一个子分类器被训练，最后将所有子　步骤４判断两个分类预测是否一致，将不一致样本加入　候选集Ｄ；　分类器集成，得到最终分类器。此算法专门为类别非均衡问题　设计，充分利用了样本信息，并避免了忽略有效信息的缺陷，在　实验中取得了稳定高效的结果。　步骤５合并样本集Ⅳ　，Ⅳ２和候选集Ｄ，得到最终训练样本　集合Ｅ；　步骤６对Ｅ进行类似步骤２操作，取大类样本子集与小　类样本合并，做ＡｄａＢｏｏｓｔ训练分类器，集成ＡｄａＢｏｏｓｔ所得弱分　类器，并得到最终分类器材。　１．２　ＱＢＣ主动学习策略　主动学习是在训练过程中采取有效的学习策略选取信息量　最丰富的样本进行学习的一种策略。ＱＢＣ即委员会投票算法，　是由Ｓｅｕｎｇ　和Ｆｒｅｕｎｄ　提出的一种基于如何减小搜索空间的　３实验与分析　３．１数据集　本次实验采用比较有代表性的６个ＵＣＩ数据集…　作为训　练集和测试集，数据集的基本信息如表１所示，其中类别比例指　多数类对少数类样本个数的倍数。本文将少数类样本作为目标　类，其他的所有类别作为多数类。　表１数据集基本信息　主动学习算法。该算法首先根据已有类标签的样本训练两个或　多个分类器，组成“委员会”，对剩余样本进行投票，选择投票最　不一致样本加入候选集。该算法无需检测整个样本空间，计算　复杂度较低，学习速度较快，能够在较少训练样本的基础上达到　给定分类精度。　２　基于集成的非均衡数据分类主动学习算　法ＳＢＡＬ　２．１算法简介　本文提出了ＳＢＡＬ算法，即拆分提升主动学习算法。本算　法是将拆分集成算法应用于ＱＢＣ主动学习策略中，在最大化均　衡数据进行分类的基础上提高分类精度。为了克服过取样和欠　取样带来的不足，本算法采取根据多数类样本对少数类样本的　比例训练分类器进行集成，不仅充分利用了少数类样本的信息，　而且反应了多数类的不同方面的信息，使所得分类器表现出样　本分布的大致状况。两个这样的分类器带来最终分类器的大致　３．２性能评价度量　通常情况下，用预测准确率来判断一个分类器的好坏，而当　数据类型非均衡或者错误的代价非常不同的情况下，预测准确　率的方法是不适用的。例如，当一个非均衡数据的比例是９８：２　时，即使将数据全部划分为大类，它的准确率依然为很高的　范围，无需对全部样本做拆分集成，只需运用ＱＢＣ委员投票，即　可得到对分类器具有影响的有效样本，这样的结合更高效地训　练出最终分类器。　算法的基本思想是：首先，将训练集均分ｍ（ｍ＞＝３）等　份，取前两份分别做拆分集成，把得到的子分类器作为委员，对　剩余（ｍ一２）等份数据集进行投票，投票不一致的样本即分类　９８％，但这个分类结果对于小类显然是毫无意义的。　ＲＯＣ曲线（接受者操作特性曲线）　Ｊ２］是一项标准的总结分　类器真正率和假正率的一个折衷，它的左上角是最理想的位置，　器最不能确定的样本，也是信息含量最丰富的样本，将其加入候　选集，最后将候选集与前面两等份数据集合并，训练最终的拆分　集成分类器。通过本文的实验表明，当ｍ＝５时，不仅可以得到　代表所有正类样本被正确分为正类，而没有负类样本被误分为　正类。因此，ＲＯＣ是公认的衡量非均衡数据分类准确率的标准　之一。ＡＵＣ（曲线下的面积）可以数值化ＲＯＣ曲线，因而也是公　认的代表ＲＯＣ曲线的性能度量。Ｆ—ｍｅａｓｕｒｅ和Ｇ—ｍｅａｎｓ，是表２　较全面的分类信息，剩余样本又可以进行较充分的主动学习，因　此本文实验中取ｍ＝５。　２．２算法描述　基于上述思想，提出的ＳＢＡＬ算法描述如下。　步骤１导入训练集，将训练集随机均分为ｍ（ｍ＞＝３）份　Ｎ　Ｌ，Ｎ　．…．Ｎ　中混淆矩阵的组合函数，同ＲＯＣ一样是公认的非均衡数据分类　检测标准。　表２混淆矩阵　步骤２对第一份和第二份样本集做如下相同操作：　步骤２．１取样本集　（ｉ＝１，２），计算其大类小类样本数　第６期　李卓然等：基于集成的非均衡数据分类主动学习算法　８３　在表２混淆矩阵中，行是预测类，列是实际类，ＴＮ（Ｔｒｕｅ　ＡｄａＢｏｏｓｔ　ＳＭ０　ＳＭＯＴＥＢｏｏｓｔ　ＥＥ　ＳＢＡＬ　Ｎｅｇａｔｉｖｅｓ）是负类样本被正确分类的数目，ＦＰ（Ｆａｌｓｅ　Ｐｏｓｅｔｉｖｅｓ）　Ｈａｂｅｒｍａｎ　０．５０２５　０．６３２３　０．５３６２　０．６１５２　０．６１７７　是负类样本被错分为正类样本的数目，ＦＮ（Ｆａｌｓｅ　Ｎｅｇａｔｉｖｅｓ）是正　Ｔｒａｎｓｆｕｓｉｏｎ　０．５４３０　０．５８４５　０．６２１４　０．６６５８　０．６３６１　类样本被错分为负类的数目，ＴＰ（Ｔｒｕｅ　Ｐｏｓｅｔｉｖｅｓ）是正类样本被　Ｂａｌａｎｃｅ　０．００１２　０．５２６３　０．００２４　０．５７７５　０．６６４７　分为正类样本的数目。ＲＯＣ曲线、Ｆ—ｍｅａｓｕｒｅ、Ｇ－ｍｅａｎｓ均可以看　ｅＬｔｔｅｒ　０．９８９２　０．９８９６　０．９９５２　０．９９５０　０．９９６３　作混淆矩阵的衍生函数。　ＲＯＣ曲线中，ｘ轴代表假正率ＦＰＲ（Ｆａｌｓｅ　Ｐｏｓｉｉｔｖｅ　Ｒａｔｅ）＝　从Ａｕｃ实验结果来看，本文的ＳＢＡＬ算法明显优于其他算　ＦＰ／（ＴＮ＋ＦＰ），Ｙ轴代表真正率ＴＰＲ（Ｔｒｕｅ　Ｐｏｓｉｔｉｖｅ　Ｒａｔｅ）：ＴＰ／　法，尤其对ｂａｌａｎｃｅ样本集，对ｌｅｔｔｅｒ数据集基本没有影响；Ｆ－　（，ＩＰ＋ＦＮ），曲线的理想点事（０，１００），这点表示所有正类样本　ｍｅａｓｕｒｅ数据来看，ＳＢＡＬ算法略优于其他算法，只有ｔｒａｎｓｆｕｓｉｏｎ　被正确划分为正类，而没有负类样本误分为正类，曲线越接近这　数据集稍逊，ｂａｌａｎｃｅ和ｌｅｔｔｅｒ数据集表现较好；Ｇ—ｍｅａｎｓ和Ｆ－　一点，分类效果越理想，ＡＵＣ值也越大。　ｍｅａｓｕｒｅ表现类似，ｂａｌａｎｃｅ数据集依然表现很好，其他略好，ＥＥ　Ｇ．ｍｅａｎｓ和Ｆ．ｍｅａｓｕｒｅ则被定义如下”　：　算法在ｔｒａｎｓｆｕｓｉｏｎ数据集表现较好。总体来看，五个方法中　Ｇ－ｍｅａｎｓ＝、　厨　丽　（１）　ＳＭＯＴＥ算法表现最差，看来单独使用该算法并不是良策，与集　２×Ｐｒｅｃｉｓｉｏｎ×Ｒｅｃａｌｌ　，　、　成学习集合后有了比较好的表现，总体也略高于单独用Ａｄａ—　，１　黜“　一　Ｌ　Ｂｏｏｓｔ集成算法，ＥＥ算法在前四种算法中表现较好，而ＳＢＡＬ算　式（２）中，Ｐｒｅｃｉｓｉｏｎ和Ｒｅｃａｌ１分别表示精度和召回率，它们分别　法基本略高于ＥＥ算法，说明ＳＢＡＬ算法对比ＳＭＯＴＥ过取样算　定义为：Ｐｒｅｃｉｓｉｏｎ＝ＴＰ／（ＴＰ＋ＦＰ），Ｒｅｃａｌｌ＝ＴＰ／（ＴＰ＋ＦⅣ）＝　法和ＥＥ欠取样算法均有所改进，即有效避免了重取样算法的　。　不足。　ＲＯＣ曲线的优点是直观，而缺点是不够精确，同样数据对　于不同算法的表现也许差距并不大，视觉效果不明显，因此通常　４结语　用ＡＵＣ数据来比较分类器精度大小。ＡＵＣ、Ｆ—ｍｅａｓｕｒｅ、Ｇ－ｍｅａｎｓ　均为数值与分类器的精度成正比，数值越大说明分类精度越大，　针对重采样算法的不足，基于集成算法提高子分类器性能　效果越好。　的优势和主动学习的高效性，本文进行了将非均衡数据分子集　３．３实验结果及分析　进行的拆分提升学习与主动学习算法相结合的尝试，提出了　本实验采用Ｍａｔｌａｂ　２００７来实现ＳＢＡＬ算法，并将其与Ａｄａ—　ＳＢＡＬ拆分提升主动学习算法。实验分析表明本文算法对非均　ｂｏｏｓｔ算法　、ＳＭＯＴＥ算法（ＳＶＭ为基础分类器）　、ＳＭＯＴＥ—　衡数据分类问题具有较好表现，说明拆分提升算法与主动学习　ＢＯＯＳＴ算法　、ＥＥ算法　进行比较。选用ＡＵＣ、Ｆ．ｍｅａｓｕｒｅ和　相结合具有深入研究的可行性。　Ｇ—ｍｅａｎｓ三种评估方法进行检测。为了实验对比，五个算法均　参考文献　通过十折交叉验证方法获得均值。表３～表５分别给出用五个　算法进行比较的三种不同实验结果。　［１］Ｅｚａｗａ　Ｋ　Ｊ，Ｓｉｎｇｈ　Ｍ，Ｎｏｒｔｏｎ　Ｓ　Ｗ．Ｌｅａｒｎｉｎｇ　Ｇｏａｌ　Ｏｒｉｅｎｔｅｄ　Ｂａｙｅｓｉａｎ　Ｎｅｔｗｏｒｋｓ　ｆｏｒ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｒｉｓｋ　Ｍａｎａｇｅｍｅｎｔ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　表３不同算法的ＡＵＣ比较　ｏｆ　ｔｈｅ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，ＩＣＭＬ－９６，１９９６：　ＡｄａＢｏｏｓｔ　ＳＭ０ＴＥ　ＳＭ０ｒＩ１ＥＢｏｏｓｔ　ＥＥ　ＳＢＡＬ　１３９—１４７．　Ｐｉｍｓ　０．７８８０　０．５５７１　０．７９０３　Ｏ．８Ｏ９４　０．８２３６　［２］Ｒａｄｉｖｏｊａｃ　Ｐ，Ｃｈａｗｌａ　Ｎ　Ｖ，Ｄｕｎｋｅｒ　Ｋ，ｅｔ　ａ１．Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｎｄ　Ｋｎｏｗｌ－　Ｐｈｏｎｅｍｅ　０．９６５０　０．７７１４　Ｏ．９３７４　０．９５８０　０．９６３３　ｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ｉｎ　Ｐｒｏｔｅｉｎ　Ｄａｔａｂａｓｅｓ［Ｊ］．Ｊｏｕｍａｌ　ｏｆ　Ｂｉｏｍｅｄｉｃａｌ　Ｉｎｆｏｒ－　ｍａｔｉｅｓ，２００４：２２４—２３９．　Ｈａｂｅｒｍａｉａ　０．６４ｌ１　０．４６９４　０．６４６６　０．６６８１　０．６７５８　［３］Ｌｅｗｉｓ　Ｄ，Ｃａｔｌｅｔｔ　Ｊ．Ｈｅｔｅｒｏｇｅｎｅｏｕｓ　Ｕｎｃｅｒｔａｉｎｔｙ　Ｓａｍｐｌｉｎｇ　ｆｏｒ　Ｓｕｐｅｒｖｉｓｅｄ　Ｔｒａｎｓｆｕｓｉｏｎ　０．６３５４　０．４９４２　Ｏ．６Ｏ２５　０．７００２　Ｏ．７Ｏ２３　ｅＬａｒｎｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｅｌｅｖｅｎｔｈ　Ｉｎｔｅｍａｔｉｏｒｌａ／Ｃｏｎｆｅｒｅｎｃｅ　ｏｆ　Ｂａｌａｎｅｅ　０．６１６４　０．４５２８　０．５９９１　０．６３３８　０．６７７９　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９９４：１４８—１５６．　ｌｅｔｔｅｒ　１．Ｏ００ｏ　０．９８５１　０．９９５４　１．ｏｏＯ０　０．９９９９　［４］Ｌｉｕ　Ｙ，Ｃｈａｗｌａ　Ｎ　Ｖ，Ｓｈｆｉｂｅｒｇ　Ｅ，ｅｔ　ａ１．Ｒｅｓａｍｐｌｉｎｇ　Ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　Ｓｅｎ－　ｔｅｎｃｅ　Ｂｏｕｎｄａｒｙ　Ｄｅｔｅｃｔｉｏｎ：Ａ　Ｃａｓｅ　Ｓｔｕｄｙ　ｉｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　ｆｒｏｍ　Ｉｍ—　表４不同算法的Ｆ・ｍｅａｓｕｒｅ比较　ｂａｌａｎｃｅｄ　Ｄａｔａ　ｆｏｒ　Ｓｐｏｋｅｎ　Ｌａｎｇｕａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ［Ｒ］．Ｔｅｃｈｎｉｃａｌ　Ｒｅｐｏｒｔ，　ＡｄａＢｏｏｓｔ　ＳＭ０ＴＥ　ＳＭ０　ｒＥＢｏｏｓｔ　ＥＥ　ＳＢＡＬ　ＩＣＳＩ，２００３．　Ｐｉｍａ　０．６ｌ１７　０．５８５８　０．６４１６　０．６６０５　０．６６７０　［５］Ｋｕｂａｔ　Ｍ，Ｈｏｌｔｅ　Ｒ，Ｍａｔｗｉｎ　Ｓ．Ｍａｃｈｉｎｅ　ｅＬａｒｎｉｎｇ　ｏｆｒ　ｔｈｅ　Ｄｅｔｅｃｔｉｏｎ　ｏｆ　Ｏｉｌ　Ｐｈｏｎｅｍｅ　０．８５２０　０．６５７５　０．７９６５　０．８２１２　０．８２８６　Ｓｐｉｌｌｓ　ｉｎ　Ｓａｔｅｌｌｉｔｅ　Ｒａｄａｒ　Ｉｍａｇｅｓ［Ｊ］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９９８：１９５　—Ｈａｂｅｒｍａｎ　０．３４８２　０．４８７７　０．３７７４　０．４６６３　０．４６９３　２１５．　Ｔｒａｎｓｆｕｓｉｏｎ　０．３７４６　０．４１８３　０．４７２８　０．４９０２　０．４５７４　［６］Ｃｈａｗｌａ　Ｎ　Ｖ．Ｄａｔａ　Ｍｉｎｉｎｇ　ｆｏｒ　Ｉｍｂａｌｎａｃｅｄ　Ｄａｔａｓｅｔｓ：Ａｎ　Ｏｖｅｒｖｉｅｗ［Ｍ］．　Ｄａｔａ　Ｍｉｎｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　Ｈａｎｄｂｏｏｋ，２０１０：８７５—８８６．　Ｂａｌ８ｎｃｅ　Ｏ．００ｏｏ　０．１６５８　Ｏ．０ｏ１１　０．１８４７　０．２２９１　［７］Ｚｈｏｕ　Ｚ　Ｈ，Ｌｉｕ　Ｘ　Ｙ．Ｔｒａｉｎｉｎｇ　ｃｏｓｔ・ｓｅｎｓｉｔｉｖｅ　ｎｅｕｒ￣ｎｅｔｗｏｒｋｓ　ｗｉｔｈ　ｍｅｔｈ－　Ｌｅｔｔｅｒ　０．９８８２　０．９５５７　０．９６６４　０．９１０２　０．９３０７　ｏｄｓ　ａｄｄｒｅｓｓｉｎｇ　ｔｈｅ　ｃｌａｓｓ　ｉｍｂａｌａｎｃｅ　ｐｒｏｂｌｅｍ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　Ｋｎｏｗ１－　表５不同算法的Ｇ－ｍｅａｌｌｋ￥比较　ｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００６，１８（１）：６３—７７．　［８］Ｌｉｕ　Ｘｕｙｉｎｇ，Ｗｕ　Ｊｉａｎｘｉｎ，Ｚｈｏｕ　Ｚｈｉｈｕａ．Ｅｘｐｌｏｒａｔｏｙｒ　Ｕｎｄｅｒ・Ｓａｍｐｌｉｎｇ　ｏｆｒ　ＡｄａＢｏｏｓｔ　ＳＭ０ＴＥ　ＳＭ０ＴＥＢｏｏｓｔ　ＥＥ　ＳＢＡＬ　Ｃｌａｓｓ—ＩｍｂＭａｎｃｅ　Ｌｅａｒｎｉｎｇ［Ｃ］／／ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａ－　Ｐｉｍａ　０．６９４６　０．６５７３　Ｏ．７１９６　０．７３４４　０．７３８４　ｔａ　Ｍｉｎｉｎｇ（ＩＣＤＭ’０６），２００６：９６５—９６９．　Ｐｈｏｎｅｍｅ　０．８９０１　０．７６７０　０．８７５２　０．８９２１　０．８９７９　（下转第８８页）　８８　计算机应用与软件　２０１２丘　矩形的标准，等腰梯形短边的两端点横坐标分别向两侧拉伸，分　基础，同时虚拟键盘的发展迎合了人们对舒适度、便携性和准确　性的高要求，有着很高的商业价值。本文旨在对几何失真的虚　别与长边的两端点横坐标相等；而纵坐标由拍摄键盘时的角度　及环境、角点识别算法精度共同决定，且不影响后续的按键落点　识别结果。　拟键盘进行高准确度和高效率的校正，是按键落点识别的基础。　本文提出算法的特色为对矩形键盘具有针对性，去除了冗余的　失真情况，用简单明了的数学方法分别对垂直俯拍造成的倾斜　失真和水平侧拍造成的透视失真进行校正，准确率较高。同时　４．２二分法效率分析　表２对使用二分法与不使用二分法的时间复杂度和空间复　杂度分别进行了分析对比。　表２二分法对校正算法效率的影响　不使用二分法　使用二分法　时间复杂度　０（ｎ）　０（１ｏｇｎ）　ＷＸＨ×Ｔ（　为图像宽度，Ⅳ　Ｗ×Ｈ×１～　×Ｈ×　空间复杂度　为图像高度，　为选取的变　１（其中　为键盘的　换角度的个数）　Ｖｎ　键数）　不使用二分法时，对图像每个点进行校正，故时间复杂度与　像素点数呈线性关系，空间复杂度即为该图大小；使用二分法　时，时间复杂度下降为对数型，且空间复杂度由选取的有效区域　大小决定。　由此可见，使用二分法虽然增加了少量划分图像的时间，但　大大缩短了校正算法的计算量，从而从整体上缩减了校正图像　所需的时间和空间。　５性能比较　Ｈｏｕｇｈ变换算法需要先检测出倾斜角度、再进行坐标变换。　本算法只需对二值化后局部图像的坐标进行变换。表３对两种　方法进行了性能比较。　表３　Ｈｏｕｇｈ变换与本文校正方法的性能比较　Ｈｏｕｇｈ变换　本文提出的算法　ＷＸＨ×Ｔ（Ｗ为图像宽度，Ⅳ　Ｗ×Ｈ×　～Ｗ×Ｈ×　计算量　为图像高度，　为选取的变　１（其中　为键盘的　换角度的个数）　√ｒｔ　键数）　适用范围　直线、圆形等多方面　矩形　冗余数据　产生大量冗余数据　信噪比　易受外界干扰，　只受角点识别影响　阈值　合适的阈值难以确定　对键盘进行三次测定，　取平均值　Ｈｏｕｇｈ方法的计算量远大于本文提出的方法，并在参数增　多时计算量急剧上升。大的计算量会导致内存占用多、计算速　度慢、实时性差等弊端，计算步骤多会致使误差累积过多，令最　后的按键落点识别错误。　需要指出的是Ｈｏｕｇｈ变换虽然速度较慢，但是适用范围很　广，不局限于直线，对于椭圆等许多形状的倾斜检测也适用。而　本文算法针对矩形，对拍摄角度进行了限制并依赖于角点的准　确识别　、　６　结语　嵌入式设备的日益普及为虚拟键盘技术提供了良好的发展　提出了二值化后的图像采用二分法获得校正有效区域，进一步　缩小校正的工作量，提高实时性。通过理论分析和实践证明，本　校正算法可以提高键盘按键落点识别的准确度，并有较高的处　理速度。　参考文献　［１］钟锡昌．嵌入式软件现状及发展趋势［Ｊ］　家用电器科技，２０１０　（９）：６０—６２．　［２］汪忠德．红外虚拟键盘的设计构想［Ｊ］．　计算机工程，２００４，３０　（６）：１８９—１９１．　［３］李攀，秦拯．一种利用拇指控制的触屏手机虚拟键盘按键提取方　法［Ｊ］．计算机系统应用，２０１０，１９（１１）：２２９—２３３．　［４］李玉山．数字视觉视频技术［Ｍ］．西安：西安电子科技大学出版　社．２００６．　［５］沈忙作．用计算机校正图像的透视几何畸变［Ｊ］．光电工程，１９８１　（６）：１—４．　［６］张雪峰，张全法，冯小星．一种扫描图像几何畸变的数字校正方　法［Ｊ］．电视技术，２００３（９）：７８—８０．　［７］张金，李洋，刘晓威，等．一种基于数字图像处理的虚拟输入方法　［Ｊ］．计算机工程与设计，２０１１（１２）：１—６　（上接第８３页）　［９］Ｓｅｕｎｇ　Ｈ　Ｓ，Ｏｐｐｅｒ　Ｍ，Ｓｏｍｐｏｌｉｎｓｋｙ　Ｈ．Ｑｕｅｒｙ　Ｂｙ　Ｃｏｍｍｉｔｔｅｅ［Ｃ］／／Ｐｒｏ—　ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１５ｔｈ　Ａｎｎｕａｌ　ＡＣＭ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｌｅａｒｎ—　ｉｎｇ　Ｔｈｅｏｒｙ，１９９２：２８７—２９４．　［１０］Ｆｒｅｕｎｄ　Ｙ，Ｓｅｕｎｇ　Ｈ　Ｓ，Ｓｈａｍｉｒ　Ｅ，ｅｔ　ａ１．Ｓｅｌｅｃｔｉｖｅ　Ｓａｍｐｌｉｎｇ　Ｕｓｉｎｇ　ｔｈｅ　Ｑｕｅｒｙ　ｂｙ　Ｃｏｍｍｉｔｔｅｅ　Ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９９７，２８：１３３　—１６８．　［１　１］ＵＣＩ　ｒｅｐｏｓｉｔｏｒｙ　ｏｆ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ　ｄａｔａｂａｓｅｓ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．　ｉｃｓ．ｕｃｉ．ｅｄｕ／～ｍｌｅａｍ／ＭＬＲｅｐｏｓｉｔｏｒｙ．ｈｔｍ１．　［１　２］Ｂｒａｄｌｅｙ　Ａ　Ｐ．Ｔｈｅ　ｕｓｅ　ｏｆ　ｔｈｅ　ａｒｅａ　ｕｎｄｅｒ　ｔｈｅ　ＲＯＣ　ｃｕｒｖｅ　ｉｎ　ｔｈｅ　ｅｖａｌｕａｔｉｏｎ　ｏｆ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，１９９７：１　１４５　ｌ】５９．　［１３］Ｔａｎ　Ｐａｎｇｎｉｎｇ．数据挖掘导论［Ｍ］．范明，等译．北京：人民邮电出版　社．２００６．　［１４］Ｆｒｅｕｎｄ　Ｙ，Ｓｃｈａｐｉｒｅ　Ｒ　Ｅ．Ｅｘｐｅｉｒｍｅｎｔｓ　ｗｉｔｈ　ａ　ｎｅｗ　ｂｏｏｓｔｉｎｇ　ａｌｇｏｉｒｔｈｍ　［Ｃ］／／ＩＥＥＥ　Ｉｎｔｅｎｒａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｎｒｉｎｇ，１９９６：１４８　１５６．　［１５］Ｃｈａｗｌａ　Ｎ　Ｖ，Ｂｏｗｙｅｒ　Ｋ　Ｗ，Ｈａｌｌ　Ｌ　０，ｅｔ　ａ１．ＳＭＯＴＥ：Ｓｙｎｔｈｅｔｉｃ　Ｍｉｎｏｒｉｔｙ　Ｏｖｅｒｓａｍｐｌｉｎｇ　Ｔｅｃｈｎｉｑｕｅ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ａｒｔｉｉｆｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　Ｒｅ—　ｓｅａｒｃｈ，２００２：３２１—３５７．　［１６］Ｃｈａｗｌａ　Ｎ　Ｖ，Ｌａｚａｒｅｖｉｃ　Ａ，Ｈａｌｌ　Ｌ　Ｏ，ｅｔ　ａ１．Ｓｍｏｔｅｂｏｏｓｔ：Ｉｍｐｒｏｖｉｎｇ　Ｐｒｅ—　ｄｉｃｔｉｏｎ　ｏｆ　ｔｈｅ　Ｍｉｎｏｒｉｔｙ　Ｃｌａｓｓ　ｉｎ　Ｂｏｏｓｔｉｎｇ［Ｃ］／／Ｓｅｖｅｎｔｈ　Ｅｕｒｏｐｅａｎ　Ｃｏｎ—　ｆｅｒｅｎｃｅ　ｏｎ　Ｐｒｉｎｃｉｐｌｅｓ　ａｎｄ　Ｐｒａｃｔｉｃｅ　ｏｆ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ｉｎ　Ｄａｔａｂａｓ—　ｅｓ，２００３：１０７—１１９．