CS 科普:计算机如何做分类

October 3, 2008 – 12:07 pm

本来是发在校内的 cc98 论坛上为 MSTC 的 staff 们科普用的,顺便转到这里来一下。

分类是一项非常基本的任务,例如,拿到一包奶粉,要判断它是不是三鹿牌的,“是”与“不是”,这是一个二元分类的问题。在杀毒的时候判断一个文件是否是病毒,也是一个二元分类问题。再比如,在玩杀人游戏的时候,对每一个人,你要判断出他是“平民”、“警察”或者是“杀手”,这是一个分做三类的问题,类别多余二的情况都可以通过组合多个二元分类来完成,比如,一种组合方式可以是:首先使用“是否是平民”进行分类,如果是,则分类完成,否则,再“是否是警察” 进行分类,如果是则分类完成,否则归为“杀手”类。所以通常二元分类是需要解决的最基本的问题。

然而相对于做大量重复、复杂的计算来讲,做分类并不是电脑所擅长的事情——在反思过我们人类如何来做这样的事情之后大概会明白为什么了。那么试想这样的场景:现在假设有一包奶粉……恩,还是换个例子吧,一包方便面,让你判断它是不是康师傅的方便面。你会如何做判断呢?

在看到这包方便面之前,你只能胡猜了,因为你没有得到任何关于这包面的可以有助于你判断的信息。但是其实也并不是胡猜,而是根据你事先已经知道的一些知识来进行猜测,如果说要你猜测这包面是康师傅的概率的话,这个可以叫做“先验概率”。比如,我如果让你猜测这包面试不是“kid 牌”的,你八成会猜不是,因为根据你事先已经知道的知识,自己并没有听说过有“kid 牌”方便面,所以这包方便面是“kid 牌”的(先验)概率非常小。因此,这是人相对于计算机的最大的优势:有非常庞大并且组织良好易于检索的记忆系统,存储了非常非常多的知识作为后备。

那么接下来,你看到了这包方便面,似乎就不用做猜测了,可以肯定地告诉我这是不是康师傅的方便面。其实还是在做猜测,只是这次得到了更多关于要分类的这个物品的信息,让你对于它的分类问题更加有信心了。对于观察到对象的相关“特征”之后再得到的概率,我们称之为“后验概率”。比如,你看到常见的包装的颜色、花样以及差不多的 Logo ,于是断定这是康师傅方便面,却没有注意到这其实是一个叫做“康帅博”的牌子的方便面。

ksb.jpg

所以,人在做这样的分类的时候,也是通过观察一些“特征”来进行“猜测”的。对于电脑来说,它也可以采用和人类是的方法来进行“猜测”。令 P(t) 是这包方便面“是康师傅方便面”的概率,取一个阈值 P0 (比如,0.5),计算机在设法估计出 P(t) 之后,再和 P0 进行比较,如果大于 P0 ,则认为“是”,否则“不是”。这里的难点在于“估算 P”,如果当作一个先验概率而不考虑当前“输入”的话,基本上又回到了“胡猜”的场景。所以将其看作后验概率是更常见的做法:P(t|x) 是条件概率,表示“当观察到 x 已经发生的时候,t 发生的概率”,用到这里就是“当观察到这包方便面的各种特征的时候,这包方便面是康师傅方便面的概率”。其中,x 是一个向量,向量的每个分量表示一个特定的特征,例如:

x = (有没有出现“康师傅”的字样, 包装是不是红色的, 有没有“统一”的商标, ...)

当观察到特征取如下值

x = (有“康师傅”的字样, 包装是红色的, 没有“统一”的商标, ...)

的时候是康师傅方便面的概率比较大。当然,计算机需要更加形式化的方法:有一个叫做贝叶斯定理的公式:

bayes.jpg

其中 P(t|x) 是要估算的概率,而等式右边分母上的 P(x) 是特征出现的概率,比如,如果我们知道市面上的方便面包装的颜色只有红色和黄色两种,并且两种数量差不多,那么“包装是红色”这个特征出现的概率就可以认为是 0.5 。这些通常都作为参数通过人自己先验的“知识”显式地告知给计算机。而分子上的两项:P(t) 是我们最开始在没有观察到任何特征的情况下得到的那个“胡猜”的先验概率;而 P(x|t) 则表示假如这包方便面已知是康师傅方便面了,在这样的情况下它出现这些特征的概率(比如,康师傅方便面的包装是红颜色的概率)。

因此,通过贝叶斯定理,可以把问题从求 P(t|x) 转化为了求 P(x|t) 。许多分类算法都是通过直接求 P(t|x) 或者先求 P(x|t) 再得到 P(t|x) 的办法来做的。然而,人之所以能根据特征进行判断,是因为人有一个知识系统,可以帮助判断。计算机要做同样的事,就必须也要建立一个系统——或者称之为模型,这个模型要经过“训练”——或者称之为“学习”之后才能用来做分类。所谓学习的过程,就是给它一包一包的方便面,然后告诉它,这是康师傅、这不是康师傅……在“阅方便面无数”之后,模型逐渐完整起来,就可以用来进行分类了。

而学习的过程——亦即训练模型的过程,通常因为各种算法的模型各异而各不相同。在这里介绍一种叫做“朴素贝叶斯”的算法。根据上面的贝叶斯定理,其中的 x 是一个各种特征组成的向量,“朴素贝叶斯”的“朴素”在于假定各个特征之间是相互无关的,比如说,“方便面的包装是否红色”和“方便面是否标有康师傅标志 ”这两个特征之间不会相互影响。虽然事实上许多特征之间或多或少都会相互关联,但是从朴素贝叶斯算法的实际应用来看,效果还是相当不错的。

在各个特征相互独立的情况下,根据概率论里的乘法原理:

naive_bayes.jpg

这样只要求出 P(xi|t) ,就能得到 P(t|x) 。而 P(xi|t) 则可以很方便地通过学习得到一个估计值。比如,假设学习的时候给定了 1000 包方便面,其中 800 包是康师傅方便面,而 800 包康师傅方便面中有 600 包的包装是红色的,因此“包装是红色的”这个特征在“康师傅方便面”的条件下发生的概率可以被估计为 600/800 = 0.75 。类似的办法可以在学习的过程中求得特征向量 x 的所有分量的条件概率估计值,这样就完成了一个可用的朴素贝叶斯分类器的模型。

其中一个重要的步骤就是使用从训练数据中的统计结果(0.75)来近似真是概率,然而这个近似是否足够好,很大程度上取决于学习用的训练数据是否能如实反映出真实世界了。亦即是说,分类器的好坏不仅取决于算法和模型的好坏,训练数据的好坏通常也是至关重要的,就算厉害如欧阳峰,给他一本乱写的九阴真经,他也最终走火入魔了。

到此打住吧,再往下就不是科普了,不知道是否说清楚了。

最后,由于今天听了不少钢琴曲,所以涂一幅钢琴的吧,顺便在贴一下 7 月份刚搬到玉泉时画的一幅笛子的图:

piano.jpg

flute.jpg

恩,其实不太了解钢琴的结构,第一幅图似乎画错了,钢琴后面的盖子都忘记画了 :p

  1. 8 Responses to “CS 科普:计算机如何做分类”

  2. 其实比较严重的是黑白键的布局, 哈哈

    By galilette on Oct 3, 2008

  3. @galilette,
    额…… *^_^*//

    By pluskid on Oct 3, 2008

  4. kidGG画mm一绝啊。。。。

    By Mike on Oct 3, 2008

  5. btw, naive bayes其实在诸多分类算法里是效果最差的,它的优点主要就在简单易于理解,有新的数据模型易于更新(incremental).不像svm,尽管效果一般非常好,但是个黑箱(may give great answers, but you will never really know why).

    btw,最近你写的东西怎么和我和sishen,chenk85在做的项目越来越像了:)

    By yawl on Oct 3, 2008

  6. @yawl,
    呵呵!我也是刚刚接触 Pattern Classifier/Recognition 这方面的东西,还没有看过 SVM ,所以情况就不知道了。 :p
    呵呵,不知道你们做的什么项目呢?如有雷同,纯属巧合。计算机科学虽然大,但是还是有很多东西是一脉相承的,哈哈! :D

    By pluskid on Oct 4, 2008

  7. 一开始看到康师傅的图片还以为你想科普泡面哦,后来发现是科普Naive Bayes classifier。

    By maninred on Oct 4, 2008

  8. 不错,通俗易懂,好文啊~

    By bones7456 on Oct 6, 2008

  9. 科普贝叶斯

    By chris on Oct 6, 2008

Post a Comment