精华内容
下载资源
问答
  • 主要介绍了javascript实现图片相似度算法,大家参考使用吧
  • 主要介绍了Java基于余弦方法实现的计算相似度算法,简单说明了余弦相似性的概念、原理并结合实例形式分析了java实现余弦相似性算法的相关操作技巧,需要的朋友可以参考下
  • 基于项目的协同过滤推荐算法也是推荐算法中最基础、最简单、很重要的算法,主要是根据用户对项目的某一种操作行为,构成项目-用户操作行为矩阵,根据操作行为矩阵计算项目之间的相似度,最终为目标用户推荐目标用户...
  • 该代码使用TF-IDF模型,可做内容相似度匹配,可做简易版论文查重使用, 注:代码我也是借鉴别人+自己改装
  • a=[01,02,04,06],b=[09.08,04,07].计算a,b的相似度。用户门户网站推荐,根据个人行为推荐。
  • 实现一个电影推荐系统,采用协同过滤算法,相似度算法为余弦相似度,基于用户和基于项目中选择基于项目数据集为movielens数据集 一,项目说明 项目名称:item_cf_go 语言:golang 项目地址:github....
  • Matlab余弦相似度算法判断图片相似度并识别源代码 Matlab 余弦相似度 图像匹配 可直接运行
  • sim代码相似度算法大致实现,核心是用LCS最长公共子序列和DP动态规划。
  • 相似度算法

    2021-01-19 16:04:17
    相似度算法 算法名称 简单描述 LCS 最长公共子序列 Hamming Distance 汉明距离 Cosine Similarity 余弦相似度算法 1、欧式距离(Euclidean Distance) 欧式距离全称是...

    今天梳理的是底层的应用算法,计算相似度的。这种算法在nlp,推荐系统领域比较常见,其他的地方怎么用就仁者见仁啦~

    相似度算法

    算法名称简单描述
    LCS最长公共子序列
    Hamming Distance

    汉明距离 

    Cosine Similarity

    余弦相似度算法
    Euclidean Distance欧式距离
    Pearson Correlation Coefficient皮尔逊相关系数
    Manhattan Distance曼哈顿距离

    Minkowski Distance

    明可夫斯基距离

    Jaccard Similarity

    Jaccard系数

    1、LCS-最长公共子序列(longest common sequence)和最长公共子串(longest common substring)

    什么是子序列呢?

    即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果。图如下:

    什么是子串呢?

    给定串中任意个连续的字符组成的子序列称为该串的子串。给一个图再解释一下:

     如上图,给定的字符序列: {a,b,c,d,e,f,g,h},它的子序列示例: {a,c,e,f} 即元素b,d,g,h被去掉后,保持原有的元素序列所得到的结果就是子序列。同理,{a,h},{c,d,e}等都是它的子序列。

    它的字串示例:{c,d,e,f} 即连续元素c,d,e,f组成的串是给定序列的字串。同理,{a,b,c,d},{g,h}等都是它的字串。

    这个问题说明白后,最长公共子序列(以下都简称LCS)就很好理解了。

    给定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2},s1和s2的相同子序列,且该子序列的长度最长,即是LCS。

    s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}

     

    2、欧式距离(Euclidean Distance)

    欧式距离全称是欧几里距离,是最易于理解的一种距离计算方式,源自欧式空间中两点间的距离公式。

    3. Python 代码简单实现:

    def EuclideanDistance(x,y):
    	d = 0
    	for a,b in zip(x,y):
    		d += (a-b)**2
    	return d**0.5

    4. 使用 numpy 简化:

    import numpy as np
    def EuclideanDistance(dataA,dataB):
        # np.linalg.norm 用于范数计算,默认是二范数,相当于平方和开根号
        return 1.0/(1.0 + np.linalg.norm(dataA - dataB))

    3、余弦相似度(Cosine)

    首先,样本数据的夹角余弦并不是真正几何意义上的夹角余弦,只不过是借了它的名字,实际是借用了它的概念变成了是代数意义上的“夹角余弦”,用来衡量样本向量间的差异。

    几何意义上的夹角余弦

    夹角越小,余弦值越接近于1,反之则趋于-1。我们假设有x1与x2两个向量:

    1. Python 代码的简单按公式还原:
    def Cosine(x,y):
        sum_xy = 0.0;  
        normX = 0.0;  
        normY = 0.0;  
        for a,b in zip(x,y):  
            sum_xy += a*b  
            normX += a**2  
            normY += b**2  
        if normX == 0.0 or normY == 0.0:  
            return None  
        else:  
            return sum_xy / ((normX*normY)**0.5)  

    2. 使用 numpy 简化夹角余弦

    def Cosine(dataA,dataB):
        sumData = dataA *dataB.T # 若列为向量则为 dataA.T * dataB
        denom = np.linalg.norm(dataA) * np.linalg.norm(dataB)
        # 归一化
        return 0.5 + 0.5 * (sumData / denom)

    我们引入一组特殊数据进行测试:

    dataA = np.mat([1,2,3,3,2,1])
    dataB = np.mat([2,3,4,4,3,2])
    print(EuclideanDistance(dataA,dataB)) # 0.28
    print(Cosine(dataA,dataB)) # 0.99

    欧式距离和夹角余弦的区别:

    对比以上的结果的 dataA 与 dataB 这两组数据,会发现 dataA 与 dataB 的欧式距离相似度比较小,而夹角余弦相似度比较大,即夹角余弦更能反映两者之间的变动趋势,两者有很高的变化趋势相似度,而欧式距离较大是因为两者数值有很大的区别,即两者拥有很高的数值差异

    4、皮尔逊相关系数(Pearson Correlation Coefficient)

    如何理解皮尔逊相关系数(Pearson Correlation Coefficient)?​www.zhihu.com 

    假如之不先介绍夹角余弦的话,第一次接触你绝对会对皮尔逊相关系数一脸懵逼。那么现在,让我们再来理解一下皮尔逊相关系数的公式:

    皮尔逊相关系数公式实际上就是在计算夹角余弦之前将两个向量减去各个样本的平均值,达到中心化的目的。从知友的回答可以明白,皮尔逊相关函数是余弦相似度在维度缺失上面的一种改进方法

    1.Python 代码实现皮尔逊相关系数:

    def Pearson(x,y):
        sum_XY = 0.0
        sum_X = 0.0
        sum_Y = 0.0
        normX = 0.0
        normY = 0.0
        count = 0
        for a,b in zip(x,y):
            count += 1
            sum_XY += a * b
            sum_X += a
            sum_Y += b
            normX += a**2
            normY += b**2
        if count == 0:
            return 0
        # denominator part
        denominator = (normX - sum_X**2 / count)**0.5 * (normY - sum_Y**2 / count)**0.5
        if denominator == 0:
            return 0
        return (sum_XY - (sum_X * sum_Y) / count) / denominator

    2. numpy 简化实现皮尔逊相关系数

    def Pearson(dataA,dataB):
        # 皮尔逊相关系数的取值范围(-1 ~ 1),0.5 + 0.5 * result 归一化(0 ~ 1)
        return 0.5 + 0.5 * np.corrcoef(dataA,dataB,rowvar = 0)[0][1]

    用余弦相似度相同的方法实现皮尔逊:

    # 余弦相似度、修正余弦相似度、皮尔逊相关系数的关系
    # Pearson 减去的是每个item i 的被打分的均值
    def Pearson(dataA,dataB):
        avgA = np.mean(dataA)
        avgB = np.mean(dataB)
        sumData = (dataA - avgA) * (dataB - avgB).T # 若列为向量则为 dataA.T * dataB
        denom = np.linalg.norm(dataA - avgA) * np.linalg.norm(dataB - avgB)
        # 归一化
        return 0.5 + 0.5 * (sumData / denom)

    5、修正余弦相似度

    1. 为什么需要在余弦相似度的基础上使用修正余弦相似度

    X和Y两个用户对两个内容的评分分别为(1,2)和(4,5),使用余弦相似度得到的结果是0.98,两者极为相似。但从评分上看X似乎不喜欢2这个 内容,而Y则比较喜欢,余弦相似度对数值的不敏感导致了结果的误差,需要修正这种不合理性
    # 修正余弦相似度
    # 修正cosine 减去的是对item i打过分的每个user u,其打分的均值
    data = np.mat([[1,2,3],[3,4,5]])
    avg = np.mean(data[:,0]) # 下标0表示正在打分的用户
    def AdjustedCosine(dataA,dataB,avg):
        sumData = (dataA - avg) * (dataB - avg).T # 若列为向量则为 dataA.T * dataB
        denom = np.linalg.norm(dataA - avg) * np.linalg.norm(dataB - avg)
        return 0.5 + 0.5 * (sumData / denom)
    print(AdjustedCosine(data[0,:],data[1,:],avg))

    6、汉明距离(Hamming distance)

    汉明距离表示的是两个字符串(相同长度)对应位不同的数量。比如有两个等长的字符串 str1 = "11111" 和 str2 = "10001" 那么它们之间的汉明距离就是3(这样说就简单多了吧。哈哈)。汉明距离多用于图像像素的匹配(同图搜索)。

    1.Python 的矩阵汉明距离简单运用:

    def hammingDistance(dataA,dataB):
        distanceArr = dataA - dataB
        return np.sum(distanceArr == 0)# 若列为向量则为 shape[0]

    7.曼哈顿距离(Manhattan Distance)

    没错,你也是会曼哈顿计量法的人了,现在开始你和秦风只差一张刘昊然的脸了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口,那么驾驶的最近距离并不是直线距离,因为你不可能横穿房屋。所以,曼哈顿距离表示的就是你的实际驾驶距离,即两个点在标准坐标系上的绝对轴距总和。

    曼哈顿距离

    # 曼哈顿距离(Manhattan Distance)
    def Manhattan(dataA,dataB):
        return np.sum(np.abs(dataA - dataB))
    print(Manhattan(dataA,dataB))

    8、Jaccard系数

    定义

    Jaccard系数值越大,样本相似度越高。

    给定两个集合A,B,Jaccard 系数定义为A与B交集的大小与A与B并集的大小的比值,定义如下:

    当集合A,B都为空时,J(A,B)定义为1。

    与Jaccard 系数相关的指标叫做Jaccard 距离,用于描述集合之间的不相似度。Jaccard 距离越大,样本相似度越低。公式定义如下:

    其中对参差(symmetric difference)

    值域

    python实现

    1、当两个集合元素个数相同,则直接调包

    from numpy import *
    
    import scipy.spatial.distance as dist # 导入scipy距离公式
    
    matV = mat([[1,1,0,1,0,1,0,0,1],[0,1,1,0,0,0,1,1,1]])
    
    print ("dist.jaccard:", dist.pdist(matV,'jaccard'))

    2、当集合元素个数不同

    def correlation(set_a,set_b):
    
    unions = len(set_a.union(set_b))
    
    intersections = len(set_a.intersection(set_b))
    
    return 1. * intersections / unions

    实例

    主要用于计算符号度量或布尔值度量的个体间的相似度,因为个体的特征属性都是由符号度量或者布尔值标识,因此无法衡量差异具体值的大小,只能获得“是否相同”这个结果,所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。

    1、如果比较X与Y的Jaccard相似系数,只比较xn和yn中相同的个数,公式如下:
    如集合A={1,2,3,4};B={3,4,5,6};
    那么他们的J(X,Y)=1{3,4}/1{1,2,3,4,5,6}=1/3;

    2、样本A与样本B是两个n维向量,而且所有维度的取值都是0或1。例如:A(0111)和B(1011)。我们将样本看成是一个集合,1表示集合包含该元素,0表示集合不包含该元素。

    概念浅析:假设A是坚果Pro2 , B是 苹果8x。 为了比较两个手机,给出了n个评价指标,即n维特征,也就是n维向量:1-是国产、2-有刘海、3-价格高于5000。那么对于A=(100),B=(011)。所以,n维向量指样本的N维特征,组成一个集合。而集合是由元素组成的,在对应的特征位置,如果样本有该特征,这个位置集合值取1,表示包含该元素;否则,取0,表示不包含该元素。可见,元素=特征。

    P:样本A与B都是1的维度的个数

    q:样本A是1,样本B是0的维度的个数

    r:样本A是0,样本B是1的维度的个数

    s:样本A与B都是0的维度的个数

    那么样本A与B的杰卡德相似系数可以表示为:

    这里p+q+r可理解为A与B的并集的元素个数,而p是A与B的交集的元素个数。

    而样本A与B的杰卡德系数表示为:

    二、了解数据结构

    以下题目和数据均来自于千里码,一个优质的程序员答题网站,由于站长食年常年失踪,于是我就无耻的分享出来啦。

    现在从豆瓣的用户中抽取了500左右个比较活跃的用户,这些用户都是忠实的电影迷,大部分人涉猎了上百部电影。

    这里有个80多万行的 文本文件,文件的每行是三个数字,分别是 userid,movieid,rating。代表一个用户对一部电影的评分。rating代表评分的星级,如上图中的红框所示,星级从低到高依次是1-5。

    接下来有个行数为10001的 文本文件(第一行为title),文件的每行为2个数字,分别代表userid和movieid,请你预测如果该用户观看了这部电影,会给该电影打多少分,你的预测值为1个大小为1-5的整数。

    本题的答案是一个长度为1万的字符串,字符串的第k位代表你对第k行的预测结果。
    如果你的预测结果和实际答案的差值的绝对值的和小于6000,通过该题。

    简单来说就是:

    • train.txt(80w 12M) --- userid, movieid, rate
    • test.txt(1w 360KB) --- userid, movieid

    你要为 test.txt 中的用户预测当前电影的打分,你可以在以下地址提交你的答案。

    协同过滤​www.qlcoder.com

     

    参考

    【1】汉明距离汉明距离实现

    【2】LCS

    【3】常见相似度原理

    【4】推荐算法入门(1)相似度计算方法大全

    【5】Implementing the five most popular Similarity Measures in Python
    【6】相似度方法总结

    【7】Jaccard相似度

    展开全文
  • 实验内容:用Java定义相似度算法接口,分别用Pearson相似度算法、欧几里得相似度、余弦相似度算法,判断第一列Gl-1数据与其它四列数据(Gl-2,Gl-3,Gl-4,Gl-5)的相似程度,并找出哪一列与Gl-1数据最相似。...

    实验内容:用Java定义相似度算法接口,分别用Pearson相似度算法、欧几里得相似度、余弦相似度算法,判断第一列Gl-1数据与其它四列数据(Gl-2,Gl-3,Gl-4,Gl-5)的相似程度,并找出哪一列与Gl-1数据最相似。

    Gl-1

    GL-2

    GL-3

    GL-4

    GL-5

    1.78

    1.78

    1.89

    1.89

    1.78

    1.53

    1.53

    1.64

    1.64

    1.53

    1.72

    1.72

    2.27

    2.27

    1.72

    1.47

    1.47

    2.17

    2.17

    1.47

    3.15

    3.15

    0

    0

    3.15

    1.66

    1.43

    1.79

    1.79

    1.43

    3.02

    1.89

    1.89

    1.89

    1.89

    2.77

    1.64

    1.64

    1.64

    1.64

    0

    3.69

    3.69

    3.69

    3.69

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    4.8

    4.8

    2.42

    2.42

    2.42

    0

    0

    2.17

    2.17

    2.17

    0

    0

    0

    0

    0

    2.15

    2.15

    2.19

    2.15

    2.15

    1.9

    1.9

    1.94

    1.9

    1.9

    1.98

    1.98

    2.68

    1.98

    1.98

    1.04

    1.04

    1.04

    1.04

    1.04

    1.3

    1.3

    1.3

    1.3

    1.3

    1.87

    1.87

    0

    1.87

    1.64

    0.96

    0.96

    1.82

    0.96

    0.96

    2.54

    2.54

    6.09

    2.54

    1.77

    2.29

    2.29

    0

    2.29

    0

    0

    0

    0

    0

    2.33

    2.81

    2.81

    3.29

    2.81

    0

    2.56

    2.56

    3.04

    2.56

    0

    2.58

    2.58

    2.58

    2.58

    0

    0

    0

    0

    0

    0

    1.14

    1.14

    1.14

    1.14

    0

    0.99

    0.99

    1.25

    1.25

    0.99

    0.99

    0.99

    1.25

    1.25

    0.99

    1.36

    1.36

    1.36

    1.36

    1.36

    2.21

    2.21

    0

    0

    0

    测试类 

    public class Test {
        public static void main(String[] args) {
            Data da = new Data();
            double[][] data =  da.getData();
            double[] GL1 = new double[35];
            double[] GL2 = new double[35];
            double[] GL3 = new double[35];
            double[] GL4 = new double[35];
            double[] GL5 = new double[35];
            for (int i = 0; i < 35; i++) {
                GL1[i] = data[0][i];
                GL2[i] = data[1][i];
                GL3[i] = data[2][i];
                GL4[i] = data[3][i];
                GL5[i] = data[4][i];
            }
    
            Inter inter = new Pearson();
            System.out.println("Person相似度算法:");
            System.out.print("GL-1 and GL-2:");inter.aldorithm_interface(GL1, GL2);
            System.out.print("GL-1 and GL-3:");inter.aldorithm_interface(GL1, GL3);
            System.out.print("GL-1 and GL-4:");inter.aldorithm_interface(GL1, GL4);
            System.out.print("GL-1 and GL-5:");inter.aldorithm_interface(GL1, GL5);
            System.out.println("由Person相似度算法得到和Gl-1最相似是Gl-2");
            System.out.println();
    
            Inter inter2 = new Euclid();
            System.out.println("欧几里得相似度算法:");
            System.out.print("GL-1 and GL-2:");inter2.aldorithm_interface(GL1, GL2);
            System.out.print("GL-1 and GL-3:");inter2.aldorithm_interface(GL1, GL3);
            System.out.print("GL-1 and GL-4:");inter2.aldorithm_interface(GL1, GL4);
            System.out.print("GL-1 and GL-5:");inter2.aldorithm_interface(GL1, GL5);
            System.out.println("由欧几里得相似度算法得到和Gl-1最相似是Gl-2");
            System.out.println();
    
            Inter inter1 = new Cosine_Similarity();
            System.out.println("余弦相似度算法:");
            System.out.print("GL-1 and GL-2:");inter1.aldorithm_interface(GL1, GL2);
            System.out.print("GL-1 and GL-3:");inter1.aldorithm_interface(GL1, GL3);
            System.out.print("GL-1 and GL-4:");inter1.aldorithm_interface(GL1, GL4);
            System.out.print("GL-1 and GL-5:");inter1.aldorithm_interface(GL1, GL5);
            System.out.println("由余弦相似度算法得到和Gl-1最相似是Gl-2");
            System.out.println();
    
        }
    }

    数据类

    
    
    import java.io.BufferedReader;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    
    public class Data {
        //创建两个函数
        //一个用于返回数据给Test
        public double[][] getData() {
            return data;
        }
        //一个用于修改数据
        public void setData(double[][] data) {
            this.data = data;
        }
    
        //将数据存进一个二维数组里面
        double[][] data = new double[5][35];//创建一个二维数组
        int p = 0;
        boolean flag = true;
        String pathname = "D:\\data.txt";//txt文件路径
        FileReader reader = null;
        //创建读取字符数据的流对象。
        /*
         * 在创建读取流对象时,必须要明确被读取的文件。一定要确定该文件是存在的。 。
         */
        {
            try {//是否存在文件
                reader = new FileReader(pathname);
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
    
            BufferedReader br = new BufferedReader(reader);
            //BufferedReader类从字符输入流中读取文本并缓冲字符,以便有效地读取字符,数组和行
            //创建一个BufferedReader对象,输入文件
            String line = null;
            while (true) {
                //用try catch,这样try中如果出现异常,会执行catch的代码
                try { //一次读入一行数据
                    if ((line = br.readLine()) == null)
                        break;
                } catch (IOException e) {
                    e.printStackTrace();//在命令行打印异常信息在程序中出错的位置及原因
                }
    
                if (flag) {
                    flag = false;
                    continue;
                }
    
                String[] str = line.split("\t");//以tab为分隔符创建字符串数组
                for (int i = 0; i < str.length; i++) {
                    data[i][p] = Double.parseDouble(str[i]);//讲字符转换成double
                }
                p++;
    
            }
    
        }
    }
    

    接口

    public interface Inter {
        public double aldorithm_interface(double g1[], double G[]);
    }

    皮尔逊算法

    public class Pearson implements Inter{
        double [] g1;
        double [] g2;
        double [] g3;
        double [] g4;
        double [] g5;
    
        public Pearson() {
            this.g1 = g1;
            this.g2 = g2;
            this.g3 = g3;
            this.g4 = g4;
            this.g5 = g5;
        }
    
        @Override
        public double aldorithm_interface(double[] g1, double[] G) {
            double result;
            double Numerator = 0;
            double Denominator ;
            double Denominator_x = 0;
            double Denominator_y = 0;
            double Average_x = 0;
            double Average_y = 0;
            for (int i = 0; i < g1.length; i++) {
                Average_x = Average_x + g1[i];
                Average_y = Average_y + G[i];
            }
            Average_x = Average_x / g1.length;
            Average_y = Average_y / G.length;
            for (int i = 0; i < g1.length; i++) {
                Numerator = (g1[i] - Average_x) * (G[i] - Average_y) + Numerator;
                Denominator_x = Math.pow((g1[i] - Average_x), 2) + Denominator_x;
                Denominator_y = Math.pow((G[i] - Average_y), 2) + Denominator_y;
            }
            Denominator = Math.sqrt(Denominator_x * Denominator_y);
            result = Numerator / Denominator;
            System.out.println(result);
            return result;
        }
    }

    余弦算法

    public  class Cosine_Similarity implements Inter{
    
        double [] g1;
        double [] g2;
        double [] g3;
        double [] g4;
        double [] g5;
    
        public Cosine_Similarity() {
            this.g1 = g1;
            this.g2 = g2;
            this.g3 = g3;
            this.g4 = g4;
            this.g5 = g5;
        }
        @Override
        public double aldorithm_interface(double[] g1, double[] G) {
            double result;
            double Numerator = 0;
            double Denominator;
            double Denominator_x = 0;
            double Denominator_y = 0;
    
            for (int i = 0; i < g1.length; i++) {
                Numerator = g1[i] * G[i] + Numerator;
                Denominator_x = Denominator_x + g1[i] * g1[i];
                Denominator_y = Denominator_y + G[i] * G[i];
            }
            Denominator = Math.sqrt(Denominator_x) * Math.sqrt(Denominator_y);
            result = Numerator / Denominator;
            System.out.println(result);
            return result;
        }
    }
    

    欧几里得算法

    public class Euclid implements Inter{
        double [] g1;
        double [] g2;
        double [] g3;
        double [] g4;
        double [] g5;
    
        public Euclid() {
            this.g1 = g1;
            this.g2 = g2;
            this.g3 = g3;
            this.g4 = g4;
            this.g5 = g5;
        }
    
        @Override
        public double aldorithm_interface(double[] g1, double[] G) {
            double result;
            double d = 0;
            for (int i = 0; i < g1.length; i++) {
                d = (g1[i] - G[i]) * (g1[i] - G[i]) + d;
            }
            result = 1 / (Math.sqrt(d) + 1);
            System.out.println(result);
    
            return result;
    
        }
    }

    展开全文
  • 文本相似度算法 基于Lucene3.5版本、TF-IDF、余弦相似实现的文本相似度算法。 详细介绍《》 样本库提取 使用webmagic爬取华为应用市场应用的描述信息,当做样本。 在工程的conf/doc目录有1000多个应用样本。 具体...
  • 易语言图片相似度算法源码
  • 本文实例讲述了.NET下文本相似度算法余弦定理和SimHash浅析及应用。分享给大家供大家参考。具体分析如下: 余弦相似性 原理:首先我们先把两段文本分词,列出来所有单词,其次我们计算每个词语的词频,最后把词语...
  • 字符串相似度算法

    2015-07-16 17:58:34
    两个字符串,计算出两个字符串的相似度,用于模糊匹配,很简单的小例子
  • NULL 博文链接:https://biansutao.iteye.com/blog/326008
  • 针对现有相似度算法存在查全率和查准率不高的问题,提出了一种基于本体的综合加权案例相似度算法。综合考虑案例的各个属性,分别采用不同的属性相似度计算方法,根据各个属性的重要程度加权,计算出案例的相似度。以...
  • 余弦相似度算法实现

    热门讨论 2013-06-07 11:29:38
    算法是用于文本相似的判定,同时也可以判定两个用户的相似性。算法是以C#实现的,封装完毕,如有急要可以留言哦
  • 两个字符串的相似度算法实现——编辑距离之Levenshtein距离
  • 针对现有相似度算法存在查全率和查准率不高的问题,提出了一种基于本体的综合加权案例相似度算法。综合考虑案例的各个属性,分别采用不同的属性相似度计算方法,根据各个属性的重要程度加权,计算出案例的相似度。以...
  • 本文于infoq,介绍了传统的hash算法,卷积神经网络计算图片相似度,...本文通过设计实验,对比三类图像相似度计算方法:感知哈希算法、基于局部不变性的图像相似度匹配算法以及基于卷积神经网络的图像相似度算法,权衡其
  • 针对目前概念相似度算法缺少语境信息的问题,提出了一种基于贝叶斯分类的概念相似度算法.该方法利用概念注释、借助语义词典Wordnet对概念扩充,利用贝叶斯分类技术确定相似概念,在一定程度上提高了相似度计算的准确率....
  • 基于语义相似度的中文文本相似度算法研究.pdf基于语义相似度的中文文本相似度算法研究.pdf基于语义相似度的中文文本相似度算法研究.pdf
  • 短文本相似度算法(distance.py) 基于分词后单词: edit_similar(str1,str2):编辑距离相似度,输入为分词后的两个句子的列表,返回值为两者相似度。 cos_sim(str1, str2):余弦相似度,输入为分词后的两个句子的列表...
  • 基于连接边权值的RDF数据语义相似度算法,张哲,俎云霄,随着互联网技术的飞速发展,网络中的数据资源迅猛增长,这就为高效地共享网络中的资源提出了新的要求,语义网技术应运而生。语义
  • 图片相似度算法(Java实现)

    千次阅读 2020-06-23 16:54:31
    图片相似度算法(Java实现)差值哈希算法主要流程代码均值哈希算法主要流程代码感知哈希算法大致流程代码附 在公司实习的时候接到一个任务:对视频抽帧生成的图片做去重处理。所以调研了一些有关计算图像相似度的...


    在公司实习的时候接到一个任务:对视频抽帧生成的图片做去重处理。所以调研了一些有关计算图像相似度的算法,目前只是用于对图片做去重处理,加以改进或许可以实现以图搜图。下面进入正题:

    差值哈希算法

    主要流程

    1. 缩小尺寸为9*8
    2. 简化色彩,转变为灰度图
    3. 计算灰度差值
    4. 计算哈希值

    代码

    	/**
         * 差值哈希算法
         * @param src
         * @return
         */
        public char[] dHash(BufferedImage src) {
            int width = 9;
            int height = 8;
            BufferedImage image = this.resize(src,height,width);
            int[] ints = new int[width * height];
            int index = 0;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    int pixel = image.getRGB(j, i);
                    int gray = this.gray(pixel);
                    ints[index++] = gray;
                }
            }
            StringBuilder builder = new StringBuilder();
            for (int i = 0;i < height;i++){
                for (int j = 0;j < width - 1;j++){
                    if (ints[9 * j + i] >= ints[9 * j + i + 1]){
                        builder.append(1);
                    }else {
                        builder.append(0);
                    }
                }
            }
            return builder.toString().toCharArray();
        }
    
    	/**
         * 简化色彩
         * @param rgb
         * @return
         */
        private int gray(int rgb) {
            int a = rgb & 0xff000000;//将最高位(24-31)的信息(alpha通道)存储到a变量
            int r = (rgb >> 16) & 0xff;//取出次高位(16-23)红色分量的信息
            int g = (rgb >> 8) & 0xff;//取出中位(8-15)绿色分量的信息
            int b = rgb & 0xff;//取出低位(0-7)蓝色分量的信息
            rgb = (r * 77 + g * 151 + b * 28) >> 8;    // NTSC luma,算出灰度值
            //(int)(r * 0.3 + g * 0.59 + b * 0.11)
            return a | (rgb << 16) | (rgb << 8) | rgb;//将灰度值送入各个颜色分量
        }
    
        /**
         * 改变图片尺寸
         * @param src 原图片
         * @param height 目标高度
         * @param width 目标宽度
         * @return
         */
        private BufferedImage resize(BufferedImage src, int height, int width) {
            BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_BGR);
            Graphics graphics = image.createGraphics();
            graphics.drawImage(src, 0, 0, width, height, null);
            return image;
        }
    
    

    以上代码求出了某张图片的灰度差值,如果要计算两张图片的相似度,只需要计算出两张图片灰度差值的汉明距离:

    	 /**
         * 计算汉明距离
         * @param c1
         * @param c2
         * @return
         */
        private int diff(char[] c1,char[] c2) {
            int diffCount = 0;
            for (int i = 0; i < c1.length; i++) {
                if (c1[i] != c2[i]) {
                    diffCount++;
                }
            }
            return diffCount;
        }
    

    均值哈希算法

    主要流程

    1. 缩小尺寸为8*8
    2. 简化色彩,转变为灰度图
    3. 计算64个像素的灰度平均值
    4. 比较每个像素的灰度
    5. 计算哈希值

    代码

    	/**
         * 均值哈希算法
         * @param src
         * @return
         */
        public char[] aHash(BufferedImage src) {
            int width = 8;
            int height = 8;
            BufferedImage image = this.resize(src,height,width);
            int total = 0;
            int[] ints = new int[width * height];
            int index = 0;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    int pixel = image.getRGB(j, i);
                    int gray = this.gray(pixel);
                    ints[index++] = gray;
                    total = total + gray;
                }
            }
            StringBuffer res = new StringBuffer();
            int grayAvg = total / (width * height);
            for (int anInt : ints) {
                if (anInt >= grayAvg) {
                    res.append("1");
                } else {
                    res.append("0");
                }
            }
            return res.toString().toCharArray();
        }
    

    简化色彩,缩小尺寸和比较汉明距离的代码和差值哈希算法里的一样,这里就不赘述了。

    感知哈希算法

    主要流程

    1. 缩小尺寸为8*8
    2. 简化色彩,转变为灰度图
    3. 计算DCT,得到32*32的DCT系数矩阵
    4. 缩小DCT,只保留左上角的8*8的矩阵
    5. 计算DCT的平均值
    6. 计算哈希值

    代码

    	 /**
         * 感知哈希算法
         * @param src
         * @return
         */
        public char[] pHash(BufferedImage src) {
            int width = 8;
            int height = 8;
            BufferedImage image = this.resize(src,height,width);
            int[] dctDate = new int[width * height];
            int index = 0;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    int pixel = image.getRGB(j, i);
                    int gray = this.gray(pixel);
                    dctDate[index++] = gray;
                }
            }
            dctDate = DCT.DCT(dctDate,width);
            int avg = DCT.averageGray(dctDate ,width,height);
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<height; i++) {
                for(int j=0; j<width; j++) {
                    if(dctDate[i*height + j] >= avg) {
                        sb.append("1");
                    } else {
                        sb.append("0");
                    }
                }
            }
            long result;
            if(sb.charAt(0) == '0') {
                result = Long.parseLong(sb.toString(), 2);
            } else {
                //如果第一个字符是1,则表示负数,不能直接转换成long,
                result = 0x8000000000000000l ^ Long.parseLong(sb.substring(1), 2);
            }
    
            sb = new StringBuilder(Long.toHexString(result));
            if(sb.length() < 16) {
                int n = 16-sb.length();
                for(int i=0; i<n; i++) {
                    sb.insert(0, "0");
                }
            }
            return sb.toString().toCharArray();
        }
        
    	 /**
         * 离散余弦变换
         * @param pix 原图像的数据矩阵
         * @param n 原图像(n*n)的高或宽
         * @return 变换后的矩阵数组
         */
        public static int[] DCT(int[] pix, int n) {
            double[][] iMatrix = new double[n][n];
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    iMatrix[i][j] = (double)(pix[i*n + j]);
                }
            }
            double[][] quotient = coefficient(n);	//求系数矩阵
            double[][] quotientT = transposingMatrix(quotient, n);	//转置系数矩阵
    
            double[][] temp = matrixMultiply(quotient, iMatrix, n);
            iMatrix =  matrixMultiply(temp, quotientT, n);
    
            int newpix[] = new int[n*n];
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    newpix[i*n + j] = (int)iMatrix[i][j];
                }
            }
            return newpix;
        }
        
        /**
         * 矩阵转置
         * @param matrix 原矩阵
         * @param n 矩阵(n*n)的高或宽
         * @return 转置后的矩阵
         */
        private static double[][]  transposingMatrix(double[][] matrix, int n) {
            double nMatrix[][] = new double[n][n];
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    nMatrix[i][j] = matrix[j][i];
                }
            }
            return nMatrix;
        }
        
        /**
         * 求离散余弦变换的系数矩阵
         * @param n n*n矩阵的大小
         * @return 系数矩阵
         */
        private static double[][] coefficient(int n) {
            double[][] coeff = new double[n][n];
            double sqrt = 1.0/Math.sqrt(n);
            for(int i=0; i<n; i++) {
                coeff[0][i] = sqrt;
            }
            for(int i=1; i<n; i++) {
                for(int j=0; j<n; j++) {
                    coeff[i][j] = Math.sqrt(2.0/n) * Math.cos(i*Math.PI*(j+0.5)/(double)n);
                }
            }
            return coeff;
        }
        
        /**
         * 矩阵相乘
         * @param A 矩阵A
         * @param B 矩阵B
         * @param n 矩阵的大小n*n
         * @return 结果矩阵
         */
        private static double[][] matrixMultiply(double[][] A, double[][] B, int n) {
            double nMatrix[][] = new double[n][n];
            double t;
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    t = 0;
                    for(int k=0; k<n; k++) {
                        t += A[i][k]*B[k][j];
                    }
                    nMatrix[i][j] = t;
                }
            }
            return nMatrix;
        }
    
        /**
         * 求灰度图像的均值
         * @param pix 图像的像素矩阵
         * @param w 图像的宽
         * @param h 图像的高
         * @return 灰度均值
         */
        public static int averageGray(int[] pix, int w, int h) {
            int sum = 0;
            for(int i=0; i<h; i++) {
                for(int j=0; j<w; j++) {
                    sum = sum+pix[i*w + j];
                }
            }
            return sum/(w*h);
        }
    

    简化色彩,缩小尺寸和比较汉明距离的代码同上。

    测试发现Java对图片的读取速度非常慢,所以引入了OpenCV对图片进行处理,以下为OpenCV处理图片的代码:

    import com.image.DCT;
    import org.opencv.core.*;
    import org.opencv.imgproc.Imgproc;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    import static org.opencv.imgcodecs.Imgcodecs.imread;
    
    public class OpenCV {
    
        /** 均值哈希算法
         * @param src 图片路径
         * @return
         */
        public static char[] aHash(String src){
            StringBuffer res = new StringBuffer();
            try {
                int width = 8;
                int height = 8;
                Mat mat = imread(src);
                Mat resizeMat = new Mat();
                Imgproc.resize(mat,resizeMat, new Size(width, height),0,0);
                // 将缩小后的图片转换为64级灰度(简化色彩)
                int total = 0;
                int[] ints = new int[64];
                int index = 0;
                for (int i = 0;i < height;i++){
                    for (int j = 0;j < width;j++){
                        int gray = gray(resizeMat.get(i, j));
                        ints[index++] = gray;
                        total = total + gray;
                    }
                }
                // 计算灰度平均值
                int grayAvg = total / (width * height);
                // 比较像素的灰度
                for (int anInt : ints) {
                    if (anInt >= grayAvg) {
                        res.append("1");
                    } else {
                        res.append("0");
                    }
                }
            }catch (Exception e){
                e.printStackTrace();
            }
            return res.toString().toCharArray();
        }
    
        /** 感知哈希算法
         * @param src
         * @return
         */
        public static char[] pHash(String src){
            int width = 8;
            int height = 8;
            Mat mat = imread(src);
            Mat resizeMat = new Mat();
            Imgproc.resize(mat,resizeMat, new Size(width, height),0,0);
            int[] dctDate = new int[width * height];
            int index = 0;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    dctDate[index++] = gray(resizeMat.get(i, j));
                }
            }
            dctDate = DCT.DCT(dctDate,width);
            int avg = DCT.averageGray(dctDate ,width,height);
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<height; i++) {
                for(int j=0; j<width; j++) {
                    if(dctDate[i*height + j] >= avg) {
                        sb.append("1");
                    } else {
                        sb.append("0");
                    }
                }
            }
            long result;
            if(sb.charAt(0) == '0') {
                result = Long.parseLong(sb.toString(), 2);
            } else {
                //如果第一个字符是1,则表示负数,不能直接转换成long,
                result = 0x8000000000000000l ^ Long.parseLong(sb.substring(1), 2);
            }
    
            sb = new StringBuilder(Long.toHexString(result));
            if(sb.length() < 16) {
                int n = 16-sb.length();
                for(int i=0; i<n; i++) {
                    sb.insert(0, "0");
                }
            }
            return sb.toString().toCharArray();
        }
    
        /** 差值哈希算法
         * @param src
         * @return
         */
        public static char[] dHash(String src){
            int width = 9;
            int height = 8;
            Mat mat = imread(src);
            Mat resizeMat = new Mat();
            Imgproc.resize(mat,resizeMat, new Size(width, height),0,0);
            int[] ints = new int[width * height];
            int index = 0;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    ints[index++] = gray(resizeMat.get(i, j));
                }
            }
            StringBuilder builder = new StringBuilder();
            for (int i = 0;i < height;i++){
                for (int j = 0;j < width - 1;j++){
                    if (ints[9 * j + i] >= ints[9 * j + i + 1]){
                        builder.append(1);
                    }else {
                        builder.append(0);
                    }
                }
            }
            return builder.toString().toCharArray();
        }
    
        /** 简化色彩
         * @param bgr
         * @return
         */
        private static int gray(double[] bgr) {
            int rgb = (int) (bgr[2] * 77 + bgr[1] * 151 + bgr[0] * 28) >> 8;
            int gray = (rgb << 16) | (rgb << 8) | rgb;
            return gray;
        }
    
        /** 计算汉明距离
         * @param c1
         * @param c2
         * @return
         */
        private static int diff(char[] c1,char[] c2){
            int diffCount = 0;
            for (int i = 0; i < c1.length; i++) {
                if (c1[i] != c2[i]) {
                    diffCount++;
                }
            }
            return diffCount;
        }
    
    展开全文
  • 五种常见的相似度算法:余弦相似度(cosine_similarity)、jaccard相似度、编辑距离(Levenshtein)、MinHash、SimHash+海明距离

    五种常见的相似度算法:余弦相似度(cosine_similarity)、jaccard相似度、编辑距离(Levenshtein)、MinHash、SimHash + 海明距离

    展开全文
  • 【短文本】短文本相似度算法研究

    千次阅读 2020-03-15 11:00:00
    公众号关注“ML_NLP”设为 “星标”,重磅干货,第一时间送达!机器学习算法与自然语言处理出品@公众号原创专栏作者 刘聪NLP学校 |NLP算法工...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,398
精华内容 26,959
关键字:

相似度算法