知识挖掘及分析评估研究报告.docx

目录第一章 绪论11.1研究背景及研究的意义11.2国内外研究的现状31.3知识挖掘内容简介41.3.1知识挖掘的目标41.2.2知识挖掘的处理过程6第二章 知识挖掘的主要研究方法92.1统计分析方法92.2机器学习112.3可视化14第三章 知识挖掘中常用算法简介163.1 C4.5 算法163.1.1 C4.5算法简介163.1.2 C4.5算法原理173.2 支持向量机193.2.1 支持向量机算法简介193.2.2支持向量机原理203.3 K-Means算法243.4 Apriori 算法253.5 kNN算法263.6 分类模型28第四章 经典知识挖掘模型举例304.1商业银行客户管理系统知识挖掘模型304.1.1 系统总体设计304.1.2 数据预处理的实现314.1.3 数据挖掘的实现324.2 教学评价系统知识挖掘模型354.2.1 系统总体设计354.2.2 构造决策树364.2.3 数据预处理394.2.4 决策树剪枝41第五章 基于知识挖掘的分析评估研究445.1 挖掘模型的评估与应用445.2 基于知识挖掘的分析评估框架455.3 分析评估的主要方法465.3.1 保持方法465.3.2 随机二次抽样465.3.3 交叉验证475.3.4 自助法47第一章 绪论1.1研究背景及研究的意义全球范围内数据库中存储的数据量正急剧增加,数据库系统提供了对这些数据的管理和简单处理能力，人们可以利用这些数据进行商业分析和科学研究。面对如此庞大的数据库人们的需求已经不只是简单的查询和维护，而是希望能够对这些数据进行较高层次的处理和分析以得到关于数据总体特征和对发展趋势的预测。而这些功能是数据库技术、人工智能和统计学等无法单独完成的。“我们淹没在信息之中，但仍于知识的饥渴中”Johe Naisbett说。由此，知识挖掘技术便应用而生。知识挖掘的定义几经变动，最新的描述性定义是由Usama M.Fayyyad等给出的：知识挖掘是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。数据是指有关事实的集合,记录和事物有关的原始信息。模式是一个用语言来表示的一个表达式，它可用来描述数据集的某个子集，我们所说的知识，是对数据包涵的信息更抽象的描述。对大量数据进行分析的过程，包括数据准备、模式搜索、知识评价，以及反复的修改求精；该过程要求是非平凡的，意思是要有一定程度的智能性、自动性(仅仅给出所有数据的总和不能算作是一个发现过程)。有效性是指发现的模式对于新的数据仍保持有一定的可信度。新颖性要求发现的模式应该是新的。潜在有用性是指发现的知识将来有实际效用，如 用于决策支持系统里可提高经济效益。最终可理解性要求发现的模式能被用户理解，目前它主要是体现在简洁性上。有效性、新颖性、潜在有用性和最终可理解性综合在一起可称之为兴趣性。由于数据挖掘是一门新兴学科，况且它又是一门受到来自各种不同领域的研究者关注的边缘学科，因此产生很多不同的术语，除了称为“知识挖掘”外，主要还有如下若干种称法：“ 数据发现”、“数据开采”、“知识抽取”、“信息发现”、“知识发现”、“智能数据分 析”、“探索式数据分析”、“信息收获”和“数据考古”等等。“数据挖掘”被许多研究者看作仅是数据发现的一个步骤。相对来讲，数据开采主要流行于统计界、数据分析、数据 库和管理信息系统(MIS)界；而数据发现则主要流行于人工智能和机器学习界。知识挖掘虽然只有十年的历史，但它已被越来越多的领域所采用,并取得了较好效果。这些 领域有科学研究、市场营销、金融投资、欺诈甄别、产品制造、通信网络管理等。由加州理 工学院喷气推进实验室与天文科学家合作开发的SKICAT(Sky Image Cataloging and Analys is Tool)是第一个获得相当成功的数据挖掘应用，已经帮助科学家发现了16颗极其遥远的类星体。虽然知识挖掘已经受到许多关注并取得了广泛应用，但它仍处于发展的早期，还有很多研究 难题和面临的挑战，如数据的巨量性、动态性、噪声性、缺值和稀疏性，发现模式的可理解性、兴趣或价值性，应用系统的集成，用户的交互操作，知识的更新管理，复杂数据库的处理等等。1.2国内外研究的现状知识挖掘的设想始于20世纪80年代末,当时,出现了从数据源中发掘新信息模式及算法的设计,被称为数据库中的知识发现KDD。2001年,Gartneroroup的一次高级技术调查将数据挖掘和人工智能列为未来三到五年内将对工业产生深远影响的五大关键技术之首,并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位知识挖掘,顾名思义是把深埋着的知识开采出来,它包括两方面:(l)从已编码的信息即从数据库、数据仓库中发现新的知识,称数据挖掘(DataMining);(2)未经编码处理即未转化为信息的知识提取、整理和积累。知识挖掘的出现是由于此前的信息或知识数据库存在着种种局限,限制了对数据库中蕴涵知识的有效利用,局限因素包括:信息膨胀,知识供需失准,不能满足不同人员的个性化需求。经常获得的是过时的、无时效性的知识。提供的知识无法解决实际问题或发挥效用。数据库中的知识可能没有以正确的形式被正确地表现出来。由于上述原因的干扰,数据库中信息和知识的使用率很低。底层标准混乱,数据库信息无法有效利用和转换,形成信息孤岛。如果不能很好地解决这些问题,将对知识管理的实施形成极大的挑战,很可能使知识管理的科学理念被架空。因此,要成功地进行知识管理,就必须研究开发先进的知识挖掘、分析和提炼技术,从而形成一个资源丰富的知识库,来满足用户的需求。从1989年知识发现概念提出到日前为止,知识发现的研究重点己从早期的以算法为主,转向现阶段的系统应用,注重多种发现策略和技术的集成,以及多学科之间的相互渗透。关于知识挖掘模型的应用,国内外的很多学者已经做了大量研究工作,而且在很多应用领域取得了丰硕的成果,如卡内基梅隆大学的万维网信息挖掘研究系统WebKB;由国家自然科学基金资助研究开发的WebMine系统,实现了一个人机交互的基于web的数据挖掘系统;个人主页搜索系统Ahoy、网结构知识挖掘系统Parasite等。1.3知识挖掘内容简介1.3.1知识挖掘的目标知识挖掘主要利用各种挖掘算法,从数据库中发现有关的知识,根据发现知识的不同种类,可以将知识挖掘的目标分为以下几类:(l)特征化和区分特征化(datacharacterization)是从与学习任务相关的一组数据中提取关于这些数据的特征式,这些特征式表达了该数据集的总特征。区分(datadiscrimination)是通过将目标对象的一般特性与其他指定对象的相应特性进行对比,可以将目标对象与其它指定对象区分开来。(2)关联规则(Assoeiationrule)所谓关联规则,是指数据对象之间的相互依赖关系,一个关联规则的形式为A1、A2 ,如果B1、B2,出现,那么A1、A2,一定出现,这表明数据A1、A2,与B1、B2,有着某种联系,而发现规则的任务就是从数据库中发现那些确信度(Confidence)和支持度(Support)都大于给定值的规则。从数据库中发现关联规则近几年研究最多。目前,已经从单一概念层次关联规则的发现发展到多个概念层次的关联规则的发现。在概念层次上的不断深入,使得发现的关联规则所提供的信息越来越具体。在许多实际应用中,能够得到的相关规则的数目可能是相当大的,而且,用户也并不是对所有的规则感兴趣,有些规则可能误导人们的决策,所以,在规则发现中常常引入兴趣度(指规则在一定数据域上为真的知识被用户关注的程度)概念而基于更高概念层次上的规则发现研究(如一般化抽象层次上的规则和多层次上的规则发现)则是当前研究的重点之一。(3)分类(Classifieation)分类是最基本的一种认知形式。数据分类就是对数据库中的每一类数据,挖掘出关于该类数据的描述或模型,而这些数据库中的类是事先利用训练数据建立起来的。作为数据挖掘的一个重要主题,数据分类在统计学、机器学习、人工智能等领域中得到了较早的研究,只是近些年来,人们才将它与数据库技术结合起来解决实际问题。(4)聚类(Clustering)在机器学习中,数据分类称为监督学习,而数据聚类则称为非监督学习,两者所采用的方法相差甚远。数据聚类是将物理的或抽象的对象分成几个群体,在每个群体内部,对象之间只有较高的相似性,而在不同群体之间,相似性则比较低。一般地,一个群体也就是一个类,但与数据分类不同的是,聚类结果主要基于当前所处理的数据,我们事先并不知道类目结构及每个对象所属的类别。(5)预测通过对数据的分析处理,估计数据库中某些丢失数据的可能值或一个数据集中某种属性值的分布情况。一般是利用数理统计的方法,找出与所要预测的属性值相关的属性,并根据相似数据的分析估算属性值的分布情况。(6)孤立点分析数据库中可能包含这样一些数据对象,它们与数据的一般行为或模型不一致。这些数据对象是孤立点大部分数据挖掘方法将其视为噪声而丢弃。然而一些应用中罕见的事件可能比正常出现的更有用,所以需要进行孤立点的分析。(7)演变分析演变分析是用来描述行为随时间变化的对象的规律或趋势,并对其建模。演变分析一般包括数据序列分析、周期匹配等。在实际挖掘中,经常几种功能相互配合,同时使用。1.2.2知识挖掘的处理过程KDD处理过程主要包括数据抽取、数据预处理、数据挖掘、以及模式评估等基本阶段。1996年,usamaM.Fa0ad等人给出的KDD阶梯处理过程是公认的知识挖掘处理过程:图1-1 知识挖掘处理过程(l)数据处理,数据处理包括:数据选择、数据预处理和数据变换,数据选择的目的是确定发现任务的操作对象,即目标数据,是根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换(如把连续值数据转换为离散型的数据,以便于符号归纳,或是把离散型的转换为连续值型的,以便于神经网络)等。当数据挖掘的对象是数据仓库时,一般来说,数据预处理己经在生成数据仓库时完成了。数据变换的主要目的是消减数据维数或降维,即从初始特征中找出真正有用的特征以减少数据挖掘时要考虑的特征或变量个数。(2)数据挖掘,数据挖掘阶段首先根据对问题的定义明确挖掘的任务或目的,如分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后,就要决定使用什么样的方法。选择实现算法有两个考虑因素:一是不同的数据有不同的特点,因此需要用与之相关的算法来挖掘;二是用户或实际运行系统的要求,有的用户可能希望获取描述型的、容易理解的知识(采用规则表示的挖掘方法显然要好于神经网络之类的方法),而有的用户只是希望获取预测准确度尽可能高的预测型知识,并不在意获取的知识是否易于理解。关于数据挖掘所采用的一些常用方法,赵丹群对知识挖掘中经常使用的方法作了讨论总结有统计学(包括各种分类、聚类、预测模型以及Bayes方法)、决策树、遗传算法、人工神经网络、粗集理论等。张瑞玲也总结了知识挖掘中几种常用的挖掘技术:数据仓库技术、联机分析处理技术、数据挖掘技术、信息可视化技术等。(3)结果解释和评估,数据挖掘阶段发现出来的模式,经过评估,可能存在冗余或无关的模式,这时需要将其剔除,也有可能模式不满足用户要求,这时则需要整个发现过程回退到前续阶段,如重新选取数据、采用新的数据变换方法、设定新的参数值,甚至换一种算法等等。另外,KDD由于最终是面向人类用户的,因此要对发现的模式转换为用户容易理解的其它表示形式。第二章 知识挖掘的主要研究方法2.1统计分析方法统计分析方法是利用统计学、概率论的原理对关系中各属性进行统计分析,从事物外在上的表现去推断各属性之间的关系和规律。统计分析方法是最基本的知识挖掘方法之一。常用的统计分析方法有:判别分析(贝叶斯判别、费歇尔判别、非参数判别等)、因子分析、相关分析、回归分析(多元回归、自回归等)以及近年来提出的模糊集、支持向量机和粗糙集。下面对其中的几种主要方法做一个简要介绍。l)判别分析通过建立一个或多个判别函数,并确定一个判别标准,根据测定的观察值将未知属性的对象划归己知类别中的一类。2)因子分析该方法是用较少的综合变量来表达多个观察变量。根据相关性大小把变量分组, 使得各组内的变量之间相关较高,不同组变量间的相关较低。3)相关分析和回归分析相关分析是用相关系数来度量变量间的相关程度,而回归分析则是用数学方程来表示变量间的数量关系,分为线性回归和非线性回归两种类型。4)支持向量机(SVM)支持向量机建立在计算学习理论的结构风险最小化原则之上。其主要思想是针对两类分类问题,在高维空间中寻找一个超平面作为两类分割,以保证最小的分类错误率。SVM的一个主要优点是可以处理线性不可分的情况。5)粗糙集粗糙集理论是一种新的数学工具,用于处理含糊性和不确定性。粗糙集是由集合的下近似、上近似来定义的。下近似中的每一个成员都是该集合的确定成员,而不是上近似中的成员肯定不是该集合的成员。粗糙集是一种处理数据不确定性的数学工具,常与规则归纳、分类和聚类等处理过程结合起来使用。粗集理论是一种处理含糊和不确定问题的新型数学工具,利用粗集理论可以处理的问题包括数据简化、数据相关性发现、数据意义的评估、数据的近似分析等。从实际系统采集到的数据可能包含各种噪声,存在许多不确定因素和不完全信息有待处理。传统的不确定信息的处理方法,如模糊集理论。证据理论等因需要数据的先验信息,有时在处理大容量数据方面无能为力。粗糙集作为一种软计算方法,可以克服传统不确定知识处理方法的不足,并且和它们有机结合,可望进一步加强对不确定、不完全信息的处理能力。粗糙集从决策表挖掘规则,其关键步骤是求值约简或数据浓缩,包括属性约简和值约简两个过程。决策表约简经常涉及到核和分明矩阵两个重要概念。一般来讲,决策表的相对约简有许多,其最小约简是人们的理想要求。另一方面决策表的核是惟一的,它定义为所有约简的交集,所以核可以作为求解最小约简的起点。分明矩阵突出属性的分辨能力,从中可以求出决策表的核以及规则。粗糙集理论和其他软计算方法的结合,能够提高数据挖掘能力。粗糙集与其他软计算方法的集成是数据挖掘的一种趋势。目前基于粗糙集的数据挖掘在以下方面有待深化:(1)粗糙集和其他软件计算方法的进一步结合问题;(2)粗糙集知识采掘的递增算法;(3)粗糙集运算的并行算法及硬件实现,将大幅度改善数据挖掘的效率。面对海量数据,有必要设计高效的启发式简化算法或研究实时性较好的并行算法;(4)扩大处理属性的类型范围,即使粗糙集理论在处理连续值上能取得较好的效果。2.2机器学习机器学习一般被定义为一个系统自我改进的过程,但仅仅从这个定义来理解和实现机器学习是困难的。从最初的基于神经元模型以及函数逼近论的方法研究,到以符号演算为基础的规则学习和决策树学习的产生,和之后的认知心理学中归纳解释类比等概念的引入,至最新的计算学习理论和统计学习的兴起,机器学习一直都在相关学科的实践应用中起着主导作用。Boes和Mhapaarta归纳了知识挖掘中使用的机器学习技术主要有以下5种:l)归纳推理运用决策树,根据不同的特征对数据进行分类。首先从数据源中选择一个变量作为因变量,然后运用扩大组间差别并缩小组内差异的统计测试方法对每一变量的值进行分组,找出对因变量来说最具有预测性的变量,那么该变量就可以设置为决策树的一个节点。决策树的最大优点是很直观;决策树的缺点是随着数据复杂性的提高,其分支数也增多,因此,管理起来也就越困难。所谓决策树就是一个类似流程图的树形结构,其中树的每个内部结点代表对一个属性的测试,其分枝就代表测试的每个结果,而树中每个叶结点就代表一个类型,树的最高层结点就是根结点。决策树是概念描述空间的一种有效方法,也是许多归纳系统常采用的知识表示形式。它的主要优点是描述简单,分类速度快,特别适合大规模的数据处理。决策树起源于概念学习系统CLS,其思路是找出最有分辨能力的属性,把数据库划分为许多子集,构成一个分枝过程,然后对每一子集递归调用分枝过程,直到所有子集包含同一类型的数据。最后得到的决策树能对新的例子进行分类,CLS的不足是它处理的学习问题不能太大。为此,Qululan提出了著名的ID3学习算法,通过选择窗口来形成决策树。从示例学习最优化的角度分析,理想的决策树分为三种:叶子数目最少,叶子结点深度最小,叶结点数最少且叶结点深度最小。寻找最优决策树己被证明是NP问题。ID3算法试图减少树的平均深度,但忽略了叶子数目的研究,其启发式函数并不是最优的。2)神经网络由类似人脑神经元的处理单元(又称节点)组成,输入节点通过隐藏节点与输出节点的连接从而组成一个多层网络结构。节点的输入信号等于所有通过其输入链接到达此节点的信号的加权和神经网络通过对历史样本数据进行反复的网络训练来学习,在训练过程中,处理单元运用一种称为学习规则的数学方法对数据进行汇总和转换,并调节链接节点的权值。神经网络由相互连接的输入层、中间层、输出层组成。中间层由多个节点组成,完成大部分网络工作。输出层输出数据分析的执行结果。神经网络的最大优点是能精确地对复杂问题进行预测。其缺点是处理大数据集时效率较低,用户在使用这种方法的时候需要具备相当的建立和运行该系统的工具知识。3)事例推理每个事例包括两部分内容:问题描述和问题的解决方法(可能是一个过程描述或者一个等级分类)。提出问题后,系统会寻找匹配事例和解决方法。其优点是能够较好地处理污染数据和缺失数据,非常适用于有大量事例的领域。4)遗传算法是一种基于生物进化过程的组合优化方法。其基本思想是适者生存,基本操作包括繁殖、杂交和变异三个过程。繁殖过程是从一个整体中选择基于某种特定标准的信息并对要求解的问题编码,产生初始群体,计算个体的适应度。杂交过程是把一个信息的某一部分与另一个信息的相关的部分进行交换;变异过程随机改变信息的某一部分以得到一个新的个体。重复这个操作,直到求得最佳或较佳的个体。遗传算法的优点是能够较好地处理污染数据和缺失数据,易于和其它系统集成。然而,作为一种较新的机器学习技术,用户在使用这种方法的时候需要具备相当的建立和运行该系统的工具知识。5)归纳性逻辑程序用一级属性逻辑来定义来描述概念。首先定义正面和负面的例子,然后对新例子进行等级划分。这一方法具有较强的概念描述机制,具有以下两个优点:一是能较好地表达复杂关系;二是较好地体现专业领域知识,因而用该方法得出的模型易于理解。然而,和遗传算法一样,作为一种较新的机器学习技术,用户在使用这种方法的时候需要具备相当的建立和运行该系统的工具知识。其中,商业应用最为广泛的是归纳推理,其次是神经网络,基于事例的推理,基因算法和归纳性逻辑程序。2.3可视化可视化就是把数据、信息和知识转化成为可视的表示形式的过程。可视化技术为人类与计算机这两个最强大的信息处理系统之间提供了一个接口。使用有效的可视化界面,可以快速高效地分析数据,发现其中隐藏的特征、关系、模式和趋势等。根据是否包括物理数据,可视化技术粗略地分为两类:科学计算可视化和信息可视化。科学计算可视化显示的对象涉及标量、矢量和张量等不同类别的空间数据,研究的重点放在如何真实、快速地显示三维数据场。信息可视化则侧重于多维的标量数据,研究的重点放在设计和选择合适的显示方式表示庞大的多维数据及其相互之间的关系,以便于用户了解。文本知识挖掘技术主要定位于信息可视化。可以将信息可视化看作是从数据信息到可视化形式再到人的感知系统的可调节的映射。主要的可视化方法包括:基于几何投影技术的可视化方法,基于图像技术的可视化方法,面向像素的可视化方法和分层技术的可视化方法。第三章 知识挖掘中常用算法简介3.1 C4.5 算法3.1.1 C4.5算法简介C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。 C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值的属性的不足； 2) 在树构造过程中进行剪枝；3) 能够完成对连续属性的离散化处理；4) 能够对不完整数据进行处理。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。决策树学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。 决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。决策树是如何工作的决策树一般都是自上而下的来生成的。选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。从根到叶子节点都有一条路径，这条路径就是一条“规则”。决策树可以是二叉的，也可以是多叉的。对每个节点的衡量： 1)通过该节点的记录数 2)如果是叶子节点的话，分类的路径 3)对叶子节点正确分类的比例。3.1.2 C4.5算法原理首先，说明一下如何计算信息增益率。熟悉了ID3算法后，已经知道如何计算信息增益，计算公式如下所示IGEx,a=HEx-vvalue(a)|xEx|valuex,a=v|Ex|HxEx|valuex,a=v （3-1） 或者，用另一个更加直观容易理解的公式计算：o 按照类标签对训练数据集D的属性集A进行划分，得到信息熵： infoD=-i=1mpilog2(pi) （3-2） 按照属性集A中每个属性进行划分，得到一组信息熵： infoA D=j=1vDJDinfo(Dj) （3-3）o 计算信息增益然后计算信息增益，即前者对后者做差，得到属性集合A一组信息增益：gainA=infoD-infoA (D) （3-4）这样，信息增益就计算出来了。o 计算信息增益率下面看，计算信息增益率的公式，如下所示IGR(Ex,a)=IG/IV （3-5）其中，IG表示信息增益，按照前面我们描述的过程来计算。而IV是我们现在需要计算的，它是一个用来考虑分裂信息的度量，分裂信息用来衡量属性分裂数据的广度和均匀程序，计算公式如下所示： IVEx,a=-vvalueaxEx|valuex,a=vEx*log2(xEx|valuex,a=vEx) （3-6）简化一下，看下面这个公式更加直观： HV=-jp(vj)logp(vj) （3-7）其中，V表示属性集合A中的一个属性的全部取值。3.2 支持向量机3.2.1 支持向量机算法简介支持向量机，简称SV机（论文中一般简称SVM）。它是一种監督式学习的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。 支持向量机属于一般化线性分类器.他们也可以认为是提克洛夫规范化方法的一个特例。这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区。因此支持向量机也被称为最大边缘区分类器。在统计计算中，最大期望算法是在概率模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量。最大期望经常用在机器学习和计算机视觉的数据集聚领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值从而计算参数的最大似然估计。M 步上找到的参数然后用于另外一个 E 步计算，这个过程不断交替进行。SVM的主要思想可以概括为两点： (1) 它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；(2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。3.2.2支持向量机原理起初，SVM主要用来解决两类别的分类问题，即在类别间寻找一个最优分类超平面，使分类错误率最小。如图2-12所示，图中黑点和白点代表两类样本，为分类线，为过与分类线最近点且与分类线平行的直线，二者之间的距离成为分类间隔。所谓的最优分类超平面就是要求分类线不但能将两类样本无差错的分离开，而且要能使两类别间的距离最大。 图2-1 二维空间SVM分类示意图假设个线性可分样本集，是类别标号，维空间中线性判别函数的为，分类面方程为： (3-8)对判别函数进行归一化，使所有样本满足，即离分类面最近的点需满足，则直线方程为： (3-9)可以求得平行线间距离为，则分类间隔等于。若使分类间隔最大，等价于使或最小。根据分类标号和式(2-29)有： (3-10)由式(2-30)可得： (3-11)也即 (3-12)满足式(2-32)且使最小的分类面称为最优分类超平面，上的样本点称为支持向量（Support Vector，SV）。由上可知，求最优分类超平面等价于求函数 (3-13)最小且w满足式(2-32)。定义拉格朗日函数： (3-14)其中为拉格朗日系数，且，求极小值等价于对求L函数的最小值。对的求偏导并令它们等于0得 (3-15)将代入式(2-34)，可得L函数变成参数为参数的函数： (3-16)根据对偶理论，求L函数最小值变成求解函数的最大值，即 (3-17)若为最优解，由式(2-35)可得： (3-18)根据karush-Kuhn-Tucker定理可知，最优解需要满足 (3-19)由式(2-39)和式(2-32)可知，对于大多数样本点的为0，只有少部分样本点的不为0，这些样本点即为支持向量，只有支持向量影响最终的分类。于是最优分类函数可表示为 (3-20)其中sgn表示符号函数，为分类阈值，可由任一支持向量通过式(2-32)求得。表示支持向量。当样本线性不可分时，需要在条件式(2-40)基础上引入松弛变量 (3-21)求最优分类面即求 (3-22)类似地，其对偶问题的约束条件变为 (3-23)函数以及最优分类函数与线性可分情况下类似。其中C是可人为设定的一常数，它控制对样本错分的惩罚程度，常称为惩罚系数。3.3 K-Means算法k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k SK K=1,2,K,KK0 （4-6）（5）最好所得到的客观实体的属性就是根节点了。3）每个客观实体的属性都可能有不同个树的叶子节点，将不同的客观实体分成不同的机会，每一个结合就是当前根节点的叶子节点。4）根本步