分类的探讨：算法评估及kNN

我们构建一个分类器，输入为运动员的身高、体重，输出为其从事的体育项目—体操、田径或篮球。

因此，上图的Marissa Coleman身高6英尺1英寸，体重160磅。我们的分类器能够将她正确判断为篮球运动员：

而另一个身高4英尺9英寸体重90磅的人可能是体操运动员：

一旦构建了分类器，我们就可能有兴趣回答类似下述的问题：

怎样才能回答上述问题呢？

训练集和测试集

我们使用了3个不同的数据集：女子运动员数据集、Iris数据集以及汽车MPG数据集。我们把每个数据集分成两个子集，一个用于构建分类器，该数据集称为训练集（training set）。另一个数据集用于评估分类器，该数据集称为测试集（test set）。训练集和测试集是数据挖掘中的常用术语。

数据挖掘领域的人永远不会在用于训练系统的数据上进行测试！

下面以近邻算法为例来解释为什么不能使用训练数据来测试。如果上述例子中的篮球运动员Marissa Coleman在训练数据中存在，那么身高6英尺1英寸体重160磅的她就会与自己最近。因此，如果对近邻算法进行评估时，若测试集是训练数据的子集，那么精确率总是接近于100%。更一般地，在评估任意数据挖掘算法时，如果测试集是训练数据的子集，那么结果就会十分乐观并且过度乐观。因此，这种做法看起来并不好。

我们将数据集分成两部分。较大的那部分用于训练，较小的那部分用于评估。事实表明这种做法也存在问题。在进行数据划分时可能会极端不走运。例如，所有测试集中的篮球运动员都比较矮（像Debbie Black的身高只有5英尺3英寸，体重只有124磅），他们会被分成马拉松运动员。而测试集中所有的田径运动员就像Tatyana Petrova（俄罗斯马拉松运动员，身高5英尺3英寸，体重108磅）一样较矮、体重较轻，可能会被分成体操运动员。如果测试集像上面一样，分类器的精确率会很差。另一方面，有时候测试集的选择又会十分幸运。测试集中的每个人都有所从事项目的标准身高和体重，此时分类器精确率接近100%。两种情况下，精确率都依赖于单个的测试集，并且该测试集可能并不能反映分类器应用于新数据的真实精确率。

上述问题的一种解决方法是重复多次上述过程并对结果求平均。例如，我们可以将数据分成两半：Part 1和Part 2。

我们可以使用Part 1的数据来训练分类器，而利用Part 2的数据对分类器进行测试。然后，我们重复上述过程，这次用Part 2训练而用Part 1测试。最后我们将两次的结果进行平均。但是，这种方法的问题在于我们每次只使用了一半数据进行训练。然而，我们可以通过增加划分的份数来解决这个问题。例如，我们可以将数据划分成3部分，每次利用2/3的数据训练而在其余1/3的数据上进行测试。因此，整个过程看起来如下：

第一次迭代 使用Part 1和Part 2训练，使用Part 3测试

第二次迭代 使用Part 1和Part 3训练，使用Part 2测试

第三次迭代 使用Part 2和Part 3训练，使用Part 1测试

对上述结果求平均。

在数据挖掘中，最常用的划分数目是10，这种方法称为……

10折交叉验证（10-fold Cross Validation）

使用这种方法，我们将数据集随机分成10份，使用其中9份进行训练而将另外1份用作测试。该过程可以重复10次，每次使用的测试数据不同。

考察一个例子。假设我想构建一个分类器，该分类器对于问题“Is this person a professional basketball player?”只回答Yes或No。我们的数据由500名篮球运动员和500名非篮球运动员组成。

10折交叉验证的例子

第1步，将数据等分到10个桶中。

我们会将50名篮球运动员和50名非篮球运动员分到每个桶中。每个桶当中放入了100人的信息。

第2步，下列步骤重复10次。

（1）每一次迭代中留存其中一个桶。第一次迭代中留存桶1，第二次留存桶2，其余依此类推。

（2）用其他9个桶的信息训练分类器（第一次迭代中利用从桶2到桶10的信息训练分类器）。

（3）利用留存的数据来测试分类器并保存测试结果。在上例中，这些结果可能如下：

35个篮球运动员被正确分类；

29个非篮球运动员被正确分类。

第3步，对上述结果汇总。

通常情况下我们会将结果放到与下表类似的表格中：

在所有500名篮球运动员中，有372人被正确分类。可能需要做的一件事是将右下角的数字也加上去，也就是说1000人当中有652（372+280）人被正确分类。因此得到的精确率为65.2%。与2折或3折交叉验证相比，基于10折交叉验证得到的结果可能更接近于分类器的真实性能。之所以这样，是因为每次采用90%而不是2折交叉验证中仅仅50%的数据来训练分类器。

留一法（Leave-One-Out） 在机器学习领域，n折交叉验证（n是数据集中样本的数目）被称为留一法。我们已经提到，留一法的一个优点是每次迭代中都使用了最大可能数目的样本来训练。另一个优点是该方法具有确定性。

确定性的含义

假设Lucy集中花费了80个小时来编写一个新分类器的代码。现在是周五，她已经筋疲力尽，于是她请她的两个同事（Emily和Li）在周末对分类器进行评估。她将分类器和相同的数据集交给每个人，请她们做10折交叉验证。周一，她问两人的结果……

嗯，她们得到了不同的结果。她们俩可能是谁犯错了吗？未必如此。在10折交叉验证中，我们随机将数据分到桶中。由于随机因素的存在，有可能Emily和Li的数据划分结果并不完全一致。实际上，她们划分一致的可能性微乎其微。因此，她们在训练分类器时，所用的训练数据并不一致，而在测试时所用的数据也不完全一致。因此，她们得到不同的结果是很符合逻辑的。该结果与是否由两个不同的人进行评估毫无关系。即使Lucy自己进行两次10折交叉验证，她得到的结果也会有些不同。之所以不同的原因在于将数据划分到桶这个过程具有随机性。由于10折交叉验证不能保证每次得到相同的结果，因此它是一种非确定性的方法。与此相反，留一法是确定性的。每次应用留一法到同一分类器及同一数据上，得到的结果都一样。这是件好事！

留一法的缺点

留一法的主要不足在于计算的开销很大。考虑一个包含1000个实例的中等规模的数据集，需要一分钟来训练分类器。对于10折交叉验证来说，我们将花费10分钟用于训练。而对于留一法来说，训练时间需要16个小时。如果数据集包含百万样本，那么花费在训练上的总时间将接近两年。我的天哪！

留一法的另一个缺点与分层采样（stratification）有关。

分层采样（Stratification）

构建分类器来确定女运动员所从事的体育项目（篮球、体操或田径）。当训练分类器时，我们希望训练数据能够具有代表性，并且包含所有3类的数据。假设采用完全随机的方式将数据分配到训练集，则有可能训练集中不包含任何篮球运动员，正因为如此，最终的分类器对篮球运动员分类时效果不佳。或者，考虑构建一个100个运动员的数据集。首先我们去WNBA的网站获得33个女子篮球运动员的信息，然后去维基百科网站获得33名参加2012年奥运会的女子体操运动员的信息，最后我们再次去维基百科网站获得34名参加奥运会田径项目的女运动员的信息。因此，最终我们的数据如下所示：

下面开始做10折交叉验证。我们从上表的第一行开始，每10个人放入一个桶。于是，第一个桶和第二个桶没有任何篮球运动员。第三个桶既有篮球运动员也有体操运动员。第四、第五个桶只包含体操运动员，其余桶的情况可以依此类推。任何一个桶都不能代表整个数据集，你认为上述划分会导致有偏差的结果，这种想法是对的。我们期望的方法是将实例按照其在整个数据集的相同比例分到各个桶中，即桶中的类别比例（篮球运动员、体操运动员、马拉松运动员）和整个数据集中的类别比例是一样的。由于整个数据集的1/3是篮球运动员，因此每个桶中应该包含1/3的篮球运动员。同样，该桶中也应包含1/3的体操运动员和1/3的马拉松运动员。上述做法称为分层采样，是一种好的方法。留一法评估的问题在于测试集中只有一个样本，因此它肯定不是分层采样的结果。总而言之，留一法可能适用于非常小的数据集，到目前为止10折交叉测试是最流行的选择。

混淆矩阵

到目前为止，通过计算下列精确率百分比，我们对分类器进行评估：

有时，我们可能希望得到分类器算法的更详细的性能。能够详细揭示性能的一种可视化方法是引入一个称为混淆矩阵（confusion matrix）的表格。混淆矩阵的行代表测试样本的真实类别，而列代表分类器所预测出的类别。

它之所以名为混淆矩阵，是因为很容易通过这个矩阵看清楚算法产生混淆的地方。下面以女运动员分类为例来展示这个矩阵。假设我们有一个由100名女子体操运动员、100名WNBA篮球运动员及100名女子马拉松运动员的属性构成的数据集。我们利用10折交叉验证法对分类器进行评估。在10折交叉测试中，每个实例正好只被测试过一次。上述测试的结果可能如下面的混淆矩阵所示：

上述表格中，算法的精确率为：

通过观察上述矩阵很容易了解分类器的错误类型。在本例当中，分类器在区分体操运动员和篮球运动员上表现得相当不错，而有时体操运动员和篮球运动员却会被误判为马拉松运动员，马拉松运动员有时被误判为体操运动员或篮球运动员。

混淆矩阵并不那么令人混淆！

一个编程的例子

来自卡内基梅隆大学的汽车MPG数据集，该数据集的格式如下：

下面试图基于气缸的数目、排水量（立方英寸）、功率、重量和加速时间预测汽车的MPG。我将所有392个实例放到mpgData.txt文件中，然后编写了如下的短Python程序，该程序利用分层采样方法将数据分到10个桶中（数据集及Python代码都可以从网站guidetodatamining.com下载）。

执行上述代码会产生10个分别为mpgData01、mpgData02… mpgData10的文件。

编程题

能否使test函数能够在刚刚构建的10个文件上进行10折交叉验证（该数据集可以从网站guidetodatamining.com下载）？

你的程序应该输出类似如下矩阵的混淆矩阵：

编程题——解答

该解答只涉及如下方面：

修改initializer方法以便从9个桶中读取数据；

加入一个新的方法对一个桶中的数据进行测试；

加入一个新的过程来执行10折交叉验证过程。

下面依次来考察上述修改。

initializer方法的签名看起来如下：

每个桶的文件名类似于mpgData-01、mpgData-02，等等。这种情况下，bucketPrefix将是“mpgData”，而testBucketNumber是包含测试数据的桶。如果testBucketNumber为3，则分类器将会在桶1、2、4、5、6、7、8、9、10上进行训练。dataFormat是一个如何解释数据中每列的字符串，比如：

它表示第一列代表实例的类别，下面5列代表实例的数值型属性，最后一列会被看成注释。

新的初始化方法的完整代码如下：

testBucket方法

下面编写一个新的方法来测试一个桶中的数据。

它以bucketPrefix和bucketNumber为输入，如果前者为“mpgData”、后者为3的话，测试数据将会从文件mpgData-03中读取，而testBucket将会返回如下格式的字典：

字典的键代表的是实例的真实类别。例如，上面第一行表示真实类别为35mpg的实例的结果。每个键的值是另一部字典，该字典代表分类器对实例进行分类的结果。例如行

表示实际为15mpg的3个实例被错分到20mpg类别中，而有4个实例被正确分到15mpg中，1个实例被错分到10mpg中。

10折交叉验证的执行流程

最后，我们需要编写一个过程来实现10折交叉验证。也就是说，我们要构造10个分类器。每个分类器利用9个桶中的数据进行训练，而将其余数据用于测试。

运行上述程序会产生如下结果：

Kappa统计量

一开始提到一些我们可能对分类器感兴趣的问题，其中包括“分类器到底好到什么程度”。我们已经对评估方法进行了改善，并且考察了10折交叉验证和混淆矩阵。前面的例子中，我们也算出分类器预测汽车MPG的精确率为53.316%。但是，53.316%意味着分类器到底是好还是坏？为回答这个问题，我们将继续考察一个统计量，即Kappa统计量。

Kappa统计量比较的是分类器与仅仅基于随机的分类器的性能。为展示其中的原理，我将引入一个比MPG更简单的例子，即再次回到女运动员那个例子。下面给出了女运动员分类的结果：

上表也给出了每行和每列的总实例数目。为确定精确率，我们将对角线的数字相加（35+88+28=151）然后除以总的实例数，得到151/200=0.755。

现在将生成另一个混淆矩阵，该矩阵代表随机分类器（进行随机预测的分类器）的分类结果。首先，生成一个只包含上述表格中总数的表格：

观察最后一行，我们发现有50%的可能会将一个实例分为“篮球运动员”（200个实例中有100个），有20%的可能会将实例分为“体操运动员”（200个实例中有40个），有30%的可能会将实例分为“马拉松运动员”。

接下来将使用这些比值将上述表格的剩余部分填满。随机分类器将会把20%的人分为体操运动员。60的20%为12，因此我们将12填入表格中。该分类器会将50%的人分为篮球运动员（即60中的30人），会将30%的人分为马拉松运动员。

接下来按照上述方法继续处理。实际有100个篮球运动员，随机分类器会将其中的20%（20人）分为体操运动员，50%分为篮球运动员，30%分为马拉松运动员。表中第四行可以依此类推，于是有：

为确定随机分类器的精确率，我们将对角线的数字累加并除以实例总数，得到：

Kappa统计量给出的是相对于随机分类器而言实际分类器到底好多少，其计算公式为：

其中，P(c)是实际分类器的精确率，而P(r)是随机分类器的精确率。本例中实际分类器的精确率为0.755，而随机分类器的精确率为0.37，因此有：

如何解释上述结果中的0.61？这到底意味着分类器是差、好还是很好？下面给出一个帮助我们理解该统计量大小的对照表：

一个最常被人引用的Kappa统计量区间对照解释

<0: 比随机方法的性能还差（less than chance performance）

0.01-0.20: 轻微一致（slightly good）

0.21-0.40: 一般一致（fair performance）

0.41-0.60: 中度一致（moderate performance）

0.61-0.80: 高度一致（substantially good performance）

0.81-1.00: 接近完美（near perfect performance）

① Landis, JR, Koch, GG. 1977. The measurement of observeragree- ment for categorical data. Biometrics 33:159-748

习题

假设我们开发了一个傻瓜分类器，它基于大家对10部电影的喜好程度预测当今大学生的专业。我们的数据集由来自计算机科学、教育、英语和心理学专业的600名学生组成。下面给出了混淆矩阵，请计算Kappa统计量并对结果进行解释。

该分类器的精确率为0.697。

习题——解答

该分类器有多好？请计算Kappa统计量并对结果进行解释。

首先，对所有列进行求和有：

接下来，为随机分类器构建混淆矩阵，有：

随机分类器的精确率为：

于是我们构建的分类器的P(c)为0.697，

随机分类器的P(r)为0.292，

Kappa统计量为：

这也意味着我们算法的性能较好。

近邻算法的改进

一个普通的分类器的例子是Rote分类器，它只记忆所有的训练集，仅当实例与训练样本精确匹配时才对实例进行分类。如果只在训练集上进行评估，那么Rote分类器的精确率一直是100%。在实际中，由于有些待分类的实例不在训练集中出现，因此Rote分类器并不是一个好的选择。我们可以将前面介绍的近邻分类器看成是Rote分类器的一个扩展。与Rote分类器寻找精确匹配不同的是，近邻方法寻找近似的匹配。Pang Ning Tan、Michael Steinbach和Vipin Kumar在他们所著的数据挖掘教材1中称这种做法为“如果某个东西走路像鸭子，叫起来像鸭子，看上去也像鸭子，那么它可能就是一只鸭子”。

近邻算法在遇到离群点时会发生问题。下面对此进行解释。我们再次回到女子运动员那个例子，这次只考察体操运动员和马拉松运动员。假设有一个个子特别矮、体重特别轻的马拉松运动员。该数据可以用下面的图来表示，其中m表示马拉松运动员，g表示体操运动员。

可以看到，那个个子矮、体重轻的马拉松运动员处于很多g中间的那个m上。假设x是待分类的实例，其最近邻是那个离群点m，因此它被会分为马拉松运动员。如果我们仔细观察上图，我们会说x更像是一名体操运动员，这是因为它出现在一堆体操运动员中间。

kNN

当前的最近邻分类器的一种改进方法是考察k个而不只是1个最近的邻居（kNN）。每个邻居会进行投票，分类器会将实例分到具有最高投票数目的类别中去。例如，假设使用的是3个最近邻（k=3）。上图中会有2票投向体操运动员，1票投向马拉松运动员，因此我们预计x是一名体操运动员。

因此当预测离散型类别（例如，马拉松运动员、体操运动员或篮球运动员）时，可以利用上述投票方法。具有最高得票的类别将被分配给实例。如果存在多个得票相同的类别，则从中随机选择最后的类别。当进行数值预测时（比如给乐队Funky Meters打几星），可以通过计算距离权重值来将影响分摊给多个近邻。这里稍微更深入地分析一下。假设我们想预测Ben喜欢Funky Meters乐队的程度，而Ben的3个最近邻分别是Sally、Tara和Jade。下面给出了他们到Ben的距离以及他们对Funky Meters的评分结果。

因此，Sally离Ben最近，她给Funky Meters的评分为4。由于我希望最近用户的评分在最终评分结果中的权重大于其他近邻的评分，因此第一步就是对距离进行转换以使数值越大用户越近。一种实现的方法就是求距离的倒数（即1除以距离）。于是Sally的距离的倒数为：

下面将每个距离的倒数除以所有倒数之和。所有距离倒数的和为0.2+0.1+0.067=0.367。

我们应该注意到两件事。第一，所有的影响因子之和为1；第二，从原始距离来看，Sally到Ben的距离是她到Tara的距离的两倍，而在最后的影响因子中，两倍的关系仍然保留，也就是说Sally的影响是Tara的两倍。最后，我们将每个人的影响因子乘上评分然后求和，有：

Ben的预测评分

= (0.545×4) + (0.272×5) + (0.183×5)

= 2.18 + 1.36 + 0.915 = 4.455

习题

我想知道Sofia对爵士乐钢琴家Hiromi的喜欢程度，下列数据使用k近邻得到的预测值是多少(k=3)？

习题——解答

第一步是计算每个距离的倒数（1除以距离），得到：

距离倒数之和为0.475。

下面通过将每个距离倒数除以距离倒数之和来计算每个用户的影响因子，有：

最后，将影响因子乘上评分并进行累加得到：

一个新数据集及挑战

现在到考察一个新数据集的时候了，该数据集是美国国立糖尿病、消化和肾脏疾病研究所（United States National Institute of Diabetes and Digestive and Kidney Diseases，简称NIDDK）所开发的皮马印第安人糖尿病数据集（Pima Indians Diabetes Data Set）。

令人吃惊的是，有超过30%的皮马人患有糖尿病。与此形成对照的是，美国糖尿病的患病率为8.3%，中国为4.2%。

数据集中的每个实例表示一个超过21岁的皮马女性的信息，她属于以下两类之一，即5年内是否患过糖尿病。每个人有8个属性。

属性：

1．怀孕次数。

2．2小时口服葡萄糖耐量测试中得到的血糖浓度。

3．舒张期血压（mm Hg）。

4．三头肌皮脂厚度（mm）。

5．2小时血清胰岛素（mu U/ml）。

6．身体质量指数（体重kg/（身高in m）^2）。

7．糖尿病家系作用。

8．年龄。 下面给出了一个数据的例子（最后一列表示类别：0表示没有糖尿病，1表示有糖尿病）。

2　　99　　52　　15　　94　　24.6　　0.637　　21　　0

3　　83　　58　　31　　18　　34.3　　0.336　　25　　0

5　　139　　80　　35　 160　　31.6　 0.361　　25　　1

3　　170　　64　　37　 225　　34.5　 0.356　　30　　1

因此，上例中第一位女性有过两个孩子，血糖为99，舒张期血压为52，等等。

编程题——第一部分

使用构建的近邻分类器对pimaSmall数据集进行10折交叉验证时，会得到如下结果：

提示

Python函数heapq.nsmallest(n,list)会返回最小的n个元素构成的列表(list)。

下面是你要完成的任务：

从网站下载分类器的代码，实现kNN算法。此时需要修改类中的initializer方法以便加入另一个参数k：

该方法的签名看起来类似于def knn(self, itemVector)：

它应该使用self.k（记住要在init方法中设置该值）并返回类别结果（在Pima癌症数据集上为0或1），还应该修改tenfold过程以便将k传递给initializer。

编程题——解答

我对init_的修改十分简单：

我的kNN方法如下：

我对tenfold的一点点修改如下：

你可以从网站guidetodatamining.com上下载上述代码。记住，这只是该方法实现的一种做法，并不一定是最佳的做法。

编程题——第二部分

哪种做法会带来更大的不同？是使用更多的数据（比较pimaSmall和pima上的分类结果）还是采用更好的算法（比较k=1和k=3两种情况）？

编程题——结果！

下面给出的是我得到的精确率结果（k=1时的算法就是上一章的最近邻算法）。

因此，看上去将数据规模提高到3倍所带来的精确率提高的程度高于算法带来的提高。

习题

嗯，72.519%的精确率看起来相当不错，但是到底是不是这样呢？计算Kappa统计量来寻找答案：

习题——解答

从上面可知，这只是一个性能一般的结果。

随机(r)分类器：

精确率为：

更多数据、更好的算法以及一辆破公共汽车 几年前我在墨西哥城参加一个学术会议，那次会议的会程与其他会议有点不同：第一天做报告，而第二天则是一天的游览（包括帝王蝶、印加遗迹等）。游览的那天涉及一段在公共汽车上的长途旅行，而汽车出了点故障。于是，在汽车进行检修时，一大堆博士有很多时间站在路边互相交谈。这段马路上的交流对我而言是那次会议的亮点。其中和我交谈的一个人叫Eric Brill，他因为开发一个称为Brill的词性标注器而闻名。与前几章类似的是，Brill标注器做的也是对数据分类，此时，它将词按照词性（名词、动词等）分类。Brill构建的算法要显著优于前人的算法（因此，Brill在自然语言处理领域变得十分出名）。在那条墨西哥公路边，我同Eric Brill探讨提高算法性能的问题。他的观点是，通过获得更多训练数据带来的提高会比算法改进带来的提高要大。实际上，他感觉如果保留原始的词性标注算法并且单纯增大训练数据的规模，所带来的提高会高于新提出的算法所带来的进步。尽管如此，他也说，只是搜集更多的数据无法获得博士学位，但是通过开发出一个具有少量性能提高的算法却能实现这一点！

这里给出了另一个例子。在很多机器翻译竞赛中，Google往往名列前茅。我们得承认Google拥有大量极其聪明的人在开发伟大的算法，但是Google之所以胜出很大部分原因应归功于其从Web上获得的极大规模训练集。

这并不是说不应该选择最佳的算法。我们已经看到，选择好的算法会带来显著的不同。但是，如果想解决一个实际问题（而不是发表学术论文），那么可能不值得花费大量时间研究和调整算法。如果集中去获取更多数据的话，你或许会得到更高的性价比或者时间上的更好回报。

在认识到数据重要性的同时，我将继续想办法引入新的算法。

人们将kNN分类器用于：

Amazon上的物品推荐

消费者信贷风险的评估

利用图像分析技术对地表分类

人脸识别

识别图像中的人物性别

推荐Web网页

推荐度假套餐

1Introduction to Data Mining. 2005. Addison-Wesley

本文节选自《写给程序员的数据挖掘实践指南》

内容简介

数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。大多数数据挖掘的教材都专注于介绍理论基础，因而往往难以理解和学习。

本书是写给程序员的一本数据挖掘指南，可以帮助读者动手实践数据挖掘、集体智慧并构建推荐系统。全书共8章，介绍了数据挖掘的基本知识和理论、协同过滤、内容过滤及分类、算法评估、朴素贝叶斯、非结构化文本分类以及聚类等内容。本书采用“在实践中学习”的方式，用生动的图示、大量的表格、简明的公式、实用的Python代码示例，阐释数据挖掘的知识和技能。每章还给出了习题和练习，帮助读者巩固所学的知识。

本书适合对数据挖掘、数据分析和推荐系统感兴趣的程序员及相关领域的从业者阅读参考；同时，本书也可以作为一本轻松有趣的数据挖掘课程教学参考书。

本文转载自异步社区

原文链接：https://www.epubit.com/articleDetails?id=NC7E3EF9154100001F648FC0026BF4700