数据挖掘算法揭秘篇——分类方法（一）

"首席"工程师

小昶

分类是一种重要的数据挖掘技术，其目的是根据数据集的特点构造一个分类函数或分类模型（也常称作分类器），该模型能把未知类别的样本映射到给定的类别当中。

分类可描述如下：输入数据，或称训练集（TrainingSet），是由一条条数据库记录（Record）组成的。每一条记录包含若干属性（Atribute），组成一个特征向量。训练集的每条记录还有一个特定的标签（ClassLabel）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：（v1，v2，...，vn；c），在这里vi表示字段值，c表示类别。分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意是预测，而不能肯定，因为分类的准确率不能达到百分之百。我们也可以由此对数据库中的每一个类有一个更好的理解，即我们获得了对这个类的知识。故此分类也可定义为：对现有的数据进行学习，得到一个目标函数或规则，把每个属性集x映射到一个预先定义的类标号y。

通常分类学习所获得的模型可以表示为分类规则形式、决策树形式或数学公式形式。例如给定一个顾客信用信息数据库，通过学习所获得的分类规则可用于识别顾客是否具有良好的信用等级或一般的信用等级。分类规则也可用于对今后未知所属类的数据进行识别判断，同时也会更好的帮助用户了解数据库中的内容。

构造模型的过程一般分为训练和测试两个阶段。在构造模型前，要求将数据集随机的分为训练集和测试集。在训练阶段，使用训练数据集，通过分析由属性描述的数据库元组来构造模型。在测试阶段，使用测试数据集来评估模型的分类准确率，如果认为可以接受，就可以用该模型对其他数据元组进行分类。一般来说，测试阶段的代价远低于训练阶段。

为了提高分类的准确性、有效性和可伸缩性，在进行分类之前，通常要对数据进行预处理，包括：

数据清理。其目的是消除或减少数据噪声，处理空缺值。

相关性分析。由于数据集中的许多属性可能与分类任务不相关，若包含这些属性可能将减慢和误导学习过程。相关性分析的目的就是删除这些不相关或冗余的属性，

数据变换。数据可以概化到较高层概念。比如，连续值属性“收入”的数值可以概化为离散值：低、中、高。又如标称值属性“市”可以概化到更高层概念“省”。此外，数据还可以规范化，规范化将给定属性的值按比例缩放，落入较小区间。

分类的方法有多种，常用的分类方法有7种：最临近、贝叶斯、神经网络、逻辑斯蒂、判别分析、支持向量机、决策树。下面进行简单介绍：

①K-近邻

K-近邻（K-NearestNeighbor，KNN）算法是一种基于实例的分类方法，最初由Cover和Hart于1968年提出，是一种非参数的分类方法。

KNN是通过测量不同特征值之间的距离进行分类。它的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

下面通过一个简单的例子说明一下：如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

由此也说明了KNN算法的结果很大程度取决于K的选择。

在KNN中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧氏距离或曼哈顿距离：

同时，KNN通过依据k个对象中占优的类别进行决策，而不是单一的对象类别决策。这两点就是KNN算法的优势。

接下来对KNN算法的思想总结一下：就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：

1）计算测试数据与各个训练数据之间的距离；

2）按照距离的递增关系进行排序；

3）选取距离最小的K个点；

4）确定前K个点所在类别的出现频率；

5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。

（实现代码参考：

http://www.cnblogs.com/ybjourney/p/4702562.html）

KNN方法在类别决策时，只与极少量的相邻样本有关，因此，采用这种方法可以较好的避免样本的不平衡问题。另外，由于KNN方法主要是靠周围有限的临近的样本，而不是靠判别类域的方法来确定所属类别，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为合适。

该方法的不足之处是计算量较大，因为对每一个待分类的样本都要计算它到全体已知样本的距离才能求得它的K个最临近点。针对该不足，主要有以下两类改进方法：

对于计算量大的问题目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

对样本进行组织与整理，分群分层，尽可能将计算压缩在接近测试样本领域的小范围内，避免盲目的与训练样本集中的每个样本进行距离计算。

总的来说，这个算法的适应性强，尤其适用于样本容量较大的自动分类问题，而那些样本容量较小的分类问题采用这种方法容易误分。

②贝叶斯分类

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

从数学角度来说，分类问题可做如下定义：已知集合

和

，确定映射规则y = f(x)，使得任意有且仅有一个

，使得

成立。

其中C叫做类别集合，其中每一个元素是一个类别，而I叫做项集合（特征集合），其中每一个元素是一个待分类项，f叫做分类器。分类算法的任务就是构造分类器f。

朴素贝叶斯的核心算法是这个公式：

，我们最终求得P(B|A)即可。

举个例子更直观的感受一下。

给定数据如下：

现在给我们的问题是，如果一对男女朋友，男生想女生求婚，男生的四个特点分别是不帅，性格不好，身高矮，不上进，请你判断一下女生是嫁还是不嫁？

这是一个典型的分类问题，转为数学问题就是比较p(嫁|(不帅、性格不好、身高矮、不上进))与p(不嫁|(不帅、性格不好、身高矮、不上进))的概率，谁的概率大，我就能给出嫁或者不嫁的答案！

这里我们联系到朴素贝叶斯公式：

我们需要求p(嫁|(不帅、性格不好、身高矮、不上进),这是我们不知道的，但是通过朴素贝叶斯公式可以转化为好求的三个量。

p(不帅、性格不好、身高矮、不上进|嫁)、p（不帅、性格不好、身高矮、不上进)、p(嫁)（至于为什么能求，后面会讲，那么就太好了，将待求的量转化为其它可求的值，这就相当于解决了我们的问题！）

那么这三个量是如何求得？

是根据已知训练数据统计得来，下面详细给出该例子的求解过程。

回忆一下我们要求的公式如下：

那么我只要求得p(不帅、性格不好、身高矮、不上进|嫁)、p（不帅、性格不好、身高矮、不上进)、p(嫁)即可，好的，下面我分别求出这几个概率，最后一比，就得到最终结果。

p(不帅、性格不好、身高矮、不上进|嫁) = p(不帅|嫁)*p(性格不好|嫁)*p(身高矮|嫁)*p(不上进|嫁)，那么我就要分别统计后面几个概率，也就得到了左边的概率！

等等，为什么这个成立呢？学过概率论的同学可能有感觉了，这个等式成立的条件需要特征之间相互独立吧！

对的！这也就是为什么朴素贝叶斯分类有朴素一词的来源，朴素贝叶斯算法是假设各个特征之间相互独立，那么这个等式就成立了！

但是为什么需要假设特征之间相互独立呢？

1、我们这么想，假如没有这个假设，那么我们对右边这些概率的估计其实是不可做的，这么说，我们这个例子有4个特征，其中帅包括，性格包括，身高包括，上进包括，那么四个特征的联合概率分布总共是4维空间，总个数为2*3*3*2=36个。

36个，计算机扫描统计还可以，但是现实生活中，往往有非常多的特征，每一个特征的取值也是非常之多，那么通过统计来估计后面概率的值，变得几乎不可做，这也是为什么需要假设特征之间独立的原因。

2、假如我们没有假设特征之间相互独立，那么我们统计的时候，就需要在整个特征空间中去找，比如统计p(不帅、性格不好、身高矮、不上进|嫁),

我们就需要在嫁的条件下，去找四种特征全满足分别是不帅，性格不好，身高矮，不上进的人的个数，这样的话，由于数据的稀疏性，很容易统计到0的情况。 这样是不合适的。

根据上面俩个原因，朴素贝叶斯法对条件概率分布做了条件独立性的假设，由于这是一个较强的假设，朴素贝叶斯也由此得名！这一假设使得朴素贝叶斯法变得简单，但有时会牺牲一定的分类准确率。

好的，上面我解释了为什么可以拆成分开连乘形式。那么下面我们就开始求解！

我们将上面公式整理一下如下：

下面我将一个一个的进行统计计算（在数据量很大的时候，根据中心极限定理，频率是等于概率的，这里只是一个例子，所以我就进行统计即可）。

p(嫁)=？

首先我们整理训练数据中，嫁的样本数如下：

则 p(嫁) = 6/12（总样本数） = 1/2

p(不帅|嫁)=？统计满足样本数如下：

则p(不帅|嫁) = 3/6 = 1/2 在嫁的条件下，看不帅有多少

p(性格不好|嫁)= ？统计满足样本数如下：

则p(性格不好|嫁)= 1/6

p（矮|嫁） = ?统计满足样本数如下：

则p(矮|嫁) = 1/6

p(不上进|嫁) = ?统计满足样本数如下：

则p(不上进|嫁) = 1/6

下面开始求分母，p(不帅)，p（性格不好），p（矮），p（不上进）

统计样本如下：

不帅统计如上红色所示，占4个，那么p（不帅） = 4/12 = 1/3

性格不好统计如上红色所示，占4个，那么p（性格不好） = 4/12 = 1/3

身高矮统计如上红色所示，占7个，那么p（身高矮） = 7/12

不上进统计如上红色所示，占4个，那么p（不上进） = 4/12 = 1/3

到这里，要求p(不帅、性格不好、身高矮、不上进|嫁)的所需项全部求出来了，下面我带入进去即可。

= (1/2*1/6*1/6*1/6*1/2)/(1/3*1/3*7/12*1/3)

下面我们根据同样的方法来求p(不嫁|不帅，性格不好，身高矮，不上进)，完全一样的做法，为了方便理解，我这里也走一遍帮助理解。首先公式如下：

下面我也一个一个来进行统计计算，这里与上面公式中，分母是一样的，于是我们分母不需要重新统计计算！

p（不嫁）=？根据统计计算如下（红色为满足条件）：

则p(不嫁)=6/12 = 1/2

p(不帅|不嫁) = ？统计满足条件的样本如下（红色为满足条件）：

则p（不帅|不嫁） = 1/6

p（性格不好|不嫁） = ？据统计计算如下（红色为满足条件）：

则p（性格不好|不嫁） =3/6 = 1/2

p（矮|不嫁） = ？据统计计算如下（红色为满足条件）：

则p（矮|不嫁） = 6/6 = 1

p（不上进|不嫁） = ？据统计计算如下（红色为满足条件）：

则p（不上进|不嫁） = 3/6 = 1/2

那么根据公式：

p (不嫁|不帅、性格不好、身高矮、不上进) = ((1/6*1/2*1*1/2)*1/2)/(1/3*1/3*7/12*1/3)

很显然(1/6*1/2*1*1/2) > (1/2*1/6*1/6*1/6*1/2)

于是有p (不嫁|不帅、性格不好、身高矮、不上进)>p (嫁|不帅、性格不好、身高矮、不上进)

所以我们根据朴素贝叶斯算法可以给这个女生答案，是不嫁！！！！

朴素贝叶斯分类器一般具有以下特点：

简单、高效、健壮，无关属性的类条件概率不会对总的后验概率的计算产生影响。

相关属性可能会降低朴素贝叶斯分类器的性能，因为对这些属性，条件独立的假设已不成立。

本期分类方法就先介绍到这，下一期我们介绍神经网络、逻辑斯蒂以及判别分析，拜拜~

本文参考周英的《大数据挖掘系统方法与实例分析》，特此感谢！

本文由小昶提供，请勿未经作者本人许可用于商业行为，谢谢！

关注我们