#博学谷IT学习技术支持#
SparkMllib分类算法比较及应用场景详解
Binary Classification
Naive Bayes
Linear Regression
Logistical Regression
Random Forrest Classifier
Probabilistic Classifier
GBT Classifier
SVM with SGD
Decision Tree Classifier
Multi Layer Perceptron Classifier
二元分类
朴素贝叶斯
线性回归
后勤回归
随机福雷斯特分类器
概率分类器
GBT分类器
支持向量机与SGD
决策树分类器
多层感知器分类器
SparkMllib回归算法比较及应用场景详解
Generalized Linear Algorithm
Isotonic Regression
Lasso with SGD
Linear Regression
Ridge Regression
Ridge Regression with SGD
Streaming Linear Algorithm
广义线性算法
同位素回归
拉索与SGD
线性回归
山脊回归
岭回归与SGD
流线性算法
SparkMllib聚类算法比较及应用场景详解
K Means
Bisecting K Means
LDA
Power Iteration Clusting
Streaming K Means
Gaussian Mixture
K表示
分裂K的意思
利达
停电了
流K表示
高斯混合
stacking 堆叠 上个model结果是下个model的输入
预测算法
时间序列 定价模型
SVR 动态模型
逻辑回归 CLV模型
产品扩展模型 流失预警模型
分量贝叶斯 RFM模型
机器学习
特征提取模型 EM
特征选择模型 Bagging
预测优化模型 AdaBoost
推测算法
SlopeOne Content-based
Apriori NBI二部图
FPTree Heat Diffusion
Hybrid CF SVD矩阵分解
相似度计算
欧氏距离 pearson相似度
Jaccard相似度 LSH局部敏感哈希
余弦相似度
分类 聚类算法
KNN 贝叶斯网络
神经网络 SVM支持向量机
文本挖掘算法
TF-IDF TestRank
VSM TopicModel
CRF条件随机场 LDA
classification (分类),regression (回归), clustering (聚类), dimension reduction (降维)
一 分类
朴素贝叶斯
贝叶斯分类法是基于贝叶斯公式(先验概率和后验概率的关系)的统计学分类方法
它通过预测一个给定的元组属于一个特定类的概率 来进行分类
logistic回归
logistic回归得出预测值后 根据预测值大小进行分类 (通常是二分类)
logistic回归又称logistic回归分析 是一种广义的线性回归分析模型 常用于数据挖掘 疾病自动诊断 经济预测等领域 例如 探讨出轨可能性 并根据生活因素预测出轨发生的概率等 以出轨分析为例 选择两组人群 一组是出轨组 一组是非出轨组 两组人群必定具有不同的体征与生活方式等 因此因变量就为是否出轨 值为“是”或“否” 自变量就可以包括很多了 如年龄 性别 饮食习惯 是否经常去酒吧等 自变量既可以是连续的 也可以是分类的 然后通过logistic回归分析 可以得到自变量的权重 从而可以大致了解到底哪些因素是出轨的危险因素 同时根据该权值可以根据危险因素预测一个人出轨的可能性
决策树
基于树的结构来进行决策
支持向量机SVM Support Vector Machine
在训练集的样本空间寻找一个划分超平面 将不同类别的样本分开 并且最大化分类边界点距离分类平面的距离
二 回归
线性回归
用直线进行拟合
逻辑回归
用logistic函数拟合
三 聚类
(1)基于分层的聚类
AGNES算法
先将每个样本看成一个初始聚类簇 然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并 不断重复 直到达到预设的聚类簇的个数
(2)基于划分的聚类
k-means算法
首先随机从数据中选k个点 每个点初始代表每个聚类的中心 然后计算剩余各个样本到聚类中心的距离 将它赋给最近的簇 接着重新计算没一簇的平均值 整个过程不断重复 如果相邻两次调整没有明显变化 说明数据聚类形成的簇收敛
（3）基于密度的聚类
DBSCAN(Density-Based Spatial Clustering of Applications with Noise 基于密度的应用程序空间聚类)聚类算法,是一种基于高密度连通区域的 基于密度的聚类算法
与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪声的空间数据库中发现任意形状的聚类.
中文名 聚类算法
外文名 Density-Based Spatial Clustering of Applications with Noise
简 称 DBSCAN
性 质 有代表性的基于密度的聚类算法
定 义 密度相连的点的最大集合
涉及知识 Ε邻域 核心对象 直接密度可达 密度可达 密度相连
DBSCAN算法
需要两个参数 半径(Eps) 以点P为中心的邻域内最少点的数量(MinPts) 若区域内点的数量大于MinPts 就把这些点加入到区域中
(4)基于网络的聚类
(5)基于模型的聚类
四 降维
主成分分析法(PCA) Principal Component Analysis
通过某种线性投影 将高维的数据映射到低维的空间中表示 并期望在所投影的维度上数据的方差最大 以此使用较少的数据维度(主成分) 同时保留住较多的原数据点的特性
下图中PCA会选择2轴
LDA Latent Dirichlet Allocation 主题模型
分类使得
1 同类的数据点尽可能的接近(within class)
2 不同类的数据点尽可能的分开(between class)
上图中LDA会选择1轴
局部线性嵌入(LLE) Locally Linear Embedding
非线性降维算法 它能够使降维后的数据较好地保持原有流形结构
使用LLE将三维数据(b)映射到二维(c)之后,映射后的数据仍能保持原有的数据流形(红色的点互相接近,蓝色的也互相接近),说明LLE有效地保持了数据原有的流行结构.
但是LLE在有些情况下也并不适用,如果数据分布在整个封闭的球面上,LLE则不能将它映射到二维空间,且不能保持原有的数据流形.那么我们在处理数据中,首先假设数据不是分布在闭合的球面或者椭球面上
1 寻找每个样本点的k个近邻点;
2 由每个样本点的近邻点计算出该样本点的局部重建权值矩阵;
3 由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值.
(近算法,或者说K最近邻(KNN,K-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一.所谓K最近邻,就是K个最近的邻居的意思,说的是每个样本都可以用它最接近的K个邻近值来代表)
LE拉普拉斯特征映射
拉普拉斯特征映射是一种基于图的降维算法,它希望相互间有关系的点(在图中相连的点)在降维后的空间中尽可能的靠近,从而在降维后仍能保持原有的数据结构.
Concept Learning System /CLS 概念学习系统
概念学习就是学习把具有共同属性的事物集合在一起并冠以一个名称,把不具有此类属性的事物排除出去.影响概念学习的因素主要有 概念的定义性特征;原型;讲授概念的方式;概念间的联系;学生在年龄 性别 智力 动机 情绪 经验 民族 语言能力 价值观以及使用学习策略上的个体差异等自身的因素.
给定一样例集合以及每个样例是否属于某一概念的标注,怎样自动推出该概念的一般定义,这一问题被称为概念学习(concept learning),或称从样例中逼近布尔值函数.
定义 概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数.
1 C4.5
C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进
1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
2)在树构造过程中进行剪枝;
3)能够完成对连续属性的离散化处理;
4)能够对不完整数据进行处理.
C4.5算法有如下优点 产生的分类规则易于理解,准确率较高.其缺点是 在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效.
2 The k-means algorithm即K-Means算法
k-means algorithm算法是一个聚类算法,把n的对象根据他们的属性分为k个分割,k < n.它与处理混合正态分布的最大期望算法很相似,因为他们都试图找到数据中自然聚类的中心.它假设对象属性来自于空间向量,并且目标是使各个群组内部的均方误差总和最小.
3 Support vector machines支持向量机
支持向量机(Support Vector Machine),简称SV机(论文中一般简称SVM).它是一种监督式学习的方法,它广泛的应用于统计分类以及回归分析中.支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面.在分开数据的超平面的两边建有两个互相平行的超平面.分隔超平面使两个平行超平面的距离最大化.假定平行超平面间的距离或差距越大,分类器的总误差越小.一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》.van der Walt和Barnard将支持向量机和其他分类器进行了比较.
4 The Apriori algorithm
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法.其核心是基于两阶段频集思想的递推算法.该关联规则在分类上属于单维 单层 布尔关联规则.在这里,所有支持度大于最小支持度的项集称为频繁项集,简称频集.
5 最大期望(EM)算法
在统计计算中,最大期望(EM,Expectation–Maximization)算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variabl).最大期望经常用在机器学习和计算机视觉的数据集聚(Data Clustering)领域.
6 PageRank网页排名
PageRank是Google算法的重要内容.2001年9月被授予美国专利,专利人是Google创始人之一拉里·佩奇(Larry Page).因此,PageRank里的page不是指网页,而是指佩奇,即这个等级方法是以佩奇来命名的.
PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值.PageRank背后的概念是,每个到页面的链接都是对该页面的一次投票,被链接的越多,就意味着被其他网站投票越多.这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩.PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多,一般判断这篇论文的权威性就越高.
7 AdaBoost
Adaboost是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个更强的最终分类器(强分类器).其算法本身是通过改变数据分布来实现的,它根据每次训练集之中每个样本的分类是否正确,以及上次的总体分类的准确率,来确定每个样本的权值.将修改过权值的新数据集送给下层分类器进行训练,最后将每次训练得到的分类器最后融合起来,作为最后的决策分类器.
8 kNN:k-nearest neighbor classification
K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一.该方法的思路是 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别.
9 Naive Bayes朴素贝叶斯
在众多的分类模型中,应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naive Bayesian Model,NBC).朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率.同时,NBC模型所需估计的参数很少,对缺失数据不太敏感,算法也比较简单.理论上,NBC模型与其他分类方法相比具有最小的误差率.但是实际上并非总是如此,这是因为NBC模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的,这给NBC模型的正确分类带来了一定影响.在属性个数比较多或者属性之间相关性较大时,NBC模型的分类效率比不上决策树模型.而在属性相关性较小时,NBC模型的性能最为良好.
10 CART:分类与回归树
CART, Classification and Regression Trees.在分类树下面有两个关键的思想.第一个是关于递归地划分自变量空间的想法;第二个想法是用验证数据进行剪枝.
C4.5是决策树算法的一种.决策树算法作为一种分类算法,目标就是将具有p维特征的n个样本分到c个类别中去.常见的决策树算法有ID3,C4.5,CART.
基本思想
下面以一个例子来详细说明C4.5的基本思想
上述数据集有四个属性,属性集合A={ 天气,温度,湿度,风速}, 类别标签有两个,类别集合L={进行,取消}.
1. 计算类别信息熵
类别信息熵表示的是所有样本中各种类别出现的不确定性之和.根据熵的概念,熵越大,不确定性就越大,把事情搞清楚所需要的信息量就越多.
2. 计算每个属性的信息熵
每个属性的信息熵相当于一种条件熵.他表示的是在某种属性的条件下,各种类别出现的不确定性之和.属性的信息熵越大,表示这个属性中拥有的样本类别越不“纯”.
3. 计算信息增益
信息增益的 = 熵 - 条件熵,在这里就是 类别信息熵 - 属性信息熵,它表示的是信息不确定性减少的程度.如果一个属性的信息增益越大,就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性,当然,选择该属性就可以更快更好地完成我们的分类目标.
信息增益就是ID3算法的特征选择指标.
但是我们假设这样的情况,每个属性中每种类别都只有一个样本,那这样属性信息熵就等于零,根据信息增益就无法选择出有效分类特征.所以,C4.5选择使用信息增益率对ID3进行改进.
4.计算属性分裂信息度量
用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息,我们把这些信息称为属性的内在信息(instrisic information).信息增益率用信息增益 / 内在信息,会导致属性的重要性随着内在信息的增大而减小(也就是说,如果这个属性本身不确定性就很大,那我就越不倾向于选取它),这样算是对单纯用信息增益有所补偿.
5. 计算信息增益率
(下面写错了..应该是IGR = Gain / H )
天气的信息增益率最高,选择天气为分裂属性.发现分裂了之后,天气是“阴”的条件下,类别是”纯“的,所以把它定义为叶子节点,选择不“纯”的结点继续分裂.
在子结点当中重复过程1~5.
至此,这个数据集上C4.5的计算过程就算完成了,一棵树也构建出来了.
总结算法流程为
while (当前节点”不纯“)
(1)计算当前节点的类别信息熵Info(D) (以类别取值计算)
(2)计算当前节点各个属性的信息熵Info(Ai) (以属性取值下的类别取值计算)
(3)计算各个属性的信息增益Gain(Ai)=Info(D)-Info(Ai)
(4)计算各个属性的分类信息度量H(Ai) (以属性取值计算)
(5)计算各个属性的信息增益率IGR(Ai)=Gain(Ai)/H(Ai)
end while
当前节点设置为叶子节点
优缺点
优点
产生的分类规则易于理解,准确率较高.
缺点
在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效.
代码
代码已在github上
# encoding=utf-8
import cv2import timeimport numpy as npimport pandas as pd
from sklearn.cross_validation import train_test_splitfrom sklearn.metrics import accuracy_score
# 二值化def binaryzation(img):
cv_img = img.astype(np.uint8)
cv2.threshold(cv_img,50,1,cv2.THRESH_BINARY_INV,cv_img)
return cv_img
def binaryzation_features(trainset):
features = []
for img in trainset:
img = np.reshape(img,(28,28))
cv_img = img.astype(np.uint8)
img_b = binaryzation(cv_img)
# hog_feature = np.transpose(hog_feature)
features.append(img_b)
features = np.array(features)
features = np.reshape(features,(-1,feature_len))
return features
class Tree(object):
def __init__(self,node_type,Class = None, feature = None):
self.node_type = node_type # 节点类型(internal或leaf)
self.dict = {} # dict的键表示特征Ag的可能值ai,值表示根据ai得到的子树
self.Class = Class # 叶节点表示的类,若是内部节点则为none
self.feature = feature # 表示当前的树即将由第feature个特征划分(即第feature特征是使得当前树中信息增益最大的特征)
def add_tree(self,key,tree):
self.dict[key] = tree
def predict(self,features):
if self.node_type == 'leaf' or (features[self.feature] not in self.dict):
return self.Class
tree = self.dict.get(features[self.feature])
return tree.predict(features)
# 计算数据集x的经验熵H(x)def calc_ent(x):
x_value_list = set([x[i] for i in range(x.shape[0])])
ent = 0.0
for x_value in x_value_list:
p = float(x[x == x_value].shape[0]) / x.shape[0]
logp = np.log2(p)
ent -= p * logp
return ent
# 计算条件熵H(y/x)def calc_condition_ent(x, y):
x_value_list = set([x[i] for i in range(x.shape[0])])
ent = 0.0
for x_value in x_value_list:
sub_y = y[x == x_value]
temp_ent = calc_ent(sub_y)
ent += (float(sub_y.shape[0]) / y.shape[0]) * temp_ent
return ent
# 计算信息增益def calc_ent_grap(x,y):
base_ent = calc_ent(y)
condition_ent = calc_condition_ent(x, y)
ent_grap = base_ent - condition_ent
return ent_grap
# C4.5算法def recurse_train(train_set,train_label,features):
LEAF = 'leaf'
INTERNAL = 'internal'
# 步骤1——如果训练集train_set中的所有实例都属于同一类Ck
label_set = set(train_label)
if len(label_set) == 1:
return Tree(LEAF,Class = label_set.pop())
# 步骤2——如果特征集features为空
class_len = [(i,len(list(filter(lambda x:x==i,train_label)))) for i in range(class_num)] # 计算每一个类出现的个数
(max_class,max_len) = max(class_len,key = lambda x:x[1])
if len(features) == 0:
return Tree(LEAF,Class = max_class)
# 步骤3——计算信息增益,并选择信息增益最大的特征
max_feature = 0
max_gda = 0
D = train_label
for feature in features:
# print(type(train_set))
A = np.array(train_set[:,feature].flat) # 选择训练集中的第feature列(即第feature个特征)
gda = calc_ent_grap(A,D)
if calc_ent(A) != 0: ####### 计算信息增益比,这是与ID3算法唯一的不同
gda /= calc_ent(A)
if gda > max_gda:
max_gda,max_feature = gda,feature
# 步骤4——信息增益小于阈值
if max_gda < epsilon:
return Tree(LEAF,Class = max_class)
# 步骤5——构建非空子集
sub_features = list(filter(lambda x:x!=max_feature,features))
tree = Tree(INTERNAL,feature=max_feature)
max_feature_col = np.array(train_set[:,max_feature].flat)
feature_value_list = set([max_feature_col[i] for i in range(max_feature_col.shape[0])]) # 保存信息增益最大的特征可能的取值 (shape[0]表示计算行数)
for feature_value in feature_value_list:
index = []
for i in range(len(train_label)):
if train_set[i][max_feature] == feature_value:
index.append(i)
sub_train_set = train_set[index]
sub_train_label = train_label[index]
sub_tree = recurse_train(sub_train_set,sub_train_label,sub_features)
tree.add_tree(feature_value,sub_tree)
return tree
def train(train_set,train_label,features):
return recurse_train(train_set,train_label,features)
def predict(test_set,tree):
result = []
for features in test_set:
tmp_predict = tree.predict(features)
result.append(tmp_predict)
return np.array(result)
class_num = 10 # MINST数据集有10种labels,分别是“0,1,2,3,4,5,6,7,8,9”
feature_len = 784 # MINST数据集每个image有28*28=784个特征(pixels)
epsilon = 0.001 # 设定阈值
if __name__ == '__main__':
print("Start read data...")
time_1 = time.time()
raw_data = pd.read_csv('../data/train.csv', header=0) # 读取csv数据
data = raw_data.values
imgs = data[::, 1::]
features = binaryzation_features(imgs) # 图片二值化(很重要,不然预测准确率很低)
labels = data[::, 0]
# 避免过拟合,采用交叉验证,随机选取33%数据作为测试集,剩余为训练集
train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
time_2 = time.time()
print('read data cost %f seconds' % (time_2 - time_1))
# 通过C4.5算法生成决策树
print('Start training...')
tree = train(train_features,train_labels,list(range(feature_len)))
time_3 = time.time()
print('training cost %f seconds' % (time_3 - time_2))
print('Start predicting...')
test_predict = predict(test_features,tree)
time_4 = time.time()
print('predicting cost %f seconds' % (time_4 - time_3))
# print("预测的结果为 ")
# print(test_predict)
for i in range(len(test_predict)):
if test_predict[i] == None:
test_predict[i] = epsilon
score = accuracy_score(test_labels, test_predict)
print("The accruacy score is %f" % score)
测试数据集为MNIST数据集,获取地址为train.csv
运行结果
调和平均数-几何平均数-算术平均数-平方平均数的4种经典证明
调和平均数-几何平均数-算术平均数-平方平均数之间的不等式——证明1
调和平均数-几何平均数-算术平均数-平方平均数之间的不等式——证明2
调和平均数-几何平均数-算术平均数-平方平均数之间的不等式——证明4
五种平均数及其比较
两个重要极限极其推导过程
tanA=∠A的对边/∠A的邻边
据说泰勒有一天无聊玩 GeoGebra 的时候,在输入框里输了
然后无聊的拨弄着滑动条来随意改变这些个A值.
屏幕上函数图像不断变化着,但那线条总是歪七八扭,不听使唤.他认真了起来,扩大了A值的范围和精度,逐渐找到规律之后,他已经能够调出 剑尖,牙齿,猫耳 等图像.
他不断增加项数,调整参数,他发现增加的项数越多,他就越能掌控图像的变化.他像扭铁丝似的上下弯折着曲线,无意中调出了一段波浪形的图像,看着似乎挺眼熟……
——这不是 sin 函数吗！
他抑制不住自己的兴奋,赶紧输入了标准的 sin 函数进行对比,同时继续调整多项式,使这个山寨函数尽可能地贴近正品.
他仔细端详着,单看眼前这一段,简直可以以假乱真,不过越到后面,分歧也就越明显了.
他猛然意识到 "我能够控制多项式画出任意图像！甚至把它伪装成其他函数！"
但是他很快冷静了下来,问了自己一连串的问题
所谓的任意,可以是无限制的任意吗？
我能否完美地"伪装"出一个目标函数？
如果不能,那又能够伪装到何种程度？
摆在眼前的具体问题就是,能否"伪装"出一个完美的 sin 函数？
他决定一探究竟.
如果存在某 n 次多项式等于 sin(x);
则其导函数也等于 sin(x) 的导函数;
它的二阶导也等于 sin(x) 的二阶导;
它的三阶导也等于 sin(x) 的三阶导;
……
它的 n 阶导也等于 sin(x) 的 n 阶导.
可是,每求导一次,多项式就会降一阶.求到 n 阶导不就变成常数了吗？再导不就归零了吗！
而 sin(x) 可以无穷阶求导,所以无论 n 有多大,都不可能完美伪装出 sin 函数.
除非…… n 为无穷大？
这就引出了下面的问题 这样的伪装可以到达何种程度？
首先,经过调整,可以使二者的起点一致;
然后,可以调整使二者在该点处斜率一致;
再然后,可以调整该点处的二阶导数一致;
再然后,可以调整该点处的三阶导数一致;
……
总之,我们总可以使该点处 n 阶导数一致.
而 n 可以无限递增下去,我们的"伪装"就可以无限逼近目标函数.
故事发展至此,事件的线索已经全部给出,真相已经呼之欲出了！请诸君充分动用自己的聪明才智,解开这个谜团,揭开凶手(泰勒公式)的真面目吧! ——埃勒里·泰勒·奎因
看着图像的变化,他不禁把那个起点当成了运动的质点,斜率即质点的速度……他忍不住做起了一个思想实验
没有其他外力,没有初速度的条件下,质点只能静止在原地,毫无自由可言.
给质点一个初速度,我们可以使质点单向匀速运动;
若再给定一个加速度,我们可以使速度均匀变化,从而产生拐弯运动;
若再给定加速度的变化率,我们使加速度均匀变化,速度拐弯变化,产生可转向拐弯运动;
……
如果一开始就设定好质点的初速度,加速度,加加速度,加加加…加速度的话,正如用一只无形的手调控着它的命运,那么无论想让它何时拐,往何处拐,如何拐……就全都在初始条件的设计之中了！[1]
这一刻,他仿佛触摸到了力量,触摸到了真理,触摸到了前所未有的自由！
他大吼一声 “泰勒展开！”,写下了"那个公式"
写罢,他对世界呼喊道 “这,就是我的初始条件！”
那一瞬间,后世所有数学系学生的苦逼命运已经全然决定,只能沿着他所设定的路线挣扎前行,沉沦其中,无法挣脱.
正当泰勒沉溺于力量之中时,他不知道,一个叫做傅里叶的人即将在圆周运动之中窥探到更深层的秘密,解开另一道更为强大的封印！这股新力量的出现到底是会终结泰勒的诅咒呢？还是会将诅咒变得更为凶残……
评价样本之间的相似性和类别时,衡量个体差异的方法主要有【距离】和【相似度(Similarity)】两种
假设我们要比较X个体和Y个体间的差异,它们都包含了N个维的特征,
X=（x1, x2, x3, … xn）
Y=（y1, y2, y3, … yn）
下面来看看主要可以用哪些方法来衡量两者的差异.
一 距离度量
距离度量的基本性质：
非负性：dist(x,y) >= 0
同一性：dist(x,x) = 0
对称性：dist(x,y) = dist(y,x)
三角不等式：dist(x,z)+dist(y,z) >= dist(x,y)
1.欧几里得距离（Euclidean Distance）以及欧式距离的标准化（Standardized Euclidean distance）欧式距离 两点之间的直线距离
2.明可夫斯基距离(Minkowski Distance)
3.曼哈顿距离（Manhattan Distance）
4.切比雪夫距离（Chebyshev Distance）
5.马哈拉诺比斯距离(Mahalanobis Distance) 马氏距离
6.海明距离（Hamming distance）
7.加权闵可夫斯基距离 加权距离(weighted distance)
8.Hellinger距离(Hellinger Distance)
距离度量（Distance）用于衡量个体在空间上存在的距离,距离越远说明个体间的差异越大.
1 欧几里得距离(Euclidean Distance)
p=2时,闵可夫斯基距离就是欧氏距离
在平面几何或者立体几何中的距离,通常就是欧氏距离
欧氏距离是最常见的距离度量,衡量的是多维空间中各个点之间的绝对距离.公式如下
ps:因为计算是基于各维度特征的绝对数值,所以欧氏度量需要保证各维度指标在相同的刻度级别,比如对身高（cm）和体重（kg）两个单位不同的指标使用欧式距离可能使结果失效.
欧式距离的标准化（Standardized Euclidean distance）
标准欧氏距离的思路 现将各个维度的数据进行标准化 标准化后的值 = ( 标准化前的值 － 分量的均值 ) /分量的标准差,然后计算欧式距离:
2 明可夫斯基距离(Minkowski Distance) 闵可夫斯基距离
明氏距离是欧氏距离的推广,是对多个距离度量公式的概括性的表述.公式如下
当p==1,“明可夫斯基距离”变成“曼哈顿距离”
当p==2,“明可夫斯基距离”变成“欧几里得距离”
当p==∞,“明可夫斯基距离”变成“切比雪夫距离”
3 曼哈顿距离(Manhattan Distance)
p=1时,闵可夫斯基距离就是曼哈顿距离
又称城市街区距离,在方正的北京大街打车,行车距离就是曼哈顿距离,如果在山城重庆就不是
曼哈顿距离来源于城市区块距离,是将多个维度上的距离进行求和后的结果,如下
4 切比雪夫距离(Chebyshev Distance)
p等于无穷大时,闵可夫斯基距离就是切比雪夫距离
若将国际象棋棋盘放在二维直角坐标系中,格子的边长定义为1,座标的x轴及y轴和棋盘方格平行,原点恰落在某一格的中心点,则王从一个位置走到其他位置需要的最少步数恰为二个位置的切比雪夫距离,因此切比雪夫距离也称为棋盘距离
切比雪夫距离起源于国际象棋中国王的走法,我们知道国际象棋国王每次只能往周围的8格中走一步,那么如果要从棋盘中A格(x1, y1)走到B格(x2, y2)最少需要走几步？扩展到多维空间,其实切比雪夫距离就是当p趋向于无穷大时的明氏距离
各对应坐标数值差的最大值.国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？你会发现最少步数总是max( | x2-x1 | , | y2-y1 | )步
二维平面上两点a(x1,y1),b(x2,y2)之间的切比雪夫距离公式
n维空间上两点a(x1,x2……..xn),b(y1,y2……..yn)的切比雪夫距离公式
5 马哈拉诺比斯距离(Mahalanobis Distance)
一个向量的不同维度如果是不同的量纲,更有甚者,维度之间是相关的,比如身高和体重组成的向量,在闵可夫斯基距离中等同对待,有时,这样是不恰当的马氏距离利用 Cholesky transformation 消除了不同维度之间的相关性和尺度不同
其中,S为样本的协方差矩阵当S是单位阵的时候,马氏距离就是欧式距离;当S是对角阵的时候,马氏距离是加权欧式距离
很多时候,一个事物的有点也可能会构成它的缺点这里马氏距离可以消除不同维度之间的不同尺度,就可能放大了变化细微维度的作用
我们可以按照连续性将属性分为“连续属性”和“离散属性”;也可以按照有序性将属性分为“有序属性”和“无序属性”[1]上面的相似性度量都是关于“连续”并“有序”属性的,下面给出几个关于“离散属性”和“无序属性”的相似性度量
既然欧几里得距离无法忽略指标度量的差异,所以在使用欧氏距离之前需要对底层指标进行数据的标准化,而基于各指标维度进行标准化后再使用欧氏距离就衍生出来另外一个距离度量——马哈拉诺比斯距离（Mahalanobis Distance）,简称马氏距离.
6 海明距离（Hamming distance）汉明距离
两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数
例如:字符串“11110011”与“10010010”之间的汉明距离为3
汉明距离可以在通信中累计定长二进制字中发生翻转的错误数据位,所以它也被称为信号距离汉明重量分析在包括信息论 编码理论 密码学等领域都有应用
如果要比较两个不同长度的字符串,不仅要进行替换,而且要进行插入与删除的运算,在这种场合下,通常使用更加复杂的编辑距离等算法
定义 在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数.
场景 在海量物品的相似度计算中可用simHash对物品压缩成字符串,然后使用海明距离计算物品间的距离
两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数.
1011101与 1001001 之间的汉明距离是2
2143896与 2233796 之间的汉明距离是3
irie与 rise之间的汉明距离是 3
7 加权(weighted)闵可夫斯基距离
当样本中不同属性的重要性不同时,可使用"加权距离"(weighted distance)
8 Hellinger距离(Hellinger Distance)
在七月算法的课程里,还讲了一个与KL散度类似的距离,表示随机分布之间的相似性的Hellinger距离
当α=0时
这时,Hellinger距离就是两个随机分布取平方根之后的欧式距离,符合距离度量的四个性质,是严格的距离度量
二 相似度度量correlation相关性
相似度度量（Similarity）,即计算个体间的相似程度,与距离度量相反,相似度度量的值越小,说明个体间相似度越小,差异越大
1 余弦相似度(Cosine Similarity)
2 调整余弦相似度(Adjusted Cosine Similarity)
3 皮尔森相关系数(Pearson Correlation Coefficient)
4 Jaccard相似系数(Jaccard Coefficient)
5 Tanimoto系数（广义Jaccard相似系数）
6 对数似然相似率
7 互信息/信息增益,相对熵/KL散度(Kullback-Leibler Divergence)
8 信息检索–词频-逆文档频率（TF-IDF）
9 词对相似度–点间互信息
1 余弦相似度(Cosine Similarity) 夹角余弦相似度
余弦相似性取值[-1,1],值越趋于1,表示两个向量的相似度越高余弦相似度与向量的幅值无关,只与向量的方向相关,在文档相似度(TF-IDF)和图片相似性(histogram)计算上都有它的身影
机器学习中可以把两点看成是空间中的两个向量,通过衡量两向量之间的相似性来衡量样本之间的相似性
当两条新闻向量夹角余弦等于1时,这两条新闻完全重复（用这个办法可以删除爬虫所收集网页中的重复网页）;当夹角的余弦值接近于1时,两条新闻相似（可以用作文本分类）;夹角的余弦越小,两条新闻越不相关
余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小.相比距离度量,余弦相似度更加注重两个向量在方向上的差异,而非距离或长度上.公式如下
2 调整余弦相似度(Adjusted Cosine Similarity)
虽然余弦相似度对个体间存在的偏见可以进行一定的修正,但是因为只能分辨个体在维之间的差异,没法衡量每个维数值的差异,会导致这样一个情况
比如用户对内容评分,5分制,X和Y两个用户对两个内容的评分分别为(1,2)和(4,5),使用余弦相似度得出的结果是0.98,两者极为相似,但从评 分上看X似乎不喜欢这2个内容,而Y比较喜欢,余弦相似度对数值的不敏感导致了结果的误差;
需要修正这种不合理性,就出现了调整余弦相似度,即所有维度上的数值都减去一个均值,比如X和Y的评分均值都是3,那么调整后为(-2,-1)和(1,2),再用余弦相似度计算,得到-0.8,相似度为负值并且差异不小,但显然更加符合现实.
余弦相似度更多的是从方向上区分差异,而对绝对的数值不敏感,因此没法衡量每个维度上数值的差异,会导致这样一种情况：
用户对内容评分,按5分制,X和Y两个用户对两个内容的评分分别为（1,2）和（4,5）,使用余弦相似度得到的结果是0.98,两者极为相似但从评分上看X似乎不喜欢2这个 内容,而Y则比较喜欢,余弦相似度对数值的不敏感导致了结果的误差,需要修正这种不合理性就出现了调整余弦相似度,即所有维度上的数值都减去一个均值,比如X和Y的评分均值都是3,那么调整后为（-2,-1）和（1,2）,再用余弦相似度计算,得到-0.8,相似度为负值并且差异不小,但显然更加符合现实
那么是否可以在（用户-商品-行为数值）矩阵的基础上使用调整余弦相似度计算呢？从算法原理分析,复杂度虽然增加了,但是应该比普通余弦夹角算法要强
3 皮尔森相关系数(Pearson Correlation Coefficient)
余弦相似度会受到向量的平移影响,怎样才能实现平移不变性？在余弦相似度的基础上,每个向量减去这个向量均值组成的向量,也就是皮尔逊相关系数,有时候也直接叫相关系数
当两个向量均值都为0时,皮尔逊相对系数等于余弦相似性
即相关分析中的相关系数r,分别对X和Y基于自身总体标准化后计算空间向量的余弦夹角.公式如下
定义 两个变量之间的皮尔逊相关系数定义为两个变量之间的协方差和标准差的商
4 Jaccard相似系数(Jaccard Coefficient)
Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度,因为个体的特征属性都是由符号度量或者布尔值标识,因此无法衡量差异具体值的大小,只能获得“是否相同”这个结果,所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题.如果比较X与Y的Jaccard相似系 数,只比较xn和yn中相同的个数,公式如下
杰卡德相似性度量
杰卡德相似系数
两个集合A和B交集元素的个数在A B并集中所占的比例,称为这两个集合的杰卡德系数,用符号 J(A,B) 表示杰卡德相似系数是衡量两个集合相似度的一种指标（余弦距离也可以用来衡量两个集合的相似度）
杰卡德距离
与杰卡德相似系数相反的概念是杰卡德距离（Jaccard Distance）,可以用如下公式来表示：
杰卡德距离用两个两个集合中不同元素占所有元素的比例来衡量两个集合的区分度
杰卡德相似系数的应用
假设样本A和样本B是两个n维向量,而且所有维度的取值都是0或1例如,A（0,1,1,0）和B（1,0,1,1）我们将样本看成一个集合,1表示集合包含该元素,0表示集合不包含该元素
p：样本A与B都是1的维度的个数
q：样本A是1而B是0的维度的个数
r：样本A是0而B是1的维度的个数
s：样本A与B都是0的维度的个数
那么样本A与B的杰卡德相似系数可以表示为：
此处分母之所以不加s的原因在于：
对于杰卡德相似系数或杰卡德距离来说,它处理的都是非对称二元变量非对称的意思是指状态的两个输出不是同等重要的,例如,疾病检查的阳性和阴性结果
按照惯例,我们将比较重要的输出结果,通常也是出现几率较小的结果编码为1（例如HIV阳性）,而将另一种结果编码为0（例如HIV阴性）给定两个非对称二元变量,两个都取1的情况（正匹配）认为比两个都取0的情况（负匹配）更有意义负匹配的数量s认为是不重要的,因此在计算时忽略
杰卡德相似度算法分析
杰卡德相似度算法没有考虑向量中潜在数值的大小,而是简单的处理为0和1,不过,做了这样的处理之后,杰卡德方法的计算效率肯定是比较高的,毕竟只需要做集合操作
在聚类中,杰卡德相似系数可以作为聚类的性能度量 在推荐系统中,杰卡德相似系数可以度量两个购买若干商品的用户之间的相似性
5 Tanimoto系数（广义Jaccard相似系数）
定义 广义Jaccard相似度,元素的取值可以是实数.又叫作谷本系数
关系 如果我们的x,y都是二值向量,那么Tanimoto系数就等同Jaccard距离.
6 对数似然相似率
7 互信息/信息增益,相对熵/KL散度
KL散度(Kullback-Leibler Divergence)
又叫相对熵,表示两个随机分布之间的相似性
可以证明,KL散度大于等于0,当p=q时等于0;KL散度不满足对称性
8 信息检索–词频-逆文档频率（TF-IDF）
9 词对相似度–点间互信息
三 距离度量与相似度度量的区别
欧氏距离是最常见的距离度量,而余弦相似度则是最常见的相似度度量,很多的距离度量和相似度度量都是基于这两者的变形和衍生,所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别
借助三维坐标系来看下欧氏距离和余弦相似度的区别：
相比于欧氏距离,余弦距离更加注重两个向量在方向上的差异
从图上可以看出距离度量衡量的是空间各点间的绝对距离,跟各个点所在的位置坐标（即个体特征维度的数值）直接相关;而余弦相似度衡量的是空间向 量的夹角,更加的是体现在方向上的差异,而不是位置如果保持A点的位置不变,B点朝原方向远离坐标轴原点,那么这个时候余弦相似度cosθ是保持不变 的,因为夹角不变,而A B两点的距离显然在发生改变,这就是欧氏距离和余弦相似度的不同之处
适用场景
根据欧氏距离和余弦相似度各自的计算方式和衡量特征,分别适用于不同的数据分析模型：
欧氏距离能够体现个体数值特征的绝对差异,所以更多的用于需要从维度的数值大小中体现差异的分析,如使用用户行为指标分析用户价值的相似度或差异;
而余弦相似度更多的是从方向上区分差异,而对绝对的数值不敏感, 更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异,同时修正了用户间可能存在的度量标准不统一的问题（因为余弦相似度对绝对数值不敏感）