精华内容
下载资源
问答
  • 距离和相似度度量方法

    万次阅读 多人点赞 2015-05-11 23:05:12
    在机器学习和数据挖掘中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如 ...根据数据特性的不同,可以采用不同的度量方法。whi...

    http://blog.csdn.net/pipisorry/article/details/45651315

    在机器学习和数据挖掘中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如 K 最近邻(KNN)和 K 均值(K-Means)等等。

    不同距离度量的应用场景

    根据数据特性的不同,可以采用不同的度量方法。which one to use depends on what type of data we have and what our notion of similar is.

    各种“距离”的应用场景简单概括为,空间:欧氏距离,路径:曼哈顿距离,国际象棋国王:切比雪夫距离,以上三种的统一形式:闵可夫斯基距离,加权:标准化欧氏距离,排除量纲和依存:马氏距离,向量差距:夹角余弦,编码差别:汉明距离,集合近似度:杰卡德类似系数与距离,相关:相关系数与相关距离。

    距离度量公理Axioms of Distance Measures

    一般而言,定义一个距离函数 d(x,y), 需要满足下面几个准则:(即距离度量需要满足的性质)

    1) d(x,y) = 0  iff x = y                  // 到自己的距离为0
    2) d(x,y) >= 0                  // 距离非负
    3) d(x,y) = d(y,x)                   // 对称性: 如果 A 到 B 距离是 a,那么 B 到 A 的距离也应该是 a
    4) d(x,k)+ d(k,y) >= d(x,y)    // 三角形法则triangle inequality: (两边之和大于第三边)

    Note: iff =  if and only if

    基础知识:熵与互信息

    [熵与互信息 ]

    文本相似度量方法一览

    此处的“文本”一词涵盖以下两个对象:

    1. 字符串/序列
    2. 包含较多文本内容的文档

    相关的度量方法可以分为两大类,各类下面再有一些具体的分类,比较常用的方法如见下图

    similarity_survey.png

    Note: lz这里LCS也可以认为就是编辑距离吧。

    总的来说,文本相似度量方法可以分为两大类:

    1. String Based,即基于待比较的文本本身中的信息,该类方法评估的是”词法“上的相似性,或说朴素的相似性
    2. Corpus Based,即基于一个较大的文本集合中的信息,该类方法评估的是“语义”上的相似性

    [文本相似度量方法(1): 概览]

    皮皮blog

    欧氏距离度量

    欧拉距离,来自于欧式几何,在数学上也可以成为范数。

    范数Norm

    Lr范数就是x,y每个维度差距上取r次方加和后再开r次方根。Lr norm: what you get by taking the rth power of the differences, summing and taking the rth root.

    给定向量x=(x1,x2,...xn)

    L1范数:向量各个元素绝对值之和,Manhattan distance。

    ║x║1=│x1│+│x2│+…+│xn│

    L2范数:向量各个元素的平方求和然后求平方根,也叫欧式范数、欧氏距离。

    ║x║2=(│x1│2+│x2│2+…+│xn│2)^1/2

    Lp范数:向量各个元素绝对值的p次方求和然后求1/p次方。

    L∞范数:向量各个元素求绝对值,最大那个元素的绝对值。也就是x,y在任意维度上差距最大的那个值。

    ║x║∞=max(│x1│,│x2│,…,│xn│)

    小示例

    Euclidean distance Vs. Non-Euclidean distance 欧氏距离对比非欧氏距离

    dense: 给定两个点,它们的均值也是这个空间的一个点。And there is no reasonable notion of the average of points in the space.欧氏距离可以计算average,但是非欧氏距离却不一定。

    皮皮blog

    非欧氏距离度量

    Jaccard相似度

    一般用于两个一元unary向量(buy or not, click or not)相似性的度量,或者用于集合sets相似性形式定义。

    Note: Jaccard distance = 1 - Jaccard similarity

    分子是集合交集,分母是集合并集。即两个集合间的Jaccard similarity就是它们交集的大小除以它们并集的大小。

    Jaccard相似度没有考虑评分的大小。

    Dice's Coefficient

    Dice(s1,s2)=2*comm(s1,s2)/(leng(s1)+leng(s2))。

    其中,comm (s1,s2)是s1、s2 中相同字符的个数leng(s1),leng(s2)是字符串s1、s2 的长度。

    Dice 系数和 Jaccard 相似性起初被用于生态学上,作为一种判断物种间相似性的方法。在生态学上,要比较两个物种间相似程度时,通常会对该物种的特性进行采样,最后得到各自的特性集合,而 Dice 系数和 Jaccard 相似性都是通过比较两者之间的 共有特性 占比来度量相似性的,因此这两种方法都不是很关心每个 "Term" 的具体量,只是关心有没有某个 "Term"。

    广义Jaccard相似度|Tanimoto系数

    EJ(A,B)=(A*B)/(||A||^2+||B||^2-A*B)

    其中A、B分别表示为两个向量,集合中每个元素表示为向量中的一个维度,在每个维度上,取值通常是[0, 1]之间的值,A*B表示向量乘积,||A||^2表示向量的模,即 ||A||^2 = sqrt (a1^2 + a2^2 + a3^2 + ......)。

    另一种扩展方法,用最大最小值函数来代替乘积和模计算,如下:

    即用向量中每个分量的的最小值和最大值来参与计算。
    个人理解,这个可以做如下解释。当集合A中的元素a1出现C(a1)次的时候,我们可以认为集合中的元素是允许重复存在的,即集合A中有C(a1)个元素;集合B也是这样,有C(b1)个相同的元素,则A和B在这个元素上的交集就是min(a1, b1) ,并集就是max(a1, b1) ,这样上述公式就是利用狭义Jaccard相似度计算的结果。

    Cosine余弦相似度/向量内积

    适合高维度向量vectors的相似度计算。

    1. 两个向量间的余弦值可以很容易地通过使用欧几里得点积和量级公式推导

    \mathbf{a}\cdot\mathbf{b}=\left\|\mathbf{a}\right\|\left\|\mathbf{b}\right\|\cos\theta 

    鉴于两个向量的属性, AB的余弦相似性θ用一个点积形式来表示其大小,如下所示:

    \text{similarity} = \cos(\theta) = {A \cdot B \over \|A\| \|B\|} = \frac{ \sum\limits_{i=1}^{n}{A_i \times B_i} }{ \sqrt{\sum\limits_{i=1}^{n}{(A_i)^2}} \times \sqrt{\sum\limits_{i=1}^{n}{(B_i)^2}} }

    也就是说两个向量的cosin距离就是这两个向量之间的夹角

    Note:  if you project P1 onto P2,the length of the projection is the dot product, divided by the length of P2.Then the cosine of the angle between them is the ratio of adjacent(the dot product divided by P2) over hypotenuse(斜边, the length of P1).

    产生的相似性范围从-1到1:-1意味着两个向量指向的方向正好截然相反,1表示它们的指向是完全相同的,0通常表示它们之间是独立的,而在这之间的值则表示中度的相似性或相异性。

    对于文本匹配,属性向量AB 通常是文档中的词频向量。余弦相似性,可以被看作是一个规范比较文件长度的方法。 在信息检索的情况下,由于一个词的频率(TF-IDF权)不能为负数,所以这两个文档的余弦相似性范围从0到1。并且,两个词的频率向量之间的角度不能大于90°。

    [余弦相似性]

    2. 向量内积是线性代数里最为常见的计算,实际上它还是一种有效并且直观的相似性测量手段。向量内积的定义如下:

    直观的解释是:如果 x 高的地方 y 也比较高, x 低的地方 y 也比较低,那么整体的内积是偏大的,也就是说 x 和 y 是相似的。举个例子,在一段长的序列信号 A 中寻找哪一段与短序列信号 a 最匹配,只需要将 a 从 A 信号开头逐个向后平移,每次平移做一次内积,内积最大的相似度最大。信号处理中 DFT 和 DCT 也是基于这种内积运算计算出不同频域内的信号组分(DFT 和 DCT 是正交标准基,也可以看做投影)。向量和信号都是离散值,如果是连续的函数值,比如求区间[-1, 1] 两个函数之间的相似度,同样也可以得到(系数)组分,这种方法可以应用于多项式逼近连续函数,也可以用到连续函数逼近离散样本点(最小二乘问题,OLS coefficients)中,扯得有点远了- -!。

    向量内积的结果是没有界限的,一种解决办法是除以长度之后再求内积,这就是应用十分广泛的余弦相似度(Cosine similarity):

    余弦相似度与向量的幅值无关,只与向量的方向相关,在文档相似度(TF-IDF)和图片相似性(histogram)计算上都有它的身影。

    cosine similarity的一个扩展是

    Tonimoto系数

    T(A,B) = {A /cdot B /over /|A/|^2 +/|B/|^2 - A /cdot B}

    其实也没什么大不了。T(A,B)的分母是大于等于 cos similarity的分母,但且仅仅但 A,B长度一样是才相等。这就意味着,Tonimoto系数考虑了两个向量的长度差异,长度差异越大相似性约小。

    另外需要注意一点的是,余弦相似度受到向量的平移影响,上式如果将 x 平移到 x+1, 余弦值就会改变。怎样才能实现平移不变性?

    皮尔逊相关系数(Pearson correlation)

    {也叫Centered Cosine,有时候也直接叫相关系数}

    {数值型数据的相关性分析Correlation Analysis (Numerical Data),从下面这个公式看出,它其实就是将数据归一化(数据减去其对应均值)后进行cosine相似度计算,所以叫centered cosine}

    另一种表示方式

    皮尔逊相关系数具有平移不变性和尺度不变性,计算出了两个向量(维度)的相关性。不过,一般我们在谈论相关系数的时候,将 x 与 y 对应位置的两个数值看作一个样本点,皮尔逊系数用来表示这些样本点分布的相关性。

    相关关系度量

    由于皮尔逊系数具有的良好性质,在各个领域都应用广泛,例如,在推荐系统根据为某一用户查找喜好相似的用户,进而提供推荐,优点是可以不受每个用户评分标准不同和观看影片数量不一样的影响。

    相关系数多大才是显著相关?

    相关系数的强弱仅仅看系数的大小是不够的。一般来说,取绝对值后,0-0.09为没有相关性,0.3-弱,0.1-0.3为弱相关,0.3-0.5为中等相关,0.5-1.0为强相关。

    但是,往往你还需要做显著性差异检验,即t-test,来检验两组数据是否显著相关。

    样本书越是大,需要达到显著性相关的相关系数就会越小。所以这关系到你的样本大小,如果你的样本很大,比如说超过300,往往分析出来的相关系数比较低,比如0.2,因为你样本量的增大造成了差异的增大,但显著性检验却认为这是极其显著的相关。
    一般来说,我们判断强弱主要看显著性,而非相关系数本身。但你在撰写论文时需要同时报告这两个统计数据。

    [怎样对数据做相关性检验]

    皮尔逊相关系数的适用范围

    当两个变量的标准差都不为零时,相关系数才有定义,皮尔逊相关系数适用于:

    1. 两个变量之间是线性关系,都是连续数据。
    2. 两个变量的总体是正态分布,或接近正态的单峰分布。
    3. 两个变量的观测值是成对的,每对观测值之间相互独立。

    如何理解皮尔逊相关系数

    rubyist:皮尔逊相关系数理解有两个角度

    其一, 按照高中数学水平来理解, 它很简单, 可以看做将两组数据首先做Z分数处理之后, 然后两组数据的乘积和除以样本数,Z分数一般代表正态分布中, 数据偏离中心点的距离.等于变量减掉平均数再除以标准差.(就是高考的标准分类似的处理)

    样本标准差则等于变量减掉平均数的平方和,再除以样本数,最后再开方,也就是说,方差开方即为标准差,样本标准差计算公式为:

    所以, 根据这个最朴素的理解,我们可以将公式依次精简为:

    其二, 按照大学的线性数学水平来理解, 它比较复杂一点,可以看做是两组数据的向量夹角的余弦。下面是关于此皮尔逊系数的几何学的解释,先来看一幅图,如下所示:

     回归直线: y=gx(x) [红色] 和 x=gy(y) [蓝色]

    如上图,对于没有中心化的数据, 相关系数与两条可能的回归线y=gx(x) 和 x=gy(y) 夹角的余弦值一致。
    对于没有中心化的数据 (也就是说, 数据移动一个样本平均值以使其均值为0), 相关系数也可以被视作由两个随机变量 向量 夹角 的 余弦值(见下方)。
    举个例子,例如,有5个国家的国民生产总值分别为 10, 20, 30, 50 和 80 亿美元。 假设这5个国家 (顺序相同) 的贫困百分比分别为 11%, 12%, 13%, 15%, and 18% 。 令 x 和 y 分别为包含上述5个数据的向量: x = (1, 2, 3, 5, 8) 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。
    利用通常的方法计算两个向量之间的夹角  (参见 数量积), 未中心化 的相关系数是:

    我们发现以上的数据特意选定为完全相关: y = 0.10 + 0.01 x。 于是,皮尔逊相关系数应该等于1。将数据中心化 (通过E(x) = 3.8移动 x 和通过 E(y) = 0.138 移动 y ) 得到 x = (−2.8, −1.8, −0.8, 1.2, 4.2) 和 y = (−0.028, −0.018, −0.008, 0.012, 0.042), 从中

    (4)皮尔逊相关的约束条件

    从以上解释, 也可以理解皮尔逊相关的约束条件:

    • 1 两个变量间有线性关系
    • 2 变量是连续变量
    • 3 变量均符合正态分布,且二元分布也符合正态分布
    • 4 两变量独立

    在实践统计中,一般只输出两个系数,一个是相关系数,也就是计算出来的相关系数大小,在-1到1之间;另一个是独立样本检验系数,用来检验样本一致性。

    Note: lz文本很短,关键词很少的时候,余弦距离就很难计算出准确的相似度。这时候可以使用主题模型。

    皮皮blog

    汉明距离-分类数据点间的距离

    汉明距离(Hamming distance)是指,两个等长字符串(一般适用于bit  vectors)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" 的距离,以为前者相同父节点路径更长。

    编辑距离Edit distance-序列之间的距离

    [编辑距离Edit distance

    kl散度/相对熵/kl距离

    1. 相对熵(relative entropy)又称为KL散度(Kullback–Leibler divergence,简称KLD),信息散度(information divergence),信息增益(information gain)。

    KL散度是两个概率分布P和Q差别的非对称性的度量(designed to measure the difference between probability distributions)。 KL散度是用来 度量使用基于Q的编码来编码来自P的样本平均所需的额外的位元数。 典型情况下,P表示数据的真实分布,Q表示数据的理论分布,模型分布,或P的近似分布。

    定义

    对于离散随机变量,其概率分布PQ的KL散度可按下式定义为

    D_{\mathrm{KL}}(P\|Q) = \sum_i P(i) \ln \frac{P(i)}{Q(i)}

    即按概率P求得的PQ的对数差的平均值。KL散度仅当概率P和Q各自总和均为1,且对于任何i皆满足?及P(i)>0时,才有定义。式中出现0 \ln 0的情况,其值按0处理。

    特性

    1. 相对熵的值为非负数

    D_{\mathrm{KL}}(P\|Q) \geq 0

    吉布斯不等式en:Gibbs' inequality)可知,当且仅当P = Q时DKL(P||Q)为0

    2. 尽管从直觉上KL散度是个度量或距离函数, 但是它实际上并不是一个真正的度量或距离。因为KL散度不具有对称性:从分布P到Q的距离(或度量)通常并不等于从Q到P的距离(或度量)。

    D_{\mathrm{KL}}(P\|Q) \neq D_{\mathrm{KL}}(Q\|P)

    L散度是不对称的,当然,如果希望把它变对称,

    Ds(p1, p2) = [D(p1, p2) + D(p2, p1)] / 2

    [KL散度]

    [相对熵]

    2. 概率分布之间的距离

    实际上两个概率分布之间的距离是可以测量的。在统计学里面经常需要测量两组样本分布之间的距离,进而判断出它们是否出自同一个 population,常见的方法有卡方检验(Chi-Square)和 KL 散度( KL-Divergence),下面说一说 KL 散度吧。

    先了解一下前面的基础知识[信息熵-信息熵的来源],而KL 散度又叫相对熵(relative entropy)。了解机器学习的童鞋应该都知道,在 Softmax 回归(或者 Logistic 回归),最后的输出节点上的值表示这个样本分到该类的概率,这就是一个概率分布。对于一个带有标签的样本,我们期望的概率分布是:分到标签类的概率是 1, 其他类概率是 0。但是理想很丰满,现实很骨感,我们不可能得到完美的概率输出,能做的就是尽量减小总样本的 KL 散度之和(目标函数)。这就是 Softmax 回归或者 Logistic 回归中 Cost function 的优化过程啦。(PS:因为概率和为 1,一般的 logistic 二分类的图只画了一个输出节点,隐藏了另外一个)

    [KL散度(Kullback-Leibler_divergence)]

    kl散度的python+scipy实现

    {计算topic_word分布矩阵所有topic_word分布两两之间的相似度-kl散度}

    1.

    # 方法1(pdist只能计算对称kl散度)
    topic_similar_mat = spatial.distance.pdist(tw_dist_ndaray,
                                               metric=lambda P, Q: ((sum(kl_div(P, Q)) + sum(kl_div(Q, P))) / 2))

    2.

    def kl(P, Q):
        '''
        计算两个ndarray的kl散度
        KL散度仅当概率P和Q各自总和均为1,且对于任何i皆满足Q(i)>0及P(i)>0时,才有定义
        '''
        return sum(P * log(P / Q)) if (P > 0).all() and (Q > 0).all() else None
        # return sum(where((P > 0).all() and (Q > 0).all(), P * log(P / Q), None), axis=0)
    
    #方法2(对称kl散度,自定义kl函数)
    topic_similar_mat = spatial.distance.pdist(tw_dist_ndaray,
                                                   metric=lambda P, Q: ((kl(P, Q) + kl(Q, P)) / 2))

    Note: kl散度可以通过scipy包的stats.entropy计算[Scipy教程 - 统计函数库scipy.stats ]

    3.# 方法3(非对称kl散度)
    topic_similar_mat = zeros([len(tw_dist_ndaray), len(tw_dist_ndaray)])
    for i_id, i in enumerate(tw_dist_ndaray):
        for j_id, j in enumerate(tw_dist_ndaray):
            if i_id != j_id:
                topic_similar_mat[i_id, j_id] = stats.entropy(tw_dist_ndaray[i_id], tw_dist_ndaray[j_id])

    4.topic_similar_mat[i_id, j_id] = sum(kl_div(tw_dist_ndaray[i_id], tw_dist_ndaray[j_id]))

    Note:

    1. 计算出的结果自己和自己的kl散度为0,为了排序计算与别人的相似度应该将对角线中的元素改为max

    topic_similar_mat = spatial.distance.squareform(topic_similar_mat)
    max_dist = topic_similar_mat.max()
    for i in range(len(topic_similar_mat)):
        topic_similar_mat[i, i] = max_dist+1
    print(topic_similar_mat)

    2. 非对称kl散度不是对称的,而用pdist计算出的topic_similar_mat一定是对称的,因为pdist只计算上三角,所以使用pdist必须要用对称的kl散度

    [Computation of Kullback-Leibler (KL) distance between text-documents using numpy]

    [http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.stats.entropy.html]

    闵可夫斯基距离

    闵可夫斯基距离(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)了。

    马氏距离

    马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性和尺度不同的性质。马氏距离的变换和 PCA 分解的白化处理颇有异曲同工之妙,不同之处在于:就二维来看,PCA 是将数据主成分旋转到 x 轴(正交矩阵的酉变换),再在尺度上缩放(对角矩阵),实现尺度相同。而马氏距离的 L逆矩阵是一个下三角,先在 x 和 y 方向进行缩放,再在 y 方向进行错切(想象矩形变平行四边形),总体来说是一个没有旋转的仿射变换。

    考虑下面这张图,椭圆表示等高线,从欧几里得的距离来算,绿黑距离大于红黑距离,但是从马氏距离,结果恰好相反:

    假设样本点(列向量)之间的协方差对称矩阵是  , 通过 Cholesky Decomposition(实际上是对称矩阵 LU 分解的一种特殊形式,可参考博客)可以转化为下三角矩阵和上三角矩阵的乘积:  。消除不同维度之间的相关性和尺度不同,只需要对样本点 x 做如下处理: 。处理之后的欧几里得距离就是原样本的马氏距离(为了书写方便,这里求马氏距离的平方):

    Note: 这个也正是多维高斯分布的指数项的二次型,即高斯对于x的依赖的二次型表达。当为单位矩阵时,马氏距离就变成了欧氏距离。

    下图蓝色表示原样本点的分布,两颗红星坐标分别是(3, 3),(2, -2):

    由于 x, y 方向的尺度不同,不能单纯用欧几里得的方法测量它们到原点的距离。并且,由于 x 和 y 是相关的(大致可以看出斜向右上),也不能简单地在 x 和 y 方向上分别减去均值,除以标准差。最恰当的方法是对原始数据进行 Cholesky 变换,即求马氏距离(可以看到,右边的红星离原点较近):

    将上面两个图的绘制代码和求马氏距离的代码贴在这里,以备以后查阅:

    import numpy as np
    import pylab as pl
    import scipy.spatial.distance as dist
    def plotSamples(x, y, z=None):
        stars = np.matrix([[3., -2., 0.], [3., 2., 0.]])
        if z is not None:
            x, y = z * np.matrix([x, y])
            stars = z * stars
        pl.scatter(x, y, s=10)    # 画 gaussian 随机点
        pl.scatter(np.array(stars[0]), np.array(stars[1]), s=200, marker='*', color='r')  # 画三个指定点
        pl.axhline(linewidth=2, color='g') # 画 x 轴
        pl.axvline(linewidth=2, color='g')  # 画 y 轴
        pl.axis('equal')
        pl.axis([-5, 5, -5, 5])
        pl.show()
    # 产生高斯分布的随机点
    mean = [0, 0]      # 平均值
    cov = [[2, 1], [1, 2]]   # 协方差
    x, y = np.random.multivariate_normal(mean, cov, 1000).T
    plotSamples(x, y)
    covMat = np.matrix(np.cov(x, y))    # 求 x 与 y 的协方差矩阵
    Z = np.linalg.cholesky(covMat).I  # 仿射矩阵
    plotSamples(x, y, Z)
    # 求马氏距离 
    print '\n到原点的马氏距离分别是:'
    print dist.mahalanobis([0,0], [3,3], covMat.I), dist.mahalanobis([0,0], [-2,2], covMat.I)
    # 求变换后的欧几里得距离
    dots = (Z * np.matrix([[3, -2, 0], [3, 2, 0]])).T
    print '\n变换后到原点的欧几里得距离分别是:'
    print dist.minkowski([0, 0], np.array(dots[0]), 2), dist.minkowski([0, 0], np.array(dots[1]), 2)

    皮皮blog

    其它距离度量方法

    卡方检验[概率论:假设检验-t检验、卡方检验和AD-Fuller test ]

    mutual information

    Spearman's rank coefficient

    Earth Mover's Distance

    SimRank 相似:SimRank 迭代算法

    SimRank来自图论,说两个变量相似,因为他们链接了同一个或相似的节点。

    [漫谈:机器学习中距离和相似性度量方法]

    大规模相似度计算方法

    [大规模数据相似度计算时,解决数据倾斜的问题的思路之一(分块思想)]

    皮皮blog

     径向基函数核

    径向基函数核(Radial Basis Function, RBF kernel),也被称为高斯核(Gaussian kernel)或平方指数核(Squared Exponential., SE kernel) [1]



     ,是常见的核函数(kernel function)。

    关于两个样本x和x'的RBF核可表示为某个输入空间(input space)的特征向量,它的定义如下:

    上面的分子部分 可以看做两个特征向量之间的平方欧氏距离。sigma 是一个自由参数。

    因为RBF核函数的值随距离减小,并介于0(极限)和1(当x=x'的时候)之间,所以它是一种现成的相似性度量表示法。

    核的特征空间有无穷多的维数;例如sigma=1时,其展开式为: 

     [径向基函数核]

    为何要选用核函数?

    获取非线性的方式[核函数与径向基函数详解]

    高斯距离示例

    #根据高斯距离进行高斯坐标转换
    def guass_kernel_trans(x, centers):
        '''
        坐标映射:x中的每一行都转换成centers坐标系,即x中的每一行与centers一一作guass_kernel转换,从x的维度d转换成centers维度nc。
        :param x: 2d array (nx,d)
        :param centers: 2d array (nc,d)
        :return: 2d array
        '''
        import numpy as np
        x = np.asarray(x)
        centers = np.asarray(centers)
        x_t_guass = np.exp(-(np.sum(x ** 2, 1, keepdims=True).repeat(centers.shape[0], axis=1) +
                             np.sum(centers ** 2, 1, keepdims=True).repeat(x.shape[0], axis=1).transpose() -
                             x.dot(centers.transpose()) * 2))
        # exp内部是负平方欧氏距离
        # print(x_t_guass)
        x_t_guass = x_t_guass / x_t_guass.sum(axis=1, keepdims=True)

        #np.asarray([i / sum(i) for i in x_t_guass])
        return x_t_guass


    userEmb = [[0.84, 0.8, 0.11, 0.85, 0.76, 0.1, 0.61, 0.6]]

    Xc = [[0.84, 0.8, 0.11, 0.85, 0.76, 0.1, 0.61, 0.6], [0.77, 0.77, 0.2, 0.74, 0.6, 0.21, 0.69, 0.48]]

    # print(guass_kernel_trans(userEmb, Xc))
    Xc_ = guass_kernel_trans(Xc, Xc)
    # print(Xc_)

    距离函数的等价性

    文本语料上训练出来的特征向量习惯采用余弦距离,图片或视频上提取的特征向量一般采用欧氏距离。此外,还有特殊场景下定制的各种距离函数,此处介绍一个在搜索排序场景中使用的angular相似度度量函数,其可有效放大被召回的头部样本点之间的差异。

    归一化向量之间的余弦距离可以跟欧氏距离进行直接转换,即euclidean_distance^2 = 1 - 2 * cosine_distance。所以很多代码在实现欧氏距离时先做归一化再直接相乘。

    Note: 归一化向量之间的余弦距离可以跟欧氏距离进行直接转换是因为: 归一化的x^2=y^2=1,则到|x-y|^2 = 2-2x*y;通过绘图也可以看出。

    ANN召回场景下:1)即使不做归一化,也可以直接让欧氏距离与余弦距离建立等价关系;2)任意向量内积的结果可与欧氏距离建立等价关系。

    ANN中按欧氏距离计算出的近似K近邻点与按内积或余弦距离计算出来的近似K近邻点结果相同,所要做的仅仅是对所有待检索的向量做预处理即可,找出最大的常数φ,然后构造一个维度+1的新向量。

    论文Speeding Up the Xbox Recommender System Using a Euclidean Transformation for Inner-Product Spaces

    [距离函数的等价性]

    非欧氏距离及其满足公理性质的证明

    Jaccard Dist

    Note: Proof中使用反证法:两个都不成立,即都相等时,minhash(x)=minhash(y)了。

    Cosine Dist余弦距离

      

    Note: vectors here are really directions, not magnitudes.So two vectors with the same direction and different magnitudes are really the same vector.Even to vector and its negation, the reverse of the vector,ought to be thought of as the same vector.

    Edit distance编辑距离

    Hamming distance汉明距离

    from:距离和相似度度量方法_皮皮blog-CSDN博客_相似度度量方法

    ref: 如何计算两个文档的相似度

    Machine Learning: Measuring Similarity and Distance

    What is Mahalanobis distance?

    Cosine similarity, Pearson correlation, and OLS coefficients

    机器学习中的相似性度量

    展开全文
  • 节点中心度量

    万次阅读 2019-02-27 10:14:09
    1.Centrality度量方法:Degree Degree是运用最广泛的centrality之一,因为它计算简单,可理解性强 局限:邻接节点的重要性没有考虑 举个例子,微博上某账户买僵尸粉增加粉丝量,可以使该账户节点的in-degree非常大...

    中心性(centrality):哪个节点的影响力更大?
    1.Centrality度量方法:Degree
    在这里插入图片描述
    Degree是运用最广泛的centrality之一,因为它计算简单,可理解性强

    局限:邻接节点的重要性没有考虑
    举个例子,微博上某账户买僵尸粉增加粉丝量,可以使该账户节点的in-degree非常大,但是并不意味着该节点的影响力就大。

    2.Centrality度量方法:Eigenvector
    影响力大的人不仅仅是朋友多,而且他的朋友也是重要的
    在这里插入图片描述
    在这里插入图片描述
    可以看出,v7节点的重要性,是由和它相边的v1,v4,v6三个节点的重要性来决定的,也就是说,如果v1,v4,v6的重要性越高,那么v7节点的重要性也就越高。
    其中,? 是矩阵的特征根

    3.Centrality度量方法:Katz
    eigenvector方法在无向图上的表现非常优异
    但当出现在有向无环图时,其中节点 eigenvector centrality变成0
    在这里插入图片描述
    Katz提出了一个改进方法,即每个节点初始就有一个centrality值
    这样,上图中v6和v5节点的centrality计算方法就变成了:
    在这里插入图片描述
    4.Centrality度量方法:PageRank
    Katz在计算时,每条出边都会带上起始节点的完整中心性值,这是否合理呢?
    显然是不合理的,举个例子,导航网站hao123,它指向了许多其它网站,在katz方法中,该网站每条出边的值都是一样的,但显然,雅虎和其它小网站的重要性是不一样的。

    为此,Google的Larry Page对Katz的方法提出了进一步的改进,称为PageRank算法。

    PageRank算法在Katz的基础上,假设一个节点的出度是n,刚每条出边附上1/n的起始节点的中心度量值
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    进行了一轮迭代计算之后
    在这里插入图片描述
    经过多轮迭代,直到centrality值收敛,即得到每个节点的centrality

    5.Centrality度量方法:Betweenness
    betweenness则从路径这个维度来度量节点的centrality.

    对于网络中的两个节点A和B,他们之间的最短路径可能有很多条。计算网络中任意两个节点的所有最短路径,如果这些最短路径中有很多条都经过了某个节点,那么就认为这个节点的Betweenness Centrality高
    在这里插入图片描述
    在这里插入图片描述
    从直观上讲,图中左边的这些节点和右边的这些节点都必须通过A ,F两个点来连接。因此这两个点的betweenness centrality也会更高。

    6.Centrality度量方法:Closeness
    Closeness的centrality 度量方法思想是:如果节点到图中其它节点的最短距离都很小,那么我们认为该节点的Closeness Centrality高。

    在这里插入图片描述
    这个定义其实比Degree Centrality从几何上更符合中心度的概念,因为到其它节点的平均最短距离最小,意味着这个节点从几何角度看是出于图的中心位置。

    举个例子,在社交网络中,Closeness Centrality高的节点一般扮演的是八婆的角色(gossiper)。他们并不是明星,但是乐于在不同的人群之间传递消息。

    想获取更多信息

    展开全文
  • 2.3距离度量方法

    2018-06-30 23:53:13
    距离度量方法 假设对于像素P(Xp,Yp), Q(Xq,Yq),R(Xr,Yr)而言,若函数D满足如下三个条件,则函数D可被称为距离函数或度量。 1、D(P,Q)&gt;=0,当且仅当P=Q时有D(P,Q) = 0 2、D(P,Q) = D(Q,P) 3、D(P,Q) =...

    距离度量方法

    假设对于像素P(Xp,Yp), Q(Xq,Yq),R(Xr,Yr)而言,若函数D满足如下三个条件,则函数D可被称为距离函数或度量。
    1、D(P,Q)>=0,当且仅当P=Q时有D(P,Q) = 0
    2、D(P,Q) = D(Q,P)
    3、D(P,Q) =< D(P,R) + D(R,Q)

    常见的几个距离函数有

    1、欧式距离

    这里写图片描述
    其距离等于r的像素形成以P为圆心的圆。

    2、D4距离(街区距离)

    这里写图片描述
    即距离等于r的像素形成以P为中心的菱形。

    3、D8距离(棋盘距离)

    这里写图片描述
    即距离等于r的像素形成以P为中心的方形。

    距离度量参数可以用于对图像特征进行比较、分类或者进行某种像素级操作。最常用的距离度量是欧式距离,然而在形态学中,也可能使用街区距离和棋盘距离。

    示例演示

    我们实现一个功能,输入一个彩色图像,输出一个相同大小的二值图像,二值图像每个像素由彩色图像每个像素颜色和我们设置的目标颜色的距离决定,距离大于100,则为白色,否则为黑色。

    我们利用D4距离来算颜色距离,主要代码如下:

    i

    nt MainWindow::getD4Distance(const cv::Vec3b &color, const cv::Vec3b& target) const
    {
        return abs(color[0]- target[0]) + abs(color[1]-target[1]) + abs(color[2]- target[2]);
    }

    运行结果:

    输入图像
    这里写图片描述
    处理后
    这里写图片描述

    展开全文
  • 为了降低内容中心网络的缓存内容冗余度和提高缓存内容命中率,提出一种基于节点中心度量的缓存机制(CMC)。CMC利用控制器获取整个网络的拓扑结构和缓存空间空闲率,根据拓扑的连接关系分别计算各节点的度中心性、...
  • 数据挖掘中的度量方法

    千次阅读 2017-12-02 22:20:13
    通常使用距离作为数据之间相似性或相异性的度量方法,常用的度量方法有欧式距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离、汉明距离、余弦距离、马氏距离、Jaccard系数、相关系数、信息熵。 欧式距离  nn维...

    原文站点:https://senitco.github.io/2017/05/24/measurement-method/

      在数据挖掘中,无论是对数据进行分类、聚类还是异常检测、关联性分析,都建立在数据之间相似性或相异性的度量基础上。通常使用距离作为数据之间相似性或相异性的度量方法,常用的度量方法有欧式距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离、汉明距离、余弦距离、马氏距离、Jaccard系数、相关系数、信息熵。


    欧式距离

       n 维空间中两个样本点x y 之间的欧几里得距离定义如下:

    d(x,y)=Σnk=1(xkyk)2

    标准化欧式距离公式如下:

    d(x,y)=Σnk=1(xkyksk)2

    式中, sk 为数据每一维的方差,标准化欧式距离考虑了数据各维分量的量纲和分布不一样,相当于对每维数据做了标准化处理。欧式距离适用于度量数据属性无关、值域或分布相同的数据对象。

    曼哈顿距离

      曼哈顿距离也称为街区距离,计算公式如下:

    d(x,y)=Σnk=1|xkyk|

    切比雪夫距离

    d(x,y)=limn(Σnk=1(|xkyk|)r)1r=maxk(|xkyk|)

    上面两个公式是等价的。

    闵可夫斯基距离

    d(x,y)=(Σnk=1(|xkyk|)r)1r

    式中,r是一个可变参数,根据参数r取值的不同,闵可夫斯基距离可以表示一类距离
      r = 1时,为曼哈顿距离
      r = 2时,为欧式距离
      r →∞时,为切比雪夫距离
    闵可夫斯基距离包括欧式距离、曼哈顿距离、切比雪夫距离都假设数据各维属性的量纲和分布(期望、方差)相同,因此适用于度量独立同分布的数据对象。

    汉明距离

      两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数,也就是将一个字符串变换为另一个字符串所需要替换的最小字符个数,例如

    HammingDistance(1001001,0101101)=3

    汉明距离常用于信息编码中。

    余弦距离

      余弦相似度公式定义如下:

    cos(x,y)=xy|x||y|=Σnk=1xkykΣnk=1x2kΣnk=1y2k

    余弦相似度实际上是向量 x y夹角的余弦度量,可用来衡量两个向量方向的差异。如果余弦相似度为 1 ,则x y 之间夹角为0°,两向量除模外可认为是相同的;如果预先相似度为 0 ,则x y 之间夹角为90°,则认为两向量完全不同。在计算余弦距离时,将向量均规范化成具有长度 1 ,因此不用考虑两个数据对象的量值。
    余弦相似度常用来度量文本之间的相似性。文档可以用向量表示,向量的每个属性代表一个特定的词或术语在文档中出现的频率,尽管文档具有大量的属性,但每个文档向量都是稀疏的,具有相对较少的非零属性值。

    马氏距离

      马氏距离的计算公式如下:

    mahalanobis(x,y)=(xy)Σ1(xy)T

    式中, Σ1 是数据协方差矩阵的逆。
    前面的距离度量方法大都假设样本独立同分布、数据属性之间不相关。马氏距离考虑了数据属性之间的相关性,排除了属性间相关性的干扰,而且与量纲无关。若协方差矩阵是对角阵,则马氏距离变成了标准欧式距离;若协方差矩阵是单位矩阵,各个样本向量之间独立同分布,则变成欧式距离。

    Jaccard系数

      Jaccard系数定义为两个集合A和B的交集元素在其并集中所占的比例,即

    J(A,B)=ABAB

    对于两个数据对象 x y,均由 n 个二元属性组成,则
    J=f11f01+f10+f11

    式中, f11 x 1 y 1的属性个数, f01 x 0 y 1的属性个数, f10 x 1 y 0的属性个数。
    Jaccard系数适用于处理仅包含非对称的二元属性的对象。
    广义Jaccard系数定义如下:
    EJ(x,y)=xyx2+y2xy

    广义Jaccard系数又称为Tanimoto系数,可用于处理文档数据,并在二元属性情况下归约为Jaccard系数。

    相关系数

      两个数据对象之间的相关性是对象属性之间线性关系的度量,计算公式如下

    ρxy=sxysxsy

    sxy=1n1Σnk=1(xkx¯)(yky¯)

    sx=1n1Σnk=1(xkx¯)2

    sy=1n1Σnk=1(yky¯)2

    x¯=1nΣnk=1xk,y¯=1nΣnk=1yk

    相关系数是衡量数据对象相关程度的一种方法,取值范围为 [1,1] 。相关系数的绝对值越大,则表明 x y相关度越高。当 x y线性相关时,相关系数取值为 1 (正线性相关)或1(负线性相关);线性无关时取值为 0 。在线性回归中,使用直线拟合样本点,可利用相关系数度量其线性性。

    信息熵

      信息熵描述的是整个系统内部样本之间的一个距离,是衡量分布的混乱程度或分散程度的一种度量。样本分布越分散(或者说分布越平均),信息熵越大;分布越有序(或者说分布越集中),信息熵就越小。给定样本集X的信息熵公式定义如下:

    Entropy(X)=Σni=1pilog2(pi)

    式中, n 为样本集的分类数,pi为第 i 类元素出现的概率。当S n 个分类出现的概率一样大时,信息熵取最大值log2(n)。当 X 只有一个分类时,信息熵取最小值0。信息熵用于度量不确定性,在决策树分类中,信息熵可用于计算子树划分前后的信息增益作为选择最佳划分的度量。

    展开全文
  • 基于中心Copula函数相似性度量的时间序列聚类方法.pdf
  • 行业分类-物理装置-一种基于局部方向中心度量的聚类方法.zip
  • 距离及相似度度量方法

    万次阅读 2016-12-22 17:51:48
    前言关于距离度量的方法的专题其实已经想...本文涵盖一下几个度量方法:欧氏距离; 曼哈顿距离; 切比雪夫距离; 闵可夫斯基距离; 标准化欧氏距离; 马氏距离; 巴氏距离 汉明距离; 夹角余弦; 相关系数与相关距离。
  • 给出一种面向Artifact的业务流程行为相似性度量方法.首先,通过测量流程模型之间关键Artifact的相似性来评估流程处理的核心业务数据的相似度.其次,根据关键Artifact生命周期特性,测量任务执行路径中任务依赖关系的...
  • 中心趋势度量度量数据散布

    千次阅读 2015-06-16 16:27:16
    中心趋势度量 中心趋势度量主要包括:均值,中位数,众数,中列数 例:属性salary(单位千美元),以递增方式排列:30,31,47,50,52,52,56,60,63,70,70,110 1:均值 数据集中心最常用,最有效的数值度量是(算术...
  • 【转载】社会网络中心度量

    千次阅读 2015-11-28 20:29:16
    社会网络中心度量
  • 聚类方法——簇间距离度量方法

    千次阅读 2019-12-17 14:37:34
     优缺点同全链接算法,往往被认为最常用也最好用的方法。 4. 中心距离 5. 离差平方和  簇类C1和C2的距离等于两个簇类所有样本对距离平方和的平均。优缺点同全连接。   引自: 层次聚类算法...
  • 在数据分析和数据挖掘的过程...当然衡量个体差异的方法有很多,这里整理罗列下。 =============距离度量,越小越相似 1 曼哈顿距离 即曼哈顿街道距离(出租车距离)。向量对应元素差值的绝对值之和。 2 欧氏距...
  • 距离计算与相似性度量方法

    千次阅读 2018-10-17 09:51:46
    0. 前言 在机器学习和数据挖掘中,我们经常...根据数据特性的不同,可以采用不同的度量方法。 1. 基本性质与名词解释 1.1 基本性质 用表示“距离度量”(distance measure),一般需满足一些基本性质: 非负性: 同一...
  • 聚类分析中距离度量方法比较

    万次阅读 2018-08-08 15:28:06
    聚类分析中如何度量两个对象之间的相似性呢?一般有两种方法,一种是对所有对象作特征投影,另一种则是距离计算。前者主要从直观的图像上反应对象之间的相似度关系,而后者则是通过衡量对象之间的差异度来反应对象...
  • 网站访问统计术语和度量方法

    千次阅读 2012-01-10 12:56:38
     中国互联网络信息中心(CNNIC)是成立于1997年6月3日的非盈利管理与服务机构,行使国家互联网络信息中心的职责。其宗旨是为我国互联网络用户服务,促进我国互联网络健康、有序地发展。随着互联网络在国内的飞速发展...
  • matlab提取文件要素代码图中心度量矩阵 社交网络分析分配 使用MatLab的共同作者网络分析 ICMB于2002年在雅典成立,后来发展成为主要的移动业务国际研究会议,有大量的研究人员和作者为学术界提供了最先进的科学论文...
  • 检索性能的评估步骤,针对度量数据给出了成功搜索度量方法,并通过度量平台的实现验证了该度量方法的实践意 义. 关键词: 搜索引擎; 检索性能度量; 用户路径; 成功搜索 中图分类号: TP311 文献标识码: A 文章编号: ...
  • 网络分析中,经常会用到中心性这个概念。通常在中心性的分析角度上有两种出发点:中心度和中心势。...目前有四种中心性的分析方法,分别是:度中心性(degree centrality),间接中心性(betweenness centrali...
  • 常用相似性(距离)度量方法概述

    千次阅读 2020-08-12 11:00:45
    距离度量(Distance)用于衡量个体在空间上存在的距离,距离越远说明个体间的差异越大。 2.1. 曼哈顿距离(Manhattan Distance) 在曼哈顿要从一个十字路口开车到另外一个十字路口,实际驾驶距离就是这个“曼哈顿距离...
  • 计算网络中心性的 Matlab 函数: Nobelity 根据算术平均距离... HarmonicCentrality 根据调和平均距离计算替代的中心度量。 HarmonicNobelity 计算到所选节点的调和平均距离。 对于有向图,函数计算紧密度或外紧密度。
  • 软件度量——方法

    2006-04-21 08:52:00
    原文来自 "现代软件工程" 周之英编著 (上)软件度量的一些方法在前面我们已介绍了组成软件度量的几个方面。在这里我们将先给出关于这几个方面的一个纲要介绍。在后面我们还会作进一步具体的阐述。当我们不从高层次的...
  • 由标准化数据和中心化数据(即原始数据与均值之差)计算出的二点之间的马氏距离相同。马氏距离还可以排除变量之间的相关性的干扰。缺点:它的缺点是夸大了变化微小的变量的作用。 6. 夹角余弦(Cosine) 也可以叫余弦...
  • 本文报告了社交网络的模拟研究,该研究调查了网络拓扑如何与系统级节点中心度量的稳健性相关。 理解这种关联很重要,因为为社交网络分析收集的数据通常有些错误,并且可能在未知程度上歪曲实际的真实网络。 因此,...
  • 软件度量的一些方法

    千次阅读 2015-06-05 09:58:20
    软件度量的一些方法http://cuiyingfeng.blog.51cto.com/43841/6775/在前面我们已介绍了组成软件度量的几个方面。在这里我们将先给出关于这几个方面的一个纲要介绍。在后面我们还会作进一步具体的阐述。当我们不从高...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,740
精华内容 21,096
关键字:

中心度量方法