(南京数据挖掘群)
(小盆友玩泥沙)
第三方登录：下次自动登录
现在的位置:
& 综合 & 正文
机器学习如何度量相似性 Cosine
夹角余弦(Cosine)
几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。
(1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式：
(2) 两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦。类似的，对于两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)，可以使用类似于夹角余弦的概念来衡量它们间的相似程度。
夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。
夹角余弦的具体应用可以参阅参考文献[吴军. 数学之美 系列 12 - 余弦定理和新闻的分类.]。
(3)Matlab计算夹角余弦
例子：计算(1,0)、( 1,1.732)、( -1,0)两两间的夹角余弦
X = [1 0 ; 1 1.732 ; -1 0]
D = 1- pdist(X, 'cosine')
% Matlab中的pdist(X, 'cosine')得到的是1减夹角余弦的值
pdist的函数的详解，见博客
这里我们还要用到一个函数 squareform,把行向量，变为举证D ,其中D(i,j)
D(j,i)代表 i 和j 的相似度/距离。
&& X = [1 0 ; 1 1.732 ; -1 0]
&& D = 1- pdist(X, 'cosine')
&& squareform(D)
&&&&推荐文章:
【上篇】【下篇】基于机器学习的用户行为异常检测
基于机器学习的用户行为异常检测
摘& 要： 对Lane T等人提出的IDS用户行为异常检测模型进行了简要介绍，在此基础上提出一种新的检测模型，此模型利用多种长度不同的shell命令序列表示用户的行为模式，建立多个样本序列库来描述正常用户的行为轮廓。检测时，采用序列匹配的方法挖掘用户命令流中的行为模式，以行为模式所对应的长度可变的命令序列为单位进行相似度赋值，并将加窗滤噪后的相似度作为用户身份的判决依据。基于UNIX用户shell命令数据的实验表明，同Lane T等人的检测模型相比，新的检测模型具有更高的检测性能。
关键词： IDS；异常检测；行为模式；机器学习；相似度
中图分类号：TP18；TP393.08&&&&& 文献标识码：A
Anomaly Detection of User Behaviors Based on Machine Learning
SUN Hong-wei，TIAN Xin-guang， ZHANG Er-yang
(1.School of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China；
&&&&&&&&&&&&&&&&&&&&&&& 2. Putian Telecom Corporation, Beijing 100088, China)
Abstract： Anomaly detection acts as one of the important directions of research on Intrusion Detection Systems (IDSs). In this paper, an anomaly detection model originated mainly by Terran Lane is briefly introduced. Then a new anomaly detection model based on machine learning is presented. The model uses shell command sequences of variable length to represent a valid user’s behavior patterns and uses more than one dictionaries of shell command sequences to build the user’s behavior profile. While performing detection, the model digs behavior patterns by sequence matching method and evaluates the similarities of the corresponding command sequences to the dictionaries. The two models are tested with UNIX users’ shell command data. The results show that the new model originated by us has higher detection performance.
Key words： IDS； anomaly detection； behavior pattern； machine learning； similarity measure
目前，异常检测是入侵检测系统（IDS）研究的主要方向，这种检测技术建立系统或用户的正常行为模式，通过被监测系统或用户的实际行为模式和正常模式之间的比较和匹配来检测入侵，其特点是不需要过多有关系统缺陷的知识，具有较强的适应性，并且能够检测出未知的入侵模式。虚警概率高是目前限制异常检测应用的主要因素。异常检测的关键问题在于正常行为模式（库）的建立以及如何利用该模式（库）对当前行为进行比较和判断。
国内外已经开展了神经网络、机器学习等智能技术在异常检测中的应用研究，研究目标主要是提高检测系统的准确性、实时性、高效性以及自适应性，其中一些研究成果在检测性能和可操作性上已接近或达到了实用化水平。本文介绍了Lane T等人提出的基于机器学习的IDS用户行为异常检测模型，在其基础上提出一种新的检测模型，此模型用多种长度不同的shell命令序列表示用户行为模式，建立多个样本序列库来描述正常用户的行为轮廓，检测时以长度可变的命令
序列为单位进行相似度赋值，并将加窗滤噪后的相似度作为用户身份的判决依据。利用UNIX用户shell命令数据进行的实验表明，新的检测模型具有很高的检测性能和较强的可操作性。
2& 基于机器学习的定长命令序列检测模型
2.1 机器学习基本原理
机器学习是人工智能的一个新的分支，它是通过对人类认知机理的研究，借助机器（计算机系统）建立各种学习模型，赋予机器学习的能力，在此基础上构建具有特定应用的面向任务的学习系统。一个机器学习系统主要有学习单元、知识库、执行单元组成，其中学习单元利用外界信息源提供的信息来建立知识库并对其做出改进（增加新知识或重新组织已有知识），执行单元利用知识库中的知识执行任务，任务执行后的信息又反馈给学习单元作为进一步学习的输入。学习单元是机器学习系统实现学习功能的核心部分，它涉及处理外界信息的方式以及获取新知识过程中所用的方法。知识库用来存储知识，包括系统原有的领域知识（这种知识是长期的、相对稳定的），以及通过学习而获得的各种新知识（这种知识是短期的、变化的），选择何种知识表示对学习系统的设计起着非常重要的作用。执行单元是使学习系统具有实际用途，同时又能够评价学习方法好坏的关键部分。
机器学习研究中的很大一部分工作集中在分类和问题求解这两个领域；经过三十多年的发展，目前已有了很多学习方法，如归纳学习、实例学习、遗传学习等，但这些方法均有其局限性，结合具体的应用领域探讨新的学习方法和算法是目前的研究主流。
2.2 定长命令序列检测模型的描述
美国Purdue大学的Lane T等人提出了一种基于机器学习的用户行为异常检测模型，并对模型进行了深入的研究和实验。其模型利用长度固定的shell命令序列表示用户的行为模式，建立样本序列库来描述正常用户的行为轮廓；工作时，将被监测用户的命令序列同正常用户的样本命令序列库进行比较和匹配，根据两者的相似度对被监测用户的身份进行判断。模型的要点简述如下[2]：
（1）将长度固定的shell命令序列作为描述用户行为模式的最小数据单元，采用实例学习方法建立正常用户的样本序列库（知识库）。
（2）定义两序列之间的相似度，它用于表示两个序列所代表的行为模式之间的相似程度。在此基础上，定义一个序列同样本序列库的相似度，它用于表示此序列所代表的行为模式同正常用户各种行为模式之间的最大相似程度。
（3）模型工作时，计算被监测用户序列流中的每个序列同正常用户样本序列库的相似度，然后，对相似度进行加窗滤噪处理，得到按时间顺序排列的相似度判决值，根据判决值的大小对被监测用户的身份进行实时判决。
模型中有以下几个关键问题：一、最佳序列长度的选择；二、样本序列的提取；三、相似度函数的定义；四、滤噪算法的选择。Lane T等人针对以上问题利用UNIX用户的shell命令数据做了大量实验，以下是他们得出的结论：
（1）最佳序列长度同具体用户的行为特点有关。随着序列长度的增大（从1到15），模型的检测性能随用户的不同而呈现出不同的变化趋势。
&&& （2）在各种相似度函数中，关心相邻命令之间相关性的相似度函数对应的检测性能优于不考虑相关性的相似度函数。均值滤噪和中值滤噪算法[2]对应的检测性能差别不大。
（3）在聚类、按出现概率提取、按时间顺序截取、随机选择等样本序列提取方法中，聚类方法对不同用户的适应性要强一些，但实现起来最复杂。
3& 基于机器学习的变长命令序列检测模型
3.1& 变长命令序列检测模型的描述
Lane T等人提出的定长命令序列检测模型主要有两个缺点：一、在用户行为模式的表示上缺乏灵活性和适应性。行为模式是指用户操作过程中体现出的某种规律性；实际中，不同用户所具有的行为模式存在差异，同一用户完成不同行为模式时所执行的命令个数也不尽相同，因而，用长度固定的命令序列难以全面准确地表示出用户的整体行为轮廓。二、不容易估算针对具体用户的最佳序列长度。Lane T等人主要采用实验方法来确定最佳序列长度，这种方法所需的计算量很大，而且其性能缺乏稳定性。我们针对定长命令序列检测模型的以上不足进行了改进和修正，提出一种变长命令序列检测模型，具体描述如下：
（1）根据正常用户的历史行为，定义种长度不同的shell命令序列，用于表示正常用户的各种行为模式。
设序列长度的集合为，其中表示第种序列的长度，且。在样本序列库的个数确定的情况下，可有不同的选择。例如时，可以为（即三种序列的长度分别为），也可以为或其它组合。和对检测性能有直接影响，在选择它们时，除了要充分考虑正常用户的行为特点之外，还需考虑模型的复杂度及检测效率（和越大，检测系统的存储量和工作中的运算量也会越大）。
（2）针对每种序列建立一个样本序列库，用个样本序列库来描述正常用户的行为轮廓（行为模式集合）。按照正常用户历史行为中各序列的出现概率来提取样本序列。
设个样本序列库的集合,其中表示长度为的序列对应的样本序列库。设正常用户的训练数据（历史数据）为，它是一个长度为的shell命令流，其中表示按时间顺序排列的第个命令，对应的长度为（）的命令序列流可表示为，其中。我们设定一个概率门限，将（）中出现概率大于的命令序列视为正常用户的行为模式，即是由这些命令序列组成。
（3）定义序列之间以及序列同样本序列库之间的相似度函数，用以描述行为模式之间以及行为模式同用户整体行为轮廓之间的相似程度。
设长度为的两序列和的相似度为，其计算方法如下[1]：
第一步：设定，，。
第二步：如果（其中表示中的第个命令），则，；否则，，。
第三步：。如果，返回执行第二步；否则，。
根据以上定义，如果时（即两序列相同），则有。
序列和样本序列库的相似度函数定义为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& （1）
（4）检测时，以长度可变的命令序列为单位进行相似度赋值，并将加窗滤噪后的相似度作为用户身份的判决依据。
对于被监测用户的命令流，将它所对应的长度为的序列流表示为，其中。模型工作时，按照以下方法定义第个长度可变的序列并计算它同样本序列库集合的相似度。
第一步：设定,，。
第二步：如果,根据（1）式计算；否则，结束序列定义和相似度计算过程。
第三步：如果（即与中的某个序列相同），则，，，，，并返回执行第二步；否则，。
第四步：如果，返回执行第二步；如果，则，，,，，并返回执行第二步。
按照以上方法进行变长序列的定义和相似度计算，可得到按时间顺序排列的相似度输出值序列，其中为中的变长序列个数，，对此序列进行加窗滤噪处理，得到相似度判决值，对此值设定一个门限，若它大于，将被监测用户判为正常用户，否则，将其判为异常用户。采用均值滤噪算法时的相似度判决值为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& （2）
式中表示用户第个变长序列对应时间点上的相似度判决值（模型在中第个变长序列之后的每个序列对应时间点上都做一次判决），为窗长度，它是一个很重要的参数，决定了从被监测用户行为发生到检测系统对其行为做出判断的最短时间（即检测时间）。
3.2& 模型的分析与比较
我们提出的变长命令序列检测模型主要有以下几个特点：
（1）用多种长度不同的命令序列表示正常用户的行为模式，并针对每种命令序列建立一个样本序列库，这可以更好地反映正常用户的实际行为轮廓。
（2）以长度可变的序列为单位进行相似度赋值，其实质是在被监测用户命令流中进行行为模式挖掘。行为模式挖掘过程中，以当前命令为起点组成多个长度不同的序列，并按照长度从大到小的顺序依次同相应的样本序列库进行比较，如果其中一个序列同相应样本序列库中的某个序列相同，则认为挖掘到一个行为模式，将此序列提取出来并进行相似度赋值，序列长度越大，所赋的值也越大，如果任何一个序列同相应样本序列库中的序列都不相同，则将当前命令提取出来作为长度为1的序列，并将它与样本序列库的相似度赋以0值；然后，再以此序列之后的下一个命令为起点组成多个序列继续进行挖掘和赋值。
Lane T等人的定长序列检测模型关心的是以当前命令为起点的定长序列与正常用户各个行为模式之间的最大相似程度，而变长序列检测模型关心的是以当前命令为起点的多个长度不同的序列是否能够同正常用户的某个行为模式完全匹配。
（3）定长序列检测模型对正常用户和异常用户的检测时间是相同的。变长序列检测模型则不然，其检测时间为个变长序列持续时间（不考虑模型的计算时间），设变长序列的平均长度为，则平均检测时间为个命令持续时间；当被监测用户是正常用户时，在其命令流中挖掘到的行为模式会比较多，相对较大，最大可为，当被监测用户是异常用户时，在其命令流中只能挖掘到很少的（正常用户的）行为模式，相对较小（最小可为1）；所以，模型对异常用户的平均检测时间相对要短。
（4）此模型需要建立多个样本序列库，因而对检测系统数据存储空间的需求相对较大。
4& 实验结果
我们利用普渡大学的shell命令实验数据[1]对上述两种检测模型的性能进行了实验。其数据库包含八个UNIX用户在两年时间内的活动记录。每个用户的数据文件中均滤除了用户名、主机名、网址等标识信息，仅保留了shell命令的名称及参数；用户命令流中的命令按照在shell会话中的出现次序进行排列，不同的shell会话按照时间顺序进行连接，每个会话开始和结束的时间点上插入了标识符。实验中采用了四个用户（分别为USER1、USER2、USER3、USER4）的数据，每个用户各有个shell命令。
我们进行了分组实验，每组实验中将一个用户设为正常用户，而将其他三个设为异常用户，分别采用两种模型进行训练和测试；正常用户的前个命令用于模型的训练（建立样本序列库），正常用户和异常用户的后个命令用于模型检测性能的测试。在定长序列检测模型中，序列长度为；在变长序列检测模型中，序列长度集合。两种模型中，每种样本序列库均由正常用户的近个序列中出现概率大于的序列组成，检测时采用均值滤噪算法计算判决值。
图1和图2给出了一组实验的结果，实验中将USER1设为正常用户，两种模型的窗长度均为。图1给出的是采用定长序列检测模型时USER1和USER2的后个命令对应的归一化判决值曲线，图中纵坐标表示加窗滤噪后的相似度判决值。图2给出了采用变长序列检测模型时相应的归一化判决值曲线，图中，USER1（正常用户）对应的变长序列个数为，平均序列长度为，而USER2（异常用户）对应的变长序列个数为，平均序列长度为。可以看出，图2中两条曲线的可分性明显好于图1。
图1& 定长序列检测模型的判决值曲线&&&&&&&&&&&&&&& 图2& 变长序列检测模型的判决值曲线
为了在对异常用户的平均检测时间相同的情况下比较两种模型的性能，我们做了四组实验，四个用户各在一组实验中被设为正常用户。每组实验中，采用变长序列检测模型时，用于性能测试的各异常用户命令流（包含个命令）中的变长序列个数平均约为，因此，我们将变长序列检测模型的窗长度设为，而将定长序列检测模型的窗长度设为，以保证两种模型对异常用户的平均检测时间基本相同。实验中通过调整判决门限可以得到不同虚警概率情况下对三个异常用户的平均检测概率。表1给出了USER4被设为正常用户时的一组实验结果。
表1& USER4被设为正常用户时的实验结果
& 虚警概率
定长序列模型的& 平均检测概率
变长序列模型的& 平均检测概率
根据表1的实验结果，在虚警概率较低的区间，变长序列检测模型对应的平均检测概率相对定长序列检测模型有明显的提高。其余三组实验的结果也证明了这一点，这里不再一一列出。
本文提出一种新的基于机器学习的IDS用户行为异常检测模型，并利用UNIX用户的shell命令数据进行了实验，实验结果表明，新模型的检测性能同Lane T等人提出的检测模型相比有较大改善。由于模型中的学习方法和检测算法对不同的检测数据有一定的适应性，因而此模型也可以用于shell命令之外其它数据类型（如系统调用）的IDS，但具体的应用范围及检测性能还需要进一步的研究和实验。
[1]& Lane T. Machine learning techniques for the computer security domain of anomaly detection[Ph.D.Thesis]. Purdue University, 2000.
[2]& Lane T., Brodley C E. An application of machine learning to anomaly detection. Proceedings of the 20th National Information Systems Security Conference, 7.
[3]& Kosoresow A P, Hofmeyr S A. A shape of self for UNIX processes. IEEE Software,)：35-42.
[4]& Warrender C, Forrest S, Pearlmutter B. Detecting Intrusions Using System Calls: Alternative Data Models. Proceedings the 1999 IEEE Symposium on Security and Privacy. Berkely, California, USA：IEEE Computer Society, 5.
下页更精彩：1
本文已影响人
基于机器学习的用户行为异常检测相关推荐
[基于机器学习的用户行为异常检测]网友评论
<div class="ds-thread" data-thread-key="368675" data-title="基于机器学习的用户行为异常检测" data-image="">966,690 二月 独立访问用户
语言 & 开发
架构 & 设计
文化 & 方法
您目前处于：
文本数据的机器学习自动分类方法(上)
文本数据的机器学习自动分类方法(上)
日. 估计阅读时间:
欲知区块链、VR、TensorFlow等潮流技术和框架，请锁定
Author Contacted
相关厂商内容
相关赞助商
QCon北京-18日，北京&国家会议中心，
告诉我们您的想法
允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p
当有人回复此评论时请E-mail通知我
写得很丰富
chen binger
允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p
当有人回复此评论时请E-mail通知我
允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p
当有人回复此评论时请E-mail通知我
赞助商链接
InfoQ每周精要
通过个性化定制的新闻邮件、RSS Feeds和InfoQ业界邮件通知，保持您对感兴趣的社区内容的时刻关注。
架构 & 设计
文化 & 方法
<及所有内容，版权所有 &#169;
C4Media Inc.
服务器由 提供, 我们最信赖的ISP伙伴。
北京创新网媒广告有限公司
京ICP备号-7
注意：如果要修改您的邮箱，我们将会发送确认邮件到您原来的邮箱。
使用现有的公司名称
修改公司名称为：
公司性质：
使用现有的公司性质
修改公司性质为:
使用现有的公司规模
修改公司规模为：
使用现在的国家
使用现在的省份
Subscribe to our newsletter?
Subscribe to our industry email notices?
我们发现您在使用ad blocker。
我们理解您使用ad blocker的初衷，但为了保证InfoQ能够继续以免费方式为您服务，我们需要您的支持。InfoQ绝不会在未经您许可的情况下将您的数据提供给第三方。我们仅将其用于向读者发送相关广告内容。请您将InfoQ添加至白名单，感谢您的理解与支持。机器学习（34）
& & & & & & & & & & & & & & & & & & & & & & & &
在机器学习和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相&#20284;性和类别。最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类算法，如 K 最近邻（KNN）和 K 均&#20540;（K-Means）等等。根据数据特性的不同，可以采用不同的度量方法。一般而言，定义一个距离函数
d(x,y), 需要满足下面几个准则：
1) d(x,x) = 0 & & & & & & & & & &// 到自己的距离为0
2) d(x,y) &= 0 & & & & & & & & &// 距离非负
3) d(x,y) = d(y,x) & & & & & & & & & // 对称性: 如果 A 到 B 距离是 a，那么 B 到 A 的距离也应该是 a
4) d(x,k)&#43; d(k,y) &= d(x,y) & &// 三角形法则: (两边之和大于第三边)
这篇博客主要介绍机器学习和数据挖掘中一些常见的距离公式，包括：
闵可夫斯基距离欧几里得距离曼哈顿距离切比雪夫距离马氏距离余弦相&#20284;度皮尔逊相关系数汉明距离杰卡德相&#20284;系数编辑距离DTW 距离KL 散度
1. 闵可夫斯基距离
闵可夫斯基距离（Minkowski distance）是衡量数&#20540;点之间距离的一种非常常见的方法，假设数&#20540;点 P 和 Q 坐标如下：
那么，闵可夫斯基距离定义为：
该距离最常用的 p 是 2 和 1, 前者是欧几里得距离（Euclidean distance），后者是曼哈顿距离（Manhattan distance）。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道：
绿色的斜线表示欧几里得距离（2范数），在现实中是不可能的。其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的，红线表示1范数。
当 p 趋近于无穷大时，闵可夫斯基距离转化成切比雪夫距离（Chebyshev distance）：
我们知道平面上到原点欧几里得距离（p = 2）为 1 的点所组成的形状是一个圆，当 p 取其他数&#20540;的时候呢？
注意，当 p&&&1 时，闵可夫斯基距离不再符合三角形法则，举个例子：当
p&&&1, (0,0) 到 (1,1) 的距离等于 (1&#43;1)^{1/p}&&&2,
而 (0,1) 到这两个点的距离都是 1。
闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅&#20540;远远大于 y 方向的&#20540;，这个距离公式就会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行&z-transform&处理，即减去均&#20540;，除以标准差：
&: 该维度上的均&#20540;
&: 该维度上的标准差
可以看到，上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis
distance）了。
2. 马氏距离
考虑下面这张图，椭圆表示等高线，从欧几里得的距离来算，绿黑距离大于红黑距离，但是从马氏距离，结果恰好相反：
马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性和尺度不同的性质。假设样本点（列向量）之间的协方差对称矩阵是&&，
通过 Cholesky Decomposition（实际上是对称矩阵 LU 分解的一种特殊形式，可参考之前的）可以转化为下三角矩阵和上三角矩阵的乘积：&&。消除不同维度之间的相关性和尺度不同，只需要对样本点
x 做如下处理：&。处理之后的欧几里得距离就是原样本的马氏距离：为了书写方便，这里求马氏距离的平方）：
下图蓝色表示原样本点的分布，两颗红星坐标分别是（3, 3），（2, -2）:
由于 x， y 方向的尺度不同，不能单纯用欧几里得的方法测量它们到原点的距离。并且，由于 x 和 y 是相关的（大致可以看出斜向右上），也不能简单地在 x 和 y 方向上分别减去均&#20540;，除以标准差。最恰当的方法是对原始数据进行 Cholesky 变换，即求马氏距离（可以看到，右边的红星离原点较近）：
将上面两个图的绘制代码和求马氏距离的代码贴在这里，以备以后查阅：
# -*- coding=utf-8 -*-
# code related at: /daniel-D/
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] & & &# 平均&#20540;
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)
马氏距离的变换和 PCA 分解的颇有异曲同工之妙，不同之处在于：就二维来看，PCA
是将数据主成分旋转到 x 轴（正交矩阵的酉变换），再在尺度上缩放（对角矩阵），实现尺度相同。而马氏距离的 L逆矩阵是一个下三角，先在 x 和 y 方向进行缩放，再在 y 方向进行错切（想象矩形变平行四边形），总体来说是一个没有旋转的仿射变换。
3. 向量内积
向量内积是线性代数里最为常见的计算，实际上它还是一种有效并且直观的相&#20284;性测量手段。向量内积的定义如下：
直观的解释是：如果 x 高的地方 y 也比较高， x 低的地方 y 也比较低，那么整体的内积是偏大的，也就是说 x 和 y 是相&#20284;的。举个例子，在一段长的序列信号 A 中寻找哪一段与短序列信号 a 最匹配，只需要将 a 从 A 信号开头逐个向后平移，每次平移做一次内积，内积最大的相&#20284;度最大。信号处理中
DFT 和 DCT 也是基于这种内积运算计算出不同频域内的信号组分（DFT 和 DCT 是正交标准基，也可以看做投影）。向量和信号都是离散&#20540;，如果是连续的函数&#20540;，比如求区间[-1, 1]&两个函数之间的相&#20284;度，同样也可以得到（系数）组分，这种方法可以应用于多项式&#36924;近连续函数，也可以用到连续函数&#36924;近离散样本点（最小二乘问题，）中，扯得有点远了- -!。
向量内积的结果是没有界限的，一种解决办法是除以长度之后再求内积，这就是应用十分广泛的余弦相&#20284;度（Cosine similarity）：
余弦相&#20284;度与向量的幅&#20540;无关，只与向量的方向相关，在文档相&#20284;度（）和图片相&#20284;性（）计算上都有它的身影。需要注意一点的是，余弦相&#20284;度受到向量的平移影响，上式如果将
x 平移到 x&#43;1, 余弦&#20540;就会改变。怎样才能实现平移不变性？这就是下面要说的皮尔逊相关系数（Pearson correlation），有时候也直接叫相关系数:
皮尔逊相关系数具有平移不变性和尺度不变性，计算出了两个向量（维度）的相关性。不过，一般我们在谈论相关系数的时候，将 x 与 y 对应位置的两个数&#20540;看作一个样本点，皮尔逊系数用来表示这些样本点分布的相关性。
由于皮尔逊系数具有的良好性质，在各个领域都应用广泛，例如，在推荐系统根据为某一用户查找喜好相&#20284;的用户,进而，优点是可以不受每个用户评分标准不同和观看影片数量不一样的影响。
4. 分类数据点间的距离
汉明距离（Hamming distance）是指，两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。举个维基百科上的例子：
还可以用简单的匹配系数来表示两点之间的相&#20284;度——匹配字符数/总字符数。
在一些情况下，某些特定的&#20540;相等并不能代表什么。举个例子，用 1 表示用户看过该电影，用 0 表示用户没有看过，那么用户看电影的的信息就可用 0,1 表示成一个序列。考虑到电影基数非常庞大，用户看过的电影只占其中非常小的一部分，如果两个用户都没有看过某一部电影（两个都是
0），并不能说明两者相&#20284;。反而言之，如果两个用户都看过某一部电影（序列中都是 1），则说明用户有很大的相&#20284;度。在这个例子中，序列中等于 1 所占的权重应该远远大于 0 的权重，这就引出下面要说的杰卡德相&#20284;系数（Jaccard similarity）。
在上面的例子中，用 M11 表示两个用户都看过的电影数目，M10 表示用户 A 看过，用户 B 没看过的电影数目，M01 表示用户 A 没看过，用户 B 看过的电影数目，M00 表示两个用户都没有看过的电影数目。Jaccard 相&#20284;性系数可以表示为：
Jaccard similarity 还可以用集合的公式来表达，这里就不多说了。
如果分类数&#20540;点是用树形结构来表示的，它们的相&#20284;性可以用相同路径的长度来表示，比如，“/product/spot/ballgame/basketball” 离“product/spot/ballgame/soccer/shoes” 的距离小于到 &/product/luxury/handbags&
的距离，以为前者相同父节点路径更长。
5. 序列之间的距离
上一小节我们知道，汉明距离可以度量两个长度相同的字符串之间的相&#20284;度，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离（Edit distance, Levenshtein
distance）等算法。编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离求的是最少编辑次数，这是一个动态规划的问题，有兴趣的同学可以自己研究研究。
时间序列是序列之间距离的另外一个例子。DTW 距离（Dynamic Time Warp）是序列信号在时间或者速度上不匹配的时候一种衡量相&#20284;度的方法。神马意思？举个例子，两份原本一样声音样本A、B都说了“你好”，A在时间上发生了扭曲，“你”这个音延长了几秒。最后A:“你~~~好”，B：“你好”。DTW正是这样一种可以用来匹配A、B之间的最短距离的算法。
DTW 距离在保持信号先后顺序的限制下对时间信号进行“膨胀”或者“收缩”，找到最优的匹配，与编辑距离相&#20284;，这其实也是一个动态规划的问题:
实现代码（转自&&）:
6. 概率分布之间的距离
前面我们谈论的都是两个数&#20540;点之间的距离，实际上两个概率分布之间的距离是可以测量的。在统计学里面经常需要测量两组样本分布之间的距离，进而判断出它们是否出自同一个 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) &#43; h(y)。满足这两个条件的函数肯定是负对数形式：
对假设一个发送者要将随机变量 X 产生的一长串随机&#20540;传送给接收者， 接受者获得的平均信息量就是求它的数学期望：
这就是熵的概念。另外一个重要特点是，熵的大小与字符平均最短编码长度是一样的（shannon）。设有一个未知的分布 p(x), 而 q(x) 是我们所获得的一个对 p(x) 的近&#20284;，按照 q(x) 对该随机变量的各个&#20540;进行编码，平均长度比按照真实分布的 p(x)
进行编码要额外长一些，多出来的长度这就是 KL 散度（之所以不说距离，是因为不满足对称性和三角形法则），即：
KL 散度又叫相对熵（relative entropy）。了解机器学习的童鞋应该都知道，在 Softmax 回归（或者 Logistic 回归），最后的输出节点上的&#20540;表示这个样本分到该类的概率，这就是一个概率分布。对于一个带有标签的样本，我们期望的概率分布是：分到标签类的概率是
1，&其他类概率是 0。但是理想很丰满，现实很骨感，我们不可能得到完美的概率输出，能做的就是尽量减小总样本的 KL 散度之和（目标函数）。这就是 Softmax 回归或者 Logistic 回归中 Cost function 的优化过程啦。（PS：因为概率和为 1，一般的 logistic 二分类的图只画了一个输出节点，隐藏了另外一个）
待补充的方法：
卡方检验 Chi-Square
衡量 categorical attributes 相关性的 mutual information
Spearman's rank coefficient
Earth Mover's Distance
SimRank 迭代算法等。
参考资料：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：27017次
排名：千里之外
转载：59篇
(1)(1)(1)(6)(5)(1)(2)(1)(1)(8)(11)(25)}