数据挖掘分类技术

数据挖掘分类技术

从分类问题的提出至今，已经衍生出了很多具体的分类技术。下面主要简单介绍四种最常用的分类技术，不过因为原理和具体的算法实现及优化不是本书的重点，所以我们尽量用应用人员能够理解的语言来表述这些技术。而且我们会在第4章再次给读者讲述分类算法和相关原理。

在我们学习这些算法之前必须要清楚一点，分类算法不会百分百准确。每个算法在测试集上的运行都会有一个准确率的指标。用不同的算法做成的分类器（Classifier）在不同的数据集上也会有不同的表现。

KNN，K最近邻算法

K最近邻（k-Nearest Neighbor，kNN）分类算法可以说是整个数据挖掘分类技术中最简单的方法。所谓K最近邻，就是k个最近的邻居，说的是每个样本都可以用它最接近的K个邻居来代表。

我们用一个简单的例子来说明kNN算法的概念。如果您住在一个市中心的住宅内，周围若干个小区的同类大小房子售价都在280万到300万之间，那么我们可以把你的房子和它的近邻们归类到一起，估计也可以售280万到300万之间。同样，您的朋友住在郊区，他周围的同类房子售价都在110万到120万之间，那么他的房子和近邻的同类房子归类之后，售价也在110万到120万之间。

KNN算法的核心思想是如果一个样本在特征空间中的K个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近样本，而不是靠判别类域的方法来确定所属类别，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

决策树（Decision Tree）

如果说KNN是最简单的方法，那决策树应该是最直观最容易理解的分类算法。最简单的决策树的形式是If-Then（如果-就）式的决策方式的树形分叉。

比如下面这样一棵决策树，根据样本的相貌和财富两个属性把所有样本分成“高富帅”、“帅哥”、“高富”和“屌丝”四类。

If（obj.相貌=="帅"）then

    {

        If(obj.财富>=1000000000)then

            {

            print（obj.Name + "高富帅"）;

            }

        else

            {

            print（obj.Name + "是帅哥"）;

            }

    }

else

    {

        If(obj.财富>=1000000000)then

            {

            print（obj.Name + "是高富"）;

            }

        else

            {

            print（obj.Name + "是屌丝"）;

            }

    }

决策树上的每个节点要么是一个新的决策节点，要么就是一个代表分类的叶子，而每一个分支则代表一个测试的输出。决策节点上做的是对属性的判断，而所有的叶子节点就是一个类别。决策树要解决的问题就是用哪些属性充当这棵树的各个节点的问题，而其中最关键的是根节点（Root Node），在它的上面没有其他节点，其他所有的属性都是它的后续节点。在上面的例子中，（obj.相貌==“帅”）就是根节点，两个（obj.财富>=1000000000）是根节点下一层的两个决策节点，四个print标志着四个叶子节点，各自对应一个类别。

所有的对象在进入决策树之后根据各自的“相貌”和“财富”属性都会被归到四个分类中的某一类。

大多数分类算法（如下面要提的神经网络、支持向量机等）都是一种类似于黑盒子式的输出结果，你无法搞清楚具体的分类方式，而决策树让人一目了然，十分方便。决策树按分裂准则的不同可分为基于信息论的方法和最小GINI指标（Gini Index）方法等。

神经网络（Neural Net）

在KNN算法和决策树算法之后，我们来看一下神经网络。

神经网络就像是一个爱学习的孩子，你教他的知识他不会忘记，而且会学以致用。我们把学习集（Learning Set）中的每个输入加到神经网络中，并告诉神经网络输出应该是什么分类。在全部学习集都运行完成之后，神经网络就根据这些例子总结出他自己的想法，到底他是怎么归纳的就是一个黑盒了。之后我们就可以把测试集（Testing Set）中的测试例子用神经网络来分别作测试，如果测试通过（比如80%或90%的正确率），那么神经网络就构建成功了。我们之后就可以用这个神经网络来判断事务的分类。

神经网络是通过对人脑的基本单元——神经元的建模和连接，探索模拟人脑神经系统功能的模型，并研制一种具有学习、联想、记忆和模式识别等智能信息处理功能的人工系统。神经网络的一个重要特性是它能够从环境中学习，并把学习的结果分别存储于网络的突触连接中。神经网络的学习是一个过程，在其所处环境的激励下，相继给网络输入一些样本模式，并按照一定的规则（学习算法）调整网络各层的权值矩阵，待网络各层权值都收敛到一定值，学习过程结束。然后我们就可以用生成的神经网络来对真实数据做分类。

支持向量机SVM（Support Vector Machine）

和上面三种算法相比，支持向量机的说法可能会有一些抽象。我们可以这样理解，尽量把样本中的从更高的维度看起来在一起的样本合在一起，比如在一维（直线）空间里的样本从二维平面上可以把它们分成不同类别，而在二维平面上分散的样本如果我们从第三维空间上来看就可以对它们做分类。

支持向量机算法的目的是找到一个最优超平面，使分类间隔最大。最优超平面就是要求分类面不但能将两类正确分开，而且使分类间隔最大。在两类样本中离分类面最近且位于平行于最优超平面的超平面上的点就是 支持向量，为找到最优超平面，只要找到所有的支持向量即可。对于非线性支持向量机，通常做法是把线性不可分转化成线性可分，通过一个非线性映射将低维输入空间中的数据特征映射到高维线性特征空间中，在高维空间中求线性最优分类超平面。

支持向量机算法是我们在做数据挖掘应用时很看重的一个算法，而原因是该算法自问世以来就被认为是效果最好的分类算法之一。

本文节选自《New Internet：大数据挖掘》

谭磊 著

电子工业出版社出版