# python实现各种相似度算法

### 欧几里德距离

```#-*-coding:utf-8 -*-

#计算欧几里德距离：
def euclidean(p,q):
#如果两数据集数目不同，计算两者之间都对应有的数
same = 0
for i in p:
if i in q:
same +=1

#计算欧几里德距离,并将其标准化
e = sum([(p[i] - q[i])**2 for i in range(same)])
return 1/(1+e**.5)```

```p = [1,3,2,3,4,3]
q = [1,3,4,3,2,3,4,3]
print euclidean(p,q)```

### 皮尔逊相关度

```-*-coding:utf-8 -*-

#计算皮尔逊相关度：
def pearson(p,q):
#只计算两者共同有的
same = 0
for i in p:
if i in q:
same +=1

n = same
#分别求p，q的和
sumx = sum([p[i] for i in range(n)])
sumy = sum([q[i] for i in range(n)])
#分别求出p，q的平方和
sumxsq = sum([p[i]**2 for i in range(n)])
sumysq = sum([q[i]**2 for i in range(n)])
#求出p，q的乘积和
sumxy = sum([p[i]*q[i] for i in range(n)])
# print sumxy
#求出pearson相关系数
up = sumxy - sumx*sumy/n
down = ((sumxsq - pow(sumxsq,2)/n)*(sumysq - pow(sumysq,2)/n))**.5
#若down为零则不能计算，return 0
if down == 0 :return 0
r = up/down
return r```

```p = [1,3,2,3,4,3]
q = [1,3,4,3,2,3,4,3]
print pearson(p,q)```

### 曼哈顿距离

```#-*-coding:utf-8 -*-

#计算曼哈顿距离：
def manhattan(p,q):
#只计算两者共同有的
same = 0
for i in p:
if i in q:
same += 1
#计算曼哈顿距离
n = same
vals = range(n)
distance = sum(abs(p[i] - q[i]) for i in vals)
return distance```

```p = [1,3,2,3,4,3]
q = [1,3,4,3,2,3,4,3]
print manhattan(p,q)```

### Jaccard系数

```#-*-coding:utf-8 -*-

# 计算jaccard系数
def jaccard(p,q):
c = [a for i in p if v in b]
return float(len(c))/(len(a)+len(b)-len(b))
#注意：在使用之前必须对两个数据集进行去重```

```p = ['shirt','shoes','pants','socks']
q = ['shirt','shoes']
print jaccard(p,q)```

### Tanimoto系数

Tanimoto系数是一种度量两个集合之间相似程度的方法（与Jaccard 系数相似，但不是完全相同）。其主要用于二元变量或者多元变量之间的数据集之间的相似度计算，其公式为：

```#-*-coding:utf-8-*-
def tanimoto(p,q):
c = [v for v in p if v in q]
return float(len(c) / (len(a) + len(b) - len(c)))```

```# coding: utf-8
#基于分词的文本相似度的计算,
#利用jieba分词进行中文分析
import jieba
import jieba.posseg as pseg
from jieba import analyse
import numpy as np
import os
import pymysql
connect = pymysql.Connect(
host='localhost',
port=8888,
user='***',
passwd='***',
db='gather',
charset='utf8'
)
cursor = connect.cursor()

'''

'''
class TextSimilarity(object):
def __init__(file_a,file_b):
'''
初始化类行
'''
str_a = ''
str_b = ''
if not os.path.isfile(file_a):
print(file_a,"is not file")
return
elif not os.path.isfile(file_b):
print(file_b,"is not file")
return
else:
with open(file_a,'r') as f:
str_a += line.strip()

f.close()
with open(file_b,'r') as f:
str_b += line.strip()

f.close()

self.str_a = str_a
self.str_b = str_b
#get LCS(longest common subsquence),DP
def lcs(str_a, str_b):
lensum = float(len(str_a) + len(str_b))
#得到一个二维的数组，类似用dp[lena+1][lenb+1],并且初始化为0
lengths = [[0 for j in range(len(str_b)+1)] for i in range(len(str_a)+1)]

#enumerate(a)函数： 得到下标i和a[i]
for i, x in enumerate(str_a):
for j, y in enumerate(str_b):
if x == y:
lengths[i+1][j+1] = lengths[i][j] + 1
else:
lengths[i+1][j+1] = max(lengths[i+1][j], lengths[i][j+1])

#到这里已经得到最长的子序列的长度，下面从这个矩阵中就是得到最长子序列
result = ""
x, y = len(str_a), len(str_b)
while x != 0 and y != 0:
#证明最后一个字符肯定没有用到
if lengths[x][y] == lengths[x-1][y]:
x -= 1
elif lengths[x][y] == lengths[x][y-1]:
y -= 1
else: #用到的从后向前的当前一个字符
assert str_a[x-1] == str_b[y-1] #后面语句为真，类似于if(a[x-1]==b[y-1]),执行后条件下的语句
result = str_a[x-1] + result #注意这一句，这是一个从后向前的过程
x -= 1
y -= 1

#和上面的代码类似
#if str_a[x-1] == str_b[y-1]:
#    result = str_a[x-1] + result #注意这一句，这是一个从后向前的过程
#    x -= 1
#    y -= 1
longestdist = lengths[len(str_a)][len(str_b)]
ratio = longestdist/min(len(str_a),len(str_b))
#return {'longestdistance':longestdist, 'ratio':ratio, 'result':result}
return ratio

def minimumEditDistance(str_a,str_b):
'''
最小编辑距离，只有三种操作方式 替换、插入、删除
'''
lensum = float(len(str_a) + len(str_b))
if len(str_a) > len(str_b): #得到最短长度的字符串
str_a,str_b = str_b,str_a
distances = range(len(str_a) + 1) #设置默认值
for index2,char2 in enumerate(str_b): #str_b > str_a
newDistances = [index2+1] #设置新的距离，用来标记
for index1,char1 in enumerate(str_a):
if char1 == char2: #如果相等，证明在下标index1出不用进行操作变换，最小距离跟前一个保持不变，
newDistances.append(distances[index1])
else: #得到最小的变化数，
newDistances.append(1 + min((distances[index1],   #删除
distances[index1+1], #插入
newDistances[-1])))  #变换
distances = newDistances #更新最小编辑距离

mindist = distances[-1]
ratio = (lensum - mindist)/lensum
#return {'distance':mindist, 'ratio':ratio}
return ratio
def levenshteinDistance(str1, str2):
'''
编辑距离——莱文斯坦距离,计算文本的相似度
'''
m = len(str1)
n = len(str2)
lensum = float(m + n)
d = []
for i in range(m+1):
d.append([i])
del d[0][0]
for j in range(n+1):
d[0].append(j)
for j in range(1,n+1):
for i in range(1,m+1):
if str1[i-1] == str2[j-1]:
d[i].insert(j,d[i-1][j-1])
else:
minimum = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+2)
d[i].insert(j, minimum)
ldist = d[-1][-1]
ratio = (lensum - ldist)/lensum
#return {'distance':ldist, 'ratio':ratio}
return ratio
@classmethod
def splitWords(str_a):
'''
接受一个字符串作为参数，返回分词后的结果字符串(空格隔开)和集合类型
'''
wordsa=pseg.cut(str_a)
cuta = ""
seta = set()
for key in wordsa:
#print(key.word,key.flag)
cuta += key.word + " "

return [cuta, seta]
def JaccardSim(str_a,str_b):
'''
Jaccard相似性系数
计算sa和sb的相似度 len（sa & sb）/ len（sa | sb）
'''
seta = self.splitWords(str_a)[1]
setb = self.splitWords(str_b)[1]

sa_sb = 1.0 * len(seta & setb) / len(seta | setb)

return sa_sb
def countIDF(text,topK):
'''
text:字符串，topK根据TF-IDF得到前topk个关键词的词频，用于计算相似度
return 词频vector
'''
tfidf = analyse.extract_tags

cipin = {} #统计分词后的词频

fenci = jieba.cut(text)

#记录每个词频的频率
for word in fenci:
if word not in cipin.keys():
cipin[word] = 0
cipin[word] += 1

# 基于tfidf算法抽取前10个关键词，包含每个词项的权重
keywords = tfidf(text,topK,withWeight=True)

ans = []
# keywords.count(keyword)得到keyword的词频
# help(tfidf)
# 输出抽取出的关键词
for keyword in keywords:
#print(keyword ," ",cipin[keyword[0]])
ans.append(cipin[keyword[0]]) #得到前topk频繁词项的词频

return ans
@staticmethod
def cos_sim(a,b):
a = np.array(a)
b = np.array(b)
#return {"文本的余弦相似度:":np.sum(a*b) / (np.sqrt(np.sum(a ** 2)) * np.sqrt(np.sum(b ** 2)))}
return np.sum(a*b) / (np.sqrt(np.sum(a ** 2)) * np.sqrt(np.sum(b ** 2)))
@staticmethod
def eucl_sim(a,b):
a = np.array(a)
b = np.array(b)
#print(a,b)
#print(np.sqrt((np.sum(a-b)**2)))
#return {"文本的欧几里德相似度:":1/(1+np.sqrt((np.sum(a-b)**2)))}
return 1/(1+np.sqrt((np.sum(a-b)**2)))
@staticmethod
def pers_sim(a,b):
a = np.array(a)
b = np.array(b)

a = a - np.average(a)
b = b - np.average(b)

#print(a,b)
#return {"文本的皮尔森相似度:":np.sum(a*b) / (np.sqrt(np.sum(a ** 2)) * np.sqrt(np.sum(b ** 2)))}
return np.sum(a*b) / (np.sqrt(np.sum(a ** 2)) * np.sqrt(np.sum(b ** 2)))
def splitWordSimlaryty(self,str_a,str_b,topK = 20,sim =cos_sim):
'''
基于分词求相似度，默认使用cos_sim 余弦相似度,默认使用前20个最频繁词项进行计算
'''
#得到前topK个最频繁词项的字频向量
vec_a = self.countIDF(str_a,topK)
vec_b = self.countIDF(str_b,topK)

return sim(vec_a,vec_b)
@staticmethod
def string_hash(self,source):  #局部哈希算法的实现
if source == "":
return 0
else:
#ord()函数 return 字符的Unicode数值
x = ord(source[0]) << 7
m = 1000003  #设置一个大的素数
mask = 2 ** 128 - 1  #key值
for c in source:  #对每一个字符基于前面计算hash
x = ((x * m) ^ ord(c)) & mask

x ^= len(source) #
if x == -1:  #证明超过精度
x = -2
x = bin(x).replace('0b', '').zfill(64)[-64:]
#print(source,x)

return str(x)
def simhash(self,str_a,str_b):
'''
使用simhash计算相似度
'''
pass```