（应用数学专业论文）数据挖掘在电信客户流失预测中的应用.pdf

中山大学应用数学硕士学位论文 数据挖掘在电信客户流失预测中的应用 应用数学 硕士生：潘嘉林 指导老师：姚正安教授 摘要 随着电信行业的垄断格局被打破，市场激烈的竞争逼使电信运营商选择技术 含量更高的数据挖掘手段，提高企业的分析能力及市场竞争力。在电信行业，争 取一个新客户的代价往往比留住一个老客户的代价要大得多，因此，客户流失预 测是电信运营商最为关心的重点之一。客户流失预测的分析对象是已经流失和没 有流失的客户，从他们的行为找出流失客户的特征，然后预测客户未来一段时间 的流失概率。这是一个时间序列分类问题。然而，目前对中国电信而言，真正流 失的客户占总客户的比例非常小。对于这种不平衡数据的挖掘问题，无论在数据 挖掘领域还是在机器学习领域都是一大难题。针对中国电信的需求，本文提出了 两种基于时间特征提取( f e a t i 将b a s e d ) 及支持向量机( s v m ) 的时间序列分类方案。 第一种方案称为e m + s v m 。主要思想是利用e m ( e x p e c t a f i o nm a x i m i z a t i o n ) 迭代 算法的思想把s v m ( s u p p o r t v e c t o rm a c h i n e ) 应用于不等长的时间序列分类中。第 二种方案称为m s n f e + s v m ( m e a n s t d - n o r mf e a t u r ee x t r a c t i o n 。m s n f e ) 。主 要思想是利用分层的思想，把不等长的时间序列映射为固定长度的时间特征向 量，然后用s v m 进行训练、预测。从实验的结果可以看出，这两种方案在处理 不平衡时间序列的分类问题时仍然有比较理想的结果。 关键字：支持向量机，客户流失，时间序列分类 中山大学应用数学硕士学位论文 d a t am i n i n gi np r e d i c t i n gc u s t o m e r sc h u r n i n gf o r t e l e c o m m u n i c a t i o n si n d u s t r y a p p l ym a t h e m a t i c s n a m e ：p a nj i a l 洫 s u p e r v i s o r ：y a oz h e n g a n a b s t r a c t w i t i lt h e b r e a k i n g o f m o n o p o l y i nt e l e c o m m u n i c a t i o n s i n d u s t r y ， t e l e c o m m u n i c a t i o n se n t e r p r i s eh a v et o i n c o r p o r a t ed a t am i n i n gi n t om a r k e t i n g a n a l y z i n gi no r d e rt os u r v i v ei nt h ec o m p e t i t i o n i tt a k e sm o r ec o s tt og e tan e w c u s t o m e ri nt e l e c o m m u n i c a t i o ni n d u s t r y s op r e d i c t i n gc u s t o m e r sc h u r n i n gi so n eo f t h em o s t i m p o r t a n t a t t e n t i o n sf o rt e l e c o m m u n i c a t i o n e n t e r p r i s e p r e d i c t i n g c u s t o m e r sc h u r n i n gi st op r e d i c tt h ep r o b a b i l i t yo ft h ec u s t o m e r sw h ow a n tt o s w i t c hf r o mt e l e e o mc h i n a ss e r v i c et oo t h e r s ，b ya n m y z i n gt h e i rb e h a v i o r s h o w e v e r , t h en u m b e ro fc u s t o m e r sc h u r n i n gf r o mt e l e c o mc h i n ai ss m a l l t h ed a t a i sv e r yu n b a l a n c e m i n i n gi nt h eu n b a l a n c ed a t ai sd i f f i c u l tb o t hi nd a t am i n i n ga n d m a c h i n el e a r n i n g i nt h i st h e s i s ，w ep r o v i d et w oa p p r o a c h e sf o rt h et a s k o n ei s c a l l e d “e m + s v m ”i t i n c o r p o r a t e se m ( e x p c c t a t i o nm a x i m i z a t i o n ) a n d s v m ( s u p p o r tv e c t o rm a c h i n e ) i n t ot i m es e r i e sm i n i n g t h eo t h e ri sc a l l e d m s n f e + s v m ，m s n f ei ss h o r tf o rm e a n - s t d - n o r mf e a t u r ee x t r a c t i o n i tm a k e st h e f e a t u r ee x t r a c t i o nf r o mt h et i m es e r i e sb ym s n f em e t h o d , a n dt h e nu s e ss v ma s c l a s s i f i c a t i o na tl a s t a tt h er e s u l t w ep r o v eo u ra p p r o a c h e sw o r kw e l lf o rt h et a s k k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e ( s v m ) ，c u s t o m e r sc h u r n i n g ， t i m es e r i e sc l a s s i f i c a t i o n 1 1 中山大学应用数学硕士学位论文 第1 章前言 本章首先介绍本文的研究背景，然后进一步明确本文的研究范围和研究意 义，最后介绍本文的主要内容以及体系结构。 1 1 背景介绍 随着人们逐渐认识到数据挖掘的威力，数据挖掘在各行业中的应用越来越普 及。电信行业是数据挖掘最早的商业应用领域之一。在国内，随着电信垄断格局 的打破，中国电信已经不再是固定电话的唯一运营商，其他运营商在争取新客户 的同时，提供各种优惠政策力图从中国电信手中把旧客户抢走。为了在越发激烈 的竞争中立于不败之地，提高市场竞争力，近年来，中国电信也开始走上运用数 据仓库、数据挖掘技术进行市场分析、客户管理的道路。其目的就是巩固自己在 电信市场上的领导地位。因此客户流失是中国电信最为关心的重点之一。导致客 户流失( c h u m ) 的原因有多种，根据流失原因的不同，可将流失分为主动流失 ( 客户对服务质量不满或其他原因主动选择流失) 和被动流失( 由于欠费或信用 方面的原因，客户被动接受流失) ，我们更关心的是前一种流失。客户流失预测 的分析对象是已经流失和没有流失的客户，通过对他们在过去一段时间内行为 ( 主要体现在话费清单上) 的分析，找出流失客户的特征，然后预测客户未来一 段时间的流失概率，以便中国电信能够针对流失概率高的客户提前采取挽留的措 旄。这实际上是一个不等长的时间序列的分类问题。 由于中国电信长期以来的垄断地位，现阶段绝大部分的客户都在使用中国电 信提供的服务，很多客户暂时还没有打算放弃中国电信提供的服务转而使用其他 运营商提供的服务。只有- - d 部分的客户出于某些原因，决定不再使用中国电信 的服务。这部分客户大概只占中国电信总客户的5 左右。客户流失预测的任务 就是把这5 的流失客户识别出来。在这种极不平衡的数据上进行分类是件非 常困难的事情。 中山大学应用数学硕士学位论文 1 2 相关工作及本文的意义 对于不等长时间序列的分类问题，一般有两种策略，一种是基于马尔可夫模 型( m a r k o vm o d e l ) 的方法 3 2 ，3 3 ，3 5 】以及基于隐马尔可夫模型的方法( h i d d e n m a r k o vm o d e l ，h m m ) 3 2 ，3 4 ，3 5 ，因为其算法本身就具有解决不等长序列问题的 特点；而另一种策略是首先提取时间序列的特征，如时问序列的统计量：均值、 方差、标准差等，从而不等长的时间序列映射成维数相等的特征向量，再用经典 的分类算法进行分类。h m m 及m a r k o vm o d e l 在很多应用中都取得了十分理想 的效果，但这两种算法都有一个前提，就是必须知道每一时刻对应的状态( s t a t e ) 。 文献【3 5 】介绍了一种基于m a r k o vm o d e l 的挖掘电信客户行为的方案，文中把客 户在不同时刻使用不同运营商的服务作为客户在该时刻对应的状态。但这对本文 的模型并不适用，因为本文所得到数据中并不包含客户在哪个时刻使用哪个运营 商服务的信息。另外对本文的话费时间序列而言，定义不同时刻对应的状态较为 困难。而基于时间特征提取的分类策略。传统的做法是对每条时间序列，用整条 序列的备种统计量生成特征向量，然后用判别( d i s c r i m i n a t i v em o d e l ) 的分类算法， 如神经网络，支持向量机( s v m ) 等进行分类。 在数据挖掘的其他商业应用领域也同样遇到不平衡数据的分类问题，比如近 年兴起的市场直销手法。所谓市场直销就是企业找出认为有购买潜力的客户，通 过发电子邮件、电话的方式向这些客户介绍最新的产品及近期的企业活动，其目 的是有效地利用资源以获取最大的回报。直销是否成功的一个关键就是找出的认 为有购买潜力的客户是否正确，以及这些客户的购买能力有多少。而实际上有购 买潜力的客户的比例相当小，如k d d c u p 9 8 1 提供的数据集中，只有5 的客 户是有购买潜力的客户。【2 】提出了一种名为m e t a c o s t 的方法，其主要思想是在 考虑客户的购买潜力的概率的同时，把对不同客户错分的代价也考虑进去。 3 】 则是把可能获得的利润考虑进去。但这两种方法都有两个前提，第一，对不同客 户，错分的代价是不相同的，第二，需要明确知道客户错分的代价或不同客户可 能带来的利润。但对于电信客户流失预测这个模型，这两种方法并不适用。因为 尽管把流失客户预测为没有流失客户的代价要比把没有流失客户预测成流失客 户的代价大，但是具体的代价是多少并不知道。 2 中山大学应用数学硕士学位论文 而在其他应用领域，例如生物信息挖掘、文本挖掘也存在同样的问题，文献 【4 】提出了一种基于支持向量机的改进算法o n e c l a s ss v m ，用于高维分布的 估计。文献 5 】 6 】【7 】分别把它应用于图象检索、文本分类及生物信息挖掘中，并 取得了不错的效果。 本文针对特定的时间序列分类问题电信客户流失的预测，提出了两种基 于时间序列特征提取及支持向量机分类的方案。一种称为m s n f e + s v m ，是运 用分层的思想，对时间序列分层，把每一层的统计量作为时间序列的新特征，从 而把不等长时间序列映射成维数相等的特征向量，形成新的样本空间，然后再用 支持向量机进行学习、预测。另一种成为e m + s v m ，是用e m 迭代的思想找出 每条已经流失的时间序列中最有代表性的月份，并生成一些能够反映之前一段时 间行为变化的时间特征，组成新的样本集合，然后用支持向量机进行预测。本文 把这两种方案应用于中国电信提供的真实数据集上，实验结果证明，这两种算法 都能够较好地解决这个不平衡数据的时间序列分类问题。本文最后还比较了这两 种方案的优劣。 1 3 本文主要内容 文章接下来的部分是这样安捧的。文章第二部分，首先简单介绍数据挖掘的 概念、挖掘的流程及一些商业应用中常用的方法。文章第三部分，先简单介绍机 器学习的任务及统计学习理论的概念，然后重点介绍与本文密切相关的数据挖掘 算法一支持向量机及其一些“变种”。文章第四部分，介绍电信客户流失预测 的任务及挖掘过程中的重点、难点所在。然后针对特定的问题提出了两种用于不 等长时间序列分类的方案：e m + s v m 方案和m s n f e + s v m 方案。文章第五部分 通过大量的实验来验证这两种方案，并比较这两种方案的优缺点。第六部分，总 结全文，提出下一步工作的想法。 中山大学应用数学硕士学位论文 第二章数据挖掘简介 在介绍客户流失预测模型之前，我们有必要先简单地了解数据挖掘的有关背 景知识以及在应用中常用的方法。 2 1 概述 数据挖掘( d a t am i n i n g ) 是近年来随着人工智能、机器学习和数据库技术的 发展而出现的一门新兴的技术，就是从海量的、有噪声的、不完全的数据中，提 取隐含的但有用的信息和知识的过程。 数据挖掘的起源来f 1 2 0 世纪6 0 年代开始的统计分析和神经网络研究。数据挖 掘其实是一个逐渐演变的过程。电子数据处理的初期，人们就试图通过某些方法 来实现自动决策支持，当时成为人们关心的焦点。而机器学习是用计算机模拟人 类学习的一门科学，其目的是想使计算机同人类一样具备学习能力，从学习过程 中总结并生成规律，从而能够智能地分析问题，解决问题。随后，随着神经网络 技术的形成和发展，人们的注意力转向知识工程，知识工程不同于机器学习那样 通过对计算机输入范例，让它生成出规则，而是直接给计算机输入已被代码化的 规则，而计算机通过使用这些规则来解决某些特定问题。专家系统就是应用这种 技术所得到的成果。2 0 世纪8 0 年代，随着神经网络迎来第二次革命，以及在专家 系统开发中，知识获取的“瓶颈”现象越发严重，于是人们又重新回到机器学习 的方法上，并将其成果应用于处理大型商业数据库。2 0 世纪8 0 年代末出现了一个 新的术语，即数据库中的知识发现，简称k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 。 k d d 是从数据中发现模式或描述数据间的联系的过程，其主要步骤包括数据选 择、数据预处理、数据转换、数据挖掘、结果解释及评估【8 】，如图2 1 所示。 4 中山大学应用数学硕士学位论文 图2 1 k d d 的步骤 数据挖掘只是k d d 中的一个阶段，却是最重要的一个阶段，所以人们往往 不加区别地使用两者，一般在工程应用领域多称为数据挖掘，而在研究领域则多 称为数据库中的知识发现。因此，在本文以下部分将不再区分数据挖掘与数据库 中的知识发现这两个概念。 目前数据挖掘已经广泛地应用于商业市场【9 】以及科学数据的分析上【1 0 】。例 如，针对蛋白质和d n a 序列数据分析的数据挖掘【1 l 】，用于检测网络入侵的数 据挖掘 1 2 1 ，针对金融数据分析的数据挖掘 1 3 ，1 4 】，电信业中的数据挖掘 1 5 ，1 6 1 。 数据挖掘在电信行业的应用领域主要有客户关系管理、客户欺诈分析、客户流失 预测、客户消费模式分析和市场推广分析等【1 5 】。 2 2 数据挖掘的分析模型及算法 2 2 1 数据挖掘的分析模型 数据挖掘是一个交叉学科领域，受多个学科影响，如图2 - 2 所示，包括数据 库技术、统计学、机器学习、信息科学、可视化技术等 1 7 1 。各个学科薪的研究 成果促使数据挖掘技术日趋成熟。 中山大学应用数学硕士学位论文 图2 2 在数据挖掘中，没有哪种方法可以解决所有的问题，不同的实际问题，必须 结合特定的背景知识，采用不同的数据挖掘方法，有的问题甚至需要结合多种方 法共同进行解决。一般地，在实际应用中，具体使用哪些方法主要取决予问题的 类型以及数据的类型和规模。 数据挖掘的方法一般分为预测型和描述型【1 8 】，如图2 - 3 所示。预测型的方 法一般有分类、预测、回归分析、时间序列分析四种，而描述型则分为聚类分析、 关联分析、序列匹配三种。 图2 3 6 中山大学应用数学硕士学位论文 2 2 2 数据挖掘的算法 数据挖掘常见的算法主要有决策树、贝叶斯网络、遗传算法、神经网络 ( a n n ) 、k 近邻算法( k n n ) 、规则推导、回归分析、判别分析、聚类分析、 主成分分析 1 7 ，1 9 ，2 0 及支持向量机( s v m ) 【2 0 ，2 1 ，2 2 ，2 3 1 等。目前最流行的算法 是2 0 世纪9 0 年代由v a p n i k 提出的支持向量机【2 1 ，2 2 。它是在统计学习理论的 基础上发展起来的新一代机器学习算法。近年它已经被广泛地应用于数据挖掘、 模式识别、生物信息等多个领域，并取得了巨大的成功。 2 3 本章小结 数据挖掘的根本任务是从数据中挖掘知识，获取知识。近年来，它不但广泛 应用于商业领域，而且已经引起了不同学科领域的研究人员的关注。广大科学工 作者都希望把数据挖掘技术有效地应用于自己的领域，寻求突破。而另一方面， 数据挖掘又是一个交叉的学科领域，而且越来越多学科领域的知识、技术渗入到 数据挖掘领域中。 但是，对数据挖掘影响最大的学科始终是机器学习与统计学。因此本文主要 是从机器学习及统计学方法的角度对数据挖掘进行描述，文中不涉及数据仓库、 o l a p 、关联规则等技术的讨论，对这方面有兴趣的读者可以参阅 1 7 ，2 4 。 本文的下一章，我们会具体介绍机器学习及新一代机器学习算法一支持向 量机。正是支持向量机的出现，为机器学习领域的发展，注入了一股新的动力。 中山大学应用数学硕士学位论文 3 1 机器学习概述 第三章支持向量机 机器学习作为人工智能的一个分支，是一个致力于有关学习过程中计算方法 的开发和研究，以及应用计算机学习系统解决实际问题的领域。机器学习中一个 重要的研究内容就是从样本中获取相应的概念描述方法。样本表示可以采用多种 形式，尤其是可以采用二维关系数据表形式来表示，因此许多机器学习方法可被 直接应用于解决数据挖掘问题，并起着重要的作用。 机器学习的研究主要经历了如下几个阶段 1 9 , 2 0 ，2 1 ，2 2 ，2 5 ： 1 、1 9 4 3 年m c c u l l o c h 和p i t s 对神经元模型( 简写为m p 模型) 的研究： 2 、五十年代，在控制理论中，使用多项式等为基函数，利用优化的方法建 立模型，以刻画被控对象的行为，这个过程在控制理论中称为辨识或参数估计； 3 ，、r o s e n b l a t 的感知器为代表的研究，则是从m p 模型出发将其扩展为多个 神经元的m p 模型作为优化算法的数学基函数； 4 、v a p n i k 提出了“统计学习理论”： 此外，z d z i s k e wp a w l a k 在1 9 8 2 年提出的粗糙集：( r o u g hs e t ) 理论也有一定的特 色。它是一种新的数学工具，可以用于处理含糊性与不确定性，在数据挖掘中发 挥了重要作用。 目前，机器学习的研究己不仅是人工智能研究的重要问题，而且已经成为计 算机科学与技术的核心问题之一。这种动力来源于数字网络的普及与计算机对社 会生活的普遍渗入。由此，根据需求，提出了一些迫切的问题【2 5 】：( 1 ) 发现海量 数据中的规律，特别是那些非结构化的数据。这方面主要的发展是数据中的知识 发现；( 2 ) 如何对个性化的需求进行处理和分析。 预测学习方法( 包括分类) 是机器学习的一个重要研究领域，绝大部分机器 学习算法的应用都涉及到对数据的预测性学习，目的是从已知数据中估计相关性 以达到准确预测将来数据的变化。经典的模式识别方法，各种统计方法以及近年 来出现的各种神经网络算法都被应用于估计这种数据中固有的相关性，试图建立 中山大学应用数学硕士学位论文 一个能预测未来数据的模型。虽然，这些应用在一些特殊的领域取得了一定的进 展，并且提出了一些新的概念和方法，但是，这些方法有其固有的算法缺陷：由 于不知道数据的分布密度以及有限的训练数据，常常导致了病态的训练结果，预 测效果往往不尽人意，人们迫切需要关于预测学习算法共同的概念和理论框架以 及更高效的预测学习方法。到目前为止，几乎所有的预测学习算法都可以归结为 以下三类【2 6 】： ( 1 ) 传统的统计预测方法 这类方法是在参数结构形式已知的前提下，通过训练数据，预测各参数的值， 例如：最小二乘法。应用这些预测方法除了需要很强的先验知识外，还需预先知 道模型的结构形式。但是，在处理大量的实际预测问题时，常常不知道背景知识， 面对一大堆采样来的数据，也不知道模型的结构形式。由于传统统计学研究的前 提是样本数目趋于无穷大时的渐近理论，而参数预测方法几乎都是建立在这一前 提基础之上的。因此只有当采样数据趋于无穷时，参数方法的训练结果才趋于真 实的模型。由于实际样本数目是有限的，很难满足这一前提。 ( 2 ) 经验非线性预测方法 8 0 年代发展起来的人工神经网络和柔性统计方法就属于这一类。虽然，这些 新的方法克服了参数预测方法的部分弱点，能够依照需要，假设数据内在相关性 而构造非线性模型。然而，这些非线性方法缺乏统一的数学理论基础，通常是从 生物学的理论和一些学术流派中得到灵感，对于诸如神经网络中的结构选择和权 重的初值设定，仍需要借助于经验，得到的模型通常是局部最优解，而非全局最 优。 ( 3 ) 统计学习理论 早期的统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 是从6 0 年代发展起来的 【2 7 ，直至l j 9 0 年代，它一直是作为一种针对有限样本的函数预测问题的纯理论分 析工具 2 8 1 。虽然，早期的统计学习理论提出t v c 维( v a p n i k c e r v o n e n k i s ) 理论 2 9 ，为衡量预测模型的复杂度，提出了有效的理论框架。但是，它仍然是建立 在经验风险最小化原则基础之上，即：以训练的平均误差为最小的模型作为期望 的最终模型。所以。早期的统计学习理论一直停留在抽象的理论和概念的探索之 中，直到9 0 年代初期，v c 维理论还没有得到很好的应用【2 6 】。9 0 年代中期，v a p n i k 9 中山大学应用数学硕士学位论文 和他的a t & t b e l l 实验室小组提出了s v m 算法，进一步丰富和发展了统计学习理 论，使它不仅是一种理论分析工具，还是一种能构造具有多维预测功能的预测学 习算法的工具，使抽象的学习理论能够转化为通用的实际预测算法。 在统计学习理论基础之上发展起来的s v m 算法，是一种专门研究有限样本 预测的学习方法。与传统统计学相比，s v m 算法没有以传统的经验风险最小化 原则作为基础，而是建立在结构风险最小化( s t r u c t u r a l 硒s km i n i m i z a t i o n ，s r m l 原理基础之上，发展成为一种新型的结构化学习方法。它能很好的解决有限数量 样本的高维模型的构造问题，而且所构造的模型具有很好的预测性能。s v m 算 法有很多成功的应用都说明了这种基于v c 维理论而发展起来的结构化学习方法 的潜在优势。本章的以下部分将详细介绍支持向量机算法及其一些“变种”。 3 2 支持向量机 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理 基础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精度， a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷，以 期获得最好的推广能力( g e n e r a l i z a t i o na b i l i t y ) 。支持向量机方法的几个主要优点 有： l 、它是专门针对有限样本情况的。其目标是得到现有信息下的最优解而不 仅仅是样本数趋于无穷大时的最优值； 2 、算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全 局最优点，解决了在神经网络方法中无法避免的局部极值问题； 3 、当遇到非线性可分的实际闯题时，算法通过非线性变换转换到高维的特 征空间( f e a t u r es p a c e ) ，在高维空间中构造线性判别函数来实现原空间中的非线 性判别函数，特殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数 问题，其算法复杂度与样本维数无关。 1 0 中山大学应用数学硕士学位论文 3 2 1 线性支持向量机 支持向量机是从线性可分情况下，寻找最优分类面的问题发展而来的。其基 本思想为：寻找一个满足分类要求的最优分类超平面，使得该超平面在保证分类 精度的同时，最大化超平面两侧的空白区域；从理论上来说，支持向量机能够实 现对线性可分数据的最优分类。具体来说，从最简单的情况开始：考虑图3 一l 所 示的二维豫类线性可分情况 玛 图3 - 1 图中实心点和空心点分别表示两类的训练样本，为把两类没有错误的分 开的分类线，马、皿分别为过各类样本中离分类线最近的点且平行于分类线的 巍线，那么日和之间的距离即两类的分类间隔( m a r g m ) 。所谓最优分类线就 是要求分类线不但能将两类无错误的分开，而且要使两类的分类间隔最大。前者 是保证经验风险最小( 为零) ，后者实际上是为了使置信范围最小，从而使实际 风险最小，这是对结构风险最小化原则的具体实现。推广到高维空间，最优分类 线就成为最优超平面( o p t i m a lh y p e r p l a n e ) 。 这可以用公式化形式表示如下： 假定训练数据( 而，y j ) ，i - l ，f ，x 掣，y e + l ，一1 可以被超平面w x + b = 0 分开。为使超平面对所有样本正确分类，就要求它满足如下约束： * ( t h ，+ 6 ) 一l 0 v i ( 3 - 1 ) 由于分类间隔等于2 川w i i ，于是我们可以在服从约束( 3 1 ) 式的条件下利用最小 化| | w i l 2 的方法来最大化分类间隔。因此，求解最优超平面问题就可以表示成如 中山大学应用数学硕士学位论文 下的约束优化问题：即在条件( 3 一1 ) 式的约束下，求函数 烈w ) = 扣w 2 = 圭( w w ) ，( 3 - 2 ) 的最小值。 支持向景( s u p p o r t v e c t o r s ) 就是使式( 3 - 1 ) 中的等号成立的那些样本，如图3 - 1 中用方框标出的点所示。对这些学习机器来说，支持向量是训练集中的关键元素， 它们离决策边界最近；如果去掉所有其他训练点( 或者移动位置，但是不穿越日。 或皿) ，再重新进行训练，得到的分类面是相同的。在下面的求解过程中我们可 以看到，正是支持向量而不是其他的样本点对最优超平面的求解有着至关重要的 作用。 为求解最优超平面，我们定义如下的l a g r a n g e 函数 上= 去w i l 2 一q 咒( 毛w + 6 ) + q ( 3 3 ) 其中， 0 为l a g r a n g e 系数，我们的问题是关于w 和b 对三求最小值。这就意 味着我们可以先对等的解决一个较为简单的“对偶”问题：求上的最大值，其约 束条件为三关于w 和b 的梯度均为零。以及啦0 。即我们需要在约束条件 咒q = o ，( 3 - 4 a ) 磁o , i = l ， 下对吼求解下列函数的最大值： ( 3 - 4 b ) f1i 矿 ) = q 一去q q 只乃( 五，x j ) ( 3 5 ) ，- l二，i l 如果z 为最优解，那么 w = 茸咒x 即最优超平面的权系数向量是训练样本向量的线性组合。 这是一个不等式约束下的二次函数极值问题，存在唯一解，而且，根据 k u h n - t u c k e r 条件，这个优化问题的解必须满足： 中山大学应用数学硕士学位论文 q ( t w ) - 6 y , - 1 ) = o ，i = i ，( s - 7 ) 因此对多数样本q 将为零，取值不为零的q 对应于使式( 3 1 ) 中等号成立的样本即 支持向量，它们通常只是全体样本中很少的一部分。求解上述问题后得到的最优 分类函数是： f ( x ) = s g n t 咒z ( 葺功+ 6 ) ， ( 3 8 ) 由于非支持向量对应的珥均为零，因此上式的求和实际上只对支持向量进 行。b + 是分类的阈值，可以由任意一个支持向量用式( 3 - 1 ) 求得或通过两类中任意 一对支持向量取中值求得。 在线性可分情形中。我们可以得到如式( 3 8 ) 的决策函数；接着，我们将此思 想推广到线性不可分的情况中。在线性不可分的情况下，我们在条件( 3 1 ) 中增加 一个松弛变量毒2 0 ，于是成为： 咒 ( w ) + 6 1 一直，i = 1 ，z ( 3 - 9 ) 因此，我们的目标就是在( 3 9 ) 的约束条件下求下列函数的极小值： ( w ，d = j 1 ( w w ) + c ( 喜毒) ( 3 - t 。) 即折中考虑最少错分样本和最大分类间隔，就得到了线性不可分情况下的最优超 平面，称作广义最优超平面。其中c 0 为某个指定的常数，它控制对错分样本 的惩罚程度。 线性可分的最优化问题是作为一种特殊的情形包含在刚才所述的线性不可 分的最优化问题中的。特别的，在式( 3 9 ) 和式( 3 - l o ) q a 对所有f 令= 0 即可得到 相应的线性可分情况时的形式。 线性不可分和线性可分情况的差别就在于可分情况下约束条件珥0 在不可 分的情况下换成了更严格的条件0 s 珥c 。除了这一修正，不可分情况的约束 最优化问题以及权值向量1 ，和偏差b 的最优值的计算都和线性可分情况中的过 程是相同的。 中山大学应用数学硕士学位论文 3 2 2 非线性支持向量机 对非线性问题，支持向量机将输入向量映射到一个高维的特征向量空间，并 在该特征空间中构造最优分类面。由于低维输入空间向高维特征空间映射过程 中，空间维数急速增长，这就使得在大多数情况下难以直接在特征空间直接计算 最佳分类平面。支持向量机通过定义核函数( k e r n e lf u n c t i o n ) 巧妙的将这一问题 转化到输入空间进行计算，其具体机理如下： 可以注意到在上面的问题求解中都只涉及内积运算，因此我们假设有非线性 映射：r ”- - h 将输入空间的样本映射到高维特征空间h 中，当在特征空间中构 造最优超平面时，训练算法仅使用特征空间中的点积，即( t ) 庐( 工，) 。所以，若 能找到一个函数k 使得置( 薯，x ，) = 妒( t ) 妒( x ，) ，这样，在高维空间中实际上只需进 行内积运算，甚至不必知道变换中的形式。 根据泛函的有关理论，只要函数k ( 薯，x ，) 满足m e r c e r 条件，它就对应某一 变换空间中的内积。因此，在最优分类面中采用满足m e r c e r 条件的内积函数 k ( x j ，x ) 就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加， 此时的决策函数就变为： ， f ( x ) = s g n z 咒z 足( 墨，曲+ 6 ) ( 3 1 1 ) f f i l 算法的其他条件均不变。由于最终的判别函数中实际只包含与支持向量的内积以 及求和，因此识别时的计算复杂度取决于支持向量的个数。 由图3 - 2 可以看出，支持向量机求得的决策函数形式上类似于一个神经网络， 其输出是若干中间层节点的线性组合，而每一个中间层节点对应于输入样本与一 个支持向量的内积，因此也被称作是支持向量网络。 1 4 中山大学应用数学硕士学位论文 x d 精出( 决置规划) ： y = s g n ( q _ y ，x ( 葺，工) + 6 ) i l l 权值口：y 基于s 个支持向量 ，屯。，t 的非 践性变换( 内积) 培八向量x ；( z ，x 2 i , , , 1 一) 图3 2 在式( 3 1 1 ) 中，满足m e r c e r 条件的内积函数k ( x j ，x ) 称为核函数。这里我们 给出一个具体的核函数的例子： 如图3 - 3 ( a ) 所示，数据样本五r 2 ( f = 1 ，) ，选择核函数k ( t ，砷为多项式 函数足( ，x j ) = ( x j ) 2 , 那么我们的目的是寻找一个满足如下条件的空间h 和映 射声，使得映射把数据从r 2 空间映射到日空间，并且满足( x y ) 2 = 庐( x ) 痧( y ) 。 满足该条件的日和是很容易找到的：当h = r 3 以及妒( x ) = 百 4 2 x , x 2 时即可 满足以上条件。对于一个特定的核函数，映射和特征空间的选择并不是唯一的。 癌 - _ ， _ ，。0 、+ t ， 乜 、世- j ” 4 _ 一， 一 ， 图3 3 a圈3 3 b 中山大学应用数学顼士学位论文 图3 3 表示了上述对二维样本进行分类，用二阶多项式作为映射函数的变换 过程。在图3 3 a 中，原始二维空间中必须要用一个椭圆形的非线性分类器才能分 开，而通过二阶多项式变换将数据映射到三维特征空间中如图3 3 b 所示，可以看 出两类数据用一个线性的分类面就可以分开。 支持向量机中不同的内积核函数将形成不同的算法，目前研究最多的核函数 主要有以下三种。 ( 1 ) 多项式核函数 k ( ，t ) = ( 葺) 4 ； ( 2 ) 径向基核函数( r b f ) 地刚= 唧( - 哔 ； ( 3 ) s i g m o i d 核函数 k ( 葺，) = t a n h ( v ( x x j ) + c ) 对于同一个的数据集，使用不同的核函数以及同一核函数的不同参数，其效 果都不尽相同，有时甚至相差甚远。因此如何根据数据本身的特性确定采用哪个 核函数以及如何确定核参数是当今机器学习中的一个研究热点。 3 3o h e c l a s ss v m o n e c l a s ss v m 最初是用于高维分布估计，即用来寻找超平面v c 维的估计值 【4 】。对于没有任何分类信息的训练向量x j f ，f = l ，初始问题为： 蝴r a i n la7出一p+西l善12 毒， 一石。p w 智 s 7 烈再) p 一点，( 3 1 2 ) 毒o ，i = l ，z ， 它的对偶问题为： 1 6 中山大学应用数学硕士学位论文 睁丢口7 缈， s 0 - q 西1 ，f = 1 ，( 3 - 1 3 ) e 1 口= 1 文献 3 0 ，3 1 提出用超球面代替超平面来划分数据的想法，改变了数据集的 描述。目标函数的初始问题为： ra矗in。r2+r 吉善毒， ，# ，w ：? 。 s 2 ( 毛f ) 7 ( 曩一c ) 兰r 2 一参， ( 3 ，1 4 ) 毒0 , i = l ， 通过设定参数0 y 1 ，使超球面的半径和它所能包含的训练样本数目之间 进行折衷。当y 小的时候，尽量把数据放进球里面，当p 大的时候，尽量压缩球 的尺寸。使用l a g r a n g i a n 函数来解这个优化问题。 它的对偶问题为： 呼善q q ( ) 一军噶( ) ， s ，o q 万1 ，( 3 - 1 5 ) q = l ， 通过q p 优化方法解这个对偶问题可以得到优化解口。决策函数为： ，( 工) = s i g n ir 2 一q 哆( ，_ ) + 2 q ( ，_ ) 一( x ，x ) i ， ( 3 1 6 ) 、t j 0 1 1 e - c l a s ss v m 只是对正( 或负) 的样本进行训练和测试。该方法通过把数据映 射到特征空间，并尽量用一个超球面来描述特征空间的数据，要把大部分的数据 包含到这个超球面。目前o n e - c l a s ss v m 的主要应用的对那些各类的样本个数极 不平衡且个数少的那一类错分的代价非常大的数据进行分类和识别。如网络入侵 检测、网上检索等。【6 】把对它作了适当的改进并应用于文本分类中， s l 把他应 用于图象检索中。而川则把这种方法应用于k d dc u p 2 0 0 2 的基因的预测中，并 成为当年比赛的优胜者。 中山大学应用数学硕士学位论文 3 4 本章小结 支持向量机己经初步表现出很多优于已有方法的性能。一些学者认为，统计 学习理论( s t l ) 和支持向量机( s v m ) j e 在成为继神经网络研究之后新的研究点， 并将有力地推动机器学习理论和技术的发展。正是由于s v m 具有良好的推广能 力，本文所提出的预测客户流失的两种方案都是基于s v m 改进的。 中山大学应用数学硕士学位论文 第四章电信客户流失预测的数据挖掘模型 4 1 问题描述与挑战 4 1 1 问题描述 中国电信首先根据客户的历史话费记录从数据库中挑选出一万多个认为极 有可能流失的客户，然后对这一万多个客户进行问卷调查，从反馈的结果得知在 这一万多个客户中，有8 0 0 多个客户已经流失了，其余的19 0 0 0 多个客户都还未 打算使用别的运营商的服务。但做问卷调查需要大量的人力物力，而且作为中国 电信来讲，这种简单地把没有流失的客户与已经流失的客户区分开来是没有多大 意义的。他们希望能够根据已流失客户的一些行为变化，挖掘出流失客户共同的 异常行为，从而在客户还没有真正流失之前能够准确预测出客户流失的可能性， 对那些流失概率较大的客户采取有效的措施，如提供某些优惠政策等，以挽留客 户，减少损失。客户的一些行为交化主要反映在客户的话费变化中，每个客户对 应一条反映话费变化的时间序列。 4 1 2 挑战 本文的任务是根据电信所提供的数据集，建立一个数据挖掘模型，挖掘流失 客户共同的行为特征，从而对没有做问卷调查的客户及未流失客户未来的流失概 率进行预测。但数据挖掘只是一个概念，对不同的数据集，会遇到不同程度的困 难，必须根据实际情况选用不同的数据挖掘方法，并作出适当的修改才能有效地 解决实际问题。 在挖掘的过程中，主要面临以下的四大挑战： 第一、由予每个客户使用电信服务的起始时间不同，因此数据集中的时间序 列是一些不等长的时间序列。这使得一些经典的分类算法无法直接应用，因为大 1 9 中山大学应用数学硕士学位论文 部分的分类算法都要求样本的维数相等。 第二、由于用于挖掘的数据集中，已流失客户与未流失客户的比例严重失衡， 使得“逃离”客户的行为变化特征被淹没，要从这样的数据集中把未流失客户识 别出来是非常困难的，对于在这种不平衡数据集中进行挖掘，无论是在机器学习 领域还是数据挖掘领域都是一大难题。 第三、调查问卷反馈的结果只表明哪些客户已经流失，哪些客户还没有流失， 但流失客户是从哪个月“逃离”的( 决定不再使用中国电信服务) ，调查问卷中 并无表明。这对挖掘过程将造成较大的麻烦。因为电信部门关心的是客户在决定 不使用中国电信提供的服务前的一些行为特征，而对客户流失后的行为并不关 心。此外客户流失后的行为不但对挖掘模型的建立没有任何帮助，而且可能造成 噪声干扰，影响最终的预测精度。 第四、由于这万条客户数据是中国电信根据经验知识筛选出来的，被认 为极有可能已经流失。也就是说在这一万多条数据的变化趋势、变化的范围都极 其相似。如果从s v m 的语言来讲，这一万多条客户数据有大部分是位于分类间 隔( m a r g i n ) 附近，是极容易错分的样本点。因此在这样的数据集中要把流失的客 户完全识别出来难度非常大。 4 2 电信客户流失预测的数据挖掘模型的建立 对于一股的两类数据的分类问题，其模型司以描述如下：已知训练样本 置= k ，善t ，- ，吒) ，v i = l ，t i ，| ，咒9 l ，- l ，求饰) 使得，( 置) = 只。对测试样 本量= ( 赫，二) ，求，面，期两_ + 1 则i 被分为正例，若，( 奶- - 1 则j 被分为负例。 现在把，( z ) 写成概率函数的形式，记鼻( x ) 表示样本盖属于+ l 的概率，则上 面的模型可以写成下面的形式： 对测试样本j = ( 五，蟊) ， 2 0 中山大学应用数学硕士学位论文 _ 厂( z ) = + l ，e ( x ) t 一1 ，e ( x ) 0 的 时候，表示样本x 被分为“正例”的概率大于被分为“负例”概率。反之，样本 x 被分为“正例”的概率小于被分为“负例”的概率。也就是说。，( 工1 的值越 大，表示样本x 被分为“正例”的概率就越大。尽管，( 工) 的值与x 被分为“正例” 的概率并不是简单的线形关系，i 雨rf ( x ) 的值也不满足os ，( x ) l 的条件，但 实际上，电信部门知c 十的是哪个客户的流失概率较高，两并非关心流失概率的确 切数值，因此本文的以下部分均把，“) 看成是x 的流失指标，流失指标越大， 流失概率就越高。另外，下文如无特别指出，所提到的s v m 均使用