基本概念

1. 通过对训练集的学习，用经验分布替代真实分布进行后续的分类预测

贝叶斯网络（信念网络）

1. Bayesian network, belief network or directed acyclic graphical model，有向无环模型

2. 应用之一是，医学诊断，根据症状判断疾病。可以筛选结构？？
3. 概率基本公式的直观了解，画几个圈圈就好了
P(A,B) = P(A|B)P(B)
=>链式法则 P(xn,xn-1,...,x1) = P(xn|xn-1,xn-2,...,x1)P(xn-1|xn-2,...,x1)...P(x1)


P(A|B) = P(A,B) / P(B)
P(B|A) = P(A,B) / P(A)
P(A|B)P(B) = P(B|A)P(A)
=>贝叶斯推理 P(A|B) = P(B|A)P(A)/P(B)
我们令 A = 分类，B = 证据，就可以推断出，当证据出现时对应的分类。 P(分类） P(证据） P(证据|分类) 可以获得


4. P(x1,x2,...,xn) 这个n个特性的所有情况概率，通常要有一张2^n行的表格
x1    x2    xn   P
T     T     F    ?

但是如果可以构建x1,x2,...,xn的一个贝叶斯网络，就可以根据独立性简化问题。

Boosting

一般算法的问题
1. 收敛速度，不收敛，震荡
2. 过拟合问题 
类比到人这里就是 经验不足 及 惯性思维

Boosting的出发点
1. 我们经常得到的分类器不总是棒棒的分类器

0.0 ------------------- 0.5 ------------1.0 error
     |强分类器       |弱分类器

2. 如果分类器的错误样例分布比较理想，不太重叠或者不重叠，那么采用投票机制就变成了一个很好的强分类器了
3. 后记： 事实证明，效果好，不会出现过拟合

Boosting 分类器的训练基本原理
1. 先训练一个简单的分类器H1
2. 将H1分类器中分错的样例，增加其权重，重新训练H2
3. 将H1分错，并排除H2中分对的样例，增加其权重，重新训练H3
4. 迭代训练到Hn

常用算法
0. AdaBoost

1. GBDT Gradient Boosting Decision Tree

2. XGBoost Extreme Gradient Boosting

参考
http://www.jianshu.com/p/7e0e2d66b3d4

决策树

用信息熵为度量，构造一棵树熵值下降最快的树。目前主流的算法有

通俗解释一下，决策树的直观原则是，选择一个属性作为判断分支，我们希望该条件分出的叶子节点里，
样例要尽量是同一类，这样就说明这个属性比较好

• ID3 : 信息熵增益最大
• C4.5 : 克服ID3的缺点，信息增益比最大
• CART ：回归树与分类树

熵的定义，我们引用信息学的定义比较好理解，信息熵表示对一个随机变量最有效编码时，所需要的最短编码长度。
举个知乎上的例子。考试选择题作弊，ABCD四个选项，如何设计？
假设ABCD的四个选项的概率一样1/4
则根据熵的定义
H = -Σ p * log(p)，H = -4*(1/4)*log(1/4) = 2，2位即可，和直觉一直 00,01,10,11表示ABCD
然后改变定义，假设ABCD的概率分布式 1/8, 1/8, 4/8, 2/8
根据定义可得 H = 1.75，平均编码长度是1.75bit，其实就是答案C的概率高，编码可以用短点的哦。
所以给定一个数据集D，由于分类结果已标注，我们可以计算H(D)，然后决策树如何建立呢？
我们依据是，对于特征Fi，我们计算H(D|Fi)条件熵，然后得到熵的增益，越大表示该特征使得信息熵下降最快！
或者说，熵增表示越混乱，我们的目的是不混乱，就是决策树到达叶子时希望都是一个类别，所以必然选择下降最快的方式。
条件熵的计算
H(Y|X) = Σ p(i)*H(Y|X=x(i))
举个例子，X是天气，Y是开花情况，1表示开花
晴天开花 1 1 0 0 0
阴天开花 1 1 1 1 
雨天开花 1 1 1 0 0
H(Y) = (-)9/14*log(9/14) + (-)5/14*log(5/14)
H(Y|X) = 5/14*( -2/5*log(2/5)-3/5*log(3/5) ) + 4/14*( -4/4*log(4/4) - 0/4*log(0/4) ) + ...
g(Y|X) = H(Y) - H(Y|X) 信息增益，这个就是天气这个特征的信息增益。

C4.5的要修正的是，如果一个特征的取值够多，则一定能把分类分开的其实。。。但是这样就木有意义了，比如上面开花的例子，
我们增加一个维度，叫ID。。。ID = [1 14]
H(Y|ID) = 1/14*(1*log1) + ... = 0， g(Y|ID) = H(Y) 最大了。。。但是这个特征明显无意义。。。所以。。。
要对分支过多进行惩罚，引入属性内部信息
IntI(D,F) = Σ |Di|/|D| * log(|Di|/|D|)，特征数越多，该值越大
信息增益比 gr(D|F) = g(D|F) / IntI(D,F)

以上两个方法都是基于信息熵的，涉及了对数运算，慢。。。所以CART选择一些近似模型，保留信息熵模型的同时减少计算
基尼数 Gini(p) = Σ p(k)*( 1 - p(k) ) = Σp(k) - Σp(k)^2 = 1 - Σp(k)^2 ，预算变得简单了
回归树 ，待定。。。是处理回归模型，使用方差来度量的

集成学习

核心思想就是多个分类器组合在一起
1. 训练集合如何划分，可以有放回抽样，均等，根据上一个分类器的学习结果来划分，分错的怎么处理等等
2. 投票规则，均等，有权重

随机森林：在随机森林中，我们将生成很多的决策树CART。当在基于某些属性对一个新的对象进行分类判别时，
随机森林中的每一棵树都会给出自己的分类选择，并由此进行“投票”，森林整体的输出结果将会是票数最多的分类选项；
而在回归问题中，随机森林的输出将会是所有决策树输出的平均值。

！！降维算法

寻找映射函数，改变维度，或者说寻找有意义的特征
x -> y


**
PCA 主成分分析，线性降维
主成分分析在分析复杂数据时尤为有用，比如人脸识别。
举个例子理解，三维空间的一堆点，其实他们是都分布在一个通过原点的斜面。
正常来说xyz可以描述这些点，但实际上我们知道，既然在一个平面，肯定可以找到一个坐标系x'y'来描述，相当于降维了。

最大方差理论
信号处理中，信号具有较大方差，噪声具有较小方差，信噪比就是信号与噪声的方差比，越大越好。
降维的目的就是，n维数据转换到k维后，应该在每一维度的样本方差都很大。或者说容易区分，说明这个维度是有效的。

注意：only 当你在原数据上跑到了一个比较好的结果，又嫌它太慢的时候才采取PCA进行降维，不然降了半天白降了~

！！深度学习

！！聚类算法

EM算法 - 竟然白写了。。。
1. 先估计一个分布，然后计算训练集的分类
2. 根据新训练集的分类，重新计算这个分布
3. 如此迭代到收敛

经典解释问题，两枚硬币AB，随机拿出一个扔10次，请估计A，B为正面的概率
B HTTTHHTHTH
A HHHHTHHHHH
A HTHHHHHTHH
B HTHTTTHHTT
A THHHTHHHTH
P(A) = 24/30 = 0.8 ，P(B) = 9/20 = 0.45
改变问题，不知道哪次是A，哪次是B，怎么破？相当于有隐变量
? HTTTHHTHTH
? HHHHTHHHHH
? HTHHHHHTHH
? HTHTTTHHTT
? THHHTHHHTH
先估计一个分布 P(A) = 0.6，P(B) = 0.5，分别假设第一次是A或B的可能性
对于第一次，我们可以得出，B的概率大，但是为了一般性，我们取分布意义
A = 0.6^5*0.4^5 = 0.0007962624
B = 0.5^5*0.5^5 = 0.0009765625
一种是认为就是B，以此可以得出12345对应的顺序，比如BABBA，然后依据这个假设，可以重新计算P(A),P(B)，如此迭代下去。
有两个结论
1. 这样迭代，分布会逼近真实的分布么，答案是肯定的，交给数学家了
2. 一定会收敛么，答案是否定的，和初始值有关
另一种是做成分布，A = A/(A+B) = 0.45
A (0.45) - B (0.55)
得出 
A(H) = 0.45*5 = 2.25H，A(T) = 2.25T
B(H) = 0.55*5 = 2.75H，B(T) = 2.75T
如此迭代，可以得出每轮的A，B的期望H和T数，从而可以重新估计出P(A)，P(B)
E step : 根据估计的分布计算期望
M step : 反思分布，根据E的结果，重新更新分布
如此迭代下去~


K-Means ： 本质是一致的，估计分布，计算，更新分布

随机算法

蒙特卡洛算法：采样越多，越近似最优解
拉斯维加斯算法：采样越多，越有机会找到最优解
举个例子，蒙特卡洛求π
在一个正方形里随机散点10000万好了，πr^2/(2r)^2 = π/4 = 落入圆内的点数 / 10000。点越多，理论越接近π值

蒙特卡洛搜索，用于博弈类问题
1. 选择，选择一个节点
2. 扩展，选择一个节点进行扩展
3. 模拟，模拟一次完整的游戏，记录结果
4. 反向传播，将结果反向传播回去，更新所有父亲节点的结果数据

UCT：Upper Confidence Bounds = w(i)/n(i) + C* ( ln(N)/n(i) )^(-1/2)
wi为赢的次数，ni为分支i（或者老虎机i）模拟次数，N为总次数，C为经验参数，一般为根号2，C越大越偏向广度搜索，越小越偏向深度搜索
举个问题，有k个老虎机，收益固定但是不知道是多少，理论上我们要找到收益较高的机子玩，怎么操作呢？
不选取平均收益最高，而是选择置信上限最高的老虎机，wi/ni是实际的平均收益，后面偏移是为了平衡收益-探索这件事的。
就是该分支上，玩的次数越多(ni越大），越可信，平衡了一下样本次数过少出现的意外~

？Alpha Go的MCTS

HMM（Hidden Markov Model）

马尔科夫链：状态转移概率，下一状态的概率分布只能由当前状态决定。
隐马尔可夫模型：是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。
然后利用这些参数来作进一步的分析，例如模式识别。

能干啥
1. 语音识别

数据集介绍

数据四个维度：Sepal花萼长，宽，Petal花瓣长，宽

分类target：Iris Setosa（山鸢尾）、Iris Versicolour（杂色鸢尾），Iris Virginica（维吉尼亚鸢尾）

#KNN - k-nearest neighbors
#Pros : 无需训练
#Cons : 计算大，评分慢，可解释性差
#step 1 : 找出预测对象A的距离最近的k个邻居
#step 2 : k个邻居投票决定，对象A属于哪个分类
from sklearn import neighbors, datasets

#训练数据
iris = datasets.load_iris()
target = iris.target
data = iris.data

#训练
knn = neighbors.KNeighborsClassifier(n_neighbors=5,weights="uniform")
knn.fit(data,target)

#预测
X_pred = [3, 5, 4, 2]
result = knn.predict([X_pred, ])

print(iris.target_names[result])
#['versicolor']
print(knn.predict_proba([X_pred, ]))
#[[ 0.   0.8  0.2]]

#Kmeans
#Step 1 : 初始化k个中心
#Step 2 : 计算所有训练集到k中心距离并标号
#Step 3 : 根据2中数据重新计算k个中心
#Step 4 : 反复执行2，3步骤，直到收敛条件

from sklearn.datasets.samples_generator import make_blobs
X, y = make_blobs(n_samples=300, centers=4,
                  random_state=0, cluster_std=0.60)
plt.scatter(X[:, 0], X[:, 1], s=50);

from sklearn.cluster import KMeans
est = KMeans(4)  # 4 clusters
est.fit(X)
y_kmeans = est.predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='rainbow');