（计算机应用技术专业论文）机器学习算法在指纹图像分割和交叉销售中的应用研究.pdf

原创性声明及关于学位论文使用授权的声明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：壹! ! 查 日 期：出噶删一 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：壶! 竖盈巳导师签名 o 丁 一0ij 山东大学硕士学位论文 目录 摘要i a b s t r a c t 】 i 第1 章绪论1 1 1 机器学习简介1 1 2 机器学习的国内外研究现状2 1 3 半监督学习与个性化指纹分割3 1 4 类别不平衡学习与交叉销售问题4 1 4 1 类别不平衡概述4 1 4 2 交叉销售问题5 1 5 本文使用的术语等价性声明6 1 6 本文的组织结构6 第2 章半监督学习算法及其在指纹分割中的应用研究8 2 1 指纹识别与指纹分割8 2 2 设备互操作性问题对指纹分割算法的影响9 2 2 1 设备互操作性问题研究现状9 2 2 2 设备互操作性理论分析1 0 2 2 3 不同的指纹在特征空间上分布的差异性11 2 2 4 设备互操作性对指纹分割算法的影响1 4 2 3 一种新的指纹分割的框架：个性化指纹分割1 7 2 4 基于图的半监督学习算法在指纹分割中的应用1 8 2 4 1 基于图的半监督学习算法1 8 2 4 2 基于线性近邻关系的标记传播算法1 8 2 4 3 本文算法a l l n p 的流程1 9 2 5 实验结果2 2 2 6 本章小结2 5 第3 章类别不平衡学习及其在交叉销售问题上的应用研究2 7 3 1 类别不平衡问题研究2 8 3 1 1 类别不平衡问题存在的应用领域2 8 3 1 2 类别不平衡问题的主要学术活动2 8 3 1 3 类别不平衡学习算法的性能度量准则2 9 3 1 4 类别不平衡学习算法研究3 0 山东大学硕士学位论文 3 1 5 类别不平衡问题讨论3 1 3 2 类别不平衡学习算法在交叉销售问题上的应用研究3 2 3 2 1 交叉销售简介3 2 3 2 2 问题描述及分析3 2 3 2 3 数据建模过程3 3 3 2 4 算法性能评价及与其它算法的比较3 9 3 2 4e n s v m 算法讨论4 0 3 3 本章小结4 0 第4 章总结与展望4 2 参考文献4 3 致谢5 1 攻读学位期间发表的学术论文5 3 攻读学位期间荣获奖励情况5 4 d。j_ii-_ 山东大学硕士学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h 】 c h a p t e rli n t r o d u c t i o n l 1 1i n t r o d u c t i o nt om a c h i n el e a r n i n g 1 1 2t h es t a t eo f t h ea r to f m a c h i n el e a m i n gh o m ea n da b r o a d 2 1 3s e m i s u p e r v i s e dl e a r n i n ga n dp e r s o n a l i z e df i n g e r p r i n ts e g m e n t a t i o n 3 1 4c l a s si m b a l a n c el e a m i n ga n dc r o s ss e l l i n g 4 1 4 1i n t r o d u c t i o nt oc l a s si m b a l a n t ep r o b l e m 4 1 4 2i n t r o d u c t i o nt oc r o s s s e l l i n gp r o b l e m 5 1 5d e c l a r a t i o no f s o m ei n t e r c h a n g a b l et e r m si nt h et h e s i s 6 1 6o r g a n i z a t i o no f t h et h e s i s 6 c h a p t e r2s e m i s u p e r v i s e dl e a r n i n ga n d i t sa p p l i c a t i o ni nf i n g e r p r i n ts e g m e n t a t i o n 8 2 1f i n g e r p r i n ti d e n t i f i c a t i o na n df i n g e r p r i n ts e g m e n t a t i o n 8 2 2i m p a c to fs e n s o ri n t e r o p e r a b i l i t yt of i n g e r p r i n ts e g m e n t a t i o n 9 2 2 1n es t a t eo f t h ea r to fs e n s o ri n t e r o p e r a b i l i t y 9 2 2 2t h e o r e t i c a la n a l y s i so fs e n s o ri n t e r o p e r a b i l i t y 1 0 2 2 3d i s t r i b u t i o nd i f f e r e n c eo f d i s t i n c tf i n g e r p r i n t si nf e a t u r es p a c e l l 2 2 4i m p a c to fs e n s o ri n t e r o p e r a b i l i t yt of i n g e r p r i n ts e g m e n t a t i o na l g o r i t h m s 14 2 3an e w f i n g e r p r i n ts e g m e n t a t i o nf r a m e w o r k ：p e r s o n a l i z e df i n g e r p r i n t s e g m e n t a t i o n 1 7 2 4g r a p h - b a s e ds e m i - - s u p e r v i s e dl e a r n i n ga n di t sa p p l i c a t i o nt of i n g e r p r i n t s e g m e n t a t i o n 18 2 4 1g r a p h b a s e ds e m i s u p e r v i s e dl e a r n i n gm e t h o d s 18 2 4 2l a b e lp r o p a g a t i o nb a s e do nl i n e a rn e i g h b o ra s s u m p t i o n 18 2 4 3n e p r o p o s e da l g o r i t h ma l l n p 1 9 2 5e x p e r i m e n t a lr e s u l t s 2 2 2 6c o n c l u s i o n ：1 5 c h a p t e r3c l a s si m b a l a n c el e a r n i n ga n di t sa p p l i c a t i o nt oc r o s ss e l l i n g 2 7 3 1r e s e a r c ho nc l a s si m b a l a n c el e a m i n g 2 8 31 1d o m a i n sw h e r ec l a s si m b a l a n c ep r o b l e me x i s t s 2 8 山东大学硕士学位论文 3 1 2a c a d e m i ca c t i v i t i e so nc l a s si m b a l a n c el e a r n i n g 2 8 3 1 3p e r f o r m a n c em e t r i c sf o rc l a s si m b a l a n t el e a m i n gm e t h o d s 2 9 3 1 4r e s e a r c ho nc l a s si m b a l a n t el e a m i n g 3 0 3 1 5d i s c u s i o n o nc l a s s i m b a l a n c e l e a m i n g 3 1 3 2a p p l i c a t i o no fc l a s si m b a l a n c el e a r n i n gt oc r o s ss e l l i n g 3 2 3 2 1i n t r o d u c t i o nt oc r o s ss e l l i n g 3 2 3 2 2p r o b l e ms t a t e m e n ta n da n a l y s i s 3 2 3 2 3m o d e lb u i l d i n gp r o c e s s 3 3 3 2 4p e r f o r m a n c ee v a l u a t i o na n dc o m p a r a s i o n 3 9 3 2 4d i s c u s s i o no ne n s v m 4 0 3 3c o n c l u s i o n 4 0 c h a p t e r4c o n c l u s i o na n df u t u r ew o r k 4 2 r e f e r e n c e s 4 3 a c k n o w l e d g e m e n t s 5 1 p u b l i c a t i o n s ! ；：； h o n o r sa n da w a r d s 5 4 - ， ，i 一一 山东大学硕士学位论文 摘要 随着信息技术的发展，尤其是数据获取技术和数据存储技术的发展，人们几 乎可以随时随地获取数量巨大的数据，并存储下来。然而，数据本身的价值有限， 如果没有一种有效的工具帮助我们对数据进行分析和处理、把数据转化成知识， 面对数量庞大的数据，我们就显得束手无策。幸运的是，机器学习和数据挖掘为 我们提供了一种数据分析和挖掘的工具。机器学习是指系统根据经验改善自身的 性能。在过去的三十年里，机器学习研究获得了前所未有的发展，并在多个领域 取得了成功的应用。本文以生物特征识别中指纹图像分割和商业领域中的交叉销 售问题为背景，深入开展了机器学习算法的应用研究。 指纹图像分割是指纹识别中的一个重要的预处理步骤。指纹分割的目的是把 包含指纹纹理特征的前景从背景图像中分割出来。传统的指纹分割算法都是使用 手工分割的指纹图像通过监督学习或者是依靠专家的经验构建一个分割模型，耗 费大量的人力。随着基于生物特征的身份认证的应用领域的不断扩展，网络环境 下的指纹识别面临着设备互操作性问题。与传统的分割算法利用多幅指纹的共性 信息进行分割不同的是，本文提出了一种只依靠输入指纹自身的信息，通过半监 督学习技术训练一个分割模型，实现了个性化指纹分割，具有良好的设备互操作 性，而且，训练模型时不再需要手工分割后的指纹图像作为训练样本，提高了自 动指纹识别系统的自动化水平。 另外，本文系统研究了类别不平衡问题以及类别不平衡学习算法在交叉销售 等商业领域中的应用研究。研究指出了类别不平衡问题主要存在的应用领域，回 顾了针对类别不平衡问题举办的学术活动，列举了常用的类别不平衡学习算法的 性能度量准则，对类别不平衡四类代表性的算法进行了归类介绍；之后，以2 0 0 7 年亚太知识发现和数据挖掘竞赛任务为案例，分析了该数据挖掘任务中面临的若 干具有挑战性的问题，提出了一种用于解决交叉销售问题的集成学习方案e n s v m ， 可以有效预测潜在的交叉销售的客户，为高层管理者提供决策支持。 关键词：机器学习；半监督学习；指纹分割；类别不平衡学习：交叉销售 山东大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , e s p e c i a l l yt h ed e v e l o p m e n to f d a t aa c q u i s i t i o na n dd a t as t o r a g et e c h n i q u e s ，p e o p l eh a v et h ea b i l i t yt oa c q u i r ea n d s t o r ev o l u m e so fd a t aa ta n y t i m ea n da n y w h e r e h o w e v e r , t h ev a l u eo fd a t ai sv e r y l i m i t e d ，i fw ec a n n o ta b s t r a c tk n o w l e d g e f r o md a t a a n dw ew i l lf e e lc o n f u s e df a c e d w i t hv o l u m e so fd a t aw i t h o u tt h eh e l po fa ne f f e c t i v ea n a l y t i c a la n dm i n i n gt o o l l u c k i l y , m a c h i n el e a m i n ga n dd a t am i n i n gt e c h n i q u e sp r o v i d eu st h et 0 0 1 m a c h i n e l e a r n i n gi s d e f i n e da ss y s t e m sp r o m o t ei t s e l fv i ae x p e r i e n c e i nt h ep a s t3 0y e a r s ， m a c h i n el e a r n i n gh a sa c h i e v e dg r e a td e v e l o p m e n ta n ds u c c e s s f u la p p l i c a t i o ni n s e v e r a ld o m a i n st h a th a sn o tb e e ns e e nb e f o r e t h et h e s i sc o n d u c t sad e e pr e s e a r c ho n s e v e r a lm a c h i n el e a r n i n gm e t h o d sw i t hf i n g e r p r i n ts e g m e n t a t i o ni nb i o m e t r i c sa n d c r o s ss e l l i n gi nf i n a n c i a ld o m a i n sa sb a c k g r o u n d s f i n g e r p r i n ts e g m e n t a t i o n i sa ni m p o r t a n tp r e p r o c e s s i n gs t e pi nf i n g e r p r i n t i d e n t i f i c a t i o n t h ea i mo ff i n g e r p r i n ts e g m e n t a t i o ni s t o s e p a r a t ef i n g e r p r i n t f o r e g r o u n dw i t h t e x t u r ef e a t u r e sf r o mb a c k g r o u n do fa c q u i r e di m a g e g e n e r a l l y s p e a k i n g ，t r a d i t i o n a lf i n g e r p r i n ts e g m e n t a t i o nm e t h o d sa r es u p e r v i s e d t r a i n e dw i t h m a n u a l l ys e g m e n t e df i n g e r p r i n t so rd e s i g n e db ye x p e a s ，s ot h e ya r el a b o rc o n s u m i n g w i t ht h ea p p l i c a t i o ns c e n a r i o so fb i o m e t r i c sa sa u t h e n t i c a t i o nt e c h n i q u e sb e c o m i n g m o r ea n dm o r e ，f i n g e r p r i n ti d e n t i f i c a t i o nm e e t ss e n s o ri n t e r o p e r a b i l i t y d i f f e r e n t f r o mt r a d i t i o n a lf i n g e r p r i n ts e g m e n t a t i o nm e t h o d sw h i c hm a k eu s eo fc o m m o n i n f o r m a t i o no fl o to ff i n g e r p r i n t sw h e nt r a i n i n g ，t h et h e s i sp r o p o s e dp e r s o n a l i z e d f i n g e r p r i n ts e g m e n t a t i o nb a s e do ns e m i - s u p e r v i s e dl e a m i n gw h i c hi so n l yt r a i n e do n i n p u tf i n g e r p r i n ti m a g ei t s e l f t h en e wf i n g e r p r i n ts e g m e n t a t i o nm o d e lh a sb e t t e r s e n s o ri n t e r o p e r a b i l i t y , i sf r e eo fm a n u a lf i n g e r p r i n ts e g m e n t a t i o n ，a n di m p r o v e st h e a u t o m a t i cd e g r e eo fa u t o m a t i cf i n g e r p r i n ti d e n t i f i c a t i o ns y s t e m b e s i d e s ，t h et h e s i sc o n d u c t sas y s t e m a t i cr e s e a r c ho nc l a s si m b a l a n c ep r o b l e m a n di t sa p p l i c a t i o ni nc r o s s - s e l l i n go ff i n a n c i a ld o m a i n t h er e s e a r c hr e c o g n i z e d s e v e r a ld o m a i n sw h e r ec l a s si m b a l a n c ee x i s t s ，r e v i e w e da c a d e m i ca c t i v i t i e so nc l a s s i m b a l a n c el e a r n i n g ，i l l u s t r a t e dp e r f o r m a n c ee v a l u a t i o nm e t r i c sf o rc l a s si m b a l a n c e i l ! i 一 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - 。 _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。- 。_ _ 。_ _ 。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。 山东大学硕士学位论文 l e a r n i n gm e t h o d s ，a n ds h o w e da l li n t r o d u c t i o nt oc l a s si m b a l a n c el e a r n i n gm e t h o d s f r o mf o u rl e v e l s t h e n ，i tt o o kp a k d d 2 0 0 7d a t am i n i n gc o m p e t i t i o na sac a s es t u d y , a n a l y z e ds e v e r a lc h a l l e n g e s i nt h et a s k ，a n dp r o p o s e da ne n s e m b l ef r a m e w o r k e n s v mt os o l v et h ec r o s s s e l l i n gp r o b l e m ，w h i c hc a np r e d i c tp o t e n t i a lc r o s s - s e l l i n g c u s t o m e r s ，a n dp r o v i d e s u p p o r tt om a k ed e c i s i o nf o rm a n a g e r s k e y w o r d s ：m a c h i n el e a r n i n g ；s e m i - s u p e r v i s e dl e a r n i n g ；f i n g e r p r i n t s e g m e n t a t i o n ；c l a s si m b a l a n c el e a r n i n g ；c r o s ss e l l i n g i i i - 一 山东大学硕士学位论文 第1 章绪论 1 1 机器学习简介 机器学习是指系统根据经验改善自身的性能。机器学习是人工智能中最活 跃、应用潜力最明显的领域之一 i3 。在过去的三十余年里，机器学习研究获得了 前所未有的发展。2 0 0 1 年9 月1 4 日，来自美国宇航局在加州的喷气推进实验室 ( j e tp r o p u l s i o nl a b o r a t o r y ) 的科学家e r i cm j o l s n e s s 和d e n n i sd e c o s t e 在( ( s c i e n c e ) ) 上撰文乜 手旨出：机器学习对科学研究的每一个阶段( 观察和探索有趣的现象，生 成假设，公式化模型以解释现象，检验根据理论做出的预测，修改理论并重复上 述过程) 正起着越来越大的支持作用，而且该领域在今后的若干年内将取得稳定 而快速的发展、对科学做出更大的贡献。从他们对机器学习的评价，机器学习的 研究价值可见一斑。 机器学习的重要性毋庸置疑，近年来受到越来越多研究学者和工业界人士关 注。美国、欧洲各国都投入了大量人力物力开展研究。例如，在2 0 0 3 年，美国 国防部高级研究计划局( d a r p a ) 开始启动为期5 年的能够学习的感知助理 ( p e r c e p t i v ea s s i s t a n t t h a tl e a r n s ) 计划，即p a l 计划。p a l 计划是一个以机器学 习为核心的计划，它又包含2 个子计划：带有分布式自适应推理的自反式智能体 ( r e f l e c t i v ea g e n mw i t hd i s t r i b u t e da d a p t i v er e a s o n i n g ) ，即r a d a r 计划，和能 够学习和观察的感知智能体( c o g n i t i v ea g e n tt h a tl e a m sa n do b s e r v e s ) ，即c a l o 计划。这两个计划首期即投入近3 千万美元，承担单位为美国的知名高校和重要 企业，如卡内基梅隆大学、麻省理工学院、斯坦福大学、加州大学、波音公司等。 d a r p a 已经把机器学习技术的重要性提升到国家安全的角度来考虑。 山东大学硕士学位论文 图卜1 机器学习的应用领域 机器学习实际上是一个应用驱动的学科，其根本的驱动力是能够更好地解决 更多实际的问题。因此，机器学习在现实问题中的成功应用成为机器学习研究取 得进展的一个重要度量。目前，机器学习的一些成功的应用领域有：语音识别， 计算机视觉，生物监测，加速实验型科学研究进展等，如图1 1 所示。应用驱动 的学科特点带动机器学习研究不断向前发展，机器学习中针对不同问题需求的学 习范式层出不穷，如表1 1 所示。然而，这些学习范式大多数没有坚实的理论基 础，目前处于实验观察阶段。 表卜1 应用驱动产生的机器学习范式 学习方法 应用场景 稀疏数据的非线性方法，用于特征抽取、 流形学习( m a n i f o l dl e a r n i n g ) 维度约减。 强化学习( r e i n f o r c e m e n tl e a m i n g )对变化环境的适应，如机器人。 药物分子设计，不同的分子结构有不同 多实例学习( m u l t i - i n s t a n c el e a r n i n g ) 的药理作用。 训练数据中只有少量的有标记样本，而 半监督学习( s e m i - s u p e r v i s e dl e a r n i n g ) 且还有大量的无标记样本可用，如互联 网上的w e b 页面和图像。 对事物排序的学习，如文本检索、基于 排序学习( 1 e a m i n gt or a n k ) 内容的图像检索等。 数据流学习( 1 e a r n i n gf r o ms t r e a md a t a )对大量数据快速过滤，如网络数据报。 利用一组任务的知识帮助提高另一个相 迁移学习( t r a n s f e rl e a r n i n g ) 关任务的性能。 1 2 机器学习的国内外研究现状 2 山东大学硕士学位论文 卡内基梅隆大学是机器学习研究的重镇，也是唯一把机器学习系从计算机科 学系独立出来，使机器学习系和计算机科学系平行的知名大学，该系的系主任 t o mm i t c h e l l 教授，是国际机器学习届的领军人物之一，同时，也是著名的机 器学习一书3 的作者。此外，俄勒冈州立大学的t h o m a sgd i e t t e r i c h ，还有同 时兼任加利福尼亚大学伯克利分校计算机系和统计系这两个系的m i c h a e li j o r d a n 教授，都是国际机器学习界非常知名的学者。 国内方面，自2 0 0 2 年起，由复旦大学陆汝钤院士、南京大学周志华教授、中 科院自动化所王珏研究员等人发起的机器学习研讨会( 前两届称之为智能信息处 理研讨会，后来更名为机器学习研讨会) ，先后在复旦大学、南京大学、南京航 空航天大学等大学成功举办。以其“学术至上，一切从简”的办会理念，和不收 取任何形式的注册费的办会风格，以及邀请中国大陆地区和香港地区的知名学者 做最前沿的讲座的形式，使其成为了一个盛会。第一届讨论会只有十余人参加， 而最近几年的机器学习研讨会每次都有3 0 0 余人参加，场面很是壮观。每年一次 的机器学习研讨会( m l a ) 和每两年一次的中国机器学习会议( c c 地) 已成为 中国机器学习界学者和学生的最主要学术交流和相互学习的平台。同时，也在国 内掀起了一股研究机器学习的热潮。 需要说明的是，尽管机器学习研究不断取得重要研究进展，但它仍然面临着 不少挑战，例如，如何提高模型泛化能力，如何加快模型的训练和测试速度，如 何增强模型的可理解性，如何处理高维数据，如何安全有效地利用无标记数据， 如何解决问题中的类别不平衡性和代价敏感性等。可以说，机器学习的研究任重 道远。 1 3 半监督学习与个性化指纹分割 半监督学习h 3 是分类学习的一种特殊形式。传统的监督学习算法只是利用有 标记的样本集进行学习。然而，在大多数的实际应用中，一方面，样本的类别标 记常难以获取，或者是对获取的样本进行标记要耗费大量的人力、财力；另一方 面，无标记样本可能相对容易采集和获取，但是，之前几乎没有好的办法能够把 采集到的大量的无标记的样本有效利用起来。为了解决这一问题，半监督学习应 山东大学硕士学位论文 运而生，它不但利用了带类别标记的样本集，而且，充分利用了大量的无标记样 本。在理论研究和应用实践中，半监督学习算法因为不但需要较少的人力，而且 能获得较高的分类性能等方面的优势，倍受青睐。广义上的半监督学习算法除了 t 包含半监督分类算法外，还包括半监督聚类算法和半监督回归学习算法。 指纹分割啼1 是指纹识别中特征提取之前的一个重要的预处理步骤。指纹分割 的目的是把包含高质量的指纹纹理的前景区从背景、低质量的前景区和不可恢复 前景区中分离出来。有效的指纹分割不仅可以降低指纹识别中后续步骤的计算复 杂度，而且可以提高指纹识别系统的整体性能。传统的指纹分割算法大都利用不 同指纹图像的共性信息进行指纹图像的分割，但是这种方法的一个显著的缺点是 当一幅新输入的指纹图像与参与i j i i 练分割模型的图像在特征空间分布有显著不 同时，使用训练好的分割算法对该图像进行分割的效果就非常糟糕。为了解决以 上问题，本文第二章提出了一种新的指纹分割的框架，即个性化指纹分割，它不 再使用多幅指纹图像的共性信息，而是利用每幅指纹图像自身的信息，为每幅指 纹图像学习一个分割模型。本文提出的个性化指纹分割模型的获得通过半监督学 习来实现。 一 1 4 类别不平衡学习与交叉销售问题 1 4 1 类别不平衡概述 传统的机器学习和数据挖掘算法一般都假设( 或潜在假设) 目标类别的先验 概率相近。然而，在现实世界的应用中，如石油管道泄漏检测、网络入侵检测和 欺诈检测，目标类别的先验概率相近的假设难以成立。在这些问题中，大多数的 示例被标记为一种类别，称为多数类( m a j o r i t yc l a s s ) ；而较少数的示例被标记为 另一种类别，称为少数类( m i n o r i t yc l a s s ) 1 。上述问题被称为类别不平衡问题哺吲。 在学习任务中，如果用于学习的数据集中，两类示例在数目上差距比较大，我们 就称该数据集为类别不平衡的数据集( i m b a l a n c e dd a t as e t s ) 。针对类别不平衡数 据上的学习，称为类别不平衡学习( c l a s si m b a l a n c el e a r n i n g ) 。一般情况下，在类 别不平衡问题中，我们更关注少数类。然而，传统的机器学习算法会被多数类所 1 如无特殊说明，本文仅讨论两类分类问题。 4 e 山东大学硕士学位论文 淹没，而忽视少数类，导致学习算法的分类性能较差，尤其是类别不平衡性非常 严重的时候( 比如，多数类和少数类的示例数目之间的比例超过1 0 0 ：1 ) 。由于 广泛存在于诸多应用领域中，近年来，类别不平衡问题吸引了越来越多的研究者 的关注，并已经成为机器学习中的一个热门研究方向。 广义上的类别不平衡有两种存在形式：类内不平衡( w i t h i n c l a s si m b a l a n c e ) 和类间不平衡( b e t w e e n c l a s si m b a l a n c e ) 阳】。类内不平衡是指数据集中每个类的样 本由多个聚类簇( c l u s t e r ) 构成，同一个类内不同的聚类簇的样本数目是不均衡 的、差距较大；而类间不平衡是指数据集中不同的类别之间的样本在数目上差距 较大。类内不平衡关注同一个类内不同的聚类簇之间的样本数之间的均衡关系， 而类间不平衡关注两类之间总体的样本数之间的均衡关系，如图卜2 所示。我们 通常所说的类别不平衡是狭义上的类别不平衡，即类间不平衡：而广义上的类别 不平衡包括类内不平衡和类间不平衡。该领域内绝大多数的研究也都是针对狭义 上的类别不平衡问题。 - 叁尝 曩一一 ( a ) 类内不平衡( b ) 类间不平衡 图1 - 2 类别不平衡示意图，图中红色。和蓝色代表两类不同的样本 1 4 2 交叉销售问题 所谓交叉销售( c r o s ss e l l i n g ) n 割，就是在现有客户身上挖掘、发现客户的多 种需求，并通过满足其需求而实现销售多种相关的服务或产品的营销方式。交叉 销售是从横向角度开发产品市场。啤酒和尿布的故事是经典的交叉销售案例。在 超市里，有一个有趣的现象：尿布和啤酒经常摆在一起出售。但是这个貌似奇怪 的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃 叁 山东大学硕士学位论文 尔玛连锁店超市的真实案例，并一直为商家所津津乐道。一个直观的解释是：妇 女们经常会嘱咐她们的丈夫下班后到超市为孩子买尿布，而丈夫在买尿布的同 时，又顺手买回自己爱喝的啤酒。因此，啤酒和尿布在一起购买的机会还是很多 的。交叉销售有两大主要功能：其一，通过增加客户的转移成本，从而增强客户 忠诚度，客户购买本公司的产品和服务越多，客户流失的可能性就越小：其二， 降低边际销售成本，提高利润率。实践证明，将一种产品和服务推销给一个现有 客户的成本远低于吸收一个新客户的成本。来自信用卡公司的数据显示：平均说 来，信用卡客户要到第三年才能开始有利润。由此可见，吸收新客户的成本是非 常高的，而对现有客户进行交叉销售，也自然成为许多公司增加投资回报的捷径。 本文基于2 0 0 7 年亚太知识发现和数据挖掘竞赛( p a k d dc o m p e t i t i o n2 0 0 7 ) 提供的数据集，以案例的形势，分析了交叉销售问题中存在的困难问题，如类别 不平衡问题和代价敏感问题，并针对存在的困难问题给出了机器学习的解决方 案。 1 5 本文使用的术语等价性声明 由于机器学习是一个交叉学科，它吸引了计算机科学、统计学、神经科学、 认知科学等及其他各种机器学习应用领域研究者的兴趣，导致机器学习中的某些 专业术语不统一。为了避免不同研究领域的研究者阅读本文时由于专业术语不一 致造成的可能的困扰，本文特将与本文相关的几组等价的专业术语定义如下。 样本( s a m p l e ) ，样例( e x a m p l e ) ，示例( i n s t a n c e ) 特征( f e a t u r e ) ，属性( a t t r i b u t e ) ，描述子( d e s c r i p t o r ) ，变量( v a r i a b l e ) 学习( 1 e a r n i n g ，l e a r n ) ，分类( c l a s s i f i c a t i o n ，c l a s s i f y ) 分类器( c l a s s i f i e r ) ，学习器( 1 e a m e r ) ，学习算法( 1 e a m i n gm e t h o d o r a l g o r i t h m ) 类别不平衡( c l a s si m b a l a n c e ) ，类间不平衡( b e t w e e nc l a s si m b a l a n c e ) 1 6 本文的组织结构 6 山东大学硕士学位论文 全文分为四章。第一章是本文的绪论部分，对本文的工作进行了概要性的介 绍。其中，第一节介绍了机器学