衡量分类器效果的一些指标 (3) – AUC/ROC 曲线

这个系列的 第一篇文章 讲述了衡量分类器效果的一些基本概念,第二篇文章 讲述了 PR 曲线一些特定的知识,今天这篇文章讲一讲 AUC/ROC 曲线,以下简称 ROC 曲线。 ROC 曲线也是使用Confusion Matrix 中的数据来衡量分类器的性能。同样,在选定了特定的阈值以后,对于一组已经标定好的数据,我们可以计算它的 True Positive, False Positive, False Negative, True Negative。在这四个数据算好以后,我们有以下两个新的定义: True Positive Rate (TPR) (1)   直观来讲,TPR 反映的就是模型标定为正例的那些正例占总共数据中的所有正例的比例。在讨论 Precision/Recall 的背景下,这个东西其实就是Recall。但是在 ROC的背景下,TPR 这个名字更有意义一些,以便和下面的 FPR 对应。 False Positive Rate (FPR) (2)   直观来讲,FPR 反映的就是模型错误的标定为正例的那些负例占总共数据中的所有负例的比例。 很明显,在阈值(Threshold)增加的时候,模型标定的正例(Postive)会减少,因为标定的正例包含了 True Positive 和 False Positive,因此 TPR 和 FPR 都会下降。同样在 阈值(Threshold)减少的时候 […]

分布式Top N 算法引出的数学问题

假定我们需要从 1 Billion 个数中找出 1000 个最大的数,在一台机器上算当然太慢了,一个有效的分布式算法是把这 1 Billion 个数分成 1000 份,每一份就有 1 Million 个数。然后在每一份中用一个机器找到最大的 1000 个数,然后把每一份中最大的1000 个数合起来,总共有 个数,然后再用一台机器从这最后的 1 Million 个数中找到最大的 1000 个数即可。 这样的分布式算法使用 1000台机器,大概要比只使用一台机器快 1000 倍。 一般来说,对于 个数,如果要找出 个最大的数,如果要分成 份进行分布式计算,那么最优的 值是多少呢? 很明显,分为 份以后,每一份中有 个数字,因为是并行计算,所以我们假定我们总是能够找到足够的机器,这样这个阶段计算需要处理的数字就是 个,在最后汇总阶段需要处理的数有 个,只能在一台机器上处理,所以总的处理时间就是正比于下面的函数: (1)   应用基本的微积分求函数极值的知识我们就有: (2)   令 ,很容易得到: (3)   对于我们上面的问题: (4)   所以分成1000份刚好就是最佳答案。 现在我们考虑如何再改进上面的算法。考虑到第二个阶段我们需要处理 个数,而且这个阶段只能在一台机器上进行,我们可以在这个方面想想办法。我们可以很快注意到下面一个事实:我们总共需要找到 个数,但是为了避免遗漏,在把数据分为 份以后,在每一份数据中我们都需要找到 个数,实际上只有在最坏的情况下,也就是所有最大的 […]

组合数学中的分配问题(四):不能区分的对象和不能区分的组

这是分配问题这个系列的最后一个帖子,关注不能区分的对象和不能区分的组。把一个正整数分解成为几个非零的其他正整数之和,叫做该正整数的一个分组(Partition)。对于任意一个正整数,它的分组总数(Partition Number)就是一个典型的被分配对象和分组本身都不能被区分的分配问题。 Partition Number 是一个很广阔的问题,分析它远远超出了我们这个帖子的内容,有兴趣可以参见 Wikipedia Page – Partition 。这里我们关心的是被分成的组的个数 已经确定的情况,也就是把一个正整数 分为 个正整数之和,一共有多少种分组方法。正像绝大多数组合数学的问题一样,这个问题有一个简洁递归公式如下: (1)   其中 就代表把正整数 分为 个正整数之和的分组数目。这个递归公式是怎么来的呢? 首先我们看到,正整数 分为 个正整数的分组有两种情况,第一种是某个分组的数等于1,第二种是所有的分组都大于1。很明显这两种情况互相不重叠,而且涵盖了所有可能的分组情况。 对于第一种情况的每个分组方案,我们可以把这个数目为1的分组拿掉,那么我们就得到了把正整数 分为 组的一个方案。可以看出,对于 中的这类方案,既然它们每一个都有一个相同的数目为1的分组,那么剩下的分组也必然各不相同,因此拿掉这个数目为1的分组之后这些分组也各不相同,正好涵盖了 的所有方案,而且我们已经成功的把数字减少到了。 对于第二种情况的每个分组方案,我们可以把该方案中的每个组的数目减去1,那么我们就得到了把 正整数分为 组的一个方案。可以看出,对于 中的这类方案,每一个都对应 中的一个分组方案,而且我们已经成功的把数字减少到了。综上所述,把这两种情况的方案加起来我们就得到了上面的递归公式: (2)   下面是一个从 stackexchange 上引用过来的一个例子,具体展示了把上面的递归公式应用于 的过程: (3)   很明显,在 的分组方案里面加上一个数目为1的组,我们就得到了 里面有一个组的数目为1的那些分组方案;而把 的分组方案里面的每一个组加上1,我们就得到了 里面所有分组都大于1的那些分组方案。这两部分结合起来,就是 的全部分组。 最后,既然这是一个递归的方案,我们必须要讨论结束递归的条件,很明显我们有: 当 的时候,分组数为1。 当 的时候,分组数为0。 当 的时候,分组数为1。

组合数学中的分配问题(三):可以区分的对象和不能区分的组

这篇帖子介绍分配问题中的第三种组合情况:被分配的对象是可以区分的,但是分配去的目的地不能区分。这个问题有两种解决的思路,下面一一阐述。 假定我们有10本不同的书《皇帝新脑》,《C语言入门》,《基督山伯爵》,《活着》,《一只特立独行的猪》,《安娜卡列宁娜》,《机器学习》,《妞妞》,《巨人三传》,《信息熵简介》,现在需要把这些书分为三组,分组的方法有多少种? 这个问题中被分配的对象本身是可以区分的,但是分配去的目的地是不可区分的。也就是说,每本书都是不一样的,但是分组以后,一组书是第一组还是第二组,本身并不重要。这个问题的答案被称为 Stirling numbers of the second kind。 个可以区分的物体分为 个不可区分的组,用 表示。很明显我们有: (1)   下来该怎么办呢,绝大多数排列组合问题都可以使用递归的方式进行思考,关键是找到正确的递归思路。对于把本书分为组,我们考虑第本书自己单独是一组的情况和第本书和其他书分在一个组的情况。很明显这两种情况互相不重叠,而且也涵盖了所有可能的分组。对于第一种情况,我们相当于要把剩下的本书分为组,所以所有的分组数目是: (2)   对于第二种情况,我们首先把本书分为组,这一共有 (3)   种方案。下来我们让第本书加入这 个分组,很明显对于 中的每一个方案,这第本书可以选择组中的任意一个加入,这样我们从一个方案就变成了个方案。 下面我们需要考虑在所有的 个方案中这样操作会不会导致重复方案。假定我们从 个方案中任意选取一对方案 和,然后我们这样把第本书加入其中的每一个组,这样就创建了 个新的方案。如果我们选定加入第本书的在方案 和 方案 中的两个组原来是一样的,那么这两个方案中肯定还有不一样的组,而且这些组在加入了第本书以后没有变化,所以这两个方案还是不一样;假定我们选定加入第本书在方案 和 方案 中的两个组是不一样的,那么在其中加入第本书以后,他们还是不一样,所以这两个方案还是不一样。综上所述,在方案 的 个组中任意选择一个组把第 本书加入而创建的新的 方案与方案 的 个组中任意选择一个组把第 本书加入而创建的新的 方案中间没有相同的方案,因此第二种情况我们一共有: (4)   种方案。而综合这两种情况,我们就会得到: (5)   将上面的公式应用于我们的问题有: (6)   思路二 在《组合数学中的分配问题(一):可以区分的对象和组》这篇帖子中,我们已经解决了把 本书分给 个人,每个人最少分到一本的问题。那个问题和这里的问题的不同之处在于,每个人是不一样的,所以分配的目的地是可以区分的,但是把书分组我们并不关心每个组是第一组还是第二组,所以分配的目的地是不可以区分的。但是这两个问题的答案就像排列数 与 […]

组合数学中的分配问题(二):不能区分的对象和可以区分的组

上一篇帖子介绍了被分配的对象和分配的目的地都可以区分的分配问题,这个帖子我们来看被分配对象不能区分的情况。 假定办公室新来了18个一样的文件夹,需要在 Alice, Bob, Charlie 和 Dave 之间分配。假定每一个人最少分到一个文件夹的话,总共有多少种分配的方式? 这个问题中,被分配的对象本身是不可区分的,但是分配去的目的地是可以区分的。Applied Combinatorics 一书中对于这个问题给出了如下的思路:假定我们把这18个文件夹排成一排,那么这些文件夹之间总共有17个空隙。在这些空隙之中选择三个空隙将把这一排文件夹分为四份,正好对应 A, B, C 和 D 四个人。因为选择这些空隙的先后顺序不影响最终的结果,所以从17个空隙中选择3个的总共方式有: (1)   假定办公室新来了18个一样的文件夹,需要在 Alice, Bob, Charlie 和 Dave 之间分配。假定对于每一个人最少分到的文件夹数量不做限制的话(也就是有些人可能分到0个)的话,总共有多少种分配的方式? 上面我们已经会求解每一个人最少分到一个文件夹了。对于有些人可能分不到文件夹的情况,我们可以转化为上面的问题进行求解。如果我们虚拟的把总文件夹数目增加4个,这样我们总共就有 个文件夹,下面我们给每个人都最少发一个文件夹,那么按照上面的办法,总共分配的方式有: (2)   下来,我们在从每个人手中拿走一个文件夹,这样分配出去的总文件夹的数量又变回到18个,而且有些人手中可能一个文件夹都没有了。实际上通过思考我们应该可以认识到,给每人增发一个虚拟文件夹的假定下所有分配方案的总数和有些人可以分到0个文件夹的分配方案总数存在一一对应的关系,因此1330就是最后的答案。 假定办公室新来了18个一样的文件夹,需要在 Alice, Bob, Charlie 和 Dave 之间分配。假定每一个人最少分到两个文件夹的话,总共有多少种分配的方式? 同样,这个问题可以转化为上面已经解决的每人最少分配一个文件夹的问题。假定我们先给每个人一个文件夹,这样我们还剩下14个文件夹,然后把这14个文件夹按照每人最少分配一个的思路考虑,那么总共就有: (3)  

组合数学中的分配问题(一):可以区分的对象和组

分配问题是一类典型的组合数学问题,根据被分配的物品和分配去的目的地是否需要区分,以及分配方式的某些限制,分配问题可以分为很多类型。把几本不同的书分给几个人属于被分配的物品和分配去的目的地都可以区分的类型,把一叠一元钞票分给几个小孩属于被分配的物品本身没有区别,但是分配去的目的地可以区分的类型,等等等等。分配问题还可以加上额外的限制条件,比如每个人最少分到一个,或者可以有人分到0个物品等等。这篇帖子我们先来看看被分配的物品和分配去的目的地都可以区分的这类问题。 假定有三本书 《皇帝新脑》,《C语言入门》,《基督山伯爵》,需要在 Alice, Bob 和 Charlie 三个人中分配,总共有多少种分配方式? 这个问题中,被分配的对象本身和分配去的目的地都是可以区分的,而且又没有额外的条件限制,这类问题最为简单。每一本书都有3个可能的人供选择,那么3本书总共可能的选择就是: (1)   一般的,假定我们有 本不同的书,个不同的人,那么总共的分配方法是: (2)   假定有三本书 《皇帝新脑》,《C语言入门》,《基督山伯爵》,需要在 Alice, Bob 和 Charlie 三个人中分配,假定每一个人最少分到一本书的话,总共有多少种分配方式? 这个问题中,被分配的对象本身和分配去的目的地都是可以区分的,但是因为加上了额外的限制条件,所以这个问题要比前面的问题复杂很多,下面是一个递归的解法。我们已经知道总共的分配方法是, 下来我们需要把某个人或者某些人没有拿到书的分配方案从其中去掉。假定我们用记号 表示 本不同的书在个不同的人中分配,每个人最少拿到一本的话,那么全部的分配方案中,有一个人拿到0本书,然后剩下的个人拿到这本书,而且每个人至少拿到一本的方案总数是: (3)   上面的公式中,第一项表示从中选取拿到0本书的那个人的方案总数,第二项表示在剩下个人中分配本书,而且每个人至少拿到一本的方案总数。很明显这些方案是互相不重复的。类似的,在全部的分配方案中,有两个人拿到0本书,然后剩下的个人拿到本书,而且每个人至少拿到一本的方案总数是: (4)   以此类推下去,我们可以得到 的递归定义如下: (5)   注意到 表示把 本书分给一个人,所以它总是等于1。上面的函数的值可以被递归的计算出来。具体这道问题的答案是: (6)