机器学习经典算法总结
knn分类算法
1.特点
- 精度高
- 对异常值不敏感、计算时间空间复杂度高
2.基本思想、算法伪代码
计算待预测样本与数据集中点的距离
选取前k个与待预测样本距离最小的点
返回这前k个点出现频率最高的类别作为待预测样本的类别
3.构思定义好存储数据结构
- dataSet (m*n阶矩阵)：m代表m个数据，n代表每个数据的特征向量维度
- labels (m*1 list)：m与数据数对应
- classCount (p个key-value对的字典)：p代表类别数，key代表类比名称，value代表与待预测样本距离最近的前k个点中相应类别出现的次数
该结构适用于投票表决情况，例如DT中子节点的类别归属问题，同样适用
4.算法python代码细节
- 注意利用np.tile将待预测样本维度扩展，餐能进一步整体计算距离
例如（testMat = np.tile(x, (m, 1))）
- 注意利用np.argsort()对距离排序，并返回由小到大的索引值
例如（sortedDistIndex = np.argsort(dist)）
- 注意sorted函数与operator.itemgetter(1)的配合使用，对字典的value进行排序，也要注意对字典进行.iems()转换为可迭代列表操作
例如（sortedClassCount = sorted(classCount.itmes(), key = operator.itemgetter(1), reverse = True)）
- 注意使用字典的.get()方法直接为不存在key设置初始值，简化代码
例如（classCount[label] = classCount.get(label, 0) + 1）
- 注意数据特征的归一化处理（消除量纲）
- 注意错误率的计算思路
例如（预测标签和测试集标签不同的数量/总预测数量）
5.实战
- 约会网站配对、手写数字识别
LR分类算法
1.特点
- 计算代价不高，易于理解实现，大部分时间用于训练，训练完成后分类快。
- 容易欠拟合，分类精度不高。
2.基本思想
- LR的目的：寻找一个非线性函数sigmoid的最佳拟合参数，求解过程由最优化算法完成。
- sigmoid函数：输入为实数域，输出为0~1之前的数值，大于0.5归入1类，小于0.5归入0类。(可看成是一种概率估计)。
- 最优化算法：BGD(批量梯度下降)、SGD(随机梯度下降)、mini-batch SGD。
SGD算法是在线学习算法(与之对应的是批处理算法)，他的优势：在新数据到来时就完成参数的更新，无需重新读取整个数据集进行计算
- 整体分类处理流程：将测试集上每个特征向量乘以之前最优化算法训练好的回归系数，再将乘积结果求和，最后出入到sigmoid函数中即可输出类别。
3.构思定义好存储数据结构
- dataSet（m*n 阶矩阵）：m代表m个数据点，n代表每个数据点向量维度(最后一维表示该点的标签)，没有x0。
- weights（n*1 阶矩阵）：n代表回归系数的维度与数据点维度相同。
4.算法伪代码
def BGD：
初始化回归系数为1
循环k次：
计算整个数据集梯度(gradient)
利用alphs*gradient更新回归系数向量
返回回归系数
def SGD：
初始化回归系数为1
循环k次：
随机选取之前未选去过的某个数据点：
计算该数据点的梯度
更新回归系数
返回回归系数
5.算法python代码细节
- 注意numpy矩阵(mat)的transpose()使用，避免矩阵相乘出错
（例如：weights += alpha * dataMatrix.transpose() * error）
- 注意numpy矩阵(mat)和numpy数组(array)的乘法使用不同
- 注意SGD中随机选取某个数据点应与之前选去过的去重
（例如：del(dataIndex[randIndex])）
6.实战
- 从疝气病症预测病马的死亡率
- 数据预处理中数据缺失问题：
LR特征缺失采用0填充
原因： 1。更新时不会影响系数的值 weights += alpha * dataMatrix * error ，以0填充，该特征系数将不做更新
2。对结果预测不产生任何倾斜性，因为sigmoid(dataMatrix * weight)中sigmoid(0)=0.5
- 注意算法错误率的计算，并测试多次取平均值思想
决策树(DT)分类算法
1.特点
- 计算复杂度不高、输出结果易于理解(训练好的模型可以序列化存储)、对中间值的缺失不敏感
- 会产生过度匹配问题(ID3算法)，可采用CART算法解决
2.基本思想
- 首先测量初始集合中数据的不一致性，即熵。熵越高，数据越混乱。
- 然后根据信息增益寻找最优方案划分数据集，直至数据集中所有数据属于同一类
- 信息增益，即熵的减少或者数据无序度的减少。信息增益最高的特征就是最好的划分选择。
3.构思定义好存储数据结构
- dataSet （m*n阶矩阵）：m个数据、每个数据n-1个特征，最后一维代表标签
- myTree ({feature: { }}字典)：构造的决策树
- labels （k大小的列表）：类别列表
4.算法伪代码（五个主要函数）
def 递归创建决策树(dataSet, labels)：
递归出口(两种情况)：
1. 划分后的集合类别完全相同
2. 遍历完所有特征（采用投票多数选举策略）
确定最佳划分特征
对于该特征的每个特征值划分后的数据：
递归调用创建决策树
返回决策树
def 确定最佳划分特征(dataSet)：
计算初始熵
对于每个特征：
对于该特征的每个特征值：
计算该特征值划分后的熵
每个特征值划分后的熵相加得到该特征划分后的熵
返回信息增益(前后熵变化)最大的特征
def 按照给定特征划分数据集(dataSet, axis, value)：
返回指定特征的去除特征值的数据
def 计算给定数据集的香农熵(dataSet)：
统计每个类别数据量
计算每个类别概率：每个类别数据量/总数据量
计算香浓熵：- prob * log(prob, 2)
def 使用决策树进行分类(tree, labels, testVec)：
对于字典中每个value：
如果该value是字典型，则递归调用函数
如果不为，则直接返回该类别
5.python代码细节
- 注意使用列表推导创建新列表，并使用python原生的集合(set)数据类型去重，简化代码
（例如：featValue = set([example[i] for example in dataSet])）
- 注意列表extend和append的恰当使用
- 注意字典类型判断使用isinstance或type().__name__
（例如：if type(secondDict[key].__name__ == 'dict') if isinstance(secondDict[key], dict)）
- 注意使用pickle序列化存储
（例如pickle.dump(tree, file) pickle.load(file)）
6.实战
- 预测隐形眼镜类型
Bayes分类
1.特点
- 数据较少的情况下仍然有效，可处理多类别问题
- 对输入数据要求较为敏感
2.基本思想
- 朴素贝叶斯前提：特征之间相互独立，即一个词的出现概率不依赖于其他的词
- 贝叶斯准则：p(c|w) = p(w|c) * p(c) / p(w)
其中c代表类别，w代表文本向量。p(c|w)最大即将其划分为对应c类。
- 主要计算p(w|c)和p(c)
- 两种主要细节解决实际问题
1.p(w|c)为0问题。在求p(w|c)时，有一个为0就会导致整个条件概率为0。
采用拉普拉斯平滑方法，初始化时将每个词条出现次数设为1，将总词条出现数设为k，k为类别数
2.下溢出问题。由于p(w|c)往往都很小，python尝试想成很多很小的数时，会四舍五入为0。
采用取对数方法，ln(a * b) = ln(a) + ln(b)
3.构思定义好存储数据结构
- dataSet （二维列表）：存储文档集；一维存储文档，二维存储每个文档的内容(词)
- vocList（1*n列表）：存储每个词；m代表文档集中的n个不同的词
- trainMat（m*n阶矩阵）：存储训练文档集向量；m代表m个训练文档，n代表每个文档中所有词出现的次数(与vocList中的n对应)
4.算法伪代码（共五大函数）
def 创建总词集合(dataSet)：
对于每个文档：
去重词条
将所有词条合并
返回总词集合列表
def 将文档转化为向量(vocList, doc)： one-hot表示法
初始化词计数列表各项为0
对于该文档每个词：
如果词在vocList(总词集合)中：
词计数列表相应位置计数+1
若果不在：
报错：总词集合中不存在该词
返回词计数列表，即文档向量
def 训练参数(trainMat, trainClass)：
计算pc1=属于类别c1的文档数/总文档数
对于每个文档：
对于每个类别：
统计各词条出现次数
统计总词条出现次数
对于每个类别：
对于每个词条：
计算p(w|c) = 该词条出现次数/总词条出现次数
返回各个p(w|c)和p(c)
def 分类函数(testVec, pwc0, pwc1, pc1)：
计算p0和p1
将测试文档划分为p值(概率)大的那一类
def 垃圾邮件分类封装函数()：
对于每篇文档：
文档预处理(去除特殊符号、和长度小于2的词、转化为小写)
读入词列表、类别标签
形成文档集合
创建总词集合
留存交叉验证划分训练集和测试集
训练出p(w|c)和p(c)
对于每篇测试文档：
根据训练好的参数分类
计算误差(错误率)
5.python代码细节
- 注重集合set类型的去重使用和并集操作
（例如：vocList = vocList | set(doc)）
- 注重列表快速初始化
（例如：docVec = [0] * len(vocList) trainingSet = range(50)）
- 注重留存交叉验证技巧，设置随机索引，并注意del的使用
（例如：trainingSet = range(50) for i in range(10)：randIndex = random.randint(0, len(trainingSet)) testSet.append(tS[rI]) del(tS[rI])）
6.实战
- 过滤网站恶意留言、过滤垃圾邮件
SVM支持向量机
1.特点
- 泛化能力强、计算开销不大、结果易解释
- 对参数调节和核函数的选择敏感，原始不加修改的分类器仅适用于二分类
2.基本思想
- 最大化支持向量到分隔超平面的距离；支持向量：离分隔超平面最近的那些点；公式化：argmax{miny(wx+b)*1/||w||}
||w||为w的L2范数
- 最优分离超平面由支持向量完全决定
- 函数间隔、几何间隔：几何间隔在函数间隔的基础上对超平面的法向量w加某些约束(当w和b成倍增加时，超平面不变，而函数间隔却也成倍增加，所以引入几何间隔，即*1/||w||)
- 凸二次规划问题，求解方法：朗格朗日乘子法；通过求解对偶问题学习线性支持向量机，即首先求解对偶问题的最优质α，然后求最优质w和b，得出分离超平面和分类决策函数
- 对偶问题：实质相同但从不同角度提出不同提法的一对问题。
二次规划问题：优化的目标函数为二次函数、约束函数为线性函数。
凸二次规划：目标函数是凸函数。
- 核函数：通过非线性变换将低维非线性问题映射为高维线性问题。常用核函数：高斯径向基函数。
- SMO(序列最小优化)算法：是支持向量机学习的一种快速算法。
基本思想：不断将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行求解，直到所有变量满足KKT条件为止。
AdaBoost(Boosting)元算法
1.特点
- 分类器组合，与bagging都属于集成算法或元算法。与bagging区别：bagging通过随机抽样的替换方式，得到与元数据集规模一样的数据集(RF随机森林算法)，而boosting在bagging的思路上更进一步，它在数据集上顺序应用多个分类器，共同决定分类结果。
2.基本思想
- AdaBoost以弱分类器作为基分类器，输入数据，使其通过权重向量D进行加权。在第一次迭代中，所有数据样本的权重相等为1/N，在后续迭代过程中，前次迭代分错的数据的权重会增大。最后基于每个弱分类器的错误率计算每个弱分类器的权重alpha，所有这些弱分类器的结果加权求和就得到了最终结果。
3.构思定义好存储数据结构
- numIt（整数）：AdaBoost训练迭代次数，即弱分类器个数
- classEst（列表中元素对应1或-1）：弱分类器评估的类别
- bestStump（字典）：存储给定数据权重向量D时所得到的弱分类器，即最佳DS(单层决策树)，的相关信息（划分特征、阈值、该分类器权重alpha等）
- weakClassList（列表）：存储每个bestStump的列表集合，用于封装各个弱分类器的相关信息，即该列表每行对应一个弱分类器的bestStump。
- aggClassEst（列表中元素为float）：存储每次alpha权重加权求和后的类别估计值，后续引入符号函数sign(aggClassEst)形成强分类器。
4.算法伪代码（三大函数）
根据向量D构建最佳DS
def buildStamp(dataList, classLabels, D):
初始化最小错误率为正无穷
对于数据集中的每个特征：
对于每个步长：
对于每个不等号：
建立一颗单层决策树并利用加权数据集对其进行测试
如果错误率低于最小错误率，则将当前单层决策树作为最佳单层决策树
返回最佳单层决策树
基于DS的adaboost训练函数
def adaBoostTrainDS(dataList, classLabels, numIt=40):
初始化数据权重D为1/N
对于每次迭代：
找到该D下的最佳单层决策树，返回该最佳决策树信息，在D下的误差和类别数组
将该DS加入DS累积数组
利用该弱分类器在D下的误差计算出分类器权重alpha
计算更新D
更新累计类别估计值，即计算alpha和相应弱分类器的类别数组加权求和
通过符号函数sign得到强分类器，计算错误率。如果错误率等于0，退出循环
返回DS累积数组
adaboost分类函数
def adaClassify(testData, classifyArr):
对于训练好的每个弱分类器：
计算测试数据的类别
进行相应alpha加权求和
利用符号函数返回类别
5.实战
- 提升从疝气病症预测病马的死亡率的准确度
- 非均衡分类问题(正反样例数目不相等)解决办法：1. 通过过抽样(复制样例)和欠抽样(删除样例)调节 2. 训练分类器时，将错误代价考虑在内
K-means聚类算法
1.特点
- 容易实现，无监督（无需训练操作）
- 容易受到初始簇质心的影响，可能收敛到局部最小、在大规模数据集上收敛较慢。
2.基本思想
- 随机确定k个初始点作为质心。
- 将数据集中每个点分配到一个簇中（为每个点找出距离其最近的质心，并将其分配给该质心所对应的簇）。
- 更新每个簇的质心为所有点的平均值（直至每个点的簇分配结果不再改变）
3.构思定义好存储数据结构
- 数据集dataSet（m*n 阶 numpy 数据 (矩阵) ）：m代表有m个数据点，n代表每个数据点向量维度为n。
- 质心集centroids（k*n 阶）：k代表有k个质心，n对应向量维度。
- 簇分配集clustAss（m*2）[minIndex, minDis]：m对应m个数据点，索引[0]（即minIndex）代表相应数据点分配的质心索引，索引[1]（即minDis）代表数据点和其分配质心的距离平方。
4.算法伪代码
初始化k个质心
当任意一个数据点的簇分配结果改变时：
对数据集中的每个点：
对每个质心：
计算该点与该质心的距离
将该点分配到距离最近的质心所在簇
对每个质心所在簇：
更新其质心为簇中所有点的均值
5.算法python代码细节
- 善于使用数组过滤器
（例如：更新质心时简短代码：centroids[i, :] = np.mean(dataSet[np.nonzero(clustAss[i, :] == cent) [0] ])）
- 善于使用标志变量
（例如：利用clustchanged来标记数据点簇分配结果是否改变）
- 善于打包函数，防止主程序过于臃肿
（例如：将加载文件、计算距离和随即初始化质心集另打包为三个函数，在kmeans主函数中直接使用上述函数）
6.算法改进
- 二分k-means聚类算法
- 基本思想：将所有点作为一个簇，然后使用传统Kmeans聚类算法（k=2）对其进行划分。下一次迭代时，选择有最大误差的簇进行划分，直至k个簇创建成功。
- 伪代码：
将所有点看作一个簇
当簇数目小于k时：
计算总误差
对于每个簇：
对该簇进行传统k-means聚类（k=2）
计算将该簇一分为二后的总误差
选择使得总误差最小的簇进行实际划分操作
7.实战
- 地图点聚类
- 具体步骤：
0. 目的：将多个地方聚类，选择最佳地点
1. 利用Yahoo PlaceFinder API 将地名转化为数据，并提取出经纬度
2. 应用biKmeans算法聚类