版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
大数据分析与应用第7章基于稀有类分类的信用卡7.1概述7.2稀有类分类基本理论7.3不均衡数据集的处理7.4基于Adaboost的稀有类分类算法欺诈识别研究7.5基于稀有类分类的信用卡欺诈识别7.6总结与展望模型7.1.1信用卡行业发展信用卡是指商业银行向信誉评价较好的单位及个人发放的,具有消费信用的特制载体卡片,用户可以凭此在特约商家购物、消费和向银行存取现金。通常来说,信用卡就是银行颁发给用户的一种先消费后还款的小额信贷支付工具。按照账户资金性质可将信用卡分为无透支功能的借记卡、有小额透支功能的准贷记卡及具有透支贷款、可“先消费后还款”功能的贷记卡。狭义的银行信用卡指的就是具有“先消费后还款”功能的贷记卡。近年来,尽管全球经济发展疲软,但在我国经济持续高速发展的带动下,我国信
用卡产业发展势头迅猛;同时由于互联网支付手段及手机支付手段的不断普及,
使得信用卡行业发展获得持续的推动力。2015年7月28日,中国银行业协会在京发布《中国信用卡产业发展蓝皮书(2014)》,显示:2014年我国信用卡产业继续保持稳健发展的良好势头,业务规模持续增长,市场影响力不断增强。
2014年,我国信用卡新增发卡量6400万张,累计发卡量达4.6亿张,比年初增长17.9%,
人均持卡量达0.34张;交易总额为15.2万亿元,比上年增长16%,交易总额占全国社会
消费品零售总额的比重为58%,较2013年提高了4.1个百分点。同时信贷潜在风险仍然
保持在较低水平,逾期半年未偿信贷总额为357.6亿元,较2013年增长42%;以年率
计的当前损失率为0.99%,较去年同期上升26.9%。2014年,境内受理市场环境进一
步改善,互联网、移动终端等创新交易渠道发展迅速。2014年我国境内受理商户新增
439.9万户,累计达1203.4万户,比年初增长57.6%;境内受理信用卡的POS机终端当年
新增530.3万台,累计达1593.5万台,比年初增长49.9%;境内ATM机当年新增9.5万台,累计达61.5万台,比年初增长18.3%。7.1.1信用卡行业发展从用卡安全上看,2014年我国信用卡欺诈损失率实现连续6年下降。但是,从具体的欺诈类型看,互联网欺诈呈快速上升态势,2014年互联网欺诈损失金额为2245.4万元,比上年增长59.1%。7.1.1信用卡行业发展7.1.2信用卡欺诈风险信用卡欺诈风险是指非真实持卡人运用伪造真实卡或顶替他人名义使用他人信用卡金额或信用额度,或者真实持卡人运用恶意透支手段进行大量交易或提现,造成巨额透支并逾期不还的行为。造成信用卡欺诈风险的主要原因有:01持卡人用卡安全意识缺乏,导致多种伪造欺诈、顶替交易情况出现。此情况是由于持卡人手中持有多张信用卡,但不采取有效措施保护自己信用卡信息安全。如设置密码时使用数字简单组合或生日、电话号码等公开数字组合,或信用卡丢失时不能及时挂失,以及随意将信用卡转借他人,公开信用卡密码等,造成信用卡欺诈行为发生。02信用卡发卡及管理过程中存在漏洞,导致虚假资信、持卡人信息泄露等风险。部分商业银行为追求高发卡量,放宽发行信用卡的申请条件,同时忽视了对持卡人资信水平的详细调查,征信手段单一,审核手段不严密,造成大量虚假申请获得信用卡。而在信用卡管理过程中随意泄露持卡人的个人信息,造成持卡人身份证号、手机号码等重要信息外泄,增加信用卡欺诈风险的产生。7.1.2信用卡欺诈风险03风险预警手段欠缺,无法有效识别信用卡欺诈行为。商业银行对信用卡欺诈行为的识别预警方法欠缺,监控手段不足,往往无法及时有效识别欺诈行为。在风险监控过程中,只重视欺诈交易行为本身的特征,而忽视了欺诈交易执行双方的信息特征,无法有效识别出欺诈行为的特点,造成不能对信用卡欺诈行为作出有效预警,给持卡人及发卡银行造成损失。7.1.2信用卡欺诈风险7.1.3信用卡欺诈识别研究防范信用卡欺诈行为的传统方法有很多,比如:完善法律法规;加强个人征信体系渠道建设;完善发卡行自身管理制度;加大信用卡从业人员培训力度等。传统的防范方法目的都在于减少信用卡欺诈行为的发生,虽然可以一定程度上减少欺诈行为的发生,但无法预先侦测到信用卡欺诈行为,一旦欺诈行为发生则无法避免持卡人或发卡行的经济损失。因此,信用卡欺诈行为的防范研究应向欺诈识别的方向转移,使用数据挖掘技术发现信用卡欺诈行为的特性,从而对欺诈行为的发生作出预警。具体流程如图7-1所示。数据清洗信用卡交易数据挖掘数据中欺诈行为特征获得欺诈行为模式监控真实交易识别欺诈行为图7-1运用数据挖掘技术进行信用卡欺诈识别流程7.1.3信用卡欺诈识别研究数据挖掘是指从数据中发现有统计规律的、事先未知的、可利用的内在特性。数据挖掘对象是有价值的、相关性较高的、经过清洗的数据。运用数据挖掘技术解决的问题都是那些定义明确的、利用查询和报表工具无法解决的问题,可以使用数据挖掘模型寻找解决方案。商业银行在多年的经营中积累了海量数据,利用数据挖掘技术能够从商业银行数据库中寻找到有效信息,为商业银行的运营提供决策支持。数据挖掘技术在商业银行业务中的主要应用领域为:客户关系管理、风险控制及金融欺诈识别等。7.1.3信用卡欺诈识别研究随着数据挖掘技术的发展,不断有新的数据挖掘方法运用到欺诈识别的研究中。从最初单一分类方法(如决策树、贝叶斯等)到多种分类方法组合运用,从给定模式的有监督方法到无监督的自学习方法。但由于在信用卡交易中欺诈行为属于少数情况,因此在分类识别过程中欺诈行为与正常行为的类别数量并不平衡,信用卡欺诈行为属于稀有类样本,一般的分类识别方法无法识别出稀有类特征,因此需要运用稀有类分类的方法来提高信用卡欺诈识别的准确度。7.1.3信用卡欺诈识别研究7.1.4国内外研究现状对于利用数据挖掘方法识别信用卡欺诈行为,国内外主要运用人工免疫系统、人工智能、神经网络、模式识别、模糊逻辑、机器学习等技术或方法来进行研究。国外研究现状1国外信用卡业发展起步较早,信用卡体系较完善,普及度高。信用卡已成为人们日常生活必不可少的支付手段,因此在产生大量交易数据的同时,也产生了大量欺诈行为。所有国外对欺诈识别的研究都非常深刻,运用不同类型的数据挖掘技术进行欺诈识别研究。①神经网络Barse等人运用一种带指数追踪存储的多层神经网络挖掘视频点播日志数据中的时序相关性。Syeda等提出使用模糊神经网络并行机可以更快识别客户专用信用卡欺诈行为规则。②贝叶斯网络Maes等人比较了贝叶斯网络的时间分段算法和神经网络的逆传算法在信用卡交易欺诈监测中的性能。结果显示:贝叶斯网络在训练中速度更快并且更加准确,但面对新的样本时却更加缓慢。Viaene等运用基于提升朴素贝叶斯的证据加权策略,计算可疑行为的相对权重,将正面证据及反欺诈证据通过一种简单的可加性原则进行加权,从而识别出欺诈行为。与其他朴素贝叶斯方法相比,这种策略能获得更精确的结果,拥有更灵活、更清晰的决策支持作用。单一有监督的方法17.1.4国内外研究现状③决策树Rosset等提出了一种基于规则的两阶段欺诈识别系统,其中第一阶段中使用C4.5算法生成欺诈行为相关规则,第二阶段中根据用户及行为水平对欺诈规则进行排序并按照欺诈覆盖度进行规则选择。HShao等基于改进的C4.5方法构建易于扩展的多维评估模型,提升了欺诈识别的准确度和决策树方法的性能。Bonchi等人将改进的C5.0算法运用在公司的税收声明的欺诈识别中。Fan介绍了一种挖掘概念漂移数据流的系统数据选择方法,目的是在不同规模的信用卡交易数据块中识别欺诈行为,在全部概念漂移数据块规模中交叉验证决策树组合的性能无疑比其他决策树分类器及加权平均组合更优,尤其当新增信用卡交易数据块规模较小时。Wang等人展示了一种修剪的C4.5分类器组合,针对每一个基分类器的预期效果给予权重,再将输出结果加权平均,作者认为,在面对最近的数据时这种分类器组合比单一加权平均分类器更有效。7.1.4国内外研究现状④其他方法其他方法包括专家系统、关联规则、遗传规划模型等。专家系统已应用于保险欺诈识别中。Major和Riedinger已经部署了一个真实的五层专家系统,将专家知识和统计信息整合来识别医疗保险欺诈。Chiu和Tsai提出一种基于Apriori算法的欺诈模式识别方法,在信用卡欺诈数据集中挖掘欺诈规则。Bentley利用遗传规划和模糊逻辑为识别欺诈创建规则,这种方法已在真实的家庭保险数据和信用卡交易数据中通过测试。上述的监督算法属于传统的学习算法,只能处理简单数据表中的结构化数据,无法应对大规模非结构化数据的欺诈识别研究。7.1.4国内外研究现状有些研究会将单一有监督的算法例如神经网络、贝叶斯网络、决策树等组合或以一定顺序形式结合,来提升欺诈识别结果的精度。Phua等提出将逆传神经网络、朴素贝叶斯和C4.5作为基分类器,来处理经过过抽样补充的稀有类数据。这种方法的独创性在于运用单一分类器叠加来选择最好的基分类器,然后将这些基分类器的预测结果组合起来得到最节省成本的汽车保险索赔。Kim提出在信用卡交易数据中用决策树来划分输入空间,双曲正切作为加权函数来生产欺诈密度,然后用逆传神经网络生成加权的欺诈可疑指数。还有一些研究是将有监督算法和无监督算法结合起来进行欺诈识别研究。Cortes和Pregibon提出利用按日更新的数字签名,将欺诈性的数字签名加入到训练集中,用有监督的算法例如决策树、模型平均回归、SLIPPER进行训练,发现欺诈行为中的共性。混合有监督的方法27.1.4国内外研究现状Kim等人实现了一种新型欺诈识别方法,该方法共分5步:①使用关联规则频繁项集Apriori算法随机生成规则并用过压延模式增加规则多样性;②将规则应用于已知合法的交易数据库中,丢弃所有匹配这些合法数据的规则;③使用剩下的规则监控真实的系统,丢弃所有没有监控出异常情况的规则;④将所有监控出异常情况的规则在增加小随机突变情况下继续监控;⑤保留所有成功的规则。这个方法已经用在零售事务处理系统中进行内部雇员欺诈识别测试。半监督的方法37.1.4国内外研究现状链接分析和图形挖掘是比较热门的研究主题,主要用在反恐怖主义、法律执行及其他安全领域,但这些技术同样可以运用在欺诈识别的研究中。NetMap介绍了如何使用紧急群算法组织紧密相连的数据群,通过图像分析从12个月的保险索赔记录中识别出实际难以捉摸的欺诈行为。Cortes等人检测了电信欺诈识别的大型动态网络的时间演化,每个网络都由多个兴趣圈子构成。为克服使用当前网络的不稳定性,和使用所有时间段中所有网络带来的存储及权重问题,Cortes等使用指数加权平均方法来按日更新子网,利用手机账户通话时长和通话次数来形成兴趣圈子,识别出欺诈行为的两个重要特征:第一,欺诈者的电话互相相连或使用同一个号码;第二,欺诈行为常发生在新的手机账户上,即被监控系统识别为欺诈行为时,欺诈者会更换新的手机账户。无监督的方法47.1.4国内外研究现状除了聚类分析之外,其他无监督方法例如离群点检测、峰值检测等方法也被用在欺诈识别中。Yamanishi等证明在医疗保险数据中可以使用无监督的SmartSifter算法处理分类和连续变量,并能运用海林格距离识别统计离群点。Bolton和Hand推荐使用组别分析(PeerGroupAnalysis)监控信用卡账务行为。在一个时间段内将目标账户的周平均累计行为次数与同组群的其他相似账户进行比较,将距离度量或可疑分数作为可以确定与该组群中心的标准距离的t统计量。计算组群的时间窗为13个周,监控时间窗为4个周。Brockett建议在已经过类属特征排序的汽车保险数据中使用主成因分析识别欺诈行为。7.1.4国内外研究现状由于我国信用卡业起步较晚,发展还不充分,法律法规还不健全,目前还没有形成有效的信用卡欺诈防范体系。但国内仍有许多学者进行了信用卡欺诈识别研究,为信用卡欺诈识别提供了很多有效的思路和方法。国内对信用卡欺诈识别的研究多集中在运用数据挖掘技术对已知欺诈行为进行特征学习,从而在未来监控交易数据中预测出欺诈行为,取得了一定成果。李洁等运用隐马尔可夫模型(HMM模型)构建信用卡欺诈识别系统,将信用卡交易过程中产生的消费数据作为隐马尔可夫模型中的随机过程,交易的商品类型作为模型中的状态,交易的金额范围作为可观察到的输出概率矩阵,同时将挖掘出的持卡人消费习惯应用到隐马尔可夫模型中初始状态的设置及模型的训练中。隐马尔可夫模型结构简单,识别能力强,在模型训练中,不需要对正常交易数据和欺诈行为数据分别训练,提高训练效率,同时可以在行为类型未知情况下进行训练,可识别出从未发现的欺诈行为类型。
国内研究现状27.1.4国内外研究现状郭涛等人针对信用卡交易行为中的异常数据,对消费者行为数据进行置信度计算,所得结果再运用多层前馈神经网络模型的后向传播误差算法进行训练,识别欺诈特性,随后采用ROC分析算法中的二类别ROC分析方法制定异常识别阈值,评估系统欺诈识别的性能。该系统可以不依赖单个行为用户,同时引入ROC分析方法制定识别阈值,可以确保欺诈识别的准确性。7.1.4国内外研究现状刘艳红等针对信用卡交易数据中正常类与欺诈类样本数量差距过大的情况,提出基于单值分类方法-支持向量数据描述算法构建欺诈识别模型。通过K-means聚类算法对正常交易数据进行聚类,将每一类正常数据分别与欺诈数据建模进行欺诈识别。再利用蚁群算法对支持向量数据描述算法的正则化参数和核参数进行寻优确定,提高建模精度。该欺诈识别模型将有相似交易行为记录的用户组合起来训练,弥补了交易行为数据中欺诈行为模式不足的缺陷。7.1.4国内外研究现状童凤茹采用组合学习方法Adaboost算法进行信用卡欺诈识别研究,首先为了弥补样本分布不均的问题,选择欠抽样(under-sampling)方法减少正常样本,再使用Adaboost方法进行训练,建立欺诈识别模型。将持卡人的账户数据与交易数据共同作为训练数据,这样可以更深刻地反映持卡人的消费特征和模式。实验表明,基于用户资料和相关行为数据利用Adaboost算法构建信用卡欺诈识别系统,可以及时预测交易的欺诈可疑性,在欺诈造成较大损失前进行欺诈防范。7.1.4国内外研究现状郑丽丽等人以基于信用卡交易行为的信用评估体系为基础,使用遗传算法和多类支持向量机构建信用卡行为框架体系。利用遗传算法进行数据清洗,有效剔除数据集中的冗余属性,构建特征子集。使用支持向量机和二叉树结合的方法对样本进行训练,优点是决策时分类器数量少且决策速度较快。采用基于密度法的增量学习淘汰算法中的经典支持向量机,使得模型除了具有多分类能力之外,还具有增量学习的能力。7.1.4国内外研究现状7.1.5研究思路和步骤在信用卡欺诈识别研究中,主要难点在于欺诈行为数据相对较少,夹杂在正常数据中难以提取欺诈特征,使得识别欺诈行为较难,而利用稀有类分类的方法则可以解决这种问题。在信用卡交易数据中,正常行为作为普通类,数量较多,欺诈行为作为稀有类,数量极少,一般识别方法难以提取欺诈特征。稀有类分类方法则通过对数据类别差距的平滑处理或采用特殊算法来识别稀有类的特征,能够从信用卡交易数据中有效识别出欺诈行为特征。本章采用稀有类分类的方法构建信用卡欺诈识别模型。首先对目前稀有类分类的方法进行分析和比较,从中选取合适的方法组合;然后对信用卡欺诈识别模型中的重点模块进行研究;最后将各模块进行整合,构建信用卡欺诈识别模型。稀有类分类方法的提出1简要介绍了稀有类及稀有类分类的相关概念,信用卡欺诈识别可以视为一个稀有类分类的问题。在稀有类分类问题中,高度不均衡的数据集和稀有类样本匮乏使得稀有类分类不同于一般的分类,因此稀有类分类的方法与一般普通分类方法也不同。着重对目前稀有类分类的方法进行分类介绍。稀有类分类的方法可分为:基于抽样的方法、基于组合的方法、基于规则的方法、基于划分的方法和代价敏感方法等,并对每一类型中的主要方法进行了介绍。根据这些方法的特性及适用环境,本章采用基于抽样和基于组合两种方法组合构建信用卡欺诈识别模型,该模型将分为两个阶段,第一阶段对不均衡数据集进行预处理,改变不均衡数据集的样本分布,改善数据集的不均衡状态;第二阶段利用分类算法进行稀有类分类时选择使用Adaboost方法进行分类。稀有类分类方法分析27.1.5研究思路和步骤主要介绍了处理不均衡数据集的方法,由于不均衡数据集是稀有类分类中需要面对的难点之一,因此需对不均衡数据集进行重点处理。对不均衡数据集传统的处理方法主要通过抽样实现,但抽样会改变数据集中样本的数量,造成样本冗余或者类别信息丢失等问题。因此选择聚类的方法,通过对普通类样本进行聚类,将普通类样本划分为不同的簇,再将这些簇与稀有类样本结合形成均衡数据集,作为训练集对分类算法进行训练。这样可以凸显稀有类特征,更易识别稀有类样本。本章对聚类方法进行了系统介绍,并详细研究了各类方法中的代表算法的基本思想和过程。通过实验对比发现,K-means算法的聚类均衡度要优于其他方法,因此本章选择K-means算法作为处理不均衡数据集的聚类方法。不均衡数据集处理37.1.5研究思路和步骤Adaboost算法作为组合学习算法中比较有代表性的算法,本章进行了简单介绍。由于普通的分类方法难以有效进行稀有类分类,使用Adaboost算法对稀有类分类数据集进行多次迭代训练,能得到较好的稀有类分类性能。通过分析指出传统的Adaboost算法中,若训练集中存在较多离群的样本,每轮分类中都会出现分类错误,使得这些样本权重过大,造成分类有偏,影响分类精度。而类别划分的关键往往是类别边界的定义,本章提出通过关注类别边界样本,对Adaboost算法的权重更新机制进行改进,提升类别边界样本的权重,同时减小分类错误样本的权重扩散幅度,来识别稀有类的类别边界,提高稀有类分类性能。通过实验对比发现,权重更新改进算法与原始Adaboost算法相比,稀有类分类的性能得到提升,证明这种思路是有效的。Adaboost权值更新改进算法47.1.5研究思路和步骤基于稀有类分类的思想构建信用卡欺诈识别模型,该模型由数据集提取、数据清洗、数据集预处理、分类器构造、模型进化等多个模块构成,其中不均衡数据集处理和分类器构造是影响模型识别性能的重要模块,因此首先完成不均衡数据集的处理研究和稀有类分类算法改进研究,然后将这些模块组合,构建信用卡欺诈识别模型。图7-2为模型流程图,通过实验证明,该模型能够有效识别信用卡欺诈行为。信用卡欺诈识别模型构建57.1.5研究思路和步骤图7-2信用卡欺诈识别模型用户信息交易行为数据清洗数据集预处理数据集提取训练稀有类分类算法生成分类器是否满意对交易行为进行欺诈识别否是7.1.5研究思路和步骤7.2.1稀有类分类介绍不均衡数据集普遍存在于现实生活中的各个方面,有些类占据了数据集中的大部分数据,即多数类;而剩下的类只占了数据集中的一小部分数据,即少数类,当少数类中数据量占整个数据集10%以下时,可称为稀有类,而相对应的多数类即为普通类。例如,在金融欺诈监测中,大多数金融交易是合法的,只有少部分可能是欺诈行为。在网络入侵侦测中,新产生的恶意网络活动是隐藏在大量正常网络流量中的。在日常信用卡交易数据中,欺诈行为产生次数相对较少,夹杂在大量正常交易行为中,只占信用卡行为数据的极少部分。虽然稀有类在数据集中只占据一小部分数据(10%以下),但能产生巨大的影响。在天文学的巡天图像中,只有0.001%的调查对象真正超越当前的研究范围,但正是它们可能导致新的发现。在医疗保险欺诈中,虚假索赔所占比例很小但造成了绝大多数的损失。相对于普通类,怎样识别稀有类更能引起人们的兴趣,稀有类分类成为比较热门的研究重点。7.2.1稀有类分类介绍我们在处理稀有类分类问题中,会遇到许多比较棘手的障碍。其一就是高度不均衡的数据集,稀有类数据在其中只占极少部分,比如金融欺诈识别问题,我们可能需要从海量未知的交易数据中寻找金融欺诈行为,若借助领域专家去进行判断,将需耗费巨大的成本,而且领域专家并不能将每一条欺诈及时识别出来。另一个难点在于稀有类数据极度匮乏,难以提取稀有类数据的特征,比较抽象的例子为:在较大规模的不均衡数据集中归纳其中几个样本的特征共性,由于样本数量极少,很有可能在特征提取时出现遗漏,如此一旦遇到新的稀有类样本,将无法及时完成识别。面对这些问题,对于稀有类分类需要特殊的方法来解决。7.2.1稀有类分类介绍7.2.2稀有类分类的方法稀有类分类的解决方法有很多,主要采用有监督的学习来解决稀有类问题,其中包括基于抽样的方法、基于组合的方法、基于规则的方法、基于划分的方法、基于代价的方法等。接下来将分别对这些方法进行介绍。稀有类分类问题与一般分类问题相似,但又有许多不同。两者都是按照定义好的规则对所有对象贴上相应标签,把所有对象区分到不同类别中。两者不同的地方在于,一般分类问题面对的是相对较均衡的数据集,各类别的样本数量差距不大;而稀有类分类所要面对的是高度不均衡的数据集,其中普通类占据样本量的大多数,稀有类只占数据集中的极少部分,特征提取较困难。一般分类的目标是建立一个最优的分类器,区分出每一个类别的样本,保证每个类别的准确率差不多;而稀有类分类中,只需关注稀有类的分类性能,从不均衡数据集中识别出稀有类样本即可,不必关注普通类的分类效果。1基于抽样的方法抽样是一种常见的数据预处理技术,在一般分类方法中经常会采用抽样。为了应对稀有类分类中的不均衡数据集问题,人们想到采用抽样方法,它的基本思想是通过抽样来改变数据集中的样本分布,这样使得稀有类样本能较好地显露出来。根据抽样的对象可以将抽样方法分为过抽样(over-sampling)和欠抽样(under-sampling),同时根据抽样样本的选择又分为随机抽样和有选择的抽样。抽样的方法按照这两种分类方式组合可分为4类:随机过抽样、随机欠抽样、有选择的过抽样和有选择的欠抽样。7.2.2稀有类分类的方法随机过抽样过抽样指的是通过增加稀有类样本来增加稀有类的样本数量,使得稀有类和普通类的样本数量接近。随机过抽样方法就是随机抽取稀有类样本进行复制,这种方法的缺点是没有给稀有类增加新的样本,使得原有稀有类样本的特征更加突出,造成分类的过分拟合,同时引入额外的训练样本,导致运算时间增加。图7-3为随机过抽样方法的介绍。1不均衡数据集均衡数据集
稀有类样本
普通类样本
图7-3随机过抽样将不均衡数据集转变为均衡数据集7.2.2稀有类分类的方法2随机欠抽样欠抽样指的是通过减少普通类样本来减少普通类的样本数量,使得普通类和稀有类样本量的差距减小。随机欠抽样方法就是随机删掉一部分普通类样本,这种方法的缺点是随机删掉的普通类样本中可能包含普通类的重要特征,造成部分重要特征信息丢失。图7-4为随机欠抽样方法的介绍。
不均衡数据集均衡数据集稀有类样本普通类样本图7-4随机欠抽样将不均衡数据集转变为均衡数据集7.2.2稀有类分类的方法3有选择的过抽样有选择的过抽样指的是运用特殊方法增加稀有类样本,其中有代表性的方法就是SMOTE(SyntheticMinorityOver-samplingTechnique)算法。SMOTE算法基于过抽样思想,但在增加稀有类样本时不是随机复制原有稀有类样本,而是根据每一个稀有类样本以及离它们最近的k个邻近普通类样本人工合成新的稀有类样本,同时可以避免稀有类样本的过度拟合问题。SMOTE算法的具体流程如图7-5所示。图7-5SMOTE算法的基本流程7.2.2稀有类分类的方法4有选择的欠抽样有选择的欠抽样是通过一定方法选出一些普通类样本,将这些普通类样本删掉。删去这些普通类样本的同时不会对普通类样本特征造成损失,不会丢失普通类重要信息。比较典型的方法有One-SidedSelection等。One-SidedSelection的核心思想是仅消除特定的普通类样本而保留全部稀有类样本,该方法利用Tomek-Links从普通类样本中识别出噪声样本(noisy)、冗余样本(redundant)以及边界样本(borderline),并将这些样本删去,保留了那些能代表普通类特征的普通类样本,在减少普通类样本量的同时避免了普通类重要类别信息的丢失,基本思想如图7-6所示。One-SidedSelection在面对极度不均衡数据集时有较好的性能。不均衡数据集均衡数据集
稀有类样本
普通类样本
noisyredundantborderline图7-6One-SidedSelection算法的基本思想7.2.2稀有类分类的方法2基于组合的方法组合学习方法是一种可以提升弱分类器分类性能的方法,其基本思想是将各基分类器的分类结果集中起来,作出最优的判断。早期性能较好的组合学习算法有Boosting等。Boosting的思想是通过简单的、粗糙的、准确度较差的基分类器,按照某种方法训练,最终得到精确的、复杂的最终分类器。在Boosting中,所有基分类器对经过加权分布处理的训练集进行抽样训练,每一轮训练完成时,训练集中的所有样本根据当前分类器的分类性能相应调整自身的权重,这样,在下一轮训练中,分类器会重点学习上一轮分类出错的样本,图7-7为Boosting算法的基本流程。由于Boosting可以改变原始数据集中的样本分布,所以被普遍用来进行样本抽样。自从Boosting被用来处理那些分类较困难的数据集开始,将Boosting用来进行稀有类分类成为比较好的研究方向。7.2.2稀有类分类的方法训练集子数据集D1子数据集D2子数据集Dn-1子数据集Dn...基分类器C1基分类器C2基分类器Cn-1基分类器Cn...训练加权投票随机抽样结束修改样本权重修改样本权重训练训练修改样本权重训练修改样本权重图7-7Boosting算法的基本流程7.2.2稀有类分类的方法组合学习方法是一种可以提升弱分类器分类性能的方法,其基本思想是将各基分类器的分类结果集中起来,作出最优的判断。早期性能较好的组合学习算法有Boosting等。Boosting的思想是通过简单的、粗糙的、准确度较差的基分类器,按照某种方法训练,最终得到精确的、复杂的最终分类器。在Boosting中,所有基分类器对经过加权分布处理的训练集进行抽样训练,每一轮训练完成时,训练集中的所有样本根据当前分类器的分类性能相应调整自身的权重,这样,在下一轮训练中,分类器会重点学习上一轮分类出错的样本,图7-7为Boosting算法的基本流程。由于Boosting可以改变原始数据集中的样本分布,所以被普遍用来进行样本抽样。自从Boosting被用来处理那些分类较困难的数据集开始,将Boosting用来进行稀有类分类成为比较好的研究方向。7.2.2稀有类分类的方法上述算法的核心思想是一致的:适当改变原始数据集的样本分布,使分类器能够重点关注那些难以确认分类的样本。RareBoost和AdaCost是采用改进的权重更新机制来改变样本分布,而SMOTEBoost则生成新的人工稀有类样本。除了权重更新机制,Boosting的其他重要组成部分:精度指标、组合投票方法、基分类器也被人研究过。Joshi等人通过实验指出:在面对稀有类分类问题时,Boosting的分类性能主要取决于基分类器的分类性能。7.2.2稀有类分类的方法3基于规则的方法由于稀有类样本在数据集中占比极小,难以提取稀有类的规则,所以传统的规则算法在稀有类分类问题上的分类效果并不理想。人们针对稀有类的特点对规则方法进行改进,一些专门处理稀有类分类的基于规则的方法应运而生。7.2.2稀有类分类的方法PNrule01Joshi等人指出现有的关联规则的方法在识别稀有类中性能不佳,是因为这些基于规则的算法总是希望找到同时满足高准确率和高覆盖率的规则,但是可能遇到这些问题:离群的普通类样本和离群的稀有类样本(稀有类样本本身可能就比较稀疏)。为了解决这些问题,他们提出了两阶段归纳法PNrule。PNrule共分为两个阶段。在第一阶段中,主要采集针对稀有类的规则,这些规则必须满足高召回率和适当的准确率要求(将高准确率要求放宽),满足这些规则的样本都被提取出来,由于准确率要求被降低,所有提取的样本中除了稀有类样本外还包含一些普通类样本。在第二阶段,采集普通类规则以求将提取出来的普通类样本删去。两阶段互相结合,非常适用于解决稀有类分类的问题。图7-8是使用PNrule进行稀有类分类的基本过程。7.2.2稀有类分类的方法P阶段
训练集:整个训练集①学习发现第一条规则P1(召回率和准确率最高),将P1覆盖的数据集(大部分稀有类样本和少数普通类样本)从训练集中删掉;②学习发现规则P2(P2的召回率和准确率仍较好,但比P1差),将P2覆盖的数据集从训练集中删掉;③继续发现召回率较高的新规则,如果规则的准确率在阈值之上,则保留该规则,将该规则覆盖的数据集从训练集中删掉。(若同时发现P3及Q1、Q2,P3的准确率不及Q1、Q2,却在阈值之上,而P3的召回率好于Q1、Q2,则选择P3而放弃Q1、Q2);④直到学习发现的规则准确率低于规定阈值时,P阶段结束。N阶段
训练集:所有P规则覆盖的数据集①学习发现规则N1(召回率和准确率最高,能最准确、最多地删除P规则覆盖的普通类样本);②依次发现规则N2,N3,…,直至学习发现的规则无法满足召回率和准确率标准,则N阶段结束。在N阶段中,由于学习发现的规则不是100%的准确,所以会出现将稀有类样本误判删掉的情况。图7-8PNrule的基本过程7.2.2稀有类分类的方法EPRC02
EPRC(Rare-classClassificationbyEmergingPatterns)是第一种基于显露模式(EmergingPatterns)进行稀有类分类的算法。显露模式(EPs)是利用数据集中某个规则在一个样本类别的支持度明显高于其他类别,来定义不同类别之间的差异。用一个直观的例子来描述显露模式就是:在判断胃肠型流感时,①用以患者的性别为自变量的函数作模式没有任何作用;②用以患者的身高、体重为自变量的函数作模式几乎没有作用;③用以患者最近生活环境如气温、饮食等为自变量的函数作模式有一定参考作用;④用呕吐、腹泻症状作模式是重要的判断依据。因此,我们说条件③、④是显露的,而条件①、②是不显露的。图7-9显示的是显露模式的基本概念。7.2.2稀有类分类的方法已知数据集D,模式X(属性名与属性值的集合),数据集D中符合模式X的样本为fred(X,D)支持度:模式X在数据集D中的支持度为Sup(X,D)=Count(fred(X,D))/Count(D)(即符合模式X的样本在数据集D中的占比)。显露模式:当模式X在不同数据集中的支持度差异大于预定阈值时,则称模式X为显露模式。
对于数据集D中的两个类别Dn和Dm,给定阈值ρ(ρ>1),若Sup(X,Dm)/Sup(X,Dn)≥ρ,则模式X为显露模式。图7-9EPs的基本概念7.2.2稀有类分类的方法EPRC在进行稀有类分类时通过三种途径提高EPs的识别能力:①生成新的未被发现过的稀有类显露模式;②修剪支持度较低的显露模式;③提高已有的稀有类显露模式的支持度。DEP是另一种基于显露模式的稀有类分类算法,通过将普通类划分为多个子类,使得稀有类显露模式能够凸显出来。同时通过一个强度函数来评估稀有类显露模式,目的是尽量降低噪声显露模式的影响。7.2.2稀有类分类的方法4基于划分的方法在一些分类情况下,将数据类划分为子类是比较常见的处理。Japkowicz提出了一个结合监督学习和非监督学习的分类框架,其中通过聚类对数据集进行划分。在不均衡数据集中通过划分子集可以将复杂的类别变得更简单,从而降低数据集的不均衡度。Wu等人基于局部聚类开发了一种稀有类分类方法,使用了划分子集的思想,用局部聚类的方法将普通类划分为多个子类,同时利用过抽样提高稀有类样本量。为了适应聚类结果,算法对过抽样控制参数进行了调整,使得稀有类样本量接近普通类子类的平均样本量。7.2.2稀有类分类的方法5基于代价的方法代价敏感学习法(CSL,Cost-SensitiveLearning)是一种被广泛应用的数据挖掘技术,其核心思想就是对数据集中不同类别给予不同等级误分类代价。在稀有类分类中,将稀有类样本误认为普通类和将普通类样本误认为稀有类,对分类器产生的影响是不同的,利用代价敏感学习法,赋予错分稀有类样本一个更高的代价,将分类的最终目标定为误分类代价最小,对稀有类分类有积极的指导作用。但在现实应用中,代价的评价信息是难以获取的。尽管稀有类错分的代价比普通类错分的代价要高,但如何设置两者间的代价差距还需要先验知识或领域专家的介入。为了解决这个难题,人们尝试用各种方法来优化误分类代价的设置,如Sun等人用遗传算法来制定每个类别的最优的误分类代价。7.2.2稀有类分类的方法7.2.3稀有类分类性能评估性能评估在数据挖掘中扮演着非常重要的角色,它不仅可以用来评价分类器的性能,还能在一些算法的训练学习过程中起到指导学习的作用。由于不均衡数据集的影响,传统的评估标准如正确率(Accuracy)在稀有类分类中并不适合,因为正确率并没有关注稀有类样本的分类情况。例如一个稀有类样本量在整个数据集中占1%,若分类器将所有样本全部识别为普通类样本,还能得到99%的整体正确率,但在稀有类分类中这是彻底失败的。为了反映稀有类分类中稀有类样本的分类情况,召回率(Recall)、准确率(Precision)和F度量(F-measure)被用来评估稀有类分类器的性能。在介绍召回率、准确率和F度量之前,我们首先给出对分类结果的定义:TP表示被正确分类的正样本数量;FP表示被错误分类的正样本数量;TN表示被正确分类的负样本数量;FN表示被错误分类的负样本数量。它们之间的关系如图7-10所示。P样本本身属性分类器识别结果属性TPFPTNFNNPN图7-10分类结果矩阵7.2.3稀有类分类性能评估召回率(Recall):在所有本身为目标类的样本中,被正确分类的样本数量所占百分比,如公式(7-1)所示。(7-1)准确率(Precision):所有被正确分类的样本在整个训练集中所占的百分比,如公式(7-2)所示。(7-2)F度量(F-measure):召回率和准确率的加权调和平均,如公式(7-3)所示。(7-3)其中是一个参数,可根据需要自行设定(),一般情况下可转化为公式(7-4)。,则公式(7-3)(7-4)7.2.3稀有类分类性能评估将F度量和召回率、准确率搭配使用,不仅可以着重评估稀有类样本的分类情况,且符合稀有类分类的特点,还可以有效评估稀有类分类器的分类性能。因此本章采用召回率、准确率和F度量作为稀有类分类算法的性能评估标准。7.2.3稀有类分类性能评估7.3.1不均衡数据集的研究现状稀有类分类研究中遇到的一大障碍是样本分布高度不均衡的数据集。不均衡数据集指的是不同类别的样本量相差较大的数据集,例如现实中患有肺癌的人群占整个人群的极少部分;互联网数据交互中,网络入侵行为较为罕见。对于信用卡交易中,存在信用卡欺诈行为的交易数据也可视为不均衡数据集,因为欺诈行为只占极少数。在拥有稀有类的不均衡数据集中,稀有类样本量在整个数据集中占比低于10%。由于稀有类样本量占比极低,稀有类特征不突出,无法有效提取稀有类的类别特征,从而无法对新样本进行有效的识别分类。而稀有类分类的目的是从不均衡数据集中识别出稀有类样本,需要提取有效的稀有类样本特征,这就需要改变不均衡数据集的样本分布,使得稀有类样本特征显露出来,以便于分类器学习。不均衡数据集(有价值数据只占总体很小一部分)的研究是近年来的研究热点,目前对不均衡数据集的处理主要是通过抽样的方式改变样本的分布。在高度不均衡的数据集中,普通类样本占大多数,稀有类样本量占比较少,通过抽样的方式,可改变普通类样本和稀有类样本的分布,解决数据集的不均衡性。前面曾提到,抽样的方法根据抽样对象的不同,主要分为过抽样(over-sampling)和欠抽样(under-sampling)。7.3.1不均衡数据集的研究现状(1)过抽样(over-sampling)指的是对稀有类样本进行抽取复制,通过复制稀有类样本来增加稀有类的样本量。原始的过抽样是通过随机抽取稀有类样本,复制N倍(通过普通类样本量和稀有类样本量的比值来确定N的值),这样可以使普通类和稀有类的样本量达到均衡。由于简单地复制已存在的稀有类样本,使得一个稀有类样本的特征被放大N倍,造成稀有类样本特征更加突出,容易使分类出现过拟合现象,即分类器过分强调某个样本的特征,使得稀有类特征提取出现偏差。7.3.1不均衡数据集的研究现状为了减少已有稀有类样本的特征影响,对过抽样进行了改进,不再简单复制已有的稀有类样本,而是通过特殊方法人工合成稀有类样本。例如SMOTE算法,在稀有类样本与最邻接普通类样本之间人工合成稀有类样本,这样使得已有的稀有类样本特征没有增加,从而避免了分类过拟合的现象。但是无论怎样增加稀有类样本,都会使得原数据集规模扩大,增加训练集的复杂度,使得机器学习的时间成本提高。7.3.1不均衡数据集的研究现状(2)欠抽样(under-sampling)指的是对普通类样本进行抽取删减,通过删减普通类样本来减少普通类的样本量。最初的欠抽样是通过随机抽取普通类样本进行删减,直到普通类与稀有类样本量达到均衡状态才结束删减。减少普通类的规模后,可以使稀有类的特征凸显出来,便于提取稀有类特征构造分类器。但由于数据集中的部分普通类样本被删减,可能使包含普通类重要特征的样本被删掉,造成重要的类别信息丢失,使得特征识别出现漏洞。7.3.1不均衡数据集的研究现状对欠抽样的改进主要集中在区分普通类样本的重要程度,选择较不重要的普通类样本进行删减,避免重要的类别信息丢失。样本的重要程度根据样本所包含的类别信息判断,将普通类样本中的噪声样本、边界线样本和冗余样本进行删减,避免删减包含类别重要特征的样本。这种样本选择尽管可以保留普通类样本
的特征信息,但对于现实中的不均衡数据集,难以判断哪些是重要样
本,哪些是冗余样本,而噪声样本中可能包含重要的类别特征,对
普通类样本进行删减,则不可避免特征信息的丢失。7.3.1不均衡数据集的研究现状由于抽样的方法存在无法避免的误差,所以本章选择聚类的方法来处理不均衡数据集。通过对普通类样本进行聚类,将普通类划分为多个子类,使每个子类的普通类样本量与稀有类达到均衡状态,再将每个普通类子类与稀有类组成训练子集,分别进行学习。这样在每个子集中,稀有类特征可以凸显,利于稀有类特征的提取。图7-11所示为聚类方法处理不均衡数据集的基本思路。7.3.1不均衡数据集的研究现状普通类样本原始数据集D普通类样本稀有类样本聚类分解...子数据集...子数据集子数据集图7-11聚类方法处理不均衡数据集的思路7.3.1不均衡数据集的研究现状7.3.2聚类方法的介绍聚类是数据挖掘方法中诞生最早的算法之一,在数据挖掘中占有比较重要的地位。虽然从诞生至今已有几十年的时间,但聚类仍被应用在数据挖掘的多个领域,如模式识别、机器学习中。聚类的核心思想可以用“物以类聚,人以群分”来表示。在1974年时,Everitt已经提出了关于聚类的定义:聚类将数据集中的样本分成不同的簇,簇是相似样本的集合,不同簇中的样本是不相似的;同一簇中的任意两个样本之间的距离小于任意两个不同簇的样本之间的距离;簇可以理解为是将多维空间分割成多个互相分离的包含相似点集的连通域。实际上,可以将聚类视为无监督的分类,在进行聚类之前,无法得知数据集中样本的类别数量和类别特征,没有先验知识可以参考。给定数据集,表示第i个样本;簇,,,样本的第一个下标表示样本属于簇,第二个下标表示样本是簇中的第t个样本;表示任意两个样本之间的距离;若簇是数据集X聚类的结果,则簇需满足:(1);(2)对于,聚类算法的一般过程如图7-12所示。7.3.2聚类方法的介绍数据准备标准化及降维特征选择从初始特征中选择最有效的特征特征提取将筛选的特征更新为更突出的特征聚类分组据所选特征构造距离函数,对样本进行聚类或分组聚类结果评估对聚类结果进行有效性评估图7-12聚类的基本过程7.3.2聚类方法的介绍按照划分簇采用的方法不同,目前聚类算法可分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法。不同的聚类算法在对数据集中的样本划分簇时都会依据自己的划分标准,即目标函数。目前聚类算法的目标函数可归纳为以下三类。7.3.2聚类方法的介绍(1)以紧密性为目标函数。以这种标准划分的簇,簇中的样本之间都比较紧密,而不同的簇之间比较疏远。基于划分的算法和基于层次的方法都是这种标准,对于规则分布的数据集或数据本身有较强的可分性的数据集聚类的效果较好;但对于复杂结构的数据或分布则无能为力。(2)以连通性为目标函数。这类聚类算法中,簇中的样本都拥有相同的特征或模式,例如基于密度的方法和基于网格的方法。(3)以隔离性为目标函数。隔离性指的是不同簇之间存在空间的间隔。但在现实数据集中很难有纯粹的空间间隔,因此隔离性常与其他标准结合作为算法的目标函数。7.3.2聚类方法的介绍基于划分的聚类算法(partitioningmethods)1在一个有N个样本的数据集中,通过划分将全部样本划分为K个分组,每一个分组代表一个聚类的簇,K<N,这K个簇需要满足以下要求:(1)每个簇中至少包含一个数据样本;(2)对于数据集中的样本,每个样本属于且仅属于一个簇(在某些模糊聚类算法中可不做此要求)。若簇的个数K提前给定,则算法首先给出初始的分簇结果,再通过多次迭代改进分簇结果,使得聚类结果不断优化,优化的标准是:在同一簇中的样本之间的距离越近越好,不同簇中的样本之间的聚类越远越好。基于划分的聚类算法的优点是:便于实现增量式聚类,适用于大规模的数据;缺点是:无法自我判断簇的个数,聚类时需要提取设定;受初始簇中心影响较强;偏向于发现椭圆形的簇;对于离群点较敏感。7.3.2聚类方法的介绍基于划分的聚类算法中比较有代表性的方法有:K-means算法、K-medoids算法、Clarans算法等。K-means算法是划分方法中最早被提出的方法,目前应用仍非常广泛。K-means算法的核心思想是将数据集中的所有样本划分到簇中心与其距离最近的簇中,任意样本都必须存在且只能存在于一个簇中;簇的描述是用该簇中所有样本的属性均值来表示。K-means算法的基本步骤如图7-13所示。7.3.2聚类方法的介绍给定数据集
,
表示第i个样本。(1)初始化,指定聚类的个数K,从数据集中随机抽取K个样本作为初始簇的中心;(2)描述簇,计算每个簇中样本的属性均值,用属性均值作为簇的中心,描述初始簇;(3)分配样本
,计算数据集中样本
到各簇中心点的距离,选择簇中心与其距离最近的簇
,将样本
划分到该簇中;(4)修正簇
,重新计算簇
中样本的属性均值,修改簇
的中心;(5)计算目标函数是否达到最优;若目标函数最优则停止,否则返回步骤(3),重新分配样本
。图7-13K-means算法的基本步骤7.3.2聚类方法的介绍K-means算法可视为寻找目标函数最优的过程,通常其目标函数为最小方差函数(MSE,MinimizesSquaredError),目标函数定义如公式(7-5)所示。(7-5)E是数据集中全部样本与其所在的簇中心的方差和,是数据集中任意样本,是所在的簇。7.3.2聚类方法的介绍基于层次的聚类算法(hierarchicalmethods)2层次聚类方法对数据集分层次进行分解构造簇,分层的方法主要分为自顶向下和自底向上两类方法。按照自顶向下的方法可称为分裂(divisive),起始状态将整个数据集视为一个簇,在反复迭代过程中根据样本间特征的不同不断对簇进行分裂,直到簇满足目标函数,不能再分为止。自底向上的方法称为凝聚(agglomerative),初始状态是将数据集中每一个样本都视为一个簇,再根据样本之间的相似性不断把相近的簇进行合并,直到簇之间无法再合并为止或满足预设条件为止。层次方法的优点是:聚类过程较为直观,层次方法的迭代过程可视为一棵树的形成;在聚类之前不需设定簇的个数,可在聚类过程中自行判断;同时可聚合多个局部簇,对已形成的聚类结果进行二次聚类;缺点是:聚类过程中需对簇之间的相似度矩阵进行存储,计算复杂度较高,在处理大规模数据时难以实现;聚类过程无法回溯,无法满足增量式聚类的要求。7.3.2聚类方法的介绍基于层次的聚类方法主要有:CURE算法、BIRCH算法和Chameleon算法等。BIRCH算法(BalancedIterativeReducingandClusteringusingHierarchies)是针对大规模数据集专门提出的基于层次的聚类算法,它采用自底向上的凝聚方法,通过反复迭代的重定位对聚类结果进行不断改进。BIRCH的核心思想是:构造一个聚类特征树,树中的每个叶节点都为聚类的簇,然后再对叶节点进行聚类。7.3.2聚类方法的介绍BIRCH算法使用特征树进行聚类,主要过程为:首先对整个数据集进行扫描,构建初始特征树,尽量使特征树包含样本的全部信息。特征树的构建是随着数据集原始样本的加入而自动生成的:当一个样本被放入与其距离最近的叶节点中,若叶节点半径大于预设的阈值,则该叶子节点会被分割,即该簇会被拆分为更小的簇。当初始特征树构建完成后,通过提升阈值改进聚类特征树,在迭代过程中聚类的对象不再是数据集原始样本,而是特征树中的叶节点,即对簇进行再聚类。7.3.2聚类方法的介绍基于密度的聚类算法(density-basedmethods)3基于密度的方法在聚类过程中不再将样本间的距离作为关注重点,而是根据样本在空间中的聚集密度的高低来划分数据簇。基于密度的方法的核心思想是将数据集中的样本按照空间中的聚集密度的大小来划分为多个分组,当空间中某个区域的点密度大过预设的阈值,即把它与相邻的组划分成一个簇。基于密度的方法关键是使用何种方法来确定空间中样本分布的密度。普遍采用的方法是计算样本所处空间的密度,预设一定的密度阈值,当样本空间的密度高于阈值时被认为是高密度区域,低于阈值时被认为是低密度区域,然后将高密度区域与低密度区域隔离;另外还有一种方法是谷点搜索法,就是将低密度区域互相连接,形成低密度连通区域,这样就可以区分高密度区域和低密度区域了。7.3.2聚类方法的介绍基于密度的方法的优点是相比划分方法只能发现类圆形的簇,基于密度的方法能够发现不同形状的簇;聚类过程中能够自行确定簇的个数;计算过程中可以识别出离群点,不受其影响。缺点是:聚类过程中需要提前确定簇中最小样本数和领域的个数;另外若数据集中样本密度相差较大,则聚类效果不佳。7.3.2聚类方法的介绍基于密度的聚类算法主要有DBSCAN算法、OPTICS算法、CLIQUE算法等。DBSCAN算法(Density-BasedSpatialClusteringofApplicationswithNoise)是基于密度的方法中比较有代表性的聚类算法。DBSCAN算法聚类时是将密度相连的样本的最大集合视为簇,通过划分样本高密度区域和低密度区域,将密度足够高的区域划分为簇。7.3.2聚类方法的介绍DBSCAN算法在计算时需要预设两个参数:(簇的半径),(簇内最少样本数)。DBSCAN算法通过扫描数据集中所有样本,若被扫描样本的邻域内包含的样本数大于,则创建以该样本为中心的簇;若某中心样本同时属于另一个簇,则合并这些簇。直到任何簇都没有新增样本时,计算结束。7.3.2聚类方法的介绍图7-14为DBSCAN算法的伪代码。预设:数据集X,簇半径Eps,簇最少样本数MinPtsfor
数据集X中每个样本Xiif样本xi已被标记thencontinue;else扫描样本xi的邻域Eps(xi)ifEps(xi)含的样本数<MinPtsthen标记样本xi为离群点else标记样本xi为中心点,构建新簇Cj,将邻域Eps(xi)中所有样本归入簇Cjfor
簇Cj中未被标记的样本yi扫描样本yi的邻域Eps(yi)ifEps(yi)包含的样本数≥MinPtsthen将邻域Eps(yi)中所有未被归入任一簇的样本归入簇Cjendifendforendifendifendfor图7-14DBSCAN算法的伪代码7.3.2聚类方法的介绍基于网格的聚类算法(grid-basedmethods)4基于网格的方法是在输入的数据集中构造一个网格结构,方法是在数据集中将空间划分为有限个网格单元(cell),网格单元是根据样本属性用矩形块划分形成的值空间,每个样本都会被分到一个网格单元中。基于网格的聚类算法的计算对象不是数据集中的单个样本,而是样本组成的单个的网格单元,直接对网格单元进行聚类。基于网格的聚类方法优点是:算法处理速度快,由于对网格单元进行聚类而不是单个样本,处理花费的时间与数据集中原有的样本数量无关,而是由划分的网格单元的数量决定;缺点是:由于网格单元是根据样本属性划分的值空间,因此只能发现边界是水平或垂直的簇,而无法对非线性边界的簇进行划分,适用性较低;在高维数据集中聚类效果较差,聚类开始之前需对样本属性进行量化,对量化标准敏感。因此基于网格的聚类方法多与其他方法进行结合使用,通常会有基于网格和基于密度组合的聚类算法,代表性算法有STING算法等。7.3.2聚类方法的介绍基于模型的聚类算法(model-basedmethod)5以上介绍的聚类方法均为判别式聚类(基于相似性或距离),而基于模型的方法为生成性聚类,基于数据集的特性选择合适的模型对目标数据集进行聚类。基于模型的算法存在一个潜在的假设:任何数据集都是由一系列的统计概论分布所决定的。因此基于模型的算法针对需聚类的数据集假设一个统计模型,即聚类的目标函数,目标函数可以是样本密度分布函数或其他,再从数据集中寻找能够满足目标函数的聚类。基于模型的算法在聚类中可以自行修正聚类的簇的数量,不需要提前预设簇的个数。但由于方法中使用的模型不确定,因此时间和空间复杂度变化不稳定,不能用于大规模数据集的聚类;而且对于偏斜的数据平衡性较差。基于模型的聚类算法通常可分为两种思路:基于统计的方法和基于神经网络的方法。7.3.2聚类方法的介绍7.3.3聚类方法的选择本章选用聚类的方法解决不均衡数据集问题,可以在不改变数据集中样本数量的情况下改变样本分布,使得稀有类样本数量与普通类样本数量达到均衡,以求稀有类样本特征凸显。基本思路是利用聚类算法,将不均衡数据集中的普通类样本进行聚类,划分成不同的簇,然后将每个簇与稀有类样本组合为数据子集,利用这些数据子集对分类器进行训练。因此对聚类的结果要求每个簇中普通类样本数量与稀有类样本量达到均衡,以便于提取稀有类特征。本章先对聚类中目前较常见且成熟的聚类算法进行对比,所选算法如表7-1所示,从中选出分簇均衡性能最好的算法来进行不均衡数据集的处理。
表7-1聚类算法聚类算法方法分类聚类算法方法分类K-means基于划分(partitioningmethods)DBSCAN基于密度(density-basedmethods)Birch基于层次(hierarchicalmethods)EM基于模型(model-basedmethod)7.3.3聚类方法的选择本章从UCI数据集中选出符合不均衡数据集要求的数据集,利用表7-1中的聚类算法进行分簇均衡性实验,对数据集中的普通类进行聚类。将聚类得到的各簇样本量与稀有类样本量进行对比,若两者样本量接近(两者比值为,),则说明聚类结果均衡度较好。数据集具体信息如表7-2所示。7.3.3聚类方法的选择数据集样本总数普通类样本数稀有类样本数普通类稀有类样本比值Sick3772354123115.3Hypothyroid3774348129311.8Page_block547349135608.8Mushroom4630420842210.1表7-2UCI数据集详细信息7.3.3聚类方法的选择Sick数据集中各聚类算法对普通类的聚类结果如表7-3所示。表7-3Sick数据集聚类结果簇序号K-meansBirchDBSCANEM1249330830719022712954181328521817345375322546013372185685119776217728327353319890176569308223163131040347508112572370171122846051913148114150214233223416315229120112253%033%40%7.3.3聚类方法的选择Hypothyroid数据集中各聚类算法对普通类的聚类结果如表7-4所示。表7-4Hypothyroid数据集聚类结果簇序号K-meansBirchDBSCANEM1380310345714925612953318366277146453347477561522611314759684919754316753317596375831131332182923515241822104818439811244426315554%027%36%7.3.3聚类方法的选择Page_block数据集中各聚类算法对普通类的聚类结果如表7-5所示。表7-5Page_block数据集聚类结果簇序号K-meansBirchDBSCANEM140341031057512796161241577355628022654458472383025838633498256409193981657132417218888826031132939595861523374555%11%11%22%7.3.3聚类方法的选择Mushroom数据集中各聚类算法对普通类的聚类结果如表7-6所示。表7-6Mushroom数据集聚类结果簇序号K-meansBirchDBSCANEM147438774561922542101327240373715768768439232272288531975418172862841140170476857704168210212444892401930620410325503122050%060%07.3.3聚类方法的选择表7-7为上述4个数据集聚类结果的综合比较,可以发现:K-means算法的聚类结果均衡度是4种方法中最优的。由于本章中使用聚类方法的目的是改变不均衡数据集的样本分布,使得稀有类特征能够凸显出来,因此需要普通类样本聚类生成的簇,应与稀有类样本量达到均衡。通过上述实验数据对比,K-means算法的聚类均衡度效果优于其他3种方法,因此选择K-means作为处理不均衡数据集的聚类方法。7.3.3聚类方法的选择表7-74个数据集聚类结果综合比较数据集K-meansBirchDBSCANEMSick53%033%40%Hypothyroid54%027%36%Page_block55%11%11%22%Mushroom50%060%0平均均衡度53%3%33%25%7.3.3聚类方法的选择7.4.1Adaboost算法介绍组合学习方法是一种通过提升弱分类器的性能而达到分类标准的算法,其核心思想就是综合多个分类器的分类结果而不是仅用单分类器完成分类,通过将各基分类器的分类结果结合起来,做出最优的选择。Boosting就是一种经典的组合学习方式,其通过将简单、粗糙、准度较差的基分类器的结果集中起来进行学习,获得最终的精确、复杂的分类器。Adaboost(AdaptiveBoosting)算法是一种对Boosting算法的改进,它的提出是为了解决利用PAC学习理论是否可以将一个弱分类器“提升”为一个强分类器的问题。Adaboost算法对该问题给出了肯定性的回答,即:可以通过多轮迭代提高弱分类器的分类精度,利用Adaboost算法可以显著提高组合学习方法的性能。Adaboost算法被以ICDM2006为依托组建的数据挖掘十大算法提名委员会专家评选为数据挖掘十大算法之一。在Adaboost算法中,所有基分类器(基分类器之间要求相对独立)对经过加权分布处理的训练集进行抽样训练,每一轮训练完成时,训练集中的所有样本根据当前分类器的分类性能相应调整自身的权重,这样,在下一轮训练中,分类器会自行加强学习上一轮分类中出错的样本。因此,Adaboost算法对稀有类分类有很好的分类性能。7.4.1Adaboost算法介绍Adaboost算法通过改变数据集的分布来提升基分类器的分类性能,通过从数据集中抽样获得初始训练集,对基分类器进行训练。在迭代过程中,它根据每一轮分类中样本的分类结果正确与否,以及基分类器的分类性能来确定每个样本的权重,然后对更新权重后的样本进行下一轮迭代训练。最终将各轮分类结果进行融合,形成最终的决策分类器。Adaboost算法的一般过程如下:给定数据集,其中,;迭代轮数T。7.4.1Adaboost算法介绍样本权重初始化:从数据集D中抽取子集,对弱分类器进行训练,获得分类结果;计算分类误差,;根据权重更新公式对数据集D中的样本更新权重:(7-6)其中是正规因子,保证;endfor最后通过投票得到分类结果,获得最终分类器,输出结果。7.4.1Adaboost算法介绍Adaboost在每轮迭代的更新样本权重时,对分类错误的样本增加权重,同时将分类正确的样本权重减少,这样在下一轮分类中对已正确分类的样本关注度下降,而把注意力更多转移到前一轮分类错误的样本中,分类错误的样本被抽为训练样本的概率提高,可以在下一轮分类器训练中增加这些样本的特征识别,提升基分类器的准确度;同时在每轮迭代中,准确率高的分类器能获得较高的权重,在最终投票决策阶段,分类结果向准确率高的基分类器倾斜,使得最终分类结果更加准确。7.4.1Adaboost算法介绍7.4.2Adaboost算法的研究现状Adaboost算法通过对样本赋予不同的权重,经过多次迭代分类来提升分类器的性能。在迭代过程中,分类正确的样本权重会减小,由于样本易于识别,可以将分类重点转移到其他样本中;而分类错误的样本会被赋予较高的权重,由于样本难以识别,会在下一轮分类中获得更多的关注。但Adaboost算法没有考虑稀有类分类与普通分类之间的区别,即稀有类分类更关注稀有类样本的识别精度,而不用考虑普通类样本的分类情况。在迭代过程中,存在离群的普通类样本难以识别,从而使得该样本权重不断提高,扰乱分类器识别稀有类样本。此外,对于难以识别的离群稀有类样本,若在迭代过程中不断增加此类样本的权重,会使已被正确分类的样本被逐渐忽视,造成稀有类样本的特征提取出现偏差。因此,许多研究中对Adaboost算法的权重更新机制和样本抽取方法进行改进,以提高算法的分类精度。潘俊等为了防止样本权重扩张给分类器正确预测造成危害,在Adaboost算法权值更新的基础上,增加参数对权重更新的速度进行控制,减小当稀有类样本中离群样本较多时,样本权重扩散对其他正确识别的稀有类的影响。在迭代过程中,当样本被正确分类时,不再减小样本权重,避免正确预测的样本被忽略;当分类不正确时才更改权重,引入控制参数1-FPR(FalseNegativeR
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 学校建筑工程质量保证措施
- 水电站引水管道安装冬季施工方案
- 医疗灭菌设备培训课件
- 填埋场地下水环境质量评估报告
- 幼儿园周边安全工作制度
- 市政路灯安装工程质量通病防治手册
- 综合管理部经理助理岗位职责培训
- 商场大型活动消防安全保障方案
- 预制装配式住宅结构维护与加固技术方案
- 商用中央吸尘系统安全运维管理规范
- 《护理管理培训》课件
- 2026重庆国际物流枢纽园区建设有限责任公司及子公司招聘19人笔试模拟试题及答案解析
- 检察官遴选考试真题及答案解析
- 江苏省无锡市梅村高级中学2025-2026学年高一上学期10月阶段检测物理试卷(含答案)
- 2026秋新北师大版数学六年级上册教学课件:数学好玩 五子棋
- TCNAS 59-2026 《患者自控镇痛护理》全面解读
- 生物酶制剂生产流程技术指南
- 2026及未来5年中国全自动商用咖啡机市场数据分析及竞争策略研究报告
- 超声评估胆囊腺肌症
- TSG08-2026《特种设备使用管理规则》解析
- 北师大版四年级上册书法练习指导 教案
评论
0/150
提交评论