第四章 分类方法 内容提要 分类的基本概念与步骤 基于距离的分类算法 决策树分类方法 贝叶斯分类 2019年2月21日星期四 第四章 分类方法 内容提要 分类的基本概念与步骤 基于距离的分类算法 决策树分类方法 贝叶斯分类 2019年2月21日星期四 DMKD Sides By MAO

分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。 分类可用于预测。从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。 分类和统计学中的回归是既相互联系，有有一定区别的概念。分类输出的是离散的类别值，而回归输出的是连续数值。 分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。 2019年2月21日星期四 DMKD Sides By MAO

机器学习方法：包括决策树法和规则归纳法。 神经网络方法。 其他，如粗糙集等（在前面绪论中也介绍了相关的情况）。 分类器的构造依据的方法很广泛： 统计方法：包括贝叶斯法和非参数法等。 机器学习方法：包括决策树法和规则归纳法。 神经网络方法。 其他，如粗糙集等（在前面绪论中也介绍了相关的情况）。 2019年2月21日星期四 DMKD Sides By MAO

分类方法的类型 从使用的主要技术可以把分类方法归结为四种类型： 贝叶斯分类方法 决策树分类方法 基于距离的分类方法 规则归纳方法。 2019年2月21日星期四 DMKD Sides By MAO

解决分类问题的关键是构造一个合适的分类器：从数据库到一组类别集的映射。一般地，这些类是被预先定义的、非交叠的。 定义4-1 给定一个数据库 D={t1，t2，…，tn}和一组类C={C1，…，Cm}，分类问题是去确定一个映射 f: DC，使得每个元组ti被分配到一个类中。一个类Cj 包含映射到该类中的所有元组，即Cj={ti|f(ti)=Cj，1≤i≤n，而且tiD}。 解决分类问题的关键是构造一个合适的分类器：从数据库到一组类别集的映射。一般地，这些类是被预先定义的、非交叠的。 构造分类器，需要有一个训练样本数据集作为输入。分类的目的是分析输入数据，通过训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型。 数据分类(Data Classification)分为两个步骤:建模和使用。 2019年2月21日星期四 DMKD Sides By MAO

分类问题的描述 2019年2月21日星期四 DMKD Sides By MAO

分类方法的类型 从使用的主要技术可以把分类方法归结为四种类型： 贝叶斯分类方法 决策树分类方法 基于距离的分类方法

1.贝叶斯分类 1.1分类的基本概念 1.2贝叶斯分类概述

1.1分类的基本概念 背景 近几十年来，Internet互联网的普及使得人们获得和存储数据的能力得到逐步的提高，数据规模不断壮大。面对“数据丰富而知识匮乏”的挑战，数据挖掘技术应运而生。数据挖掘是一门多学科的交叉领域，涉及统计学，机器学习、神经网络、模式识别、知识库系统、信息检索、高性能计算和可视化等学科。而数据挖掘中的分类技术是一项非常重要的技术。

Q1 什么是分类 超市中的物品分类 生活中的垃圾分类

Q1 什么是分类 由此可见，分类是跟我们的生活息息相关的东西，分类让生活更加有条理，更加精彩. 生活信息的分类

Q1 什么是分类 分类在数据挖掘中的学术定义 分类就是把一些新的数据项映射到给定类别的中的某一个类别，比如说当我们发表一篇文章的时候，就可以自动的把这篇文章划分到某一个文章类别。 分类也称为有监督学习(supervised learning),与之相对于的是无监督学习(unsupervised learning),比如聚类。 分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。  

Q2 分类问题 名称 胎生 会飞 水中生活 有腿 类别 Human 是 否 哺乳动物 python 非哺乳动物 salmon whale frog 有时 komodo bat pigeon cat leopard_shark turtle penguin porcupine eel salamander gila_monster platypus owl dolphin eagle 胎生 会飞 水中生活 有腿 类别 是 否 ？

Q2 分类的流程 根据现有的知识，我们得到了一些关于哺乳动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？ 动物种类 体型 翅膀数量 脚的只数 是否产蛋 是否有毛 类别 狗 中 4 否 是 哺乳动物 猪 大 牛 麻雀 小 2 鸟类 天鹅 大雁 动物A 无 ？ 动物B 根据现有的知识，我们得到了一些关于哺乳动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？

Q2 分类的流程 步骤一：将样本转化为等维的数据特征（特征提取）。 所有样本必须具有相同数量的特征 兼顾特征的全面性和独立性 狗 中 4 否 动物种类 体型 翅膀数量 脚的只数 是否产蛋 是否有毛 类别 狗 中 4 否 是 哺乳动物 猪 大 牛 麻雀 小 2 鸟类 天鹅 大雁

Q2 分类的流程 步骤二：选择与类别相关的特征（特征选择）。 比如，绿色代表与类别非常相关，黑色代表部分相关，浅蓝色代表完全无关 狗 中 4 动物种类 体型 翅膀数量 脚的只数 是否产蛋 是否有毛 类别 狗 中 4 否 是 哺乳动物 猪 大 牛 麻雀 小 2 鸟类 天鹅 大雁

1.2 贝叶斯分类概述 背景 贝叶斯分类基于贝叶斯定理，贝叶斯定理是由18世纪概率论和决策论的早起研究者Thomas Bayes发明的，故用其名字命名为贝叶斯定理。 分类算法的比较研究发现，一种称为朴素贝叶斯分类法的简单贝叶斯分类法可以与决策树和经过挑选的神经网络分类器相媲美。用于大型数据库，贝叶斯分类法也已表现出高准确率和高速度。 目前研究较多的贝叶斯分类器主要有四种，分别是：Naive Bayes、TAN、BAN和GBN。 Thomas Bayes

贝叶斯定理 贝叶斯定理（Bayes' theorem）是概率论中的一个结果，它跟随机变量的条件概率以及边缘概率分布有关。在有些关于概率的解说中，贝叶斯定理能够告知我们如何利用新证据修改已有的看法。 通常，事件A在事件B（发生）的条件下的概率，与事件B在事件A的条件下的概率是不一样的；然而，这两者是有确定的关系，贝叶斯定理就是这种关系的陈述。

贝叶斯公式 贝叶斯公式提供了从先验概率P(A)、P(B)和P(B|A)计算后验概率P(A|B)的方法：P(A|B)=P(B|A)*P(A)/P(B) ，P(A|B)随着P(A)和P(B|A)的增长而增长，随着P(B)的增长而减少，即如果B独立于A时被观察到的可能性越大，那么B对A的支持度越小。

贝叶斯法则 机器学习的任务：在给定训练数据D时，确定假设空间H中的最佳假设。

贝叶斯分类的原理 贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。也就是说，贝叶斯分类器是最小错误率意义上的优化。 根据贝叶斯定理：   由于P(X)对于所有类为常数，只需要P(X|H)*P(H)最大即可。

朴素贝叶斯 朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。 通俗来说，就好比这么个道理，你在街上看到一个黑人，我问你你猜这哥们哪里来的，你十有八九猜非洲。为什么呢？因为黑人中非洲人的比率最高，当然人家也可能是美洲人或亚洲人，但在没有其它可用信息下，我们会选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。 黑人 概率最大 非洲人

朴素贝叶斯分类的流程 第一阶段——准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备，主要工作是根据具体情况确定特征属性，并对每个特征属性进行适当划分，然后由人工对一部分待分类项进行分类，形成训练样本集合。这一阶段的输入是所有待分类数据，输出是特征属性和训练样本。这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段，其质量对整个过程将有重要影响，分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。 第二阶段——分类器训练阶段，这个阶段的任务就是生成分类器，主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计，并将结果记录。其输入是特征属性和训练样本，输出是分类器。这一阶段是机械性阶段，根据前面讨论的公式可以由程序自动计算完成。   第三阶段——应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。这一阶段也是机械性阶段，由程序完成。

是真是假？ 朴素贝叶斯分类实例 检测SNS社区中不真实账号   下面讨论一个使用朴素贝叶斯分类解决实际问题的例子。       这个问题是这样的，对于SNS社区来说，不真实账号（使用虚假身份或用户的小号）是一个普遍存在的问题，作为SNS社区的运营商，希望可以检测出这些不真实账号，从而在一些运营分析报告中避免这些账号的干扰，亦可以加强对SNS社区的了解与监管。       如果通过纯人工检测，需要耗费大量的人力，效率也十分低下，如能引入自动检测机制，必将大大提升工作效率。这个问题说白了，就是要将社区中所有账号在真实账号和不真实账号两个类别上进行分类。 下面我们一步一步实现这个过程。       是真是假？

首先设C=0表示真实账号，C=1表示不真实账号。    1、确定特征属性及划分       这一步要找出可以帮助我们区分真实账号与不真实账号的特征属性，在实际应用中，特征属性的数量是很多的，划分也会比较细致，但这里为了简单起见，我们用少量的特征属性以及较粗的划分，并对数据做了修改。       我们选择三个特征属性：a1：日志数量/注册天数 a2：好友数量/注册天数 a3：是否使用真实头像 在SNS社区中这三项都是可以直接从数据库里得到或计算出来的。       下面给出划分：a1：{a<=0.05, 0.05<a<0.2, a>=0.2} a2：{a<=0.1, 0.1<a<0.8, a>=0.8} a3：{a=0（不是）,a=1（是）}

  2、获取训练样本       这里使用运维人员曾经人工检测过的1万个账号作为训练样本。  3、计算训练样本中每个类别的频率       用训练样本中真实账号和不真实账号数量分别除以一万，得到：        P(C = 0) = 8900/10000 = 0.89 P(C = 1) = 1100/10000 = 0.11            4、计算每个类别条件下各个特征属性划分的频率 P(a1<=0.05| C = 0) = 0.3 P(a1<=0.05| C = 1) = 0.8 P(0.05<a1<0.2|C = 0) = 0.5 P(0.05<a1<0.2| C = 1) = 0.1 P(a1>0.2| C = 0) = 0.2 P(a1>0.2| C = 1) = 0.1 P(a2<=0.1| C = 0) = 0.1 P(a2<=0.1| C = 1) = 0.7 P(0.1<a2<0.8 | C=0) = 0.7 P(0.1<a2<0.8 | C=1) = 0.2 P(a2>0.8| C = 0) = 0.2 P(a2>0.8| C = 0) = 0.1 P(a3 = 0|C = 0) = 0.2 P(a3 = 1|C = 0) = 0.8 P(a3 = 0|C = 1) = 0.9 P(a3 = 1|C = 1) = 0.1

 5、使用分类器进行鉴别       下面我们使用上面训练得到的分类器鉴别一个账号，属性如下 a1:日志数量与注册天数的比率为0.1 a2 :好友数与注册天数的比率为 0.2 a3:不使用真实头像 (a = 0) P(C = 0)P( x|C = 0) = P(C = 0) P(0.05<a1<0.2|C = 0)P(0.1<a2<0.8|C = 0)P(a3=0|C = 0) = 0.89*0.5*0.7*0.2 = 0.0623 P(C = 1)P( x|C = 1) = P(C = 1) P(0.05<a1<0.2|C = 1)P(0.1<a2<0.8|C = 1)P(a3=0|C = 1) = 0.11*0.1*0.2*0.9 = 0.00198 可以看到，虽然这个用户没有使用真实头像，但是通过分类器的鉴别，更倾向于将此账号归入真实账号类别。

朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以 及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是朴素贝叶斯分类有一个限制条件，就是特征属性必须有条件独立或基本独立（实际上在现实应用中几乎不可能做到完全独立）。当这个条件成立时，朴素贝叶斯分类法的准确率是最高的，但不幸的是，现实中各个特征属性间往往并不条件独立，而是具有较强的相关性，这样就限制了朴素贝叶斯分类的能力。于是诞生了一种更高级、应用范围更广的——贝叶斯网络。

Q2 分类问题 税号 去年退税 婚姻状况 可征税收入 逃税 1 是 单身 125k 否 2 婚姻中 100k 3 70k 4 120k 5 离婚 95k 6 60k 7 220k 8 85k 9 75k 10 90k

分类方法的类型 从使用的主要技术可以把分类方法归结为四种类型： 贝叶斯分类方法 决策树分类方法 基于距离的分类方法

Example of a Decision Tree categorical continuous class Splitting Attributes Refund Yes No NO MarSt Single, Divorced Married TaxInc NO < 80K > 80K NO YES Training Data Model: Decision Tree

Another Example of Decision Tree categorical categorical continuous class MarSt Single, Divorced Married NO Refund No Yes NO TaxInc < 80K > 80K NO YES There could be more than one tree that fits the same data!

Decision Tree Classification Task

Apply Model to Test Data Start from the root of tree. Refund MarSt TaxInc YES NO Yes No Married Single, Divorced < 80K > 80K

Apply Model to Test Data Refund MarSt TaxInc YES NO Yes No Married Single, Divorced < 80K > 80K

Apply Model to Test Data Refund Yes No NO MarSt Single, Divorced Married TaxInc NO < 80K > 80K NO YES

Apply Model to Test Data Refund Yes No NO MarSt Single, Divorced Married TaxInc NO < 80K > 80K NO YES

Apply Model to Test Data Refund Yes No NO MarSt Single, Divorced Married TaxInc NO < 80K > 80K NO YES

Apply Model to Test Data Refund Yes No NO MarSt Married Assign Cheat to “No” Single, Divorced TaxInc NO < 80K > 80K NO YES

Decision Tree Classification Task

Decision Tree Induction Many Algorithms: Hunt’s Algorithm (one of the earliest) CART ID3, C4.5 SLIQ,SPRINT

Hunt’s Algorithm Let Dt be the set of training records that reach a node t General Procedure: If Dt contains records that belong the same class yt, then t is a leaf node labeled as yt If Dt is an empty set, then t is a leaf node labeled by the default class, yd If Dt contains records that belong to more than one class, use an attribute test to split the data into smaller subsets. Recursively apply the procedure to each subset. Dt ?

Hunt’s Algorithm Don’t Cheat Don’t Cheat Don’t Don’t Cheat Cheat Refund Don’t Cheat Yes No Don’t Cheat Refund Don’t Cheat Yes No Marital Status Single, Divorced Married Refund Don’t Cheat Yes No Marital Status Single, Divorced Married Taxable Income < 80K >= 80K

Tree Induction Greedy strategy. Issues Split the records based on an attribute test that optimizes certain criterion. Issues Determine how to split the records How to specify the attribute test condition? How to determine the best split? Determine when to stop splitting

How to Specify Test Condition? Depends on attribute types Nominal Ordinal Continuous Depends on number of ways to split 2-way split Multi-way split

Splitting Based on Nominal Attributes Multi-way split: Use as many partitions as distinct values. Binary split: Divides values into two subsets. Need to find optimal partitioning. CarType Family Sports Luxury CarType {Sports, Luxury} {Family} CarType {Family, Luxury} {Sports} OR

Splitting Based on Continuous Attributes Different ways of handling Discretization to form an ordinal categorical attribute Static – discretize once at the beginning Dynamic – ranges can be found by equal interval bucketing, equal frequency bucketing (percentiles), or clustering. Binary Decision: (A < v) or (A  v) consider all possible splits and finds the best cut can be more compute intensive

Splitting Based on Continuous Attributes

How to determine the Best Split Before Splitting: 10 records of class 0, 10 records of class 1 Which test condition is the best?

The loan data (reproduced) Approved or not

A decision tree from the loan data Decision nodes and leaf nodes (classes)

Use the decision tree No

Is the decision tree unique? No. Here is a simpler tree. We want smaller tree and accurate tree. Easy to understand and perform better. Finding the best tree is NP-hard. All current tree building algorithms are heuristic algorithms

From a decision tree to a set of rules A decision tree can be converted to a set of rules Each path from the root to a leaf is a rule.

Choose an attribute to partition data The key to building a decision tree - which attribute to choose in order to branch. The objective is to reduce impurity or uncertainty in data as much as possible. A subset of data is pure if all instances belong to the same class. The heuristic in C4.5 is to choose the attribute with the maximum Information Gain or Gain Ratio based on information theory.

The loan data (reproduced) Approved or not

Two possible roots, which is better? Fig. (B) seems to be better.

Information theory: Entropy measure The entropy formula, Pr(cj) is the probability of class cj in data set D We use entropy as a measure of impurity or disorder of data set D. (Or, a measure of information in a tree)

Entropy measure: let us get a feeling As the data become purer and purer, the entropy value becomes smaller and smaller. This is useful to us!

Information gain Given a set of examples D, we first compute its entropy: If we make attribute Ai, with v values, the root of the current tree, this will partition D into v subsets D1, D2 …, Dv . The expected entropy if Ai is used as the current root:

Information gain (cont …) Information gained by selecting attribute Ai to branch or to partition the data is We choose the attribute with the highest gain to branch/split the current tree.

Own_house is the best choice for the root.

We build the final tree We can use information gain ratio to evaluate the impurity as well (see the handout)

Handling continuous attributes Handle continuous attribute by splitting into two intervals (can be more) at each node. How to find the best threshold to divide? Use information gain or gain ratio again Sort all the values of an continuous attribute in increasing order {v1, v2, …, vr}, One possible threshold between two adjacent values vi and vi+1. Try all possible thresholds and find the one that maximizes the gain (or gain ratio).

An example in a continuous space

Avoid overfitting in classification Overfitting: A tree may overfit the training data Good accuracy on training data but poor on test data Symptoms: tree too deep and too many branches, some may reflect anomalies due to noise or outliers Two approaches to avoid overfitting Pre-pruning: Halt tree construction early Difficult to decide because we do not know what may happen subsequently if we keep growing the tree. Post-pruning: Remove branches or sub-trees from a “fully grown” tree. This method is commonly used. C4.5 uses a statistical method to estimates the errors at each node for pruning. A validation set may be used for pruning as well.

An example Likely to overfit the data

Underfitting and Overfitting (Example) 500 circular and 500 triangular data points. Circular points: 0.5  sqrt(x12+x22)  1 Triangular points: sqrt(x12+x22) > 0.5 or sqrt(x12+x22) < 1

Underfitting and Overfitting Underfitting: when model is too simple, both training and test errors are large

Overfitting due to Noise Decision boundary is distorted by noise point

Overfitting due to Insufficient Examples Lack of data points in the lower half of the diagram makes it difficult to predict correctly the class labels of that region - Insufficient number of training records in the region causes the decision tree to predict the test examples using other training records that are irrelevant to the classification task

Notes on Overfitting Overfitting results in decision trees that are more complex than necessary Training error no longer provides a good estimate of how well the tree will perform on previously unseen records Need new ways for estimating errors

分类方法的类型 从使用的主要技术可以把分类方法归结为四种类型： 贝叶斯分类方法 决策树分类方法 基于距离的分类方法

K-Nearest-Neighbors Algorithm and Its Application

K-Nearest-Neighbors Algorithm K nearest neighbors (KNN) is a simple algorithm that stores all available cases and classifies new cases based on a similarity measure (distance function) KNN has been used in statistical estimation and pattern recognition since 1970’s.

K-Nearest-Neighbors Algorithm A case is classified by a majority voting of its neighbors, with the case being assigned to the class most common among its K nearest neighbors measured by a distance function. If K=1, then the case is simply assigned to the class of its nearest neighbor

Distance Function Measurements

Hamming Distance For category variables, Hamming distance can be used.

K-Nearest-Neighbors

What is the most possible label for c?

What is the most possible label for c? Solution: Looking for the nearest K neighbors of c. Take the majority label as c’s label Let’s suppose k = 3:

What is the most possible label for c?

What is the most possible label for c? The 3 nearest points to c are: a, a and o. Therefore, the most possible label for c is a.

Voronoi Diagram

Voronoi Diagram

Remarks

Choosing the most suitable K

Normalization

Normalization

Normalization

Normalization

k-Nearest Neighbor Classification (kNN) Unlike all the previous learning methods, kNN does not build model from the training data. To classify a test instance d, define k-neighborhood P as k nearest neighbors of d Count number n of training instances in P that belong to class cj Estimate Pr(cj|d) as n/k No training is needed. Classification time is linear in training set size for each test case.

Discussions kNN can deal with complex and arbitrary decision boundaries. Despite its simplicity, researchers have shown that the classification accuracy of kNN can be quite strong and in many cases as accurate as those elaborated methods. kNN is slow at the classification time kNN does not produce an understandable model