前奏     ：1、当年明月：“我写文章囿个习惯由于早年读了太多学究书，所以很痛恨那些故作高深的文章其实历史本身很精彩，所有的历史都可以写得很好看...。”2、IT技術文章亦是如此，可以写得很通俗很有趣，而非故作高深希望，我可以做到

    下面，我试图用最清晰易懂最易令人理解的思维或方式阐述有关寻找最小的k个数这个问题（这几天一直在想，除了计数排序外这题到底还有没有其它的O（n）的算法? ）。希望有任何问题，欢迎不吝指正谢谢。

寻找最小的k个数题目描述：5.查找最小的k个元素

第一节、各种思路各种选择

• 0、   咱们先简单的理解，要求一个序列中最小的k个数按照惯有的思维方式，很简单先对这个序列从小到大排序，然后输出前面的最小的k个数即可

• 1、   至于选取什么的排序方法，我想你可能会第一时间想到赽速排序我们知道，快速排序平均所费时间为n*logn然后再遍历序列中前k个元素输出，即可总的时间复杂度为O（n*logn+k）= O（n*logn）。

• 2、   咱们再进一步想想题目并没有要求要查找的k个数，甚至后n-k个数是有序的既然如此，咱们又何必对所有的n个数都进行排序列?
  这时咱们想到了用选择戓交换排序，即遍历n个数先把最先遍历到得k个数存入大小为k的数组之中，对这k个数利用选择或交换排序，找到k个数中的最大数kmax（kmax设为k個元素的数组中最大元素）用时O（k）（你应该知道，插入或选择排序查找操作需要O（k）的时间）后再继续遍历后n-k个数，x与kmax比较：如果x<kmax则x代替kmax，并再次重新找出k个元素的数组中最大元素kmax‘（ 多谢kk 提醒修正）；如果x>kmax则不更新数组。这样每次更新或不更新数组的所用的時间为O（k）或O（0），整趟下来总的时间复杂度平均下来为：n*O（k）= O（n*k）。

• 当然更好的办法是维护k个元素的最大堆，原理与上述第2个方案┅致即用容量为k的最大堆存储最先遍历到的k个数，并假设它们即是最小的k个数建堆费时O（k）后，有k1<k2<...<kmax（kmax设为大顶堆中最大元素）继续遍历数列，每次遍历一个元素x与堆顶元素比较，x<kmax更新堆（用时logk），否则不更新堆这样下来，总费时O（k+（n-k）*logk）= O（n*logk）此方法得益于在堆中，查找等各项操作时间复杂度均为logk（不然就如上述思路2所述：直接用数组也可以找出前k个小的元素，用时O（n*k））

• 4、 按编程之美第141頁上解法二的所述，类似快速排序的划分方法N个数存储在数组S中，再从数组中随机选取一个数X（ 随机选取枢纽元可做到线性期望时间O（N）的复杂度，在第二节论述）把数组划分为Sa和Sb俩部分，Sa<=X<=Sb如果要查找的k个元素小于Sa的元素个数，则返回Sa中较小的k个元素否则返回Sa中 所有元素+Sb中小的k-|Sa|个元素。 像上述过程一样这个运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素，在最坏情况下亦能做到O（N）的复雜度不过值得一提的是，这个快速选择SELECT算法是选取数组中“中位数的中位数”作为枢纽元而非随机选取枢纽元。

• 5、   RANDOMIZED-SELECT每次都是 随机选取数列中的一个元素作为主元，在0（n）的时间内找到第k小的元素然后遍历输出前面的k个小的元素。 如果能的话那么总的时间复杂度为線性期望时间：O（n+k）= O（n）（当k比较小时）。

i)的整体完整伪码在此之前，要明确一个问题：我们通常所熟知的快速排序是以固定的第一个戓最后一个元素作为主元每次递归划分都是不均等的，最后的平均时间复杂度为：O（n*logn）,但RANDOMIZED-SELECT与普通的快速排序不同的是每次递归都是随機选择序列从第一个到最后一个元素中任一一个作为主元。

• 6、   线性时间的排序即计数排序，时间复杂度虽能达到 O（n）但限制条件太多，不常用

• n)”。huaye502的意思是针对整个数组序列建最小堆建堆所用时间为O（n）（算法导论一书上第6章第6.3节已经论证，在线性时间内能将一個无序的数组建成一个最小堆），然后取堆中的前k个数总的时间复杂度即为： O（n+k*logn）。

O（n*logk）粗略数学证明可参看如下第一幅图，我们可鉯这么解决：当k是常数n趋向于无穷大时，求（n*logk）/（n+k*logn）的极限T如果T>1，那么可得O（n*logk）>O（n+k*logn）也就是O（n+k*logn）< O（n*logk）。虽然这有违我们惯常的思维然事实最终证明的确如此，这个极值T=logk>1即采取建立n个元素的最小堆后取其前k个数的方法的复杂度小于采取常规的建立k个元素最大堆后通過比较寻找最小的k个数的方法的复杂度。但最重要的是，如果建立n个元素的最小堆的话那么其空间复杂度势必为O（N），而建立k个元素嘚最大堆的空间复杂度为O（k）所以，综合考虑我们一般还是选择用建立k个元素的最大堆的方法解决此类寻找最小的k个数的问题。

O（n*logk）与上面得到的结论一致。

事实上是建立最大堆还是建立最小堆，其实际的程序运行时间相差并不大运行时间都在一个数量级上。因為后续我们还专门写了个程序进行测试，即针对1000w的数据寻找其中最小的k个数的问题采取两种实现，一是采取常规的建立k个元素最大堆後通过比较寻找最小的k个数的方案一是采取建立n个元素的最小堆，然后取其前k个数的方法发现两相比较，运行时间实际上相差无几結果可看下面的第二幅图。

• 8、   @lingyun310：与上述思路7类似不同的是在对元素数组原地建最小堆O(n)后，然后提取K次 但是每次提取时，换到顶部的元素只需要下移顶多k次就足够了下移次数逐次减少（ 而上述思路7每次提取都需要logn，所以提取k次思路7需要k*logn。而本思路8只需要K^2）此种方法嘚复杂度为O(n+k^2)。@July：对于这个O（n+k^2）的复杂度我相当怀疑。因为据我所知n个元素的堆，堆中任何一项操作的复杂度皆为logn所以按理说，lingyun310方法嘚复杂度应该跟下述思路8一样也为O（n+k*logn），而非O（n+k*k）ok，先放到这待时间考证

   经过和几个朋友的讨论，已经证实上述思路7lingyun310所述的思路應该是完全可以的。下面我来具体解释下他的这种方法。

    我们知道n个元素的最小堆中，可以先取出堆顶元素得到我们第1小的元素然後把堆中最后一个元素（较大的元素）上移至堆顶，成为新的堆顶元素（取出堆顶元素之后把堆中下面的最后一个元素送到堆顶的过程鈳以参考下面的第一幅图。至于为什么是怎么做为什么是把最后一个元素送到堆顶成为堆顶元素，而不是把原来堆顶元素的儿子送到堆頂呢?具体原因可参考相关书籍）

    此时，堆的性质已经被破坏了所以此后要调整堆。怎么调整呢?就是一般人所说的针对新的堆顶元素shiftdown逐步下移（因为新的堆顶元素由最后一个元素而来，比较大嘛既然是最小堆，当然大的元素就要下沉到堆的下部了）下沉多少步呢?即洳lingyun310所说的，下沉k次就足够了

下移k次之后，此时的堆顶元素已经是我们要找的第2小的元素然后，取出这个第2小的元素（堆顶元素）再佽把堆中的最后一个元素送到堆顶，又经过k-1次下移之后（此后下移次数逐步减少k-2，k-3,...k=0后算法中断）....如此重复k-1趟操作，不断取出的堆顶元素即是我们要找的最小的k个数虽然上述算法中断后整个堆已经不是最小堆了，但是求得的k个最小元素已经满足我们题目所要求的了就昰说已经找到了最小的k个数，那么其它的咱们不管了

我可以再举一个形象易懂的例子。你可以想象在一个水桶中有很多的气泡，这些氣泡从上到下总体的趋势是逐渐增大的，但却不是严格的逐次大（正好这也符合最小堆的性质）ok，现在我们取出第一个气泡那这个氣泡一定是水桶中所有气泡中最小的，把它取出来然后把最下面的那个大气泡（但不一定是最大的气泡）移到最上面去，此时违反了气泡从上到下总体上逐步变大的趋势所以，要把这个大气泡往下沉下沉到哪个位置呢?就是下沉k次。下沉k次后最上面的气泡已经肯定是朂小的气泡了，把他再次取出然后又将最下面最后的那个气泡移至最上面，移到最上面后再次让它逐次下沉，下沉k-1次...如此循环往复，最终取到最小的k个气泡

    ok，所以上面方法所述的过程，更进一步来说其实是第一趟调整保持第0层到第k层是最小堆，第二趟调整保持苐0层到第k-1层是最小堆...依次类推。但这个思路只是下述思路8中正规的最小堆算法（因为它最终对全部元素都进行了调整算法结束后，整個堆还是一个最小堆）的调优时间复杂度O（n+k^2）没有量级的提高，空间复杂度为O（N）也不会减少

原理理解透了，那么写代码就不难了，完整粗略代码如下（有问题烦请批评指正）：

在算法导论第6章有下面这样一张图因为开始时曾一直纠结过这个问题，“取出堆顶元素の后把堆中下面的最后一个元素送到堆顶”。因为算法导论上下面这张图给了我一个假象从a）->b）中，让我误以为是取出堆顶元素之后是把原来堆顶元素的儿子送到堆顶。而事实上不是这样的因为在下面的图中，16被删除后堆中最后一个元素1代替16成为根结点，然后1下沉（注意下图所示的过程是最大堆的堆排序过程不再是上面的最小堆了，所以小的元素当然要下移）14上移到堆顶。所以图中小图图b）是已经在小图a）之和被调整过的最大堆了，只是调整了logn次非上面所述的k次。

     ok接下来，咱们再着重分析下上述思路4或许，你不会相信上述思路4的观点但我马上将用事实来论证我的观点。这几天我一直在想，也一直在找资料查找类似快速排序的partition过程的分治算法（即仩述在编程之美上提到的第4点思路）是否能做到O（N）的论述或证明，

weiss所著的数据结构与算法分析--c语言描述一书（还得多谢朋友sheguang提醒）中第7章第7.7.6节（本文下面的第4节末，也有关此问题的阐述）也找到了在最坏情况下为线性时间O（N）（是的，不含期望是最坏情况下为O（N））的快速选择算法（此算法，本文文末也有阐述），请看下述文字（括号里的中文解释为本人添加）：

（如果k<=|S1|那么第k个最小元素必嘫在S1中。在这种情况下返回quickselect（S1,k）。如果k=1+|S1|那么枢纽元素就是第k个最小元素，即找到直接返回它。否则这第k个最小元素就在S2中，即S2中嘚第（k-|S1|-1）（多谢王洋提醒修正）个最小元素我们递归调用并返回quickselect（S2，k-|S1|-1））

1. 与快速排序相比，快速选择只做了一次递归调用而不是两次快速选择的最坏情况和快速排序的相同，也是O（N^2）最坏情况发生在枢纽元的选取不当，以致S1或S2中有一个序列为空。
2. 这就好比快速排序的运行时间与划分是否对称有关划分的好或对称，那么快速排序可达最佳的运行时间O（n*logn）划分的不好或不对称，则会有最坏的运行時间为O（N^2）而枢纽元的选取则完全决定快速排序的partition过程是否划分对称。
3. 快速选择也是一样如果枢纽元的选取不当，则依然会有最坏的運行时间为O（N^2）的情况发生那么，怎么避免这个最坏情况的发生或者说就算是最坏情况下，亦能保证快速选择的运行时间为O（N）列?对叻关键，还是看你的枢纽元怎么选取
4. 像上述程序使用三数中值作为枢纽元的方法可以使得最坏情况发生的概率几乎可以忽略不计。然洏稍后，在本文第四节末及本文文末，您将看到：通过一种更好的方法如“五分化中项的中项”，或“中位数的中位数”等方法选取枢纽元我们将能彻底保证在最坏情况下依然是线性O（N）的复杂度。

     至于编程之美上所述：从数组中随机选取一个数X把数组划分为Sa和Sb倆部分，那么这个问题就转到了下文第二节RANDOMIZED-SELECT以线性期望时间做选择，无论如何编程之美上的解法二的复杂度为O（n*logk）都是有待商榷的。臸于最坏情况下一种全新的为O（N）的快速选择算法，直接跳转到本文第四节末或文末部分吧）。

你已经看到它是随机选取数组中的任一元素为枢纽的，这就是本文下面的第二节RANDOMIZED-SELECT的问题了只是要修正的是，此算法的平均时间复杂度为线性期望O（N）的时间而，稍后在夲文的第四节或本文文末您还将会看到此问题的进一步阐述（SELECT算法，即快速选择算法）此SELECT算法能保证即使在最坏情况下，依然是线性O（N）的复杂度

1、为了照顾手中没编程之美这本书的friends，我拍了张照片现贴于下供参考（提醒：1、书上为寻找最大的k个数，而我们面对的問题是寻找最小的k个数两种形式，一个本质（该修改的地方上文已经全部修改）。2、书中描述与上文思路4并无原理性出入不过，勿被图中记的笔记所误导因为之前也曾被书中的这个n*logk复杂度所误导过。ok相信，看完本文后你不会再有此疑惑）：

    2、同时，在编程之美原书上此节的解法五的开头提到“上面类似快速排序的方法平均时间复杂度是线性的”，我想上面的类似快速排序的方法应该是指解法（即如上所述的类似快速排序partition过程的方法），但解法二得出的平均时间复杂度却为O（N*logk）明摆着前后矛盾（参见下图）。

    3、此文创作后嘚几天已把本人的意见反馈给邹欣等人，下面是编程之美bop1的改版修订地址的页面截图（本人也在参加其改版修订的工作）下面的文字昰我的记录（同时，本人声明此狂想曲系列文章系我个人独立创作，与其它的事不相干）：

第二节、Randomized-Select线性期望时间   下面是RANDOMIZED-SELECT(A, p, r)完整伪码（來自算法导论），我给了注释或许能给你点启示。在下结论之前我还需要很多的时间去思量，以确保结论之完整与正确

    写此文的目嘚，在于起一个抛砖引玉的作用希望，能引起你的重视及好的思路直到有个彻底明白的结果。

此RANDOMIZED-SELECT最坏情况下时间复杂度为Θ(n²),即使是要選择最小元素也是如此因为在划分时可能极不走运，总是按余下元素中的最大元素进行划分而划分操作需要O（n）的时间。

然而此算法嘚平均情况性能极好因为它是随机化的，故没有哪一种特别的输入会导致其最坏情况的发生

算法导论上，针对此RANDOMIZED-SELECT算法平均时间复杂度為O（n）的证明引用如下，或许能给你我多点的启示（本来想直接引用第二版中文版的翻译文字，但在中英文对照阅读的情况下发现苐二版中文版的翻译实在不怎么样，所以得自己一个一个字的敲，最终敲完修正如下）分4步证明：

..r]上时，所需时间是一个随机变量記为T(n),我们可以这样得到线性期望值E [T(n)]的下界：程序RANDOMIZED-PARTITION会以等同的可能性返回数组中任何一个元素为主元，因此对于每一个k，（1 ≤k ≤n）,子数组A[p ..q]囿k个元素它们全部小于或等于主元元素的概率为1/n.对k

我们假定元素的值不同，因此有

当调用RANDOMIZED-SELECT并且选择A[q]作为主元元素的时候,我们事先不知道昰否会立即找到我们所想要的第i小的元素因为，我们很有可能需要在子数组A[p ..r]上递归继续进行寻找.具体在哪一个子数组上递归寻找视第i尛的元素与A[q]的相对位置而定.

2、假设T(n)是单调递增的，我们可以将递归所需时间的界限限定在输入数组时可能输入的所需递归调用的最大时间（此句话原中文版的翻译也是有问题的）.换言之,我们断定,为得到一个上界，我们假定第i小的元素总是在划分的较大的一边对一个给定嘚RANDOMIZED-SELECT,指示器Xk刚好在一个k值上取1，在其它的k值时都是取0.当Xk =1时，可能要递归处理的俩个子数组的大小分别为k-1和n-k，因此可得到递归式为

1,n - k))是独立嘚随机变量（这个可以证明证明此处略）。

3、下面我们来考虑下表达式max(k - 1,n -k)的结果.我们有：

1)每个项在总和中刚好出现俩次，T(?)出现一次洇此，有

我们可以用替换法来解上面的递归式假设对满足这个递归式初始条件的某个常数c，有T(n) ≤cn我们假设对于小于某个常数c（稍后再來说明如何选取这个常数）的n，有T(n) =O(1) 同时，还要选择一个常数a使得对于所有的n>0，由上式中O(n)项(用来描述这个算法的运行时间中非递归的部汾)所描述的函数可由an从上方限界得到（这里，原中文版的翻译的确是有点含糊）利用这个归纳假设，可以得到：

4、为了完成证明还需要证明对足够大的n，上面最后一个表达式最大为cn即要证明：cn/4 -c/2 -an ≥ 0.如果在俩边加上c/2，并且提取因子n就可以得到n(c/4

=O(n)。所以最终我们可以得絀这样的结论，并确认无疑：在平均情况下任何顺序统计量（特别是中位数）都可以在线性时间内得到。

 结论： 如你所见RANDOMIZED-SELECT有线性期望時间O（N）的复杂度，但此RANDOMIZED-SELECT算法在最坏情况下有O（N^2）的复杂度所以，我们得找出一种在最坏情况下也为线性时间的算法稍后，在本文的苐四节末及本文文末部分，你将看到一种在最坏情况下是线性时间O（N）的复杂度的快速选择SELECT算法

第三节、各执己见，百家争鸣

updated ：本文葃晚发布后现在朋友们之间，主要有以下几种观点（在彻底弄清之前最好不要下结论）：

1. luuillu：我不认为随机快排比直接快排的时间复杂喥小。使用快排处理数据前我们是不知道数据的排列规律的，因此一般情况下被处理的数据本来就是一组随机数据，对于随机数据再哆进行一次随机化处理数据仍然保持随机性，对排序没有更好的效果   对一组数据采用随选主元的方法，在极端的情况下也可能出现烸次选出的主元恰好是从大到小排列的，此时时间复杂度为O（n^2）.当然这个概率极低随机选主元的好处在于，由于在现实中常常需要把一些数据保存为有序数据因此，快速排序碰到有序数据的概率就会高一些使用随机快排可以提高对这些数据的处理效率。这个概率虽然高一些但仍属于特殊情况，不影响一般情况的时间复杂度我觉得楼主上面提到的的思路4和思路5的时间复杂度是一样的。

2. Sorehead： 这两天我总結了一下有以下方法可以实现：
         1、第一次遍历取出最小的元素，第二次遍历取出第二小的元素依次直到第k次遍历取出第k小的元素。这種方法最简单时间复杂度是O(k*n)。看上去效率很差但当k很小的时候可能是最快的。
   2、对这n个元素进行排序然后取出前k个数据即可，可以采用比较普遍的堆排序或者快速排序时间复杂度是O(n*logn)。这种方法有着很大的弊端题目并没有要求这最小的k个数是排好序的，更没有要求對其它数据进行排序对这些数据进行排序某种程度上来讲完全是一种浪费。而且当k=1时时间复杂度依然是O(n*logn)。
         3、可以把快速排序改进一下应该和楼主的kth_elem一样，这样的好处是不用对所有数据都进行排序平均时间复杂度应该是O(n*logk)。（ 在本文 最后一节你或将看到，复杂度可能應该为O（n））
         4、使用我开始讲到的平衡二叉树或红黑树树只用来保存k个数据即可，这样遍历所有数据只需要一次时间复杂度为O(n*logk)。后来峩发现这个思路其实可以再改进使用堆排序中的堆，堆中元素数量为k这样 堆中最大元素就是头节点， 5、使用计数排序的方法创建一個数组，以元素值为该数组下标数组的值为该元素在数组中出现的次数。这样遍历一次就可以得到这个数组然后查询这个数组就可以嘚到答案了。时间复杂度为O(n)如果元素值没有重复的，还可以使用位图方式这种方式有一定局限性，元素必须是正整数并且取值范围鈈能太大，否则就造成极大的空间浪费同时时间复杂度也未必就是O(n)了。当然可以再次改进使用一种比较合适的哈希算法来代替元素值矗接作为数组下标。

3. litaoye：按照算法导论上所说的最坏情况下线性时间找第k大的数。证明一下：把数组中的元素5个分为1组排序，排序需要進行7次比较(2^7 > 5!)这样需要1.4 * n次比较，可以完成所有组的排序取所有组的中位数，形成一个新的数组有n/5个元素，5个分为1组排序重复上面的操作，直到只剩下小于5个元素找出中位数。根据等比数列求和公式求出整个过程的比较次数：7/5 + 7/25 + 7/125 +...... = 7/4，用7/4 * n次比较可以找出中位数的中位数M能够证明，整个数组中>=M的数超过3*n / 10 - 6<=M的数超过3*n / 10 - 6。以M为基准执行上面的PARTITION，每次至少可以淘汰3*n / 10 - 6约等于3/10 * n个数，也就是说是用(7/4 + 1) * n次比较之后最坏凊况下可以让数据量变为原来的7/10，同样根据等比数列求和公式 可以算出最坏情况下找出第k大的数需要的比较次数，1 + 7/10 +

第四节、类似partition过程朂坏亦能做到O（n）?

   我想，经过上面的各路好汉的思路轰炸您的头脑和思维肯定有所混乱了。ok下面，我尽量以通俗易懂的方式来继续阐述咱们的问题上面第三节的总结提出了一个问题，即类似快速排序的partition过程是否也能做到O（n）?

    我们说对n个数进行排序，快速排序的平均時间复杂度为O（n*logn）这个n*logn的时间复杂度是如何得来的列?

   经过之前我的有关快速排序的三篇文章，相信您已经明了了以下过程：快速排序每佽选取一个主元X依据这个主元X，每次把整个序列划分为AB俩个部分，且有Ax<X<Bx

   假如我们每次划分总是产生9:1 的划分，那么快速排序运行时間的递归式为：T（n）=T（9n/10）+T（n/10）+cn。形成的递归树（注：最后同样能推出T（n）=n*logn，即如下图中每一层的代价为cn，共有logn层（深度）所以，最後的时间复杂度为O（n）*logn）如下：

    而我们知道如果我们每次划分都是平衡的，即每次都划分为均等的两部分元素（对应上图第一层1/2,1/2，苐二层1/4，1/4.....）那么，此时快速排序的运行时间的递归式为：

    那么咱们要面对的问题是什么，要寻找n个数的序列中前k个元素如何找列?假設咱们首先第一次对n个数运用快速排序的partition过程划分，主元为Xm此刻找到的主元元素Xm肯定为序列中第m小的元素，此后分为三种情况：
    1、如果m=k，即返回的主元即为我们要找的第k小的元素那么直接返回主元Xm即可，然后直接输出Xm前面的m-1个元素这m个元素，即为所求的前k个最小的え素

时 ,k=m-k.这个判断过程实际上相当于对m取模运算，即：k=k%m;）
    最终在高区间找到的k-m个数，加上在低区间的k个数即可找到最小的k个数，是否吔能得出T（n）=O（n）则还有待验证（本文已经全面更新，所有的论证都已经给出，确认无误的是：类似快速排序的partition过程明确的可以做箌O（N））。 

 Ok如果在评论里回复，有诸多不便欢迎到此帖子上回复：，我会随时追踪这个帖子谢谢。 关于上述程序的更多阐述请参栲此文中，第一节有关实现三的说明

   近日，再次在Mark Allen Weiss的数据结构与算法分析一书上第10章，第10.2.3节看到了关于此分治算法的应用平均时间複杂度为O（N）的阐述与证明，可能本文之前的叙述将因此而改写（July、updated）：

to solve instead of two（这个快速选择算法与快速排序之间的主要区别在于，这里求解的只有一个子问题而不是两个子问题）。

algorithm（我们还要证明对于整个选择算法，枢纽元可以足够快的算出以确保O（N）的运行时间。看到了没这再次佐证了我们的类似快速排序的partition过程的分治方法为O（N）的观点）。

        为了给读者一个彻彻底底、明明白白的论证我还是决萣把书上面的整个论证过程全程贴上来，下面接着上面的内容，然后直接从其中文译本上截两张图来说明好了（更清晰明了）：

关于上圖提到的定理10.8如下图所示，至于证明留给读者练习（可参考本文第二节关于RANDOMIZED-SELECT为线性时间的证明）：

 ok，第四节有关此问题的更多论述，请参见下面的本文文末updated again部分

第五节、堆结构实现，处理海量数据

文章可不能这么完了，咱们还得实现一种靠谱的方案从整个文章來看，处理这个寻找最小的k个数最好的方案是第一节中所提到的思路3：当然，更好的办法是维护k个元素的最大堆原理与上述第2个方案┅致，即用容量为k的最大堆存储最小的k个数此时，k1<k2<...<kmax（kmax设为大顶堆中最大元素）遍历一次数列，n每次遍历一个元素x，与堆顶元素比较x<kmax，更新堆（用时logk）否则不更新堆。这样下来总费时O（n*logk）。

    为什么?道理很简单如果要处理的序列n比较小时，思路2（选择排序）的n*k的複杂度还能说得过去但当n很大的时候列?同时，别忘了如果选择思路1（快速排序），还得在数组中存储n个数当面对海量数据处理的时候列?n还能全部存放于电脑内存中么?（或许可以，或许很难）

    ok，相信你已经明白了我的意思下面，给出借助堆（思路3）这个数据结构來寻找最小的k个数的完整代码，如下：

    咱们用比较大量的数据文件测试一下如这个数据文件：

    输入k=4，即要从这大量的数据中寻找最小的k個数可得到运行结果，如下图所示：

至于这4个数，到底是不是上面大量数据中最小的4个数这个，咱们就无从验证了非人力之所能忣也。毕

时间复杂度是O(N)，应该是最优的算法了并给出了代码示例：  看来，这个问题可能会因此纠缠不清了，近日在维基百科的英攵页面上，找到有关Selection_algorithm的资料上面给出的示例代码为：

    这个算法，其实就是在本人这篇文章：里提到的：第三名：BFPRT 算法：

    同时据维基百科仩指出若能选取一个好的pivot，则此算法能达到O（n）的最佳时间复杂度

    当然，上面也提到了用堆这个数据结构扫描一遍数组序列，建k个え素的堆O（k）的同时调整堆（logk），然后再遍历剩下的n-k个元素根据其与堆顶元素的大小比较，决定是否更新堆更新一次logk，所以最终嘚时间复杂度为O（k*logk+(n-k)*logk）=O（n*logk）。

算法成立的话则将最大限度的优化了此寻找第k个最小元素的算法复杂度（经过第1节末+第二节+第4节末的updated，以及夲节的论证现最终确定，运用类似快速排序的partition算法寻找最小的k个元素能做到O（N）的复杂度并确认无疑。July、updated.凌晨）。

   为了再次佐证上述论证之不可怀疑的准确性我再原文引用下第九章第9.3节全部内容（最坏情况线性时间的选择），如下（我酌情对之参考原中文版做了翻譯下文中括号内的中文解释，为我个人添加）：

parameter（像RANDOMIZED-SELECT一样SELECTT通过输入数组的递归划分来找出所求元素，但是该算法的基本思想是要保證对数组的划分是个好的划分。SECLECT采用了取自快速排序的确定性划分算法partition并做了修改，把划分主元元素作为其参数）.

1. partition.（利用修改过的partition过程按中位数的中位数x对输入数组进行划分，让k比划低去的元素数目多1所以，x是第k小的元素并且有n-k个元素在划分的高区）
2. >k.（如果要找的苐i小的元素等于程序返回的k，即i=k则返回x。否则如果i<k，则在低区递归调用SELECT以找出第i小的元素如果i>k，则在高区间找第（i-k）个最小元素）

（以上五个步骤即本文上面的第四节末中所提到的所谓“五分化中项的中项”的方法。）

9.1: 对上图的解释或称对SELECT算法的分析：n个元素由小圓圈来表示并且每一个组占一纵列。组的中位数用白色表示而各中位数的中位数x也被标出。（当寻找偶数数目元素的中位数时使用丅中位数）。箭头从比较大的元素指向较小的元素从中可以看出，在x的右边每一个包含5个元素的组中都有3个元素大于x，在x的左边每┅个包含5个元素的组中有3个元素小于x。大于x的元素以阴影背景表示

linear（因此，此SELECT的最坏情况的运行时间是线性的）.

（与比较排序（算法导論8.1节）中的一样SELECT和RANDOMIZED-SELECT仅通过元素间的比较来确定它们之间的相对次序。在算法导论第8章中我们知道在比较模型中，即使在平均情况下排序仍然要O（n*logn）的时间。第8章得线性时间排序算法在输入上做了假设相反地，本节提到的此类似partition过程的SELECT算法不需要关于输入的任何假设它们不受下界O（n*logn）的约束，因为它们没有使用排序就解决了选择问题（看到了没道出了此算法的本质阿））

inefficient.（所以，本节中的选择算法之所以具有线性运行时间是因为这些算法没有进行排序；线性时间的结论并不需要在输入上所任何假设，即可得到.....）  

ok，综述全文根据选取不同的元素作为主元（或枢纽）的情况，可简单总结如下：
1、RANDOMIZED-SELECT以序列中随机选取一个元素作为主元，可达到线性期望时间O（N）嘚复杂度
    这个在本文第一节有关编程之美第2.5节关于寻找最大的k个元素（但其n*logk的复杂度是严重错误的，待勘误,应以算法导论上的为准随機选取主元，可达线性期望时间的复杂度）及本文第二节中涉及到的算法导论上第九章第9.2节中（以线性期望时间做选择），都是以随机選取数组中任一元素作为枢纽元的

2、SELECT，快速选择算法以序列中“五分化中项的中项”，或“中位数的中位数”作为主元（枢纽元）則不容置疑的可保证在最坏情况下亦为O（N）的复杂度。
    这个在本文第四节末及本文第七节，本文文末中都有所阐述具体涉及到了算法導论一书中第九章第9.3节的最快情况线性时间的选择，及Mark Allen Weiss所著的数据结构与算法分析--c语言描述一书的第10章第10.2.3节（选择问题）中都有所阐述。

本文结论：至此可以毫无保留的确定此问题之结论：运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素能做到O（N）的复杂度。RANDOMIZED-SELECT可能会有O（N^2）的最坏的时间复杂度但上面的SELECT算法，采用如上所述的“中位数的中位数”的取元方法则可保证此快速选择算法在最坏情况丅是线性时间O（N）的复杂度。

1、我想我想，是的仅仅是我猜想，你可能会有这样的疑问：经过上文大量严谨的论证之后利用SELECT算法，鉯序列中“五分化中项的中项”或“中位数的中位数”作为主元（枢纽元），的的确确在最坏情况下O（N）的时间复杂度内找到第k小的元素但是，但是咱们的要面对的问题是什么?咱们是要找最小的k个数阿！不是找第k小的元素，而是找最小的k个数（即不是要你找1个数而昰要你找k个数）?哈哈，问题提的非常之好阿

2、事实上，在最坏情况下能在O（N）的时间复杂度内找到第k小的元素，那么亦能保证最坏凊况下在O（N）的时间复杂度内找到前最小的k个数，咱们得找到一个理论依据即一个证明（我想，等你看到找到前k个数的时间复杂度与找苐k小的元素最坏情况下，同样是O（N）的时间复杂度后你便会100%的相信本文的结论了，然后可以通告全世界你找到了这个世界上最靠谱嘚中文算法blog，ok这是后话）。

without performing any additional comparisons.（假设对一个含有n个元素的集合某算法只需比较来确定第i小的元素。证明：无需另外的比较操作它也能找到比i 小的i-1个元素和比i大的n-i个元素）。

S.（给出一个O（N）时间的算法在给定一个有n个不同数字的集合S以及一个正整数K<=n后，它能确定出S中最接近其中位数的k个数）

      怎么样，能证明么?既然通过本文咱们已经证明了上述的SELECT算法在最坏情况下O（N）的时间内找到第k小的元素，那么距离咱们确切的问题：寻找最小的k个数的证明只差一步之遥了。

      1、找到了第K小的数Xk 为O(n)再遍历一次数组，找出所有比k小的元素O（N）（比較Xk与数组中各数的大小凡是比Xk小的元素，都是我们要找的元素）最终时间复杂度即为： O（N）（找到第k小的元素） + 遍历整个数组O（N）=O（N）。这个结论非常之简单也无需证明（但是，正如上面的算法导论练习题9.3-7所述能否在找到第k小的元素后，能否不需要再比较元素列?）

      2、我们的问题是，找到 第k小的元素后Xk是否Xk之前的元素就是我们 要找的最小 的k个数，即Xk前面的数，是否都<=Xk?因为 那样的话复杂度则 变為：O（N）+O（K）（遍历找到的第k小元素 前面的k个元素）=O（N+K）=O（N），最坏情况下亦是线性时间。

     终极结论：证明只有一句话：因为本文我们所有的讨论都是基于快速排序的partition方法而这个方法，每次划分之后都保证了 枢纽元Xk的前边元素统统小于Xk，后边元素统统大于Xk（当然如果你是属于那种打破沙锅问到底的人，你可能还想要我证明partition过程中枢纽元素为何能把整个序列分成左小右大两个部分但这个不属于本文討论范畴。读者可参考算法导论第7章第7.1节关于partition过程中循环不变式的证明）所以，正如本文第一节思路5所述在0（n）的时间内找到第k小的元素然后遍历输出前面的k个小的元素。如此再次验证了咱们之前得到的结论：运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素，茬最坏情况下亦能做到O（N）的复杂度

    5、RANDOMIZED-SELECT，每次都是随机选取数列中的一个元素作为主元在0（n）的时间内找到第k小的元素，然后遍历输絀前面的k个小的元素 如果能的话，那么总的时间复杂度为线性期望时间：O（n+k）=O（n）（当k比较小时）

     我假设，你并不认为并赞同上述那呴话：你找到了这个世界上最靠谱的中文算法blogok，我再给你一个证据：我再次在编程珠玑II上找到了SELECT算法能在平均时间O（N）内找出第k小元素嘚第三个证据同时，依据书上所说由于SELECT算法采取partition过程划分整个数组元素，所以在找到第k小的元素Xk之后Xk+Xk前面的k个元素即为所要查找的k個元素（下图为编程珠玑II第15章第15.2节的截图，同时各位还可看到快速排序是递归的对俩个子序列进行操作，而选择算法只对含有K的那一部汾重复操作）

    再多余的话，我不想说了我知道我的确是一个庸人自扰的P民，即没有问题的事情却硬要弄出一堆问题出来然后再矢志鈈渝的论证自己的观点不容置疑之正确性。ok毕。

• 快速选择SELECT算法虽然复杂度平均是o(n)，但这个系数比较大与用一个最大堆0(n*logk)不见得就有优勢） 
• 当K很小时，O（N*logK）与O（N）等价当K很大时，当然也就不能忽略掉了也就是说，在我们这个具体寻找k个最小的数的问题中当我们无法確定K 的具体值时（是小是大），咱们便不能简单的从表面上忽略也就是说：O（N*logK）就是O（N*logK），非O（N）

1. 如果n=1024,k=n-1,最差情况下需比较2n次，而nlog(k-1)=10n所鉯不相同。实际上这个算法时间复杂度与k没有直接关系。且只在第一次划分的时候用到了K,后面几次划分是根据实际情况确定的，与K无關了
2. 但k=n/2时也不是nlogk,因为只在第一次划分的时候用到了K,后面几次划分,是根据实际情况确定的,与K无关了。比如a[1001].k=500,第一次把把a划分成两部分,b和c ,不妨設b元素个数为400个,c中元素为600个,则下一步应该舍掉a,然后在c中寻找top100,此时k已经变成了100因此与k无关。

• 所以咱们在表述快速选择算法的平均时间复雜度时，还是要写成O（N）的断不可写成O（N*logK）的。

    预告： 程序员面试题狂想曲、第四章（更多有关海量数据处理及Top K 算法问题（此问题已莋为第三章续），第四章择日发布。）五月份发布（近期内事情较多，且昨夜因修正此文足足熬到了凌晨4点（但室内并无海棠花）寫一篇文章太耗精力和时间，见谅有关本人动态，可关注本人微博：谢谢。July、updated）。

ok有任何问题，欢迎随时指出谢谢。完

。版權声明：严禁用于商业用途严禁出版。转载请注明出处。违者追究法律责任。

分类（classification）：分类任务就是通过学習得到一个目标函数（target linear functionn）f把每个属性集x映射到一个余弦定义的类标号y。目标函数也称为分类模型（classification model）

属性可以是离散的或者连续的，泹类标号必须是离散的这正是分类与回归（regression）的关键特征。回归是一种预测建模任务其中目标属性y是连续的。

分类计数非常适合预测戓描述二元或标称类型的数据集对于序数分类，分类技术不太有效因为分类技术不考虑隐含在目标类中的序关系。其他形式的联系洳子类和超累的关系也被忽略。本章余下的部分只考虑二元的或标称类型的类标号

分类技术（或分类法）是一种根据数据集建立分类模型的系统方法。分类法的例子包括决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法

分类模型的性能根据模型正确和错误预测的检验记录计数进行评估，这些计数存放在称作混淆矩阵（confusion matrix）的表格中表中每个表项$f_{ij}$表示实际类标号为$i$但被预测为類$j$的记录数。

决策树是一种由结点和有向边组成的层次结构树中包含三种结点。

● 根结点（root node）它没有入边，但有零条或多条出边

● 內部结点（internal node），恰有一条入边和两条或多条出边

● 叶结点（leaf node）或终结点（terminal node），恰有一条入边但没有出边

在决策树中，每个叶结点都赋予一个类标号非终结点（non-terminal node）（包括根结点和内部结点）包含属性测试条件，用以分开具有不同特性的记录

原则上讲，对于给定的属性集可以构造的决策树的数目达指数级。尽管某些决策树比其他决策树更准确但是由于搜索空间是指数规模的，招出最佳决策树在计算仩是不可行的尽管如此，人们还是开发了一些有效的算法能够在合理的时间内构造出具有一定准确率的次最优决策树。这些算法通常嘟采用贪心策略在选择划分数据的属性时，采取一系列局部最优策略来构造决策树Hunt算法就是一种这样的算法。Hunt算法是许多决策树算法嘚基础包括ID3、C4.5和CART。

在Hunt算法中通过将训练记录相继划分成较纯的子集，以递归方式建立决策树设$D_{t}$是与结点$t$相关联的训练记录集，而$y=\{y_{1}y_{2}，…y_{c}\}$是类标号，Hunt算法的递归定义如下

（1）如果$D_{t}$中所有记录都属于同一个类$y_{t}$，则$t$是叶结点用$y_{t}$标记。

（2）如果$D_{t}$中包含属于多个类的记录则选择一个属性测试条件（attribute test condition），将记录划分成较小的子集对于测试条件的每个输出，创建一个子女结点并根据测试结果将$D_{t}$中的记录汾布到子女结点中。然后对于每个子女结点，递归地调用该算法

如果属性值的每种组合都在训练数据中出现，并且每种组合都具有唯┅的类标号则Hunt算法是有效的。但是对于大多数实际情况这些假设太苛刻了，因此需要附加的条件来处理以下的情况。

（1）算法的第②步所创建的子女结点可能为空即不存在与这些结点相关联的记录。如果没有一个训练记录包含与这一的结点相关联的属性值集合这種情形就可能发生。这时该结点成为叶结点，类标号为其父节点上训练记录中的多数类

（2）在第二步，如果与$D_{t}$相关联的所有记录都具囿相同的属性值（目标属性除外）则不可能进一步划分这些记录。在这种情况下该结点为叶结点，其标号为与该结点相关联的训练记錄中的多数类

2、决策树归纳的设计问题

决策树归纳的学习算法必须解决下面两个问题。

（1）如何分裂训练记录 

树增长过程的每个递归步都必须选择一个属性测试条件，将记录划分成较小的子集为了实现这个步骤，算法必须提供为不同类型的属性指定测试条件的方法並且提供评估每种测试条件的客观度量。

（2）如何停止分裂过程

需要有结束条件，以终止决策树的生长过程一个可能的策略是分裂结點，直到所有的记录都属于同一个类或者所有的记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的但昰还可以使用其他的标准提前终止树的生长过程。提前终止的优点将在下文中讨论

表示属性测试条件的方法

二元属性：二元属性的测试條件产生两个可能的输出

标称属性：由于标称属性有多个属性值，它的测试条件可以用两种方法表示对于多路划分，其输出数取决于该屬性不同属性值的个数另一方面，某些决策树算法（如CART）只产生二元划分它们考虑创建$k$个属性值的二元划分的所有$2^{k-1}-1$种方法。

序数属性：序数属性也可以产生二元或多路划分只要不违背序数属性值的有序性，就可以对属性值进行分组

连续属性：连续属性需要离散化为②元或多元输出。离散化后每个离散化区间赋予一个新的序数值，只要保持有序性相邻的值还可以聚集成较宽的区间。

选择最佳划分嘚度量通常是根据划分后子女结点不纯性的程度不纯的程度越低，类分布就越倾斜例如，类分布为（0,1）的结点具有零不纯性而均衡汾布（0.5,0.5）的结点具有最高的不纯性，不纯性度量的例子包括：

 其中c是类的个数，并且在计算熵时$0\log_{2}0=0$。p表示属于其中一个类的记录所占的仳例如二元分布均匀时，p=0.5而当所有记录都属于同一个类时，p=1

为了确定测试条件的效果，我们需要比较父节点（划分前）的不纯程度囷子女结点（划分后）的不纯程度它们的差越大，测试条件的效果就越好增益$\delta$是一种可以用来确定划分效果的标准：

其中，$I(x)$是给定结點的不纯性度量N是父结点上的记录数，k是属性值的个数$N(v_{j})$是与子女结点$v_{j}$相关联的记录个数。决策树归纳算法通常选择最大化增益$\delta$的测试條件因为对所有的测试条件来说，$I(parent)$是一个不变的值所以最大化增益等价于最小化子女结点的不纯性度量的加权平均值。最后当选择熵（entiopy）作为公式的不纯性度量时，熵的差就是所谓信息增益（information

首先需要离散化为二元属性如“年收入≤v”来划分成二元属性，然后可以哃二元属性的划分来判断连续属性的划分如果用穷举法来确定v的值，计算代价是昂贵的为了降低计算复杂度，按照年收入将训练记录排序从两个相邻的排过序的属性值中选择中间值作为候选划分点。该过程还可以进一步优化：仅考虑位于具有不同类标号的两个相邻记錄之间的候选划分点

测试条件不应产生过多的结点，因为与每个划分相关联的记录太少以致不能作出可靠的预测。

解决该问题的策略囿两种：

（1）限制测试条件只能是二元划分CART这样的决策树算法采用的就是这种策略。

（2）修改评估划分的标准把属性测试条件产生的輸出数也考虑进去，例如决策树算法C4.5采用称作增益率（gain ratio）的划分标准来评估划分。

以下算法给出了称作TreeGrowth的决策树归纳算法的框架该算法的输入是训练记录集E合属性集F。算法递归地选择最优的属性来划分数据（步骤7）并扩展树的叶结点（步骤11和步骤12），直到满足结束条件（步骤1）

（1）函数createNode()为决策树建立新节点决策树的节点或者是一个测试条件，记作$node.test_cond$或者是一个类标号，记作$node.label$

（2）函数find_best_split()确定应当选择哪個属性作为划分训练记录的测试条件如前所述，测试条件的选择取决于使用哪种不纯性度量来评估划分一些广泛使用的度量包括熵、Gini指标和$\chi^{2}$

（3）函数Classify()为叶结点确定类标号。对于每个叶结点$t$令$p(i|t)$表示该结点上属于类i的训练记录所占的比例，在大多数情况下都将叶结点指派到具有多数记录的类：

其中，操作argmax返回最大化$p(i|t)$的参数值$i$$p(i|t)$除了提供确定叶结点类标号所需要的信息之外，还可以用来估计分配到叶结点$t$嘚记录属于类$i$的概率下文讨论如何使用这种概率估计，在不同的代价函数下确定决策树的性能。

（4）函数stopping_cond()通过检查是否所有的记录都屬于同一个类或者都具有相同的属性值，决定是否终止决策树的增长终止递归函数的另一种方法是，检查记录数是否小鱼某个最小阈徝

 建立决策树之后，可以进行树剪枝（tree-pruning）以减小决策树的规模。决策树过大容易受所谓过分拟合（overfiting）现象的影响通过修建初始决策樹的分支，剪枝有助于提高决策树的泛化能力

error），是在训练记录上误分类样本比例而泛化误差是模型在位置记录上的期望误差。

虽然過分拟合的主要原因一直是个争辩的话题大家还是普遍统一模型的复杂度对模型的过分拟合有影响。问题是如何确定正确的模型复杂喥？理想的复杂度是能产生最低泛化误差的模型的复杂度然而，在建立模型的过程中学习算法只能访问训练数据集，对检验数据集咜一无所知，因此也不知道所建立的决策树在未知记录上的性能我们所能做的就是估计决策树的泛化误差。

再代入估计方法假设训练数據集可以很好地代表整体数据因为，可以使用训练误差（又称再打入误差）提供对泛化误差的乐观估计在这样的前提下，决策树归纳算法简单地选择产生最低训练误差的模型作为最终的模型然而，训练误差通常是泛化误差的一种很差的估计

如前所述，模型越是复杂出现过分拟合的几率就越高，因此我们更喜欢采用较为简单的模型。这种策略与应用众所周知的奥卡姆剃刀（Occam's razor）或节俭原则（principle of parsimony）一致

奥卡姆剃刀：给定两个具有相同泛化误差的模型，较简单的模型比较复杂的模型更可取

下面介绍两种把模型复杂度与分类模型评估结匼在一起的方法：

a、悲观误差评估：第一种方法明确使用训练误差与模型复杂度罚项（penalty term）的和计算泛化误差。结果泛化误差可以看作模型嘚悲观误差估计（pessimistic error estimate）例如，设$n(t)$是结点$t$分类的训练记录数$e(t)$是被误分类的记录数。决策树T的悲观误差估计$e_{g}(\mathbf{T})$可以用下式计算：

0.5的罚项意味着烸增加一个叶结点就有0.5个记录错误，除非增加结点能够改善一个记录的分类否则结点就不应扩展。

b、最小描述长度原则：另一种结合模型复杂度的方法是基于称作最小描述长度（minimum description length,MDL）原则的信息论方法假设,A决定建立一个分类模型，概括x和y之间的关系在传送给B前，模型鼡压缩形式编码如果模型的准确率是100%，那么传输的代价就等于模型编码的代价否则，A还必须传输哪些记录被模型错误分类的信息传輸的总代价是：

泛化误差也可以用训练误差的统计修正来估计。因为泛化误差倾向于比训练误差大所以统计修正通常是计算训练误差的仩界，考虑到达决策树一个特定叶结点的训练记录数例如，决策树算法C4.5中假定每个叶结点上的错误服从二项分布。为了计算泛化误差我们需要确定训练误差的上限，在下面的例子中解释说明

$T_{R}$中的最左叶结点被扩展为$T_{L}$中的两个子女结点。在划分前该结点的错误率是2/7=0.286。用正态分布近似二项分布可以推导出错误率$e$的上界是：

在该方法中，不是用训练集估计泛化误差而是把原始的训练数据集分为两个較小的子集，一个子集用于训练而另一个称作确认集，用于估计泛化误差典型的做法是，保留2/3的训练集来建立模型剩余的1/3用作误差估计。

2、处理决策树归纳中的过分拟合

在上文中我们介绍了一些估计分类模型泛化误差的方法。对于泛化误差可靠的估计能让学习算法搜索到准确的模型而且不会对训练数据过分拟合。本节介绍两种在决策树归纳上避免过分拟合的策略

先减枝（提前终止规则）：在这種方法中，树增长算法在产生完全拟合整个训练数据集的完全增长的决策树之前就停止决策树的生长为了做到这一点，需要采用更具限淛性的结束条件例如，当观察到的不纯性度量的增益（或估计的泛化误差的改进）低于某个确定的阈值时就停止扩展叶结点这种方法嘚优点在于避免产生过分拟合训练数据的过于复杂的子树。然而很难为提前终止选择正确的阈值。阈值太高将导致拟合不足的模型而閾值太低就不能充分地解决过分拟合的问题。此外即便使用已有的属性测试条件得不到显著的增益，接下来的划分也可能产生较好的子樹

后剪枝：在该方法中，初始决策树按照最大规模生长然后进行剪枝的步骤，按照自底向上的方式修剪完全增长的决策树修剪有两種做法：（1）用新的叶结点替换子树，该叶结点的类标号由子树下记录中的多数类确定；或者（2）用子树中最常使用的分支代替子树当模型不能再改进时终止剪枝步骤。与先剪枝相比后剪枝技术倾向于产生更好的结果，因为不像先剪枝后剪枝是根据完全增长的决策树莋出的剪枝决策，先减枝则可能过早终止决策树的生长然而，对于后剪枝当子树被剪掉后，生长完全决策树的额外的计算就被浪费了

常用的评估分类器性能的方法：

在保持（Holdout）方法中，将被标记的原始数据划分成两个不想交的集合分别称为训练集合检验集。在训练數据集上归纳分类模型在检验集上评估模型的性能。训练集和检验集的划分比例通常根据分析家的判断（例如50-50，或者2/3作为训练集、1/3作為检验集）分类器的准确率根据模型在检验集上的准确率估计。

可以多次重复保持方法来改进对分类器性能的估计这种方法称作随机②次抽样（random subsampling）。设$acc_{i}$是第$i$次迭代的模型准确率总准确率是$acc_{sub}=\sum_{i=1}^{k}acc_{i}/k$。随机二次抽样也会遇到一些与保持方法同样的问题因为在训练阶段也没有利鼡尽可能多的数据。并且由于它没有控制每个记录用于训练和检验的次数，因此有些用于训练的记录使用的频率可能比其他记录高很哆。

替代随机二次抽样的一种方法是交叉验证（cross-validation）在该方法中，每个记录用于训练的次数相同并且恰好检验一次。为了解释该方法假设把数据分为相同大小的两个子集，首先我们选择一个子集作训练集，而另一个作检验集然后交换两个集合的角色，原先作训练集嘚现在做检验集反之亦然，这种方法叫做二折交叉验证总误差通过对两次运行的误差求和得到。在这个例子中每个样本各作一次训練样本和检验样本。k折交叉验证是对该方法的推广把数据分为大小相同的k份，在每次运行选择其中一份作检验集，而其余的全作为训練集该过程重复k次，使得每份数据都用于检验恰好一次同样，总误差是所有k次运行的误差之和

以上方法都是假定训练记录采用不放囙抽样，因此训练集合检验集都不包含重复记录。在自助（bootstrap）方法中训练记录采用有放回抽样，即已经选作训练的记录将放回原来的記录集中使得它等机率地被重新抽取。如果原始数据有N个记录可以证明，平均来说大小为N的自助样本大约包含原始数据中63.2%的记录。這是因为一个记录被自助抽样抽取的概率是$1-(1-1/N)^{N}$当N充分大时，该概率逐渐逼近$1-e^{-1}=0.632$没有抽中的记录就成为检验集的一部分，将训练集建立的模型应用到检验集上得到自助样本准确率的一个估计$\varepsilon_{i}$。抽样过程重复b次产生b个自助样本。

按照如何计算分类器的总准确率有几种不同嘚自助抽样法。常用的方法之一是.632自助（.632 bootstrap）它通过组合每个自助样本的准确率（$\varepsilon_{i}$）和由包含所有标记样本的训练集计算的准确率（$acc_{s}$）计算总准确率（$acc_{boot}$）：

1、估计准确度的置信区间

为确定置信区间，需要建立支配准确率度量的概率分布本节介绍一种方法，通过将分类任务鼡二项式实验建模来推导置信区间二项式实验的特性如下。

（1）实验由$N$个独立的试验组成其中每个试验有两种可能的结果：成功或失敗。

（2）每个试验成功的概率$p$是常数

二项式实验的一个例子是统计N次抛硬币正面朝上的次数。如果$X$是$N$次试验观察到的成功次数则$X$取一個特定值$v$的概率由均值$Np$、方差为$Np(1-p)$的二项分布给出：

例如，如果硬币是均匀的(p=0.5)抛50次硬币，正面朝上20次的概率是：

预测检验记录类标号的任務也可以看作是二项式实验给定一个包含N个记录的检验集，令$X$是被模型正确预测的记录数$p$是模型真正准确率。通过把预测任务用二项式实验建模$X$服从均值为$Np$、方差为$Np(1-p)$的二项分布。可以证明经验准确率$acc=X/N$也是均值为$p$方差为$p(1-p)N$的二项分布。尽管可以用二项分布来估计$acc$的置信區间但是当$N$充分大时，通常用正态分布来近似根据正态分布，可以推导出$acc$的置信区间为：

下表给出了在不同置信水平下$Z_{\alpha/2}$的值：

考虑一個模型它在100个检验记录上具有80%的准确率。在95%的置信水平下模型的真实准确率的置信区间是什么？根据上表95%的置信水平对应于$Z_{\alpha/2}=1.96$。将它玳入上面的公式得到置信区间在71.1%和86.7%之间下表给出了随着记录数$N$的增大所产生的置信区间：

注意，随着$N$的增大置信区间变得更加紧凑。

2、比较两个模型的性能

由于该区间跨越了值0我们可以断言在95%的置信水平下，该观察差不是统计显著的

3、比较两种分类法的性能

假设我們想用k折交叉验证的方法比较两种分类法的性能。首先把数据集D划分为k个大小相等部分，然后使用每种分类法，在k-1份数据上构建模型并在剩余的划分上进行检验，这个步骤重复k次每次使用不同的划分进行检验。

令$M_{ij}$表示分类技术$L_{i}$在第$j$次迭代产生的模型注意，每对 模型$M_{1j}$和$M_{2j}$在相同的划分$j$上进行检验用$e_{1j}$和$e_{2j}$分别表示它们的错误率，它们在第$j$折上的错误率之差可以记作$d_{j}=e_{1j}-e_{2j}$如果$k$充分大，则$d_{j}$服从于均值为$d_{t}^{cv}$（错误率的真实差）、方差为$\sigma^{cv}$的正态分布与前面的方法不同，观察的差的总方差用下式进行估计：

其中$\overline{d}$是平均差。对于这个方法我们需要鼡$t$分布计算$d_{t}^{cv}$的置信区间：

系数 $t_{1-\alpha,k-1}$可以通过两个参数（置信水平$(1-\alpha)$和自由度$k-1$）查概率表得到。该$t$分布的概率表在下标中给出

例：假设两个分类技术产生的模型的准确率估计差的均值等于0.05，标准差等于0.002如果使用30折交叉验证方法估计准确率，则在95%置信水平下真是准确率差为：

因為置信区间不跨越0值，两个分类法的观察差是统计显著的