SOCSEC

机器学习笔记之KNN算法

描述

存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签。即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应特征进行比较,然后算法提取样本集中特征最相似的数据(最邻近)的分类标签。一般来说只选择样本集中前k个最相似的数据,这就是k-邻近算法中k的出处,通常k是不大于20的整数,最后,选择k个最相似数据中出现次数最多的分类,作为新的分类。

图解为:

图2

特点

优点:精度高、对异常值不敏感、无数据输入假定。

缺点:计算复杂度高、空间复杂度高。

适用范围:数值型和标称型。

一般流程

(1) 收集数据:可以使用任何方法。

(2) 准备数据:距离计算所需要的数值,最好是结构化的数据格式。

(3) 分析数据:可以使用任何方法。

(4) 训练算法:此步骤不适用于k-近邻算法。

(5) 测试算法:计算错误率。

(6) 使用算法:首先需要输入样本数据和结构化的输出结果,然后运行k-近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理。

常用距离

分类时常常需要估算不同样本之间的相似性度量(Similarity Measurement),通常采用的方法就是计算样本间的“距离”(Distance)。这里总结下常用的距离。

  • 欧氏距离

    欧氏距离是最易于理解的一种距离计算方法,源自欧氏空间中两点间的距离公式。

    (1) . 二维平面上两点a($x_1$,$y_1$)与b($x_2$,$y_2$)间的欧氏距离:

    $d_{12} = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

    (2)三维空间两点a($x_1$,$y_1$,$z_1$)与b($x_2$,$y_2$,$z_2$)间的欧氏距离:

    $d_{12} = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$

    (3)两个n维向量 $a(x_{11},x_{12},…,x_{1n})$ 与 $b(x_{21},x_{22},…,x_{2n})$ 间的欧氏距离:

    $d_{12} = \sqrt{\sum_{k=1}^{n}(x_{1k}-x_{2k})^2}$

  • 曼哈顿距离(Manhattan Distance)

    曼哈顿距离(Manhattan Distance)是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ,是种使用在几何度量空间的几何学用语,用以标明两个点在标准坐标系上的绝对轴距总和。图中红线代表曼哈顿距离,绿色代表欧氏距离,也就是直线距离,而蓝色和黄色代表等价的曼哈顿距离.曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离,

    图2

    (1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离:

    $d_{12} = |x_1-x_2|+|y_1-y_2|$

    (2)两个n维向量a($x_{11}$,$x_{12}$,…,$x_{1n}$)与 b($x_{21}$,$x_{22}$,…,$x_{2n}$)间的曼哈顿距离

    $d_{12} = \sum_{k=1}^{n}|x_{1k}-x_{2k}|$

  • 切比雪夫距离 ( Chebyshev Distance )

    数学上,切比雪夫距离(Chebyshev distance)或是$L_{\infty}$度量,是向量空间中的一种度量,二个点之间的距离定义为其各座标数值差的最大值。

    (1)二维平面两点a($x_1,y_1$)与b($x_2,y_2$)间的切比雪夫距离

    $d_{12} = max(|x_2-x_1|,|y_2-y_1|)$。

    (2)两个n维向量a($x_{11}$,$x_{12}$,…,$x_{1n}$)与 b($x_{21}$,$x_{22}$,…,$x_{2n}$)间的切比雪夫距离

    $d_{12} = max(|x_{1i}-x_{2i}|)$。

    这个公式的另一种等价形式是:

    $d_{12} = \lim_{k\to\infty}(\sum_{i=1}^{n}|x_{1i}-x_{2i}|^k)^{^1/_k}$

  • 闵可夫斯基距离(Minkowski Distance)

    被看做是欧氏距离和曼哈顿距离的一种推广

    定义:

    两个n维变量 a($x_{11}$,$x_{12}$,…,$x_{1n}$)与 b($x_{21}$,$x_{22}$,…,$x_{2n}$)$\in R^n$ 间的闵可夫斯基距离定义为:

    $d_{12} = (\sum_{i=1}^{n}|x_{1i}-x_{2i}|^p)^{^1/_p}$

    其中p是一个变参数。

    当p=1时,就是曼哈顿距离

    当p=2时,就是欧氏距离

    当p→∞时,就是切比雪夫距离

    根据变参数的不同,闵氏距离可以表示一类的距离。

    闵氏距离的缺点主要有两个:

    (1)将各个分量的量纲(scale),也就是“单位”当作相同的看待了。

    (2)没有考虑各个分量的分布(期望,方差等)可能是不同的。

  • 标准化欧氏距离 (Standardized Euclidean Distance)

    标准化欧氏距离是针对欧氏距离的缺点而作的一种改进。标准欧氏距离的思路:既然数据各维分量的分布不一样,那先将各个分量都“标准化”到均值、方差相等。假设样本集X的均值(mean)为m,标准差(standard deviation)为s,X的“标准化变量”表示为:

    $X^*= \frac{X-m}{s}$

    标准欧式距离为:

    $d_{12} = \sqrt{\sum_{k=1}^{n}(\frac{x_{1k}-x_{2k}}{s_k})^2}$

    如果将方差的倒数看成一个权重,也可称之为加权欧氏距离(Weighted Euclidean distance)。

  • 马氏距离(Mahalanobis Distance)

    马氏距离的引出:

    图3

    上图有两个正态分布的总体,它们的均值分别为ab,但方差不一样,则图中的A点离哪个总体更近?或者说A有更大的概率属于谁?显然,A离左边的更近,A属于左边总体的概率更大,尽管Aa的欧式距离远一些。这就是马氏距离的直观解释。

    概念:马氏距离是基于样本分布的一种距离。物理意义就是在规范化的主成分空间中的欧氏距离。所谓规范化的主成分空间就是利用主成分分析对一些数据进行主成分分解。再对所有主成分分解轴做归一化,形成新的坐标轴。由这些坐标轴张成的空间就是规范化的主成分空间。

    图4

    马氏距离由印度统计学家马哈拉诺斯(P.C.Mahalanobis)提出,表示数据的协方差距离,与欧式距离不同,它考虑了各指标之间相关性的干扰,而且不受各指标量纲的影响,但是它的缺点是夸大了变化微小的变量的作用。

    定义:有M个样本向量$X_1~X_m$,协方差矩阵记为S,均值记为向量μ,则其中样本向量Xμ的马氏距离表示为:

    $D(X) = \sqrt{(X-\mu)^TS^{-1}(X_i-X_j)}$

    向量$X_i$与$X_j$之间的马氏距离定义为:

    $D(X_i,X_j) = \sqrt{(X_i-X_j)^TS^{-1}(X_i-X_j)}$

    若协方差矩阵是单位矩阵(各个样本向量之间独立同分布),则Xi与Xj之间的马氏距离等于他们的欧氏距离:

    $D(X_i,X_j) = \sqrt{(X_i-X_j)^T(X_i-X_j)}$

    若协方差矩阵是对角矩阵,则就是标准化欧氏距离。

    欧式距离vs马氏距离:

    图5
    图6

    马氏距离的特点:

    1. 量纲无关,排除变量之间的相关性的干扰;

    2. 马氏距离的计算是建立在总体样本的基础上的,如果拿同样的两个样本,放入两个不同的总体中,最后计算得出的两个样本间的马氏距离通常是不相同的,除非这两个总体的协方差矩阵碰巧相同;

    3. 计算马氏距离过程中,要求总体样本数大于样本的维数,否则得到的总体样本协方差矩阵逆矩阵不存在,这种情况下,用欧式距离计算即可。

  • 余弦距离(Cosine Distance)

    几何中,夹角余弦可用来衡量两个向量方向的差异;机器学习中,借用这一概念来衡量样本向量之间的差异。

    二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式:

    $\cos\theta = \frac{x_1x_2+y_1y_2}{\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}}$

    两个n维样本点a($x_{11}$,$x_{12}$,…,$x_{1n}$)与 b($x_{21}$,$x_{22}$,…,$x_{2n}$)的夹角余弦为:

    $\cos(\theta) = \frac{\overrightarrow{a} \cdot \overrightarrow{b}}{|\overrightarrow{a} ||\overrightarrow{b}|}$

    即:

    $\cos(\theta) = \frac{\sum_{k=1}^{n}x_{1k}x_{2k}}{\sqrt{\sum_{k=1}^{n}x_{1k}^2}\sqrt{\sum_{k=1}^{n}x_{2k}^2}}$

    夹角余弦取值范围为[-1,1]。余弦越大表示两个向量的夹角越小,余弦越小表示两向量的夹角越大。当两个向量的方向重合时余弦取最大值1,当两个向量的方向完全相反余弦取最小值-1

    欧氏距离是最常见的距离度量,而余弦相似度则是最常见的相似度度量,很多的距离度量和相似度度量都是基于这两者的变形和衍生,所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。

    借助三维坐标系来看下欧氏距离和余弦相似度的区别:

    图8

    从图上可以看出距离度量衡量的是空间各点间的绝对距离,跟各个点所在的位置坐标(即个体特征维度的数值)直接相关;而余弦相似度衡量的是空间向量的夹角,更加的是体现在方向上的差异,而不是位置。如果保持A点的位置不变,B点朝原方向远离坐标轴原点,那么这个时候余弦相似度cosθ是保持不变的,因为夹角不变,而AB两点的距离显然在发生改变,这就是欧氏距离和余弦相似度的不同之处。

    根据欧氏距离和余弦相似度各自的计算方式和衡量特征,分别适用于不同的数据分析模型:欧氏距离能够体现个体数值特征的绝对差异,所以更多的用于需要从维度的数值大小中体现差异的分析,如使用用户行为指标分析用户价值的相似度或差异;而余弦相似度更多的是从方向上区分差异,而对绝对的数值不敏感,更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异,同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。

    调整余弦相似度(Adjusted Cosine Similarity)

    余弦相似度更多的是从方向上区分差异,而对绝对的数值不敏感。因此没法衡量每个维数值的差异,会导致这样一个情况:比如用户对内容评分,5分制,X和Y两个用户对两个内容的评分分别为(1,2)和(4,5),使用余弦相似度得出的结果是0.98,两者极为相似,但从评分上看X似乎不喜欢这2个内容,而Y比较喜欢,余弦相似度对数值的不敏感导致了结果的误差,需要修正这种不合理性。

    调整余弦相似度,将所有维度上的数值都减去一个均值,比如X和Y的评分均值都是3,那么调整后为(-2,-1)和(1,2),再用余弦相似度计算,得到-0.8,相似度为负值并且差异不小,但显然更加符合现实。

  • 汉明距离(Hamming Distance)

    图7

    定义:两个等长字符串s1与s2的汉明距离为:将其中一个变为另外一个所需要作的最小字符替换次数。例如:

    1
    2
    3
    The Hamming distance between "1011101" and "1001001" is 2.
    The Hamming distance between "2143896" and "2233796" is 3.
    The Hamming distance between "toned" and "roses" is 3.

    汉明重量:是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是 1 的个数,所以 11101 的汉明重量是 4。因此,如果向量空间中的元素ab之间的汉明距离等于它们汉明重量的差a-b

    应用:汉明重量分析在包括信息论、编码理论、密码学等领域都有应用。比如在信息编码过程中,为了增强容错性,应使得编码间的最小汉明距离尽可能大。但是,如果要比较两个不同长度的字符串,不仅要进行替换,而且要进行插入与删除的运算,在这种场合下,通常使用更加复杂的编辑距离等算法。

    编辑距离,又称Levenshtein距离(也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

    应用:DNA分析、拼字检查、语音辨识、抄袭侦测、小规模的字符串近似搜索,需求类似于搜索引擎中输入关键字,出现类似的结果列表。

  • 杰卡德距离(Jaccard Distance) 和 杰卡德相似系数(Jaccard similarity coefficient)

    两个集合AB的交集元素在AB的并集中所占的比例,称为两个集合的杰卡德相似系数,用符号J(A,B)表示:

    $J(A,B) = \frac{|A\bigcap B|}{|A\bigcup B|}$

    杰卡德距离(Jaccard Distance):与杰卡德相似系数相反,用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度:

    $J_{\delta}(A,B) = 1-J(A,B)=\frac{|A \bigcup B|-|A \bigcap B|}{|A \bigcup B|}$

    应用:可将杰卡德相似系数用在衡量样本的相似度上,样本A与样本B是两个n维向量,而且所有维度的取值都是01。例如:A(0111)B(1011)。我们将样本看成是一个集合,1表示集合包含该元素,0表示集合不包含该元素。

    p:样本A与B都是1的维度的个数

    q :样本A是1,样本B是0的维度的个数

    r :样本A是0,样本B是1的维度的个数

    s :样本A与B都是0的维度的个数

    那么样本A与B的杰卡德相似系数可以表示为:

    这里p+q+r可理解为A与B的并集的元素个数,而pAB的交集的元素个数。

    而样本A与B的杰卡德距离表示为:

    $J=\frac{p}{p+q+r}$

    Tanimoto系数

    常常用于文档数据,并在二元属性情况下规约为Jaccard系数。该系数用EJ表示,定义如下:

    $EJ(A,B)=\frac{A\cdot B}{|A|^2+|B|^2-A\cdot B} = \frac{\sum_{i=1}^nx_{1i}x_{2i}}{\sum_{i=0}^nx_{1i}^2+\sum_{i=0}^nx_{2i}^2-\sum_{i=0}^nx_{1i}x_{2i}}$

  • 相关距离(Correlation distance)

    图8

    皮尔逊相关系数(Pearson Correlation coefficient):是衡量随机变量XY相关程度的一种方法,相关系数的取值范围是[-1,1]。相关系数的绝对值越大,则表明XY相关度越高。当XY线性相关时,相关系数取值为1(正线性相关)或-1(负线性相关):

    $\rho_{XY} = \frac{Cov(XY)}{\sqrt{D(X)}\sqrt{D(Y)}} = \frac{E((X-EX)(Y-EY))}{\sqrt{D(X)}\sqrt{D(Y)}}$

    相关距离:

    $D_xy= 1-\rho_{XY}$

    斯皮尔曼秩相关系数(Spearman Rank Correlation): 与Pearson相关系数一样,它也可以反映两组变量联系的紧密程度,取值在-1到+1之间,计算方法上也完全相同,不同的是它建立在秩次的基础之上,对原始变量的分布和样本容量的大小不作要求,属于非参数统计方法,适用范围更广。

    设$R(R_1,R_2,…,R_n)$ 表示X在 $(X_1,X_2,…,X_n)$ 中的秩, $Q(Q_1,Q_2,…,Q_n)$ 表示Y在 $(Y_1,Y_2,…,Y_n)$ 中的秩,如果XY具有同步性,那么RQ也会表现出同步性,反之依然,将其代入Pearson相关系数,就得到秩之间的一致性,也就是Spearman相关系数。考虑到:

    $R_1+R_2+…+R_n = Q_1+Q_2+…+Q_n = \frac{n(n+1)}{2}$

    $R_1^2+R_2^2+…+R_n^2 = Q_1^2+Q_2^2+…+Q_n^2 = \frac{n(n+1)(2n+1)}{6}$

    Spearman相关系数可以定义为:

    $r(X,Y)=1-\frac{6\ast[(R_1-Q_1)^2+(R_2-Q_2)^2+…+(R_n-Q_n)^2]}{[n(n^2-1)]} = 1 - \frac{6\ast\sum_{k=1}^n (R_k-Q_k)^2}{n(n^2-1)}$

    肯德尔秩相关系数(Kendall Rank Correlation)

    Kendall在本质设想方面与Spearman是一样的,它从两个变量是否协同一致的角度出发检验两变量之间是否存在相关性。

    什么是协同?假设两个变量XYn对观察值 $(X_1,Y_1),(X_2,Y_2),…,(X_n,Y_n)$,如果 $(X_j-X_i)(Y_j-Y_i)>0 , (j>i)$,称 $(X_i,Y_i)$ 与 $(X_j,Y_j)$ 满足协同性(concordant),或者说变化方向一致。否则,不满足协同性。

    全部数据共有n(n-1)/2对,如果用$N_c$表示同向数对的数目,$N_d$表示反向数对的数目,则 $N_c+N_d=n(n-1)/2$,Kendall相关系数由两者的平均差定义:$(N_c-N_d)/[n(n-1)/2]$。Kendall相关系数的取值范围在-1到1之间,当等于1时,表示两个随机变量拥有一致的等级相关性;当等于-1时,表示两个随机变量拥有完全相反的等级相关性;当等于0时,表示两个随机变量是相互独立的。

  • 信息熵(Information Entropy)

    以上的距离度量方法度量的皆为两个样本(向量)之间的距离,而信息熵描述的是整个系统内部样本之间的一个距离,或者称之为系统内样本分布的集中程度(一致程度)、分散程度、混乱程度(不一致程度)。系统内样本分布越分散(或者说分布越平均),信息熵就越大。分布越有序(或者说分布越集中),信息熵就越小。

    图9

    计算给定的样本集X的信息熵的公式:

    $Entropy(X) = -\sum_{i=1}^{n}p_{i}log_2p_i$

    参数的含义:

    n:样本集X的分类数

    $p_i$:X中第 i 类元素出现的概率

    信息熵越大表明样本集S的分布越分散(分布均衡),信息熵越小则表明样本集X的分布越集中(分布不均衡)。当Sn个分类出现的概率一样大时(都是1/n),信息熵取最大值log2(n)。当X只有一个分类时,信息熵取最小值0

-

参考资料

  1. 机器学习实战

  2. http://www.cnblogs.com/heaad/archive/2011/03/08/1977733.html

  3. https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference

  4. http://www.niubua.com/2014/12/20/%E8%B7%9F%E6%88%91%E4%B8%80%E8%B5%B7%E6%95%B0%E6%8D%AE%E6%8C%96%E6%8E%98%EF%BC%888%EF%BC%89-%E7%9B%B8%E4%BC%BC%E6%80%A7%E5%92%8C%E7%9B%B8%E5%BC%82%E6%80%A7/