6数据挖掘基本算法

数据仓库与数据挖掘2数据仓库与数据挖掘第一章数据仓库与数据挖掘概述第二章数据仓库的分析第三章数据仓库的设计与实施第四章信息分析的基本技术第五章数据挖掘过程第六章数据挖掘基本算法第七章非结构化数据挖掘第八章离群数据挖掘第九章数据挖掘语言与工具的选择第十章知识管理与知识管理系统3第六章数据挖掘基本算法数据挖掘的核心是为数据集建立模型的过程。所有的数据挖掘产品都有这个建模过程，不同的是它们构造模型的方式互不相同。进行数据挖掘时可以采用许多不同的算法。4第六章数据挖掘基本算法6.1分类规则挖掘6.2预测分析与趋势分析规则6.3数据挖掘的关联算法6.4数据挖掘的聚类算法6.5数据挖掘的统计分析算法6.6数据挖掘的品种优化算法6.7数据挖掘的进化算法56.1分类规则挖掘6.1.1分类与估值6.1.2决策树6.1.3贝叶斯分类66.1.1分类与估值分类的主要目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每一类找到一种准确的描述或模型。这种描述通常用谓词表示，由此生成的类描述用来对未来的测试数据进行分类。分类方法典型应用于信用卡系统中的信用分级、市场调查、疗效诊断、寻找店址等。76.1.1分类与估值分类问题的描述：输入数据，或称训练集（trainingset），是由一条条的数据源记录（record）组成的。一条记录包含了若干个属性（attribute）而组成的一个特征向量。训练集的每条记录还有一个特定的类标签（classlabel）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体的样本的形式可为样本向量：(v1,v2,,vn;c)。在这里vi(i=1,2,,n)表示字段值，c表示类别。86.1.1分类与估值1、分类所谓分类，就是为了理解事物特征并做出预测使用历史数据建立一个分类模型（即分类器）的过程。首先从数据中选出已经分好类的训练集，然后在该训练集上运用数据挖掘分类的技术，建立分类模型，最后对没有分类的数据进行分类。96.1.1分类与估值分类要有主题。列名数据类型取值的特点或内容说明Cost_ID数值唯一值客户的唯一标识符Time_Cost数值整型值客户留在公司的天数Line_Use字符VeryHigh,High,Medium,Low,VeryLow客户在上个月使用的时间（以分钟计）Trend字符Increase,Variedincrease,same,Varieddecrease,Decrease客户在过去6个月中使用趋势的指示器Status_Indicator字符SurreyHigh,SurreyFair,SurreyLow,Unknown对客户满意度的评价结果Cust_Type字符Loyal,Lost客户是留（Loyal）还是去（Lost）表6.1客户跳槽数据集106.1.1分类与估值2、估值估值与分类类似。分类描述的是离散型变量的输出，估值处理的是连续值的输出。分类的类别是确定的数目，估值的量是不确定的。一般来说，估值可以作为分类的前一步工作。首先给定一些输入数据，通过估值，得到未知的连续变量的值，然后根据预先设定的阈值，进行分类。116.1.1分类与估值3、分类方法与步骤常用的分类方法有决策树归纳、贝叶斯分类、贝叶斯网络、神经网络、K-最临近分类、基于案例的推理、遗传算法、粗糙集和模糊集方法。分类的一般步骤：（1）模型创建。对一个类别已经确定的训练数据集创建模型，每一条记录都属于一个确定的类别，使用类标签确定属性类别。模型可以用分类规则、决策树、或者数学方程的形式来表达。（2）模型使用。用创建的模型预测未来或者类型未知的记录，估计模型的准确率，使用创建的模型在一个测试数据集上进行预测，并将结果和实际值进行比较。126.1.1分类与估值4、评估分类方法判断分类的好坏可从如下指标进行考虑：预测准确度、速度、创建速度、使用速度、鲁棒性、处理噪声和丢失值、伸缩性、对磁盘驻留数据的处理能力、对模型的可理解程度、规则好坏的评价、决策树的大小和分类规则的简明性。目前公认的方法是分层交叉验证的损失函数方法（stratifiedcrossvalidatedlossfunction）。136.1.2决策树6.1.2.1决策树算法原理6.1.2.2常用决策树算法6.1.2.3决策树剪枝6.1.2.4由决策树提取分类规则6.1.2.5决策树方法在数据挖掘中的应用146.1.2.1决策树算法原理一棵决策树是这样一棵树，如图6.1所示。树中的每一个元素就是一个结点。每一个结点可以是叶结点，对应着某一类，也可以对应着一个划分，将该结点对应的样本集划分为若干子集，每个子集对应一个结点。全部是叶结点的树称为纯树。图6.1一般决策树结构156.1.2.1决策树算法原理决策树的一个例子如图6.2所示。它表示概念buys_computer，即，它预测AllElectronics的顾客是否可能购买计算机。在决策树中有两种结点：决策结点和状态结点。由决策结点引出若干树枝，每个树枝代表一个决策方案，每个方案树枝连接到一个新的结点。这个新的结点既可能仍是一个新的决策结点，也可能是一个状态结点。每个状态结点表示一个具体的最终状态。在决策树中，状态结点对应着叶结点。决策树用于解决分类问题时，决策结点表示待分类对象的属性，每个树枝表示它的一个可能取值，而状态结点则表示分类结果。166.1.2.1决策树算法原理fairexcellentyesno＞4031…40＜＝30Age?Student?Credit_ratingyesnoyesnoyes图6.2概念buys_computer的判定树，指出AllElectronics公司的顾客是否可能购买计算机（决策节点表示一个属性上的测试，每个状态（树叶）节点代表一个类（buys_computer=yes，或buys_computer=no））176.1.2.1决策树算法原理决策树算法的技术难点是如何选择一个好的分支方法进行取值。对一个分类问题或规则学习问题，决策树的生成是一个从上而下、分而治之的过程。为了分类一个特定数据项目，我们从根节点开始，一直向下判定，直到到达一个终端结点（叶子）为止。当到达一个终端结点时，一个决策便形成了。决策树也可以解释成一种特殊形式的规则集，其特征是规则的层次组织关系。186.1.2.1决策树算法原理优点：使用者不需要了解很多背景知识，只要训练事例能用属性→结论的方式表达出来，就能用该算法学习；决策树模型效率高，对训练集数据量较大的情况较为适合；分类模型是树状结构，简单直观，可将到达每个叶结点的路径转换为IF→THEN形式的规则，易于理解；决策树方法具有较高的分类精确度；可理解性；直观性。196.1.2.1决策树算法原理缺点：不易处理连续数据。数据的属性必须被划分为不同的类别才能处理，但是并非所有的分类问题都能明确划分成这个区域类型；对缺失数据难以处理，这是由于不能对缺失数据产生正确的分支进而影响了整个决策树的生成；决策树的过程忽略了数据库属性之间的相关性。206.1.2.1决策树算法原理传统的数据分类操作通常有以下两个步骤:（1）模型训练阶段：根据给定的训练集，找到合适的映射函数H:f(x)→C的表示模型。（2）使用上一步训练完成的函数模型预测数据的类别，或利用该函数模型，对数据集中的每一类数据进行描述，形成分类规则。216.1.2.1决策树算法原理在第一步中是使用决策树来代表映射函数，首先利用训练集建立决策树模型，找到训练集中各个属性之间的关系，然后根据这个决策树模型对输入数据进行分类。决策树分类模型的工作过程可以简单地用图6.3描述。图6.3决策树分类模型的工作过程图训练数据集决策树分类算法评估模式测试集预测预测结果类别未知的数据集1创建决策树过程2使用决策树模型预测过程226.1.2.1决策树算法原理决策树算法的大体框架都是一样的，都采用了贪心（非回溯的）方法来以自顶向下递归的方式构造决策树。它首先根据所使用的分裂方法来对训练集递归地划分递归地建立树的节点，直至满足下面两个条件之一，算法才停止运行：（1）训练数据集中每个子集的记录项全部属于一类或某一个类占压倒性的多数；（2）生成的树节点通过某个终止的分裂准则；最后，建立起决策树分类模型。236.1.2.1决策树算法原理目前评价决策树好坏主要使用如下几个量化评估标准。（1）预测准确性——描述分类模型准确预测新的或未知的数据类的能力。（2）模型强健性——在存在噪声及数据缺损的情况下，准确对求知其类的数据进行分类的能力。（3）描述的简洁性——针对分类发现模型对问题的描述能力，对于决策人员来说，模型描述越简洁，也就越易于理解，同时也就越受欢迎。（4）计算复杂性——依赖于具体的实现细节，空间和时间的复杂性将直接影响生成与使用模型的计算成本。（5）处理规模性——在巨量数据的情况下构造模型的能力，以及构造分类模型的精确度。246.1.2.2常用决策树算法（1）ID3算法（2）C4.5算法25（1）ID3算法ID3是Quinlan于1986年提出的，是机器学习中一种广为人知的一个算法，它的提出开创了决策树算法的先河，而且是国际上最早最有影响的决策树方法，在该算法中，引入了信息论中熵的概念，利用分割前后的熵来计算信息增益，作为判别能力的度量。26（1）ID3算法信息熵可以用来度量整个信源X整体的不确定性。定义6.1信息熵设某事物具有n种相互独立的可能结果(或称状态)：x1,x2,…,xn，每一种结果出现的概率分别为P(x1),P(x2),…,P(xn)，且有：11niixp(6-1)那么，该事物所具有的不确定量H(X)为：niiinnxPxpxIxpxIxpxIxpXH122211log(6-2)式（6-2）即为著名的香农信息量公式。27（1）ID3算法注意到式（6-2）中的对数以2为底，当n=2时且P(X1)=P(X2)=1/2时，H(X)=1比特。由此可见，一个等概率的二选一事件具有1比特的不确定性。所以，可以把一个等概率的二选一事件所具有信息量定为信息量的单位。任何一个事件能够分解成n个可能的二选一事件，它的信息量就是n比特。Quinlan的首创性工作主要是在决策树的学习算法中第一次引入了信息论中的互信息（称之为信息增益），以之作为属性选择的标准，并且将建树的方法嵌入在其中。其核心是在决策树的各级节点上选择属性，用信息增益作为属性选择标准，使得在每个非叶子节点上进行测试时，能够获得关于被测试例子最大的类别信息。28（1）ID3算法属性选择度量在树的每个节点上使用信息增益（informationgain）度量选择测试属性。这种度量称作属性选择度量或分裂的优良性度量。选择具有最高信息增益（或最大信息熵压缩）的属性作为当前节点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目达到最小，并确保找到一棵简单的（但不必是最简单的）树。29（1）ID3算法设训练数据集D=D1D2…Dn是n维有穷向量空间，其中Dj是有穷离散符号集，D中的每个元素d=t1,…,tn叫做例子，其中tjDj，j=1,2,…,n。设训练数据集D一共有m个不同类Ci（i=1,…,m），每类样例数为pi，i=1,2,…,m，设si是类Ci中的样本数，pi是任意样本属于Ci的概率，并用si/|D|估计。对给定的样本分类所需的期望信息由公式（6-3）给出：miiimppsssI1221log,,,(6-3)30（1）ID3算法以属性A作为决策树的根，A具有v个值v1,v2,…,vv，它将D分为v个子集{e1,e2,…,ev}。设sir是子集er中类Ci的样本数，则子集er中任意元组属于类Ci的概率用pir表示，并用sir/|er|估计，那么该子集er的期望信息是I(s1r,s2r,…,smr)，以属性A为根分类后所需的信息期望可以用公式（6-4）计算。vrmr