无敌的Log-Likelihood Ratio(1)——LLR的计算方式_log likelihood ratio-程序员宅基地

文章目录

1. LLR的计算方式
2. LLR的代码实现
3 相关疑问
4 参考资料

Ted\; Dunning

在

《Accurate\; Methods\; for\; the\; Statistics\; of\; Surprise\; and\; Coincidence》

中介绍了

Log-Likehood\; Ratio

在文本计算中的基本使用。

L L R

因为实现简单、有效并且具有大规模数据上的可扩展性，能够被很好的使用到工业系统中。因此基于

L L R

的相似度度量广泛应用在推荐系统等多种应用当中。
在这篇Blog中，我们忽略

《Accurate\; Methods\; for\; the\; Statistics\; of\; Surprise\; and\; Coincidence》

中对

L L R

过多的冗余描述，主要集中的去关注

L L R

的计算方式和现有的一些简单有效的代码实现。
本篇博客的组织方式如下。在章节1中，以最简单的方式讨论了

Log-Likelihood\; Ratio

相似度的计算方式，在章节2中讨论了

Log-Likelihood\; Ratio

的具体的代码实现，以及一些可以现用的相似度计算工具。

1. LLR的计算方式

在计算两个事件(例如推荐系统中的点击行为)的 $L L R$ 值来做相似度衡量的时候，我们通过两个事件的计数来计算事件之间的相似度。接下来我们以推荐系统中物品相似度的计算为例来介绍 $L L R$ 的计算方式。
有两个物品分别为物品 $i$ 和物品 $j$ 。对应事件计数的简单形式化描述如下：
$k_{11}$ ：表示同时浏览了物品 $i$ 和物品 $j$ 的用户。
$k_{12}$ ：表示浏览了物品 $i$ ，但是没有浏览物品 $j$ 的用户。
$k_{21}$ ：表示浏览了物品 $j$ ，但是没有浏览物品 $i$ 的用户。
$k_{22}$ ：表示没有浏览物品 $i$ ，并且没有浏览物品 $j$ 的用户。
根据上述，我们可以得到如下的一个表格:

事件	浏览 $Item\;i$	没有浏览 $Item\;i$
浏览 $Item\; j$	$k_{11}$	$k_{21}$
没有浏览 $Item\;j$	$k_{12}$	$k_{22}$

$Item\; i$ 和 $Item\;j$ 的 $L L R$ 计算公式如下：
$S=2\times (H_m - H_c - H_r)$
其中：
$H_m$ 表示上述矩阵的矩阵熵，总体的计算公式如下：
$H_m = - (\frac{k_{11}}{N}\;log(\frac{k_{11}}{N}) + \frac{k_{12}}{N}\;log(\frac{k_{12}}{N}) + \frac{k_{21}}{N}\;log(\frac{k_{21}}{N}) + \frac{k_{22}}{N}\;log(\frac{k_{22}}{N}))$
$H_r$ 表示每行相加计算得到的信息熵，相关的具体计算公式如下：
$H_r = -(\frac{k_{11} + k_{12}}{N}\; log(\frac{k_{11}+k_{12}}{N}) +\frac{k_{21} + k_{22}}{N}log(\frac{k_{21} + k_{22}}{N}))$
$H_c$ 表示矩阵的每一列相加计算得到的信息熵，相关的具体计算公式如下：
$H_c=-(\frac{k_{11} + k_{21}}{N}\; log(\frac{k_{11}+k_{21}}{N}) +\frac{k_{21} + k_{22}}{N}log(\frac{k_{21} + k_{22}}{N}))$

其中 $N=k_{11} + k_{12} + k_{21} + k_{22}$

2. LLR的代码实现

在 $M a h o u t$ 的 $m a t h$ 库中定义了 $L o g L i k e l i h o o d$ 类，实现了 $L L R$ 的计算，其中具体的计算代码在下面给出。

$r o w E n t r o p y$ 的计算方式如下

private static double xLogX(long x) {
    
    return x == 0 ? 0.0 : x * Math.log(x);
  }

private static double entropy(long a, long b) {
    
    return xLogX(a + b) - xLogX(a) - xLogX(b);
  }

其中 $a=k_{11} + k_{12}$ 并且 $b=k_{21} + k_{22}$ ，综合得到
$\times log\;(N) - (k_{11} + k_{12}) \times log\;(k_{11} + k_{12}) -(k_{21} + k_{22} )\times log\;(k_{21} + k_{22})) \\ \;\\ = -((k_{11}+k_{12})\times log\;(N)-(k_{11} + k_{12}) \times log\;(k_{11} + k_{12}) + (k_{21} + k_{22}) \times log\;(N) - (k_{21} + k_{22} )\times log\;(k_{21} + k_{22})) \\ \;\\ =-((k_{11} + k_{12}) \times(log(N)-log(k_{11}+k_{12})) + (k_{21} + k_{22}) \times(log(N)-log(k_{21}+k_{22})))\\ \;\\ =(k_{11} +k_{12}) \times(log\;\frac{k_{11} + k_{12}}{N}) + (k_{21} + k_{22}) \times(log\;\frac{k_{21} + k_{22}}{N}) = - H_r \times N$

同样的 $c o l E n t r o p y$ 的计算方式如下:
$(k_{11} +k_{21}) \times(log\;\frac{k_{11} + k_{21}}{N}) + (k_{12} + k_{22}) \times(log\;\frac{k_{12} + k_{22}}{N}) = -H_c \times N$

$m a t r i x E n t r o p y$ 的计算方式

private static double entropy(long a, long b, long c, long d) {
    
    return xLogX(a + b + c + d) - xLogX(a) - xLogX(b) - xLogX(c) - xLogX(d);
  }

$N\times log\;(N) - k_{11}\;log(k_{11}) -k_{12}\;log(k_{12}) - k_{21}\;log\;(k_{21}) - k_{22}\;log(k_{22}) \\ \;\\ = - (k_{11}\times log\;(\frac{k_{11}}{N})+k_{12}\times log\;(\frac{k_{12}}{N}) + k_{21}\times log\;(\frac{k_{21}}{N})) + k_{21}\times log\;(\frac{k_{21}}{N})) \times N$

最终相似度 $S$ 的计算结果

public static double logLikelihoodRatio(long k11, long k12, long k21, long k22) {
    
    Preconditions.checkArgument(k11 >= 0 && k12 >= 0 && k21 >= 0 && k22 >= 0);
    // note that we have counts here, not probabilities, and that the entropy is not normalized.
    double rowEntropy = entropy(k11 + k12, k21 + k22);
    double columnEntropy = entropy(k11 + k21, k12 + k22);
    double matrixEntropy = entropy(k11, k12, k21, k22);
    if (rowEntropy + columnEntropy < matrixEntropy) {
    
      // round off error
      return 0.0;
    }
    return 2.0 * (rowEntropy + columnEntropy - matrixEntropy);
  }

$\times(rowEntropy + colEntropy - matrixEntropy) = 2 \times (- \frac{H_r}{N} - \frac{H_c}{N} + \frac{H_m}{N}) = \frac{2}{N}(H_m - H_r - H_c)$

在代码实现里面相似度的计算过程中把 $N$ 约掉了,所以在 $m a h o u t$ 计算当中实际计算得到的值为
$S=\frac{2}{N}(H_m - H_r - H_c)$

3 相关疑问

问题 1: 在代码的计算过程中，约掉分母 $N$ 对整个结果有影响嘛？
问题 2: 在有些博客资料中称 $H_r$ 为行熵，称 $H_c$ 为列熵，并且计算公式不如下:
博客相关资料截图
这种方式和我上面描述的计算方式等价嘛？那种更准确？

欢迎大家留言讨论，如果有问题或者建议的地方希望大家能够提出再核对问题后我会在第一时间进行修正。

4 参考资料

【1】LLR (Log-Likelihood Ratio) used for recommendations
【2】Accurate Methods for the Statistics of Surprise and Coincidence
【3】Building a Correlated Cross-Occurrence (CCO) Recommenders with the Mahout CLI
【4】github · Mathout LogLikelihood Similarity
【5】Surprise and Coincidence
【6】loglikelihood ratio 相似度

本文链接：https://blog.csdn.net/redhatforyou/article/details/104052951

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

从零开始搭建Hadoop_创建一个hadoop项目-程序员宅基地

文章浏览阅读331次。第一部分：准备工作1 安装虚拟机2 安装centos73 安装JDK以上三步是准备工作，至此已经完成一台已安装JDK的主机第二部分：准备３台虚拟机以下所有工作最好都在root权限下操作1 克隆上面已经有一台虚拟机了,现在对master进行克隆,克隆出另外2台子机;1.1 进行克隆21.2 下一步1.3 下一步1.4 下一步1.5 根据子机需要,命名和安装路径1.6 ..._创建一个hadoop项目

心脏滴血漏洞HeartBleed CVE-2014-0160深入代码层面的分析_heartbleed代码分析-程序员宅基地

文章浏览阅读1.7k次。心脏滴血漏洞HeartBleed CVE-2014-0160 是由heartbeat功能引入的，本文从深入码层面的分析该漏洞产生的原因_heartbleed代码分析

java读取ofd文档内容_ofd电子文档内容分析工具（分析文档、签章和证书）-程序员宅基地

文章浏览阅读1.4k次。前言ofd是国家文档标准，其对标的文档格式是pdf。ofd文档是容器格式文件，ofd其实就是压缩包。将ofd文件后缀改为.zip，解压后可看到文件包含的内容。ofd文件分析工具下载：点我下载。ofd文件解压后，可以看到如下内容：对于xml文件，可以用文本工具查看。但是对于印章文件(Seal.esl)、签名文件(SignedValue.dat)就无法查看其内容了。本人开发一款ofd内容查看器，..._signedvalue.dat

基于FPGA的数据采集系统（一）_基于fpga的信息采集-程序员宅基地

文章浏览阅读1.8w次，点赞29次，收藏313次。整体系统设计本设计主要是对ADC和DAC的使用，主要实现功能流程为：首先通过串口向FPGA发送控制信号，控制DAC芯片tlv5618进行DA装换，转换的数据存在ROM中，转换开始时读取ROM中数据进行读取转换。其次用按键控制adc128s052进行模数转换100次，模数转换数据存储到FIFO中，再从FIFO中读取数据通过串口输出显示在pc上。其整体系统框图如下：图1：FPGA数据采集系统框图从图中可以看出，该系统主要包括9个模块：串口接收模块、按键消抖模块、按键控制模块、ROM模块、D.._基于fpga的信息采集

微服务 spring cloud zuul com.netflix.zuul.exception.ZuulException GENERAL-程序员宅基地

文章浏览阅读2.5w次。1.背景错误信息：-- [http-nio-9904-exec-5] o.s.c.n.z.filters.post.SendErrorFilter : Error during filteringcom.netflix.zuul.exception.ZuulException: Forwarding error at org.springframework.cloud..._com.netflix.zuul.exception.zuulexception

邻接矩阵-建立图-程序员宅基地

文章浏览阅读358次。1.介绍图的相关概念　　图是由顶点的有穷非空集和一个描述顶点之间关系-边（或者弧）的集合组成。通常，图中的数据元素被称为顶点，顶点间的关系用边表示，图通常用字母G表示，图的顶点通常用字母V表示，所以图可以定义为:　　G=(V,E)其中，V(G)是图中顶点的有穷非空集合，E(G)是V(G)中顶点的边的有穷集合1.1 无向图：图中任意两个顶点构成的边是没有方向的1.2 有向图：图中..._给定一个邻接矩阵未必能够造出一个图

随便推点

MDT2012部署系列之11 WDS安装与配置-程序员宅基地

文章浏览阅读321次。（十二）、WDS服务器安装通过前面的测试我们会发现，每次安装的时候需要加域光盘映像，这是一个比较麻烦的事情，试想一个上万个的公司，你天天带着一个光盘与光驱去给别人装系统，这将是一个多么痛苦的事情啊，有什么方法可以解决这个问题了？答案是肯定的，下面我们就来简单说一下。WDS服务器，它是Windows自带的一个免费的基于系统本身角色的一个功能，它主要提供一种简单、安全的通过网络快速、远程将Window..._doc server2012上通过wds+mdt无人值守部署win11系统.doc

python--xlrd/xlwt/xlutils_xlutils模块可以读xlsx吗-程序员宅基地

文章浏览阅读219次。python–xlrd/xlwt/xlutilsxlrd只能读取，不能改,支持 xlsx和xls 格式xlwt只能改，不能读xlwt只能保存为.xls格式xlutils能将xlrd.Book转为xlwt.Workbook，从而得以在现有xls的基础上修改数据，并创建一个新的xls，实现修改xlrd打开文件import xlrdexcel=xlrd.open_workbook('E:/test.xlsx') 返回值为xlrd.book.Book对象,不能修改获取sheett_xlutils模块可以读xlsx吗

关于新版本selenium定位元素报错：‘WebDriver‘ object has no attribute ‘find_element_by_id‘等问题_unresolved attribute reference 'find_element_by_id-程序员宅基地

文章浏览阅读8.2w次，点赞267次，收藏656次。运行Selenium出现'WebDriver' object has no attribute 'find_element_by_id'或AttributeError: 'WebDriver' object has no attribute 'find_element_by_xpath'等定位元素代码错误，是因为selenium更新到了新的版本，以前的一些语法经过改动。..............._unresolved attribute reference 'find_element_by_id' for class 'webdriver