《机器学习实战》


2. KNN  计算距离分类

 kNN中文又称为k-近邻算法，其基本思想是通过计算输入样本点和训练集样本点之前的这两个向量之前的距离，距离越近的话，说明其特征

 越靠近，通过取出其k个距离最近的样本点，然后计算这k个样本点中类别占比最大的类比以此来预测输入样本点(被测样本点)的类别


kNN的优势
kNN是ML里最简单，最基本的算法。
kNN不会受到差别特别大的样本中的特征元素的影响(对异常值不敏感)。因为采用了归一化技术
kNN的精度高
kNN的劣势
kNN算法时间复杂度较高，需要计算被测样本点和训练集中所有样本点的距离


3. Decision Tree: 按照计算的熵分类

决策树（Decision Tree）算法主要用来处理分类问题，
熵（entropy）指的是体系的混乱的程度
信息熵（香农熵）： 是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。
信息增益： 在划分数据集前后信息发生的变化称为信息增益。

		检测数据集中的所有数据的分类标签是否相同:
		    If so return 类标签
		    Else:
		        寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
		        划分数据集
		        创建分支节点
		            for 每个划分的子集
		                调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
		        return 分支节点

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。



4. Naive Bayes: 计算条件概率，选择高概率的决策

朴素贝叶斯的原理十分简单，如果假定数据有两类，分别计算待分类数据属于这两类的概率，p1和p2，如果

p1 > p2, 则属于类别1
p1 < p2, 则属于类别2
略微提及一下贝叶斯公式：
p(c|x)=p(x|c)p(c)p(x)。

这个公式的强大之处在于，可以将先验概率和后验概率进行转换，看起来简单，但是使用的时候的确很强大，而且计算很便捷。

先来看朴素贝叶斯的两个基本假设：

文本之间相互独立
每个特征同等重要
根据这两个基本假设，就可以着手构造分类器了

	优点：在数据较少的情况下依然有效，可处理多类别问题。

	缺点：对于输入数据的格式要求严格。




5. Logistic Regression/逻辑回归：更具梯度上升的方法，拟合数据，分类数据
	Logistic回归是众多分类算法中的一员。通常，Logistic回归用于二分类问题，例如预测明天是否会下雨。
	假设现在有一些数据点，我们利用一条直线对这些点进行拟合(该线称为最佳拟合直线)，这个拟合过程就称作为回归
	Logistic回归是分类方法，它利用的是Sigmoid函数阈值在[0,1]这个特性。Logistic回归进行分类的主要思想是：根据现有数据对分类边界线建立回归公式，以此进行分类。其实，Logistic本质上是一个基于条件概率的判别模型(Discriminative Model)。


	1 logistic分类器只适用于数值属性，不能处理非数值型数据集；
　　  2 logistic分类器的目的是寻找一个非线性函数sigmoid的最佳拟合参数；求解过程用到了最优化方法梯度上升法；



6. SVM:二值分类器：求解一个二次优化问题，来最大化分类间隔，产生一个二值决策结果 (SMO/Sequential Minimal Optimization 序列最小优化)

	线性分类
在训练数据中，每个数据都有n个的属性和一个二类类别标志，我们可以认为这些数据在一个n维空间里。我们的目标是找到一个n-1维的超平面（hyperplane），这个超平面可以将数据分成两部分，每部分数据都属于同一个类别。
其实这样的超平面有很多，我们要找到一个最佳的。因此，增加一个约束条件：这个超平面到每边最近数据点的距离是最大的。也成为最大间隔超平面（maximum-margin hyperplane）。这个分类器也成为最大间隔分类器（maximum-margin classifier）。
支持向量机是一个二类分类器。

非线性分类
SVM的一个优势是支持非线性分类。它结合使用拉格朗日乘子法和KKT条件，以及核函数可以产生非线性分类器。


		SVM的目的是要找到一个线性分类的最佳超平面 f(x)=xwT+b=0。求 w 和 b。
		首先通过两个分类的最近点，找到f(x)的约束条件。
		有了约束条件，就可以通过拉格朗日乘子法和KKT条件来求解，这时，问题变成了求拉格朗日乘子αi 和 b。
		对于异常点的情况，加入松弛变量ξ来处理。
		使用SMO来求拉格朗日乘子αi和b。这时，我们会发现有些αi=0，这些点就可以不用在分类器中考虑了。
		惊喜! 不用求w了，可以使用拉格朗日乘子αi和b作为分类器的参数。
		非线性分类的问题：映射到高维度、使用核函数。

		


7. k-means:
	k-means算法是一种很常见的聚类算法，它的基本思想是：通过迭代寻找k个聚类的一种划分方案，使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小
	k-means算法是一种简单的迭代型聚类算法，采用距离作为相似性指标，从而发现给定数据集中的K个类，且每个类的中心是根据类中所有值的均值得到，每个类用聚类中心来描述。对于给定的一个包含n个d维数据点的数据集X以及要分得的类别K,选取欧式距离作为相似度指标，聚类目标是使得各类的聚类平方和最小


				伪代码 如下:

			创建 k 个点作为起始质心（通常是随机选择）
			当任意一个点的簇分配结果发生改变时
				对数据集中的每个数据点
					对每个质心
						计算质心与数据点之间的距离


			将数据点分配到距其最近的簇


			对每一个簇, 计算簇中所有点的均值并将均值作为质心



优点：

1、该算法时间复杂度为O(tkmn)，（其中，t为迭代次数，k为簇的数目，m为记录数，n为维数）与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好；

2、原理简单，实现容易。

缺点：

1、聚类中心的个数K 需要事先给定，但在实际中这个 K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适； 

2、Kmeans需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。（可以使用K-means++算法来解决）；

3、结果不一定是全局最优，只能保证局部最优；

4、对噪声和离群点敏感；

5、该方法不适于发现非凸面形状的簇或大小差别很大的簇；

6、需样本存在均值（限定数据种类）。





8. 线性回归：预测数值数据， 包括：线性回归（最小二乘法拟合参数），局部加权线性回归,岭回归



9. 树回归：CART/分类树回归，建立二叉树然后使用回归分类 classifciation and regression tree

	决策树的树构建算法是ID3。ID3的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分。也就是说，如果一个特征有4种取值，那么数据将被切分成4份。一旦按某特征切分后，该特征在之后的算法执行过程中将不会再起作用，所以有观点认为这种切分方式过于迅速。

	除了切分过于迅速外，ID3算法还存在另一个问题，它不能直接处理连续型特征。只有事先将连续型特征离散化，才能在ID3算法中使用。但这种转换过程会破坏连续型变量的内在特性


	CART算法有两步：

决策树生成：递归地构建二叉决策树的过程，基于训练数据集生成决策树，生成的决策树要尽量大；自上而下从根开始建立节点，在每个节点处要选择一个最好的属性来分裂，使得子节点中的训练集尽量的纯。不同的算法使用不同的指标来定义"最好"：
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。