python实现各种相似度算法

在数据挖掘中有很多地方要计算相似度,比如聚类分析和协同过滤。计算相似度的有许多方法,其中有欧几里德距离、曼哈顿距离、Jaccard系数和皮尔逊相关度等等。我们这里把一些常用的相似度计算方法,用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)

 

得出结果是:0.261203874964

皮尔逊相关度

几个数据集中出现异常值的时候,欧几里德距离就不如皮尔逊相关度‘稳定’,它会在出现偏差时倾向于给出更好的结果。其公式为:

 

复制代码
-*-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)

得出结果是:0.00595238095238

曼哈顿距离

曼哈顿距离是另一种相似度计算方法,不是经常需要,但是我们仍然学会如何用python去实现,其公式为:

复制代码
#-*-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)

得出结果为4

Jaccard系数

当数据集为二元变量时,我们只有两种状态:0或者1。这个时候以上的计算相似度的方法就无法派上用场,于是我们引出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)

得出结果是:0.5

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)))

当比较的数据集的数据集合中的元素都是相异的时候,Jaccard系数与Tanimoto系数相同。

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

'''
文本相似度的计算,基于几种常见的算法的实现
'''
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:
                for line in f.readlines():
                    str_a += line.strip()

                f.close()
            with open(file_b,'r') as f:
                for line in f.readlines():
                    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 + " "
            seta.add(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