最近在面试中，除了基础& 算法& 项目之外，经常被问到或被要求介绍和描述下自己所知道的几种分类或聚类算法，而我向来恨对一个东西只知其皮毛而不得深入，故写一个有关聚类& 分类算法的系列文章以作为自己备试之用(尽管貌似已无多大必要，但还是觉得应该写下以备将来常常回顾思考)。
行文杂乱，但侥幸若能对读者也起到一定帮助，则幸甚至哉。
本分类& 聚类算法系列借鉴和参考了两本书，一本是Tom M.Mitchhell所著的机器学习，一本是数据挖掘导论，这两本书皆分别是机器学习& 数据挖掘领域的开山or杠鼎之作，读者有继续深入下去的兴趣的话，不妨在阅读本文之后，课后细细研读这两本书。
除此之外，还参考了网上不少牛人的作品(文末已注明参考文献或链接)，在此，皆一一表示感谢。
本分类& 聚类算法系列暂称之为Top 10 Algorithms in Data Mining，其中，各篇分别有以下具体内容：
1. 开篇：决策树学习Decision Tree，与贝叶斯分类算法(含隐马可夫模型HMM)；
2. 第二篇：支持向量机SVM(support vector machine)，与神经网络ANN；
3. 第三篇：待定...
说白了，一年多以前，我在本blog内写过一篇文章，叫做：数据挖掘领域十大经典算法初探(题外话：最初有个出版社的朋友便是因此文找到的我，尽管现在看来，我离出书日期仍是遥遥无期)。
现在，我抽取其中几个最值得一写的几个算法每一个都写一遍，以期对其有个大致通透的了解。
OK，全系列任何一篇文章若有任何错误，漏洞，或不妥之处，还请读者们一定要随时不吝赐教& 指正，谢谢各位。
基础储备：分类与聚类
在讲具体的分类和聚类算法之前，有必要讲一下什么是分类，什么是聚类，都包含哪些具体算法或问题。
常见的分类与聚类算法
简单来说，自然语言处理中，我们经常提到的文本分类便就是一个分类问题，一般的模式分类方法都可用于文本分类研究。
常用的分类算法包括：朴素的贝叶斯分类算法(native Bayesian classifier)、基于支持向量机(SVM)的分类器，k-最近邻法(k-nearest neighbor，
kNN)，神经网络法，决策树分类法，模糊分类法等等(本篇稍后会讲决策树分类与贝叶斯分类算法，当然，所有这些分类算法日后在本blog内都会一一陆续阐述)。
而K均值聚类则是最典型的聚类算法。
监督学习与无监督学习
一般来说，机器学习方法分为监督学习方法，和无监督学习方法。
举个具体的对应例子，则是比如说，在词义消岐中，也分为监督的消岐方法，和无监督的消岐方法。
在有监督的消岐方法中，训练数据是已知的，即没歌词的语义分类是被标注了的；而在无监督的消岐方法中，训练数据是未经标注的。
有监督的学习也通常称为分类任务，而无监督的学习通常称为聚类任务。
也就是说，分类属于监督学习，聚类属于无监督学习。
第一部分、决策树学习
1.1、什么是决策树
咱们直接切入正题。
所谓决策树，顾名思义，是一种树，一种依托于策略抉择而建立起来的树。
机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。
树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。
决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。
从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树。
来理论的太过抽象，下面举两个浅显易懂的例子：
第一个例子
套用俗语，决策树分类的思想类似于找对象。
现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的分类树决策。
相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。
假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑：
也就是说，决策树的简单策略就是，好比公司招聘面试过程中筛选一个人的简历，如果你的条件相当好比如说某985/211重点大学博士毕业，那么二话不说，直接叫过来面试，如果非重点大学毕业，但实际项目经验丰富，那么也要考虑叫过来面试一下，即所谓具体情况具体分析、决策。
第二个例子
此例子来自Tom M.Mitchell著的机器学习一书：
小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，他了解到人们决定是否打球的原因最主要取决于天气情况。
而天气状况有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。
如此，我们便可以构造一棵决策树，如下（根据天气这个分类决策这天是否合适打网球）：
上述决策树对应于以下表达式：
（Outlook=Sunny ^Humidity<=70）V （Outlook = Overcast）V （Outlook=Rain ^
Wind=Weak）
1.2、ID3算法
1.2.1、决策树学习之ID3算法
ID3算法是决策树算法的一种。
想了解什么是ID3算法之前，我们得先明白一个概念：奥卡姆剃刀。
奥卡姆剃刀（Occam's Razor, Ockham's Razor），又称―奥坎的剃刀‖，是由14世纪逻辑学家、圣方济各会修士奥卡姆的威廉（William of Occam，约1285年至1349年）提出，他在《箴言书注》2卷15题说―切勿浪费较多东西，去做‗用较少的东西，同样可以做好的事情‘。
简单点说，便是：be simple。
ID3算法（Iterative Dichotomiser 3 迭代二叉树3代）是一个由Ross Quinlan发明的用于决策树的算法。
这个算法便是建立在上述所介绍的奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。
尽管如此，该算法也不是总是生成最小的树形结构，而是一个启发式算法。
OK，从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。
ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益(很快，由下文你就会知道信息增益又是怎么一回事)最大的属性进行分裂。
该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。
所以，ID3的思想便是：
1. 自顶向下的贪婪搜索遍历可能的决策树空间构造决策树(此方法是ID3算法和C4.5
算法的基础)；
2. 从―哪一个属性将在树的根节点被测试‖开始；
3. 使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属
性作为树的根结点测试。
4. 然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也
就是说，样例的该属性值对应的分支）之下。
5. 重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。
这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。
下图所示即是用于学习布尔函数的ID3算法概要：
1.2.2、哪个属性是最佳的分类属性
1、信息增益的度量标准：熵
上文中，我们提到：―ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益(很快，由下文你就会知道信息增益又是怎么一回事)最大的属性进行分裂。
‖接下来，咱们就来看看这个信息增益是个什么概念(当然，在了解信息增益之前，你必须先理解：信息增益的度量标准：熵)。
上述的ID3算法的核心问题是选取在树的每个结点要测试的属性。
我们希望选择的是最有利于分类实例的属性，信息增益(Information Gain)是用来衡量给定的属性区分训练样例的能力，而ID3算法在增长树的每一步使用信息增益从候选属性中选择属性。
为了精确地定义信息增益，我们先定义信息论中广泛使用的一个度量标准，称为熵（entropy），它刻画了任意样例集的纯度（purity）。
给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：
上述公式中，p+代表正样例，比如在本文开头第二个例子中p+则意味着去打羽毛球，而p-则代表反样例，不去打球(在有关熵的所有计算中我们定义0log0为0)。
如果写代码实现熵的计算，则如下所示：
1.//根据具体属性和值来计算熵
2.double ComputeEntropy(vector <vector <string> > remain_state, string attribute, str
ing value,bool ifparent){
3. vector<int> count (2,0);
4. unsigned int i,j;
5.bool done_flag = false;//哨兵值
6.for(j = 1; j < MAXLEN; j++){
7.if(done_flag) break;
8.if(!attribute_row[j].compare(attribute)){
9.for(i = 1; i < remain_state.size(); i++){
10.if((!ifparent&&!remain_state[i][j].compare(value)) || ifparent){//i
fparent记录是否算父节点
11.if(!remain_state[i][MAXLEN - 1].compare(yes)){
12. count[0]++;
13. }
14.else count[1]++;
15. }
16. }
17. done_flag = true;
18. }
19. }
20.if(count[0] == 0 || count[1] == 0 ) return 0;//全部是正实例或者负实例
21.//具体计算熵根据[+count[0],-count[1]],log2为底通过换底公式换成自然数底数
22.double sum = count[0] + count[1];
23.double entropy = -count[0]/sum*log(count[0]/sum)/log(2.0) - count[1]/sum*log(co
unt[1]/sum)/log(2.0);
24.return entropy;
25.}
举例来说，假设S是一个关于布尔概念的有14个样例的集合，它包括9个正例和5个反例（我们采用记号[9+，5-]来概括这样的数据样例），那么S相对于这个布尔样例的熵为：
Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。
So，根据上述这个公式，我们可以得到：S的所有成员属于同一类，Entropy(S)=0； S 的正反样例数量相等，Entropy(S)=1；S的正反样例数量不等，熵介于0，1之间，如下图所示：
信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数。
更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为：
Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。
2、信息增益度量期望的熵降低
信息增益Gain(S,A)定义
已经有了熵作为衡量训练样例集合纯度的标准，现在可以定义属性分类训练数据的效力的度量标准。
这个标准被称为―信息增益（information gain）”。
简单的说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低(或者说，样本按照某属性划分时造成熵减少的期望)。
更精确地讲，一个属性A相对样例集合S的信息增益Gain(S,A)被定义为：
其中 Values(A)是属性A所有可能值的集合，是S中属性A的值为v的子集。
换句话来讲，Gain(S,A)是由于给定属性A的值而得到的关于目标函数值的信息。
当对S的一个任意成员的目标值编码时，Gain(S,A)的值是在知道属性A的值后可以节省的二进制位数。
接下来，有必要提醒读者一下：关于下面这两个概念 or公式，
1.
2.
第一个Entropy(S)是熵定义，第二个则是信息增益Gain(S,A)的定义，而Gain(S,A)由第一个Entropy(S)计算出，记住了。
下面，举个例子，假定S是一套有关天气的训练样例，描述它的属性包括可能是具有Weak和Strong两个值的Wind。
像前面一样，假定S包含14个样例，[9+，5-]。
在这14
个样例中，假定正例中的6个和反例中的2个有Wind =Weak，其他的有Wind=Strong。
由于按照属性Wind分类14个样例得到的信息增益可以计算如下。
运用在本文开头举得第二个根据天气情况是否决定打羽毛球的例子上，得到的最佳分类属性如下图所示：
在上图中，计算了两个不同属性：湿度(humidity)和风力(wind)的信息增益，最终humidity 这种分类的信息增益0.151>wind增益的0.048。
说白了，就是在星期六上午是否适合打网球的问题诀策中，采取humidity较wind作为分类属性更佳，决策树由此而来。
1.//计算信息增益，DFS构建决策树
2.//current_node为当前的节点
3.//remain_state为剩余待分类的样例
4.//remian_attribute为剩余还没有考虑的属性
5.//返回根结点指针
6.Node * BulidDecisionTreeDFS(Node * p, vector <vector <string> > remain_state, vecto
r <string> remain_attribute){
7.//if(remain_state.size() > 0){
8.//printv(remain_state);
9.//}
10.if (p == NULL)
11. p = new Node();
12.//先看搜索到树叶的情况
13.if (AllTheSameLabel(remain_state, yes)){
14. p->attribute = yes;
15.return p;
16. }
17.if (AllTheSameLabel(remain_state, no)){
18. p->attribute = no;
19.return p;
20. }
21.if(remain_attribute.size() == 0){//所有的属性均已经考虑完了,还没有分尽
22. string label = MostCommonLabel(remain_state);
23. p->attribute = label;
24.return p;
25. }
26.
27.double max_gain = 0, temp_gain;
28. vector <string>::iterator max_it;
29. vector <string>::iterator it1;
30.for(it1 = remain_attribute.begin(); it1 < remain_attribute.end(); it1++){
31. temp_gain = ComputeGain(remain_state, (*it1));
32.if(temp_gain > max_gain) {
33. max_gain = temp_gain;
34. max_it = it1;
35. }
36. }
37.//下面根据max_it指向的属性来划分当前样例，更新样例集和属性集
38. vector <string> new_attribute;
39. vector <vector <string> > new_state;
40.for(vector <string>::iterator it2 = remain_attribute.begin(); it2 < remain_attr
ibute.end(); it2++){
41.if((*it2).compare(*max_it)) new_attribute.push_back(*it2);
42. }
43.//确定了最佳划分属性，注意保存
44. p->attribute = *max_it;
45. vector <string> values = map_attribute_values[*max_it];
46.int attribue_num = FindAttriNumByName(*max_it);
47. new_state.push_back(attribute_row);
48.for(vector <string>::iterator it3 = values.begin(); it3 < values.end(); it3++){
49.for(unsigned int i = 1; i < remain_state.size(); i++){
50.if(!remain_state[i][attribue_num].compare(*it3)){
51. new_state.push_back(remain_state[i]);
52. }
53. }
54. Node * new_node = new Node();
55. new_node->arrived_value = *it3;
56.if(new_state.size() == 0){//表示当前没有这个分支的样例，当前的new_node为叶子节
点
57. new_node->attribute = MostCommonLabel(remain_state);
58. }
59.else
60. BulidDecisionTreeDFS(new_node, new_state, new_attribute);
61.//递归函数返回时即回溯时需要1 将新结点加入父节点孩子容器 2清除new_state容器
62. p->childs.push_back(new_node);
63. new_state.erase(new_state.begin()+1,new_state.end());//注意先清空new_state中
的前一个取值的样例，准备遍历下一个取值样例
64. }
65.return p;
66.}
1.2.3、ID3算法决策树的形成
OK，下图为ID3算法第一步后形成的部分决策树。
这样综合起来看，就容易理解多了。
1、overcast样例必为正，所以为叶子结点，总为yes；
2、ID3无回溯，局部最优，而非全
局最优，还有另一种树后修剪决策树。
下图是ID3算法第一步后形成的部分决策树：
如上图，训练样例被排列到对应的分支结点。
分支Overcast的所有样例都是正例，所以成为目标分类为Yes的叶结点。
另两个结点将被进一步展开，方法是按照新的样例子集选取信息增益最高的属性。
1.3、C4.5算法
1.3.1、ID3算法的改进：C4.5算法
C4.5，是机器学习算法中的另一个分类决策树算法，它是决策树(决策树也就是做决策的节点间的组织方式像一棵树，其实是一个倒树)核心算法，也是上文1.2节所介绍的ID3的改进算法，所以基本上了解了一半决策树构造方法就能构造它。
决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的分类条件。
既然说C4.5算法是ID3的改进算法，那么C4.5相比于ID3改进的地方有哪些呢？：
1. 用信息增益率来选择属性。
ID3选择属性用的是子树的信息增益，这里可以用很多
方法来定义信息，ID3使用的是熵(entropy，熵是一种不纯度度量准则),也就是熵的变化值，而C4.5用的是信息增益率。
对，区别就在于一个是信息增益，一个是信息增益率。
2. 在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考
虑最好，不然容易导致overfitting。
3. 对非离散数据也能处理。
4. 能够对不完整数据进行处理
针对上述第一点，解释下：一般来说率就是用来取平衡用的，就像方差起的作用差不多，比如有两个跑步的人，一个起点是10m/s的人、其10s后为20m/s；另一个人起速是1m/s、其1s后为2m/s。
如果紧紧算差值那么两个差距就很大了，如果使用速度增加率(加速度，即都是为1m/s^2)来衡量，2个人就是一样的加速度。
因此，C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。
C4.5算法之信息增益率
OK，既然上文中提到C4.5用的是信息增益率，那增益率的具体是如何定义的呢？：
是的，在这里，C4.5算法不再是通过信息增益来选择决策属性。
一个可以选择的度量标准是增益比率gain ratio（Quinlan 1986）。
增益比率度量是用前面的增益度量Gain(S，A)
和分裂信息度量SplitInformation(S，A)来共同定义的，如下所示：
其中，分裂信息度量被定义为(分裂信息用来衡量属性分裂数据的广度和均匀)：
其中S1到Sc是c个值的属性A分割S而形成的c个样例子集。
注意分裂信息实际上就是S关于属性A的各值的熵。
这与我们前面对熵的使用不同，在那里我们只考虑S关于学习到的树要预测的目标属性的值的熵。
请注意，分裂信息项阻碍选择值为均匀分布的属性。
例如，考虑一个含有n个样例的集合被属性A彻底分割（译注：分成n组，即一个样例一组）。
这时分裂信息的值为log2n。
相反，一个布尔属性B分割同样的n个实例，如果恰好平分两半，那么分裂信息是1。
如果属性A和B产生同样的信息增益，那么根据增益比率度量，明显B会得分更高。
使用增益比率代替增益来选择属性产生的一个实际问题是，当某个Si接近S（|Si|»|S|）时分母可能为0或非常小。
如果某个属性对于S的所有样例有几乎同样的值，这时要么导致增益比率未定义，要么是增益比率非常大。
为了避免选择这种属性，我们可以采用这样一些启发式规则，比如先计算每个属性的增益，然后仅对那些增益高过平均值的属性应用增益比率测试（Quinlan 1986）。
除了信息增益，Lopez de Mantaras（1991）介绍了另一种直接针对上述问题而设计的度量，它是基于距离的（distance-based）。
这个度量标准基于所定义的一个数据划分间的距离尺度。
具体更多请参看：Tom M.Mitchhell所著的机器学习之3.7.3节。
1.3.2、C4.5算法构造决策树的过程
1.Function C4.5(R:包含连续属性的无类别属性集合,C:类别属性,S:训练集)
2./*返回一棵决策树*/
3.Begin
4. If S为空,返回一个值为Failure的单个节点;
5. If S是由相同类别属性值的记录组成,
6.返回一个带有该值的单个节点;
7. If R为空,则返回一个单节点,其值为在S的记录中找出的频率最高的类别属性值;
8. [注意未出现错误则意味着是不适合分类的记录]；
9. For 所有的属性R(Ri) Do
10. If 属性Ri为连续属性，则
11. Begin
12.将Ri的最小值赋给A1：
13.将Rm的最大值赋给Am；/*m值手工设置*/
14. For j From 2 To m-1 Do Aj=A1+j*(A1Am)/m;
15.将Ri点的基于{< =Aj,>Aj}的最大信息增益属性(Ri,S)赋给A；
16. End；
17.将R中属性之间具有最大信息增益的属性(D,S)赋给D;
18.将属性D的值赋给{dj/j=1,2...m}；
19.将分别由对应于D的值为dj的记录组成的S的子集赋给{sj/j=1,2...m};
20.返回一棵树，其根标记为D;树枝标记为d1,d2...dm;
21.再分别构造以下树:
22. C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm);
23.End C4.5
1.3.3、C4.5算法实现中的几个关键步骤
在上文中，我们已经知道了决策树学习C4.5算法中4个重要概念的表达，如下：
1.
2.
3.
4.
接下来，咱们写下代码实现，
1、信息熵
1.double C4_5::entropy(int *attrClassCount, int classNum, int allNum){
2.double iEntropy = 0.0;
3.for(int i = 0; i < classNum; i++){
4.double temp = ((double)attrClassCount[i]) / allNum;
5.if(temp != 0.0)
6. iEntropy -= temp * (log(temp) / log(2.0));
7. }
8.return iEntropy;
9.}
2、信息增益率
1.double C4_5::gainRatio(int classNum, vector<int *> attriCount, double pEntropy){
2.int* attriNum = new int[attriCount.size()];
3.int allNum = 0;
4.
5.for(int i = 0; i < (int)attriCount.size(); i++){
6. attriNum[i] = 0;
7.for(int j = 0; j < classNum; j++){
8. attriNum[i] += attriCount[i][j];
9. allNum += attriCount[i][j];
10. }
11. }
12.double gain = 0.0;
13.double splitInfo = 0.0;
14.for(int i = 0; i < (int)attriCount.size(); i++){
15. gain -= ((double)attriNum[i]) / allNum * entropy(attriCount[i], classNum, a
ttriNum[i]);
16. splitInfo -= ((double)attriNum[i]) / allNum * (log(((double)attriNum[i])/al
lNum) / log(2.0));
17. }
18. gain += pEntropy;
19.delete[] attriNum;
20.return (gain / splitInfo);
21.}
3、选取最大增益属性作为分类条件
1.int C4_5::chooseAttribute(vector<int> attrIndex, vector<int *>* sampleCount){
2.int bestIndex = 0;
3.double maxGainRatio = 0.0;
4.int classNum = (int)(decisions[attrIndex[(int)attrIndex.size()-1]]).size();//nu
mber of class
5.
6.//computer the class entropy
7.int* temp = new int[classNum];
8.int allNum = 0;
9.for(int i = 0; i < classNum; i++){
10. temp[i] = sampleCount[(int)attrIndex.size()-1][i][i];
11. allNum += temp[i];
12. }
13.double pEntropy = entropy(temp, classNum, allNum);
14.delete[] temp;
15.
16.//computer gain ratio for every attribute
17.for(int i = 0; i < (int)attrIndex.size()-1; i++){
18.double gainR = gainRatio(classNum, sampleCount[i], pEntropy);
19.if(gainR > maxGainRatio){
20. bestIndex = i;
21. maxGainRatio = gainR;
22. }
23. }
24.return bestIndex;
25.}
4、还有一系列建树，打印树的步骤，此处略过。
1.4、决策树归纳的特点
略过....
第二部分、贝叶斯分类
说实话，友人刘未鹏有一篇讲的贝叶斯的文章：数学之美番外篇：平凡而又神奇的贝叶斯方法，已经把贝叶斯讲的很清晰透彻了，我再讲也是如李白看到崔颢在黄鹤楼上所提的：登黄鹤楼
昔人已乘黄鹤去，此地空余黄鹤楼；
黄鹤一去不复返，白云千载空悠悠。
后便大为折服，已无什兴致再提了(偶现在就是这感觉)，然文章还得继续写。
So，本文第二部分之大部分基本整理自未鹏兄之手，若有任何不妥之处，还望读者和未鹏兄海涵，谢谢。
2.1、什么是贝叶斯分类
贝叶斯定理：已知某条件概率，如何得到两个事件交换后的概率，也就是在已知P(A|B)的情况下如何求得P(B|A)。
这里先解释什么是条件概率：
表示事件B已经发生的前提下，事件A发生的概率，叫做事件B发生下事件A的条件概率。
其基本求解公式为：。
贝叶斯定理之所以有用，是因为我们在生活中经常遇到这种情况：我们可以很容易直接得出P(A|B)，P(B|A)则很难直接得出，但我们更关心P(B|A)，贝叶斯定理就为我们打通从P(A|B)获得P(B|A)的道路。
下面不加证明地直接给出贝叶斯定理（公式被网友指出有问题，待后续验证改正）：
2.2 贝叶斯公式如何而来
贝叶斯公式是怎么来的？下面是wikipedia 上的一个例子：
一所学校里面有60% 的男生，40% 的女生。
男生总是穿长裤，女生则一半穿长裤一半穿裙子。
有了这些信息之后我们可以容易地计算“随机选取一个学生，他（她）穿长裤的概率和穿裙子的概率是多大”，这个就是前面说的“正向概率”的计算。
然而，假设你走在校园中，
迎面走来一个穿长裤的学生（很不幸的是你高度近似，你只看得见他（她）穿的是否长裤，而无法确定他（她）的性别），你能够推断出他（她）是男生的概率是多大吗？
一些认知科学的研究表明（《决策与判断》以及《Rationality for Mortals》第12章：小孩也可以解决贝叶斯问题），我们对形式化的贝叶斯问题不擅长，但对于以频率形式呈现的等价问题却很擅长。
在这里，我们不妨把问题重新叙述成：你在校园里面随机游走，遇到了N 个穿长裤的人（仍然假设你无法直接观察到他们的性别），问这N 个人里面有多少个女生多少个男生。
你说，这还不简单：算出学校里面有多少穿长裤的，然后在这些人里面再算出有多少女生，不就行了？
我们来算一算：假设学校里面人的总数是U 个。
60% 的男生都穿长裤，于是我们得到了U * P(Boy) * P(Pants|Boy) 个穿长裤的（男生）（其中P(Boy) 是男生的概率= 60%，这里可以简单的理解为男生的比例；P(Pants|Boy) 是条件概率，即在Boy 这个条件下穿长裤的概率是多大，这里是100% ，因为所有男生都穿长裤）。
40% 的女生里面又有一半（50%）是穿长裤的，于是我们又得到了U * P(Girl) * P(Pants|Girl) 个穿长裤的（女生）。
加起来一共是U * P(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl) 个穿长裤的，其中有U * P(Girl) * P(Pants|Girl) 个女生。
两者一比就是你要求的答案。
下面我们把这个答案形式化一下：我们要求的是P(Girl|Pants) （穿长裤的人里面有多少女生），我们计算的结果是U * P(Girl) * P(Pants|Girl) / [U * P(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl)] 。
容易发现这里校园内人的总数是无关的，可以消去。
于是得到
P(Girl|Pants) = P(Girl) * P(Pants|Girl) / [P(Boy) * P(Pants|Boy) + P(Girl) *
P(Pants|Girl)]
注意，如果把上式收缩起来，分母其实就是P(Pants) ，分子其实就是P(Pants, Girl) 。
而这个比例很自然地就读作：在穿长裤的人（P(Pants) ）里面有多少（穿长裤）的女孩（P(Pants, Girl) ）。
上式中的Pants 和Boy/Girl 可以指代一切东西，So，其一般形式就是：
P(A|B) = P(A|B) * P(B) / [P(A|B) * P(B) + P(A|~B) * P(~B) ]
收缩起来就是：
P(A|B) = P(AB) / P(B)
其实这个就等于：
P(A|B) * P(B) = P(AB)
更进一步阐述，P(A|B)便是在条件B的情况下，A出现的概率是多大。
然看似这么平凡的贝叶斯公式，背后却隐含着非常深刻的原理。
2.3、拼写纠正
经典著作《人工智能：现代方法》的作者之一Peter Norvig 曾经写过一篇介绍如何写一个拼写检查/纠正器的文章，里面用到的就是贝叶斯方法，这里我们不打算复述他写的文章，而是简要地将其核心思想介绍一下。
首先，我们需要询问的是：―问题是什么？‖
问题是我们看到用户输入了一个不在字典中的单词，我们需要去猜测：―这个家伙到底真正想输入的单词是什么呢？‖用刚才我们形式化的语言来叙述就是，我们需要求：
P(我们猜测他想输入的单词| 他实际输入的单词)
这个概率。
并找出那个使得这个概率最大的猜测单词。
显然，我们的猜测未必是唯一的，就像前面举的那个自然语言的歧义性的例子一样；这里，比如用户输入：thew ，那么他到底是想输入the ，还是想输入thaw ？到底哪个猜测可能性更大呢？幸运的是我们可以用贝叶斯公式来直接出它们各自的概率，我们不妨将我们的多个猜测记为h1 h2 .. （h 代表hypothesis），它们都属于一个有限且离散的猜测空间H （单词总共就那么多而已），将用户实际输入的单词记为D （ D 代表Data ，即观测数据），于是
P(我们的猜测1 | 他实际输入的单词)
可以抽象地记为：
P(h1 | D)
类似地，对于我们的猜测2，则是P(h2 | D)。
不妨统一记为：
P(h | D)
运用一次贝叶斯公式，我们得到：
P(h | D) = P(h) * P(D | h) / P(D)
对于不同的具体猜测h1 h2 h3 .. ，P(D) 都是一样的，所以在比较P(h1 | D) 和P(h2 | D) 的时候我们可以忽略这个常数。
即我们只需要知道：。
