呆板进修中间隔和相似性怀抱要领
|
副问题[/!--empirenews.page--]
在呆板进修和数据发掘中，我们常常必要知道个别间差此外巨细，进而评价个另外相似性和种别。最常见的是数据说明中的相干说明，数据发掘中的分类和聚类算法，如 K 最近邻（KNN）和 K 均值（K-Means）等等。按照数据特征的差异，可以回收差异的怀抱要领。一样平常而言，界说一个间隔函数 d(x,y),必要满意下面几个准则： 1) d(x,x) = 0 ? ? ? ? ? ? ? ? ? ?// 到本身的间隔为0 1. 闵可夫斯基间隔闵可夫斯基间隔（Minkowski distance）是权衡数值点之间间隔的一种非经常见的要领，假设数值点 P 和 Q 坐标如下：
那么，闵可夫斯基间隔界说为：
该间隔最常用的 p 是 2 和 1,前者是欧几里得间隔（Euclidean distance），后者是曼哈顿间隔（Manhattan distance）。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色暗示高楼大厦，灰色暗示街道：
绿色的斜线暗示欧几里得间隔，在实际中是不行能的。其他三条折线暗示了曼哈顿间隔，这三条折线的长度是相称的。 当 p 趋近于无限大时，闵可夫斯基间隔转化成切比雪夫间隔（Chebyshev distance）：
我们知道平面上到原点欧几里得间隔（p = 2）为 1 的点所构成的外形是一个圆，当 p 取其他数值的时辰呢？
留意，当 p?<?1 时，闵可夫斯基间隔不再切合三角形法例，举个例子：当 p?<?1,(0,0) 到 (1,1) 的间隔便是 (1+1)^{1/p}?>?2,而 (0,1) 到这两个点的间隔都是 1。 闵可夫斯基间隔较量直观，可是它与数据的漫衍无关，具有必然的范围性，假如 x 偏向的幅值远宏大于 y 偏向的值，这个间隔公式就会太过放大 x 维度的浸染。以是，在计较间隔之前，我们也许还必要对数据举办?z-transform?处理赏罚，即减去均值，除以尺度差：
可以看到，上述处理赏罚开始浮现数据的统计特征了。这种要领在假设数据各个维度不相干的环境下操作数据漫衍的特征计较出差异的间隔。假如维度彼此之间数据相干（譬喻：身高较高的信息很有也许会带来体重较重的信息，由于两者是有关联的），这时辰就要用到马氏间隔（Mahalanobis distance）了。 ? 2. 马氏间隔思量下面这张图，椭圆暗示等高线，从欧几里得的间隔来算，绿黑间隔大于红黑间隔，可是从马氏间隔，功效刚好相反：
马氏间隔现实上是操作 Cholesky transformation 来消除差异维度之间的相干性和标准差异的性子。假设样本点（列向量）之间的协方差对称矩阵是??， 通过 Cholesky Decomposition（现实上是对称矩阵 LU 解析的一种非凡情势）可以转化为下三角矩阵和上三角矩阵的乘积：?
下图蓝色暗示原样本点的漫衍，两颗红星坐标别离是（3,3），（2,-2）:
因为 x， y 偏向的标准差异，不能纯真用欧几里得的要领丈量它们到原点的间隔。而且，因为 x 和 y 是相干的（大抵可以看出斜向右上），也不能简朴地在 x 和 y 偏向上别离减去均值，除以尺度差。最适当的要领是对原始数据举办 Cholesky 调动，即求马氏间隔（可以看到，右边的红星离原点较近）：
马氏间隔的调动和 PCA 解析的白化处理赏罚颇有异曲同工之妙，差异之处在于：就二维来看，PCA 是将数据主因素旋转到 x 轴（正交矩阵的酉调动），再在标准上缩放（对角矩阵），实现标准沟通。而马氏间隔的 L逆矩阵是一个下三角，先在 x 和 y 偏向举办缩放，再在 y 偏向举办错切（想象矩形变平行四边形），总体来说是一个没有旋转的仿射调动。 3. 向量内积
向量内积是线性代数里最为常见的计较，现实上它照旧一种有用而且直观的相似性丈量本领。向量内积的界说如下： 直观的表明是：假如 x 高的处所 y 也较量高， x 低的处所 y 也较量低，那么整体的内积是偏大的，也就是说 x 和 y 是相似的。举个例子，在一段长的序列信号 A 中探求哪一段与短序列信号 a 最匹配，只必要将 a 从 A 信号开头逐个向后平移，每次平移做一次内积，内积最大的相似度最大。信号处理赏罚中 DFT 和 DCT 也是基于这种内积运算计较出差异频域内的信号组分（DFT 和 DCT 是正交尺度基，也可以看做投影）。向量和信号都是离散值，假如是持续的函数值，好比求区间[-1,1]?两个函数之间的相似度，同样也可以获得（系数）组分，这种要领可以应用于多项式迫近持续函数，也可以用到持续函数迫近离散样本点（最小二乘题目，OLS coefficients）中，扯得有点远了- -!。 向量内积的功效是没有边界的，一种办理步伐是除以长度之后再求内积，这就是应用异常普及的余弦相似度（Cosine similarity）：
皮尔逊相相关数具有平移稳固性和标准稳固性，计较出了两个向量（维度）的相干性。不外，一样平常我们在评论相相关数的时辰，将 x 与 y 对应位置的两个数值看作一个样本点，皮尔逊系数用来暗示这些样本点漫衍的相干性。
因为皮尔逊系数具有的精采性子，在各个规模都应用普及，譬喻，在保举体系按照为某一用户查找兴趣相似的用户,进而提供保举，利益是可以不受每个用户评分尺度差异和寓目影片数目纷歧样的影响。 4. 分类数据点间的间隔
汉明间隔（Hamming distance）是指，两个等长字符串s1与s2之间的汉明间隔界说为将个中一个变为其它一个所必要作的最小替代次数。举个维基百科上的例子： 还可以用简朴的匹配系数来暗示两点之间的相似度——匹配字符数/总字符数。 在一些环境下，某些特定的值相称并不能代表什么。举个例子，用 1 暗示用户看过该影戏，用 0 暗示用户没有看过，那么用户看影戏的的信息就可用 0,1 暗示成一个序列。思量到影戏基数很是复杂，用户看过的影戏只占个中很是小的一部门，假如两个用户都没有看过某一部影戏（两个都是 0），并不能声名两者相似。反而言之，假如两个用户都看过某一部影戏（序列中都是 1），则声名用户有很大的相似度。在这个例子中，序列中便是 1 所占的权重应该远宏大于 0 的权重，这就引出下面要说的杰卡德相似系数（Jaccard similarity）。 在上面的例子中，用 M11 暗示两个用户都看过的影戏数量，M10 暗示用户 A 看过，用户 B 没看过的影戏数量，M01 暗示用户 A 没看过，用户 B 看过的影戏数量，M00 暗示两个用户都没有看过的影戏数量。Jaccard 相似性系数可以暗示为： Jaccard similarity 还可以用荟萃的公式来表达，这里就不多说了。 假如分类数值点是用树形布局来暗示的，它们的相似性可以用沟通路径的长度来暗示，好比，“/product/spot/ballgame/basketball” 离“product/spot/ballgame/soccer/shoes” 的间隔小于到 "/product/luxury/handbags" 的间隔，觉得前者沟通父节点路径更长。 5. 序列之间的间隔
上面我们知道，汉明间隔可以怀抱两个长度沟通的字符串之间的相似度，假如要较量两个差异长度的字符串，不只要举办替代，并且要举办插入与删除的运算，在这种场所下，凡是行使越发伟大的编辑间隔（Edit distance,Levenshtein distance）等算法。编辑间隔是指两个字串之间，由一个转成另一个所需的起码编辑操纵次数。容许的编辑操纵包罗将一个字符替代成另一个字符，插入一个字符，删除一个字符。编辑间隔求的是起码编辑次数，这是一个动态筹划的题目，有乐趣的同窗可以本身研究研究。 时刻序列是序列之间间隔的其它一个例子。DTW 间隔（Dynamic Time Warp）是序列信号在时刻可能速率上不匹配的时辰一种权衡相似度的要领。神马意思？举个例子，两份本来一样声音样本A、B都说了“你好”，A在时刻上产生了扭曲，“你”这个音延迟了几秒。最后A:“你~~~好”，B：“你好”。DTW正是这样一种可以用来匹配A、B之间的最短间隔的算法。 DTW 间隔在保持信号先后次序的限定下对时刻信号举办“膨胀”可能“紧缩”，找到最优的匹配，与编辑间隔相似，这着实也是一个动态筹划的题目: 6. 概率漫衍之间的间隔
前面我们评论的都是两个数值点之间的间隔，现实上两个概率漫衍之间的间隔是可以丈量的。在统计学内里常常必要丈量两组样天职布之间的间隔，进而判定出它们是否出自统一个 population，常见的要领有卡方检讨（Chi-Square）和?KL 散度（ KL-Divergence），下面说一说 KL 散度吧。 先从信息熵提及，假设一篇文章的问题叫做“黑洞到底吃什么”，包括词语别离是 {黑洞,到底,吃什么},我们此刻要按照一个词语展望这篇文章的种别。哪个词语给以我们的信息最多？很轻易就知道是“黑洞”，由于“黑洞”这个词语在全部的文档中呈现的概率太低啦，一旦呈现，就表白这篇文章很也许是在讲科普常识。而其他两个词语“到底”和“吃什么”呈现的概率很高，给以我们的信息反而越少。怎样用一个函数 h(x) 暗示词语给以的信息量呢？第一，必定是与 p(x) 相干，而且是负相干。第二，假设 x 和 y 是独立的（黑洞和宇宙不彼此独立，谈到黑洞肯定会说宇宙）,即 p(x,y) = p(x)p(y),那么得到的信息也是叠加的，即 h(x,y) = h(x) + h(y)。满意这两个前提的函数必定是负对数情势： 对假设一个发送者要将随机变量 X 发生的一长串随机值传送给吸取者， 接管者得到的均匀信息量就是求它的数学祈望：
这就是熵的观念。其它一个重要特点是，熵的巨细与字符均匀最短编码长度是一样的（shannon）。设有一个未知的漫衍 p(x),而 q(x) 是我们所得到的一个对 p(x) 的近似，凭证 q(x) 对该随机变量的各个值举办编码，均匀长度比凭证真实漫衍的 p(x) 举办编码要特殊长一些，多出来的长度这就是 KL 散度（之以是不说间隔，是由于不满意对称性和三角形法例），即：
KL 散度又叫相对熵（relative entropy）。相识呆板进修的童鞋应该都知道，在 Softmax 回归（可能 Logistic 回归），最后的输出节点上的值暗示这个样天职到该类的概率，这就是一个概率漫衍。对付一个带有标签的样本，我们祈望的概率漫衍是：分到标签类的概率是 1，?其他类概率是 0。可是抱负很饱满，实际很骨感，我们不行能获得美满的概率输出，能做的就是只管减小总样本的 KL 散度之和（方针函数）。这就是 Softmax 回归可能 Logistic 回归中 Cost function 的优化进程啦。（PS：由于概率和为 1，一样平常的 logistic 二分类的图只画了一个输出节点，潜匿了其它一个） 作者：daniel-D 来历：http://www.cnblogs.com/daniel-D/p/3244718.html （编辑：湖南网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
