k-近邻算法 kNN

k-近邻算法(kNN)采用测量不同特征值之间的距离方法进行分类。

优点：精度高，对异常值不敏感，无数据输入假定
缺点：计算复杂度和空间复杂度都较高
适用数据范围：数值型和标称型

决策树

决策树的关键在于建立决策树。
利用ID3方法构建决策树：通过分别计算将数据按照每种特征进行划分后的信息增益，得到最佳划分特征，并递归获得决策树。

香农熵：
对于任意一个随机变量X，它的熵定义如下：变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。

`H(x) = - sum_x P(x) log_2P(x)`

信息增益：
将数据划分之前的熵和信息划分之后的熵相减即为信息增益。

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

基于概率论的分类方法：朴素贝叶斯

朴素贝叶斯是一个用于文档分类的常用方法。

朴素（naive）贝叶斯的假设：1、每一个特征或者单词出现的可能性与它和其他单词相邻没有关系。2、每个特征同等重要。
这两个假设都有问题，但是实际效果却比较好。

`p(c|x) = (p(x|c)p(c))/(p(x))`

优点：在较小数据量的情况下仍然有效，可以处理多类别的问题 缺点：对于输入数据的准备方式较为敏感 适用范围：标称型