- 优点: 精度高， 对异常值不敏感， 无数据输入假定。
- 缺点: 计算复杂度高，空间复杂度高。
- 适用数据范围: 数值型和标称型
- 计算已知类别数据集中的点与当前点之间的距离；
- 按照距离递增次序排序；
- 选取与当前点距离最小的k个点；
- 确定前k个点所在类别的出现频率；
- 返回前k个点出现频率最高的类别作为当前点的预测分类。
在sklearn 中默认的使用 闵科夫斯基距离(minkowski) , p的值为2。
假设n 维空间中的两个点为 X与Y $$ X = (x_1, x_2, ... ..., x_n) \ Y = (y_1, y_2, ... ..., y_n) $$ 则minkowski 距离为: $$ D(X, Y) = (\sum_{i=1}^n |x_i - y_i|^p)^{(\frac{1}{p})} $$ 可知: 当p为1时，距离就是曼哈顿距离， 当p为2时，距离就是 欧几里得距离(欧式距离)
权重可以分为两种:
- 统一权重: 所有样本的权重相同
- 距离加权重:样本的权重与待预测样本的距离成反比。
- KNN 代码实现
import numpy as np
import operator
def classify0(index, data_set, labels, k):
"""
:param index: 用于分类的输入向量的
:param data_set: 输入的训练样本集
:param labels: 标签向量
:param k: 最近邻居的数量
:return:
"""
data_set_size = data_set.shape[0]
diff_mat = np.tile(index, (data_set_size, 1)) - data_set
sq_diff_mat = diff_mat ** 2
sq_distances = sq_diff_mat.sum(axis=1)
distances = sq_distances ** 0.5
sorted_dist_indices = distances.argsort()
class_count = {}
for i in range(k):
vote_i_label = labels[sorted_dist_indices[i]]
class_count[vote_i_label] = class_count.get(vote_i_label, 0) + 1
sorted_class_count = sorted(
class_count.items(),
key=operator.itemgetter(1),
reverse=True
)
return sorted_class_count[0][0]-
归一化代码实现 $$ newValue = \frac{oldValue - min}{max - min} $$
def auto_norm(data_set): """ :param data_set: 需要归一化的array :return: """ min_values = data_set.min(0) max_values = data_set.max(0) ranges = max_values - min_values norm_data_set = np.zeros(np.shape(data_set)) m = data_set.shape[0] norm_data_set = data_set - np.tile(min_values, (m, 1)) norm_data_set = norm_data_set / np.tile(ranges, (m, 1)) return norm_data_set, ranges, min_values
- 优点: 计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感， 可以处理不相关特征数据。
- 缺点: 可能会产生过拟合现象。
- 适用数据类型: 数值型和标称型
- 收集数据: 可以适用任何方法.
- 准备数据: 树构造算法只使用与于标称数据， 因此数值型数据必须离散化。
- 分析数据: 可以使用任何方法， 构造树完成之后， 我们应该检查图形是否符合预期
- 训练算法： 构造树的数据结构。
- 测试算法: 使用经验树计算错误率
- 使用算法: 此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。
划分数据集的最大的原则是: 将无序的数据变得更加有序。
熵: 信息的期望值。 $$ l(x_i) = - \log_2p(x_i) $$
-
$p(x_i)$ 是选择该分类的概率。
信息期望值(信息熵): $$ H = -\sum_{i=1}^np(x_i)log_2p(x_i) $$ 实现过程:
from math import log
def calc_shannon_ent(data_set):
num_entries = len(data_set)
label_counts = {}
for feat_vec in data_set:
current_label = feat_vec[-1]
if current_label not in label_counts.keys():
label_counts[current_label] = 0
label_counts[current_label] += 1
shannon_ent = 0.0
for key in label_counts:
prob = float(label_counts[key]) / num_entries
shannon_ent -= prob * log(prob, 2)
return shannon_ent信息增益(IG-Information gain) $$ IG(D_p, f) = I(D_p) - \sum_{j=1}^n \frac{N_j}{N_p}I(D_j) $$
-
$f$ : 划分的特征。 -
$D_p$ : 父节点，即使用特征$f$ 分割之前的节点。 -
$IG(D_p, f)$ : 父节点$D_p$ 使用特征$f$划分下，获得的信息增益. -
$D_j$ : 父节点$D_p$经过分割之后，会产生$n$个子节点，$D_j$为第$j$个子节点。 -
$N_p$ : 父节点$D_p$包含样本的数量。 -
$N_j$ : 第$j$个子节点$D_j$包含样本的数量。 - I: 不纯度度量标准。例如，之前介绍的信息熵， 就是标准之一
信息熵 $$ I_H(D) = - \sum_{i=1}^mp(i|D)log_2p(i|D) $$
- m: 节点D中含有样本的类别数量
-
$p(i|D):$ 节点D中， 属于类别$i$ 的样本占节点D中样本总数的比例(概率)。
基尼系数 $$ I_G(D) = 1 - \sum_{i=1}^mp(i|D)^2 $$ 错误率 $$ I_E(D) = 1 - \max{p(i|D)} $$
ID3(Iterative Dichotomiser3-迭代二分法) 算法是非常经典的决策树算法、
- 使用多叉树结构
- 使用信息熵作为不纯度度量标准, 选择信息增益最大的特征分割数据。
ID3算法简单，训练较快。但是算法具有一些局限，如下:
- 不支持连续特征。
- 不支持缺失值。
- 仅支持分类， 不支持回归。
- 在选择特征时，会倾向与选择类别多的特征。
C4.5算法是在 ID3算法上改进而来，该算法描述如下:
- 使用多叉树结构
- 仅支持分类， 不支持回归。
C4.5进行优化的部分:
- 支持对缺失值的处理
- 支持将连续值进行离散化处理
- 使用信息熵作为不纯度量标准，但选择信息增益率(而不是信息增益) 最大的特征分裂节点。
信息增益率的定义方式为: $$ IG_{Ratio}(D_P,f) = \frac{IG_H(D_p, f)}{I_H(f)} $$
-
$I_H(f)$ : 根据特征 f 的不同类别值比例(概率)，计算得到的信息熵。
之所以从信息增益改为信息增益率，是因为在ID3算法中，倾向于选择类别多的特征，因此，经过这样的调整，从信息增益调整为 信息增益率， 会在分母上进行一定的惩罚。
CART(Classification And Regression Tree), 分类与回归树。
- 使用二叉树结构
- 支持连续值和缺失值处理。
- 既支持分类，也支持回归。
- 使用基尼系数作为不纯度度量标准，选择基尼增益最大的特征分裂节点(分类)
- 使用MSE或者 MAE 最小的特征分类节点.(回归)
- 优点: 在数据较少的情下仍然有效，可以处理多类别问题。
- 缺点: 对于输入数据的准备方式较为敏感。
- 适用数据类型: 标称型数据
随机事件: 指可能发生，也可能不发生的事件。
样本空间: 即我们进行随机试验时， 所有可能结果构成的集合。习惯用S来表示
概率: 用来反应一个随机事件出现的可能性大小。习惯使用 P(A) 来表示事件A的概率 $$ P(A) = \frac{A包含的基本事件数}{S中基本事件的总数} $$
联合概率: 指多个事件同时发生的概率，例如, P(AB) 表示事件A与事件B的联合概率。 $$ P(AB) = \frac{事件A于B交集的面积}{样本空间S的面积} $$
条件概率, 指在事件A发生的前提下， 事件B发生的概率，使用$P(B|A)$表示。 $$ P(B|A) = \frac{事件A与B交集的面积}{事件A的面积} \ P(B|A) = \frac{P(AB)}{P(A)} $$
-
收集数据: 采用任意方法收集数据。
-
准备数据: 由于需要进行距离计算，因此要求数据类型为数值型。另外，结构化数据格式最佳。
-
分析数据: 采用任意方法对数据进行分析。
-
训练算法: 大部分时间将用于训练，训练的目的是为了找到最佳的分类回归系数
-
测试算法: 一旦训练步骤完成，分类将会很快。
-
使用算法： 首先，我们需要输入一些数据，并将其转换成对应的结构化数据；
接着，基于训练好的回归系数就可以对这些数值进行简单的回归计算，判定它们属于那个类别；在这之后，我们就可以子啊输出的类别上做一些其他分析工作。
- 优点:计算代价不高，易于理解和实现
- 缺点: 容易欠拟合，分类精度可能不高。
- 适用数据类型: 数值型和标称型数据。
梯度上升法基于的思想是: 要找到某函数的最大值，最好的方法就是沿着该函数的梯度方向探索。
如果梯度记为$\nabla$, 则函数$f(x, y)$ 的梯度
$$
\nabla f(x, y) = \begin{pmatrix} \frac{\partial f(x, y)}{\partial x} \
\frac{\partial f(x, y)}{\partial y}
\end{pmatrix}
$$
这个梯度意味着要沿$x$的方向移动
梯度算子总是指向函数值增长最快的方向，移动量称为步长 记为
梯度上升算法的迭代公式如下: $$ w:= w + \alpha\nabla_wf(w) $$ 该公式一直被迭代执行，直至达到某个停止条件为止，比如迭代次数达到指定值或算法达到某个可以允许的误差范围。
梯度上升算法用来求函数的最大值。
梯度下降算法来求函数的最小值。
支持向量机(support vector) 就是离分隔超平面最近的那些点。
- 优点: 泛华错误率低，计算开销不大，结果易解释。
- 缺点: 对参数调节和核核函数的选择敏感， 原始分类器不加修改适用于处理二类问题。
- 使用数据类型: 数据型和标称型数据。
分割超平面的形式可以写为
就必须给出点到分割面的法线或垂线的长度
类似Sigmoid 函数的作用，使用类似 海维赛德阶跃函数(单位阶跃函数)
当
需要找到具有最小间隔的数据点，而这些数据点也就是 支持向量。一旦找到最小间隔的数据点，就需要对该间隔最大化。 $$ \arg \max_{w,b} \begin{Bmatrix} \min_{n}(label*(w^Tx+b)) \frac{1}{||w||} \end{Bmatrix} $$ 通过引入拉格朗日乘子，可以基于约束条件来表述原来的问题。 $$ \max_{\alpha}\begin{bmatrix} \sum^m_{i=1}\alpha -\frac{1}{2} \sum^m_{j=1} label^{(i)} label^{(j)}*\alpha_i *\alpha_j [x^{(i)}, x^{(j)}] \end{bmatrix} $$
-
$label*(w^Tx+b)$ 被称为点到分隔离的函数间隔 -
$label*(w^Tx+b)* \frac{1}{||w||}$ 称为点到分隔面的几何间隔 -
约束条件: $$ \alpha \geq 0, 和 \sum_{i=1}^m \alpha_i* label^{(i)} = 0 $$