数据挖掘-分类

1、数据挖掘概念与技术 分类计算机信息与工程学院计算机科学与技术专业邱骏达事实的真相往往被层层迷雾所掩盖，我们不能在杂乱无章的荆棘道路上横冲直撞，我们要相信，磨刀不误砍柴工，当一大堆埋葬着巨大财富但又杂乱无章的数据堆放在我们面前的时候，好的分类方法，正确构建的分类器可以帮助我们进行快速、准确的数据分类。本章节学习脉络：分类的一般方法几种分类器的原理模型评估与选择提高分类准确率的技术万物溯其源何为分类分类是预测问题的主要类型之一。许多问题，诸如：银行贷款信用预测、销售人群预测、医学数据分析都需要用到分类的知识，通过构造模型或者分类器来预测“类标号”。所谓的“类标号”比如：贷款申请数据的“安全”或“危

2、险”，销售数据中的“是”或“否”。万物寻其因分类有何作用分类的目的：通过对大量同类信息的分类，来做出对整体数据集的分析，从而实现对事物结果的预测，辅助人们进行决策。分类的应用有很多种：比如欺诈检测、目标经营、性能预测、制造和医疗诊断。分类的一般方法分为两个阶段：学习阶段（构件分类模型）：建立描述预先定义的数据类或概念集的分类器。分类阶段（使用模型预测给定数据的类标号）：在分类阶段，要使用检验数据来评估分类规则的准确性。万物观其形分类的一般方法分类的第一阶段：学习阶段学习阶段又可称为监督学习，从监督学习四个字中，就可以大致掌握学习阶段的基本理念。所谓监督学习，就是分类器的学习在被告知每个训练元祖

3、属于哪个类的“监督”下进行的，也就是说学习阶段的训练数据是有其已知的“类标号”的。学习阶段理解的前期准备以银行贷款信用预测为例来认识学习阶段：注：在此只简单地把贷款的风险与贷款人的姓名、年龄段、收入三个属性进行“挂钩”，以求得简单易懂。举例：数据库中的数据表如下所示nameageIncomeSandy JonesyouthLowBill LeeyouthLowCaroline FoxMiddle_agedhighStep1：建立训练集训练集由数据库元组加上与它们相关联的类标号组成。其中训练集中的元组称为训练元组。训练集=数据元组+类标号（多组数据）训练元组=数据元组+类标号（单个数据库元组）n

4、ameageincomeLoan_decisionSandy Jones youthlowRiskyBill LeeyouthlowRiskyCaroline Fox middle_aged highSafeRick Fieldmiddle_aged lowriskyStep 2：分类算法通过分析或从训练集“学习”来确定分类规则，从而构造分类器。分类算法有很多：决策树、贝叶斯法等等。现在只是举例说明分类的一般过程，算法具体的分析在后面展开。经过分类算法的分析以后，此例的分类规则如下IF age=youth THEN loan_decision=riskyIF income=high THEN

5、loan_decision=safeIF age=middle_aged AND income=low THEN loan_decision=risky.学习阶段的最终小结学习阶段可以看做学习一个映射或者函数y=f(X)其中，y是给定元组X的类标号。学习以后这一函数常常以分类规则、决策树或数学公式的形式来表示。在上例中，就是以分类规则的形式来体现出学习阶段的结果的。分类阶段理解的前期准备每一个分类器都不是绝对准确的，也不是绝对高效或者适合所研究的问题的，分类的第二个阶段就是来评估分类器的预测准确率。Step 1：选取检验集如果以训练集中的训练元组来进行对分类器准确率的检验，那无疑是不合理的，因

6、为分类器趋向于过分拟合。某些数据太具有个性了，不适合来反映出共性。于是应该选举检验集来进行对分类器准确率的检验。检验集=检验元组+相关的类标号检验元组要选用数据库元组中未参与到训练集中的元组。Step 2：检验分类器的准确率分类器在给定检验集上的准确率是分类器正确分类的检验元组所占的百分比。在后面会具体介绍一些估计分类器准确率的方法。I MISS YOU,OLD FRIEND 决策树归纳简单回顾：1、决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。2、基本的决策树学习算法ID3通过自顶向下构造决策树来进行学习。构造过程是从“哪一个属性将在树的根节点被测试？”这个问题开始的。

7、为了回答这个问题，使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的根节点进行测试。然后为根节点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支之下。然后重复整个过程，用每个分支节点关联的训练样例来选取在改点被测试的最佳属性。这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。 新鲜血液：上学期未接触过或为深入的问题（1）分裂准则（2）基尼指数（3）树剪枝（4）可伸缩性与决策树归纳（5）决策树归纳的可视化挖掘（a）属性A是离散值分裂方法为直接按照各种不同的离散值分类（b）属性A事连续值分裂方法是设置一个分裂点（在实践中，分裂点a通常

8、取A的两个已知相邻值的中点，因此可能不是训练数据中A的存在值）。分别对应两边区间的条件。（c）A是离散值并且必须产生二叉树（2）基尼指数：Q1：基尼指数到底是什么？基尼指数是用来度量数据分区或训练元组集D的不纯度的。定义式为：Gini（D）=1-pi2其中pi是D中元组属于Ci类的概率Q2：基尼指数有什么作用？通过计算每个属性对于训练元组集D的基尼指数来判断哪个属性可以使得训练元组集D的“不纯度”降得最多，从而选举其为分裂属性。Q3：什么是所谓的降低“不纯度”？对于每个属性来说，都可以进行二元划分来降低整个训练元组集D的不纯度，离散值属性和连续值属性都可以进行相应的二元划分，把整个训练元组集划

9、分为两个部分D1，D2。经过二元划分后，对于某个属性A来说，D的基尼指数为：GiniA(D)=( D1 / D )Gini(D1 )+ ( D2 / D )Gini(D2)属性A经过二元划分以后导致的不纯度降低为：Gini(A)=Gini(D)- GiniA(D)由此式可以很简单的看出，哪个属性进过二元划分后自身的基尼指数最低，那么它就可以使得整个训练元组集D的不纯度降低的最多，那他显而易见是要做为老大的，就和信息增益中那个信息增益值最大的属性一样，需要站在金字塔的顶端，作为分裂属性。简单的例子来说明基尼指数进行决策树归纳的过程：电脑店做销售预测，收集到了一些客户的基本信息作为资料，属性包括：

10、年龄、收入、是否为学生、信用评级。类标号为：买、不买。（1）类标号分为两种情况：买、不买，对应于C1，C2。（2）现在知道一共14个训练数据中，有9个的类标号属于C1，5个的类标号属于C2。（3）首先计算训练元组集D的“不纯度”Gini(D)=1-(9/14)2-(5/14) 2=0.459（4）到此，思路明确，哪个属性可以使不纯度降低最多，哪个属性就是老大，它和它的分裂子集或者分裂点就一起形成分裂准则。（5）排好队一个个属性接受检验，以收入（income）为例：该属性为离散属性，共有三个可能值low,medium,high，对这个属性进行二元划分。这个属性为离散值属性，它存在八个子集，不考虑

11、空集和全集，因为空集全集对D不纯度的降低没有任何意义。六个有效子集为：low,medium、low,high、medium, highlow、medium、high。以low,medium为例进行计算：这两个情况加在一起一共有10个满足他的元组在分区D1中：Giniincome low,medium=0.443其他结果参照书本P221 很容易理解（3）树剪枝树剪枝的由来：在决策树创建时，由于数据中的噪声和离群点，许多分支反映的是训练数据中的异常。剪枝方法的产生就是为了处理这种过分拟合数据问题的。先剪枝：在构建决策树的过程中，使用诸如统计显著性、信息增益、基尼指数等度量来评估划分的优劣。在构造树

12、的过程中通过提前停止构建来去掉一些低于预定义阈值的元组。此方法阈值的选取比较困难，不方便准确地进行剪枝。后剪枝：在一棵决策树完全构建完成以后，通过删除结点的分支并用树叶替换它而剪掉给定结点上的子树。该树叶的类标号用子树中最频繁的类标记。相当于少数服从多数了。（4）可伸缩性与决策树归纳可伸缩性理念的由来：决策树算法的确很科学，但是它只是为相对较小的数据集设计的，当他用于超大型现实世界数据库的挖掘时，有效性就大大降低，在现实世界数据库的挖掘过程中，训练数据不能放在内存，由于训练元组在主存和高速缓存换进换出，决策树的构造可能变得效率低下。需要更加可伸缩的办法，处理因为太大而不能放在内存的训练数据。R

13、ainForest方法该方法在每个结点，对每个属性维护一个AVC-集（AVC表示“属性值，类标号”），用它来表述该结点的训练元组。（5）决策树归纳的可视化挖掘基于感知的分类（PBC）是一种基于多维可视化技术的交互式方法，允许用户在构建决策树时加上关于数据的背景知识。通过可视化地与数据交互，用户也可能逐步深入地理解数据。在获得大约相同准确率的同时，构建的决策树往往比使用传统的决策树归纳方法建立的决策树更小，因而更容易理解。树交互地构建。用户在数据交互窗口观察多维数据，并选择分类属性和一个或多个分裂点。当前决策树在知识窗口扩展。用户选择决策树的一个结点，可以给该结点指定一个类标号（使该结点变成树叶

14、），或者要求可视化对应于该结点的训练数据。这导致出从根到该结点路径上使用的分裂准则外，每个属性重新可视化，该交互过程继续，直到决策树的每个树叶都被指定一个类标号。站在巨人的肩膀上有强大数学理论支持的贝叶斯分类前期准备：贝叶斯定理：)()()(XPHPHXPXHP）其中：X为条件，可以看他为“证据” H为某种假设 例如：X代表某位35岁且收入为4万美元的顾客，H为购买计算机。则)(XHP指的是35岁且收入为4万美元的顾客购买计算机的概率朴素贝叶斯分类法的工作过程：（1）首先犹如分类一般方法一样，先确定训练集。（2）假设有m个类标号，贝叶斯分类法的目的就是找出具有最高后验概率属性元组。使用贝叶斯定

15、理：)()()(XPCiPCiXPXCiP）P（X）对所有类来说都是常数，所以要想使得后验概率P（Ci X）最大，只需要其P（X Ci）P（Ci）最大即可。如果所有类标号的先验概率P（Ci）未知，则一般假设各个类标号的先验概率相同，所以只要得到最大的P(X Ci)即可。（3）为了降低计算P（X Ci）的复杂度，可以使用类条件独立的朴素假定，即假定属性值有条件地相互独立（即属性之间不存在依赖关系）：P（X Ci）= P（xk Ci）= P（x1 Ci） P（xn Ci）（a）如果是分类属性（比如职业），则P（xk Ci）就是训练集中此属性值为xk的Ci类的元组数除以训练集中Ci类的元组数。（b）

16、如果为连续指属性，则使用高斯分布来计算P（xk Ci）。（4）比较算出的各个属性的后验概率值，选取其中具有最大后验概率值得属性作为被预测出的属性。朴素贝叶斯分类法遭遇零概率值问题。如果出现了零概率值，即某个P（xk Ci）的值为0，例如买电脑的里面一个学生都没有。则使用拉普拉斯校准法，在每个属性的计数上加1，对整个结果影响非常小，但是可以避免零概率事件。精益求精 模型的评估与选择一些专业术语的初步了解：（1）正元组：感兴趣的主要类的元组（比如buys_computer=yes）。（2）负元组：其他元组（比如buys_computer=no）。（3）真正例/真阳性（TP）：是指分类器正确分类的正

17、元组。令TP为真正例的个数。（4）真负例/真阴性（TN）：是指分类器正确分类的负元组。令TN为真负例的个数。（5）假正例/假阳性（FP）：是被错误地标记为正元组的负元组。令FP为假正例的个数。（6）假负例/假阴性（FN）：是被错误地标记为负元组的正元组。令FN为假负例的个数。（一）评估分类器性能的度量评估度量：其中precision为精度，它可以看做精度性的度量（即标记为正类的元祖实际为正类所占的百分比）。其中recall为召回率，它是完全性的度量（及正元组标记为正的百分比）。除了基于准确率的度量之外，还可以根据其他方面比较分类器：（1）速度：这涉及产生和使用分类器的计算开销（2）鲁棒性：这是

18、假定数据有噪声或有缺失值时分类器做出正确预测的能力。通常，鲁棒性用噪声和缺失值渐增的一系列合成数据集评估。（3）可伸缩性：这涉及给定大量数据，有效地构造分类器的能力。通常可伸缩性用规模渐增的一系列数据集评估。（4）可解释性：这涉及分类器或预测器提供的理解和洞察水平，可理解性是主观的，因为难以评估。（二）保持方法和随机二次抽样保持方法：把样本集一分为二，其中三分之一作为训练集、三分之二作为检验集，这样的方法估计是悲观的，因为只有样本集中的三分之二用于到处模型。随机二次抽样：将保持方法重复k次。总准确率估计取每次迭代准确率的平均值。（三）交叉验证k-折交叉验证：将初始数据随机的划分成k个互不相交的子集D1、D2、D