粉丝日志 | 跨界的IT博客| R, 数据科学, 金融量化, Nodejs, Hadoop家族,区块链

Posted:

Jul 3, 2025

Tags:

Comments:

用R语言实现方差分析ANOVA

R的极客理想系列文章，涵盖了R的思想，使用，工具，创新等的一系列要点，以我个人的学习和体验去诠释R的强大。

R语言作为统计学一门语言，一直在小众领域闪耀着光芒。直到大数据的爆发，R语言变成了一门炙手可热的数据分析的利器。随着越来越多的工程背景的人的加入，R语言的社区在迅速扩大成长。现在已不仅仅是统计领域，教育，银行，电商，互联网….都在使用R语言。

要成为有理想的极客，我们不能停留在语法上，要掌握牢固的数学，概率，统计知识，同时还要有创新精神，把R语言发挥到各个领域。让我们一起动起来吧，开始R的极客理想。

关于作者：

张丹，分析师/程序员/Quant: R,Java,Nodejs
blog: http://blog.fens.me
email: bsspirit@gmail.com

转载请注明出处：
http://blog.fens.me/r-stat-anova/

前言

方差分析是一种基本统计学方法，在众多领域都有非常广泛的应用，比如评估不同药物的疗效，不同的广告策略的效果。

大模型的时代，是否能用方差分析，判断大模型结论与实际结论，是否有显著性差异，那么就能够快速验证大模型的是否产生了幻觉，以此来对大模型进行改进。

方差分析介绍
用R语言方差分析aov()函数
用R语言方进行方差分析

1. 方差分析介绍

方差分析(Analysis of Variance，简称ANOVA)是一种用于比较多个群体均值是否存在显著差异的统计方法。它通过分析数据中不同来源的变异来检验均值差异的显著性。

方差分析的核心思想是将总变异分解为,组间变异(不同处理组之间的差异)和组内变异(同一组内的个体差异)，通过比较这两种变异的相对大小来判断均值差异是否显著。

方差分析的主要类型为，

单因素方差分析(One-way ANOVA)：比较一个分类自变量(因素)对连续因变量的影响，例如：比较三种不同教学方法对学生成绩的影响
双因素方差分析(Two-way ANOVA)：同时考察两个分类自变量对连续因变量的影响，可以分析主效应和交互效应，例如：研究性别(男/女)和教学方法(A/B/C)对学生成绩的共同影响
多元方差分析(MANOVA)：适用于多个连续因变量的情况

ANOVA的核心目标是区分数据变异性的来源：是由实验条件（或处理）的不同引起的，还是由随机变异（即自然波动或实验误差）引起的。这种区分有助于我们判断实验条件是否对研究变量有显著影响。

ANOVA的关键组成部分

总方差（Total Variance）: 数据总体的方差，包括组间方差和组内方差。
组间方差（Between-Group Variance）: 不同组（或处理条件）间均值的差异。
组内方差（Within-Group Variance）: 同一组内个体间的差异。

通过比较组间方差和组内方差，ANOVA帮助我们判断各组间是否存在显著的均值差异。如果组间方差显著大于组内方差，我们有理由相信不同组的均值存在显著差异。

方差分析的基本假设

正态性：每个组的数据应近似呈正态分布。这意味着数据的分布应该是对称的，没有明显的偏斜，使用Shapiro-Wilk检验
方差齐性：所有组的方差应该大致相等。这个假设确保了不同组别的数据具有一致的波动性，使用Levene’s Test或Bartlett’s Test来检验
独立性：数据点之间应该是相互独立的，即一个数据点的值不应影响或决定另一个数据点的值。

方差分析步骤

提出假设：零假设(H₀)：所有组的均值相等，即组间不存在显著差异。备择假设(H₁)：至少有两组的均值不等，即存在至少一个组间的显著差异。
计算组间和组内方差：组间方差（Between-Group Variance）：计算每个组的均值与总体均值之间的差异，反映了不同处理或条件下数据的变化程度。组内方差（Within-Group Variance）：计算组内数据点与各自组均值的差异，表示在相同条件下的数据波动。
计算F统计量：F值是方差分析中的核心统计量，它是组间方差与组内方差的比率：F = 组间方差 / 组内方差，较高的F值通常表明组间存在显著差异。但我们需要通过F分布来确定这个差异是否统计上显著。
将计算得到的F值与临界值比较，或直接看p值，根据自由度和显著性水平（通常是0.05）找到F值的临界值。如果计算出的F值超过临界值，我们拒绝零假设，认为至少有两组间存在显著差异。
做出统计决策

事后检验：当方差分析结果显示显著差异时，需要进行事后检验(Post-hoc tests)来确定具体哪些组之间存在差异，常用方法包括：Tukey’s HSD检验，Bonferroni校正，Scheffe检验。

2. 用R语言方差分析aov()函数

R中的方差分析（ANOVA）是一种统计方法，用于比较两个或多个组之间的均值是否存在显著差异。在R语言中，可以使用ANOVA函数（aov）进行方差分析。

在R语言中，自带的stat包的aov()函数，就是我们最常用方差分析的计算函数。

aov()函数的语法为aov(formula, data=dataframe)，y是因变量，字母ABC代表因子。

R语言代码的写法：


model <- aov(response ~ group, data = dataset)
summary(model)

符号	用途
~	分隔符号，左边为响应变量（因变量），右边为解释变量（自变量），如 y ~ A + B + C
:	表示预测变量的交互项，A与B的交互，如y ~ A + B + A:B
*	表示所有可能交互项的简洁方式，如 y ~ ABC 等同于 y ~ A+B+C + A:B + A:C + B:C + A:B:C
^	表示交互项达到某个次数，如y~(A+B+C)^2 等同于 y~ A+B+C + A:B + A:C + B:C
.	表示包含除因变量外的所有变量，如y~. 等同于 y~ A+B+C

下面是常见研究设计的表达式

设计	表达式
单因素ANOVA	y ~ A
含单个协变量的单因素ANOVA	y ~ x + A
双因素ANOVA	y ~ A * B
含两个协变量的双因素ANOVA	y ~ x1 + x2 + A * B
随机化区组	y ~ B + A (B是区组因子)
单因素组内ANOVA	y ~ A + Error(subject/A)
含单个组内因子(W)和单个组间因子的重复测量ANOVA	y ~ B * W + Error(Subject/W)

3. R语言实现方差分析

数据集使用datarium包的职位满意度调查jobsatisfaction数据集。


# 安装datarium
> install.packages("datarium")

# 加载程序包
> library(datarium)
> library(dplyr)

查看jobsatisfaction数据集的基本情况，共4列，ID,gender性别，education_level学历水平，score得分。


> data("jobsatisfaction", package = "datarium")
> jobsatisfaction
# A tibble: 58 × 4
   id    gender education_level score
                 
 1 1     male   school           5.51
 2 2     male   school           5.65
 3 3     male   school           5.07
 4 4     male   school           5.51
 5 5     male   school           5.94
 6 6     male   school           5.8 
 7 7     male   school           5.22
 8 8     male   school           5.36
 9 9     male   school           4.78
10 10    male   college          6.01
# ℹ 48 more rows
# ℹ Use `print(n = ...)` to see more rows

# 查看统计概率
> summary(jobsatisfaction)
       id        gender     education_level     score       
 1      : 1   male  :28   school    :19     Min.   : 4.780  
 2      : 1   female:30   college   :19     1st Qu.: 5.800  
 3      : 1               university:20     Median : 6.380  
 4      : 1                                 Mean   : 6.963  
 5      : 1                                 3rd Qu.: 8.515  
 6      : 1                                 Max.   :10.000

对数据集进行分组gender, education_level，计算均值和标准差


> jobsatisfaction %>%
+   group_by(gender, education_level) %>%
+   get_summary_stats(score, type = "mean_sd")
# A tibble: 6 × 6
  gender education_level variable     n  mean    sd
                     
1 male   school          score        9  5.43 0.364
2 male   college         score        9  6.22 0.34 
3 male   university      score       10  9.29 0.445
4 female school          score       10  5.74 0.474
5 female college         score       10  6.46 0.475
6 female university      score       10  8.41 0.938

画出分组的数据分箱图


> ggboxplot(
+   jobsatisfaction, x = "gender", y = "score",
+   color = "education_level", palette = "jco"
+ )

建立方差分析模型，有几个变量我们就全部都加入分析，以score为因变量，以gender和education_level的组合为自变量。


# 建模
> model<- aov(score ~ gender*education_level, data = jobsatisfaction)

# 查看因子显著性水平
> summary(model)
                       Df Sum Sq Mean Sq F value  Pr(>F)    
gender                  1   0.54    0.54   1.787 0.18709    
education_level         2 113.68   56.84 187.892 < 2e-16 ***
gender:education_level  2   4.44    2.22   7.338 0.00156 ** 
Residuals              52  15.73    0.30                    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

其中，education_level和gender:education_level的P值对score有影响，gender没有影响。

对模型进行正态分布检验shapiro.test，p值大于0.05，说明符合正态分布。


> shapiro.test(residuals(model))

	Shapiro-Wilk normality test

data:  residuals(model)
W = 0.96786, p-value = 0.1267

进行方差齐性检验bartlett.test，p值小于0.05，说明education_level方差有显著地不同，方差不是齐性的。


> bartlett.test(score ~ education_level, data = jobsatisfaction)

	Bartlett test of homogeneity of variances

data:  score by education_level
Bartlett's K-squared = 11.651, df = 2, p-value = 0.002951

进行方差齐性检验bartlett.test，p值大于0.05，说明gender方差没有显著地不同，方差是齐性的。


> bartlett.test(score ~ gender, data = jobsatisfaction)

	Bartlett test of homogeneity of variances

data:  score by gender
Bartlett's K-squared = 2.3701, df = 1, p-value = 0.1237

Bartlett's K-squared:Bartlett's K-squared是Bartlett检验的统计量，用于衡量不同组间方差的差异。它是通过计算各组的方差并比较它们之间的差异而得出的。如果各组方差相等，则K-squared值应较小;如果方差不相等，K-squared值则较大。

df(自由度):自由度(degrees offreedom，df)是统计分析中的一个重要概念，它指的是在计算某个统计量时，可以自由变化的数值的数量。在上面 Bartlett检验中，由于假设有三个不同种族的组来比较它们之间的出生体重(bwt)的方差，自由度等于组数减一(这里为2)。

p-value(p值):p值用于衡量观察到的统计量在假设检验中的极端性。具体来说，它表示在零假设为真的情况下，观察到像样或更极端结果的概率。若p值小于某个显著性水平(通常为0.05)，则我们拒绝零假设;若p值大于显著性水平，则不能拒绝零假设。在Bartlett检验中，p值大于0.05表示没有足够的证据表明各组间方差存在显著差异。

使用Tukey’s HSD检验，进行分组的显著差异。


> TukeyHSD(model)
  Tukey multiple comparisons of means
    95% family-wise confidence level

Fit: aov(formula = score ~ gender * education_level, data = jobsatisfaction)

$gender
                  diff        lwr        upr     p adj
female-male -0.1932143 -0.4832329 0.09680436 0.1870895

$education_level
                        diff       lwr      upr     p adj
college-school     0.7573684 0.3268386 1.187898 0.0002637
university-school  3.2518102 2.8266960 3.676924 0.0000000
university-college 2.4944417 2.0693275 2.919556 0.0000000

$`gender:education_level`
                                        diff          lwr        upr
female:school-male:school          0.3143333 -0.433358082  1.0620247
male:college-male:school           0.7966667  0.029551460  1.5637819
female:college-male:school         1.0363333  0.288641918  1.7840247
male:university-male:school        3.8653333  3.117641918  4.6130247
female:university-male:school      2.9793333  2.231641918  3.7270247
male:college-female:school         0.4823333 -0.265358082  1.2300247
female:college-female:school       0.7220000 -0.005749384  1.4497494
male:university-female:school      3.5510000  2.823250616  4.2787494
female:university-female:school    2.6650000  1.937250616  3.3927494
female:college-male:college        0.2396667 -0.508024749  0.9873581
male:university-male:college       3.0686667  2.320975251  3.8163581
female:university-male:college     2.1826667  1.434975251  2.9303581
male:university-female:college     2.8290000  2.101250616  3.5567494
female:university-female:college   1.9430000  1.215250616  2.6707494
female:university-male:university -0.8860000 -1.613749384 -0.1582506
                                      p adj
female:school-male:school         0.8132166
male:college-male:school          0.0374890
female:college-male:school        0.0019203
male:university-male:school       0.0000000
female:university-male:school     0.0000000
male:college-female:school        0.4086560
female:college-female:school      0.0529764
male:university-female:school     0.0000000
female:university-female:school   0.0000000
female:college-male:college       0.9317495
male:university-male:college      0.0000000
female:university-male:college    0.0000000
male:university-female:college    0.0000000
female:university-female:college  0.0000000
female:university-male:university 0.0087499

TukeyHSD的检验，education_level的显著性水平最高，所以我们画出education_level检验图。


> plot(TukeyHSD(model, "education_level"))

本文通过方差分析，实现对不同变量的影响权重的计算，可以通过统计学的方法，发现新的变量特征。

转载请注明出处：
http://blog.fens.me/r-stat-anova/

Post Views: 96

Posted:

Jun 29, 2025

Tags:

kdtree KD树 R 检索

Comments:

0 Comments

用R语言实现KDTree多维索引

R的极客理想系列文章，涵盖了R的思想，使用，工具，创新等的一系列要点，以我个人的学习和体验去诠释R的强大。

关于作者：

张丹，分析师/程序员/Quant: R,Java,Nodejs
blog: http://blog.fens.me
email: bsspirit@gmail.com

转载请注明出处：
http://blog.fens.me/r-kdtree/

前言

多维向量数据检索，在自然语言处理以及标签向量匹配等应用场景，越来越多的被使用到。提升匹配效率，就能使用体验有巨大的改善。本文从kd树的底层数据结构，和R语言算法实现的角度，介绍kdtree在多维度数据匹配过程中的应用。

KD Tree算法介绍
用R语言实现KD Tree
进行三维索引匹配

1. KD Tree算法介绍

k-D Tree(KDT , k-Dimension Tree) 是一种可以对K 维资料进行划分的资料结构，可以看成二元搜索树的一种延伸，不断的对空间中的维度做划分，利用搜索树剪枝的特性缩短时间复杂度，主要应用在多维空间搜寻，例如最近邻居搜索。在结点数 n 远大于 2^k 时，应用 k-D Tree 的时间效率很好。

k-D Tree 具有二叉搜索树的形态，二叉搜索树上的每个结点都对应 k 维空间内的一个点。其每个子树中的点都在一个 k 维的超长方体内，这个超长方体内的所有点也都在这个子树中。

假设我们已经知道了 k 维空间内的 n 个不同的点的坐标，要将其构建成一棵 k-D Tree，步骤如下：

若当前超长方体中只有一个点，返回这个点。
选择一个维度，将当前超长方体按照这个维度分成两个超长方体。
选择切割点：在选择的维度上选择一个点，这一维度上的值小于这个点的归入一个超长方体（左子树），其余的归入另一个超长方体（右子树）。
将选择的点作为这棵子树的根节点，递归对分出的两个超长方体构建左右子树，维护子树的信息。

以k=2时举例

其构建出 k-D Tree 的形态可能是这样的：

其中树上每个结点上的坐标是选择的分割点的坐标，非叶子结点旁的 x 或 y 是选择的切割维度。

这样的复杂度无法保证。对于 2,3 两步，我们提出两个优化：

轮流选择 k 个维度，以保证在任意连续 k 层里每个维度都被切割到。
每次在维度上选择切割点时选择该维度上的中位数，这样可以保证每次分成的左右子树大小尽量相等。
可以发现，使用优化 2 后，构建出的 k-D Tree 的树高最多为 log(n)+O(1)。

现在，构建 k-D Tree 时间复杂度的瓶颈在于快速选出一个维度上的中位数，并将在该维度上的值小于该中位数的置于中位数的左边，其余置于右边。如果每次都使用 sort 函数对该维度进行排序，时间复杂度是 O(nlog^2(n)) 的。事实上，单次找出 n 个元素中的中位数并将中位数置于排序后正确的位置的复杂度可以达到 O(n)。

我们来回顾一下快速排序的思想。每次我们选出一个数，将小于该数的置于该数的左边，大于该数的置于该数的右边，保证该数在排好序后正确的位置上，然后递归排序左侧和右侧的值。这样的期望复杂度是 O(nlog(n)) 的。但是由于 k-D Tree 只要求要中位数在排序后正确的位置上，所以我们只需要递归排序包含中位数的一侧。可以证明，这样的期望复杂度是 O(n) 的。借助这种思想，构建 k-D Tree 时间复杂度是 O(nlog(n)) 的。

参考文章：https://oi-wiki.org/ds/kdt/

2. 用R语言实现KD Tree

首先，安装less(Learning with Subset Stacking)包，less包中包含了多种的算法，DKTree就是集成的一种算法。


# 安装
> install.packages("less")

# 加载
> library(less)

选定数据集


# 选定数据集，以iris数据集为例，取前2例
> dat<-iris[,1:2]

# 查看数据内容
> head(dat)
  Sepal.Length Sepal.Width
1          5.1         3.5
2          4.9         3.0
3          4.7         3.2
4          4.6         3.1
5          5.0         3.6
6          5.4         3.9

创建一个kdtree实例化对象kdt，kdt对象中一共3个函数，分别是clone,initialize,query。


# 创建
> kdt <- KDTree$new(dat)

# 查看数据结构
> kdt

  Public:
    clone: function (deep = FALSE) 
    initialize: function (X = NULL) 
    query: function (query_X = private$X, k = 1) 
  Private:
    X: data.frame

接下来，我们生成一些与创建 kdtree 不同的查询点，用于查询。


> q_data <- iris[1:5,1:2] + array(rnorm(10)*0.1, dim=c(5,2))
> q_data
  Sepal.Length Sepal.Width
1     5.067010    3.464073
2     4.913018    3.100844
3     4.678508    3.203468
4     4.634521    3.105371
5     4.948339    3.594034

把q_data输入kdt对象，用于kdtree查询。


# 查询k=2，为二维
> res<-kdt$query(query_X = q_data, k = 2)
> res
$nn.idx                      # 输出索引号
     [,1] [,2]
[1,]   18    1
[2,]   10   35
[3,]   30    3
[4,]    4   48
[5,]   38    5
                   
$nn.dists                     # 输出距离
           [,1]       [,2]
[1,] 0.04877580 0.04877580
[2,] 0.01304518 0.01304518
[3,] 0.02177005 0.02177005
[4,] 0.03493634 0.10072915
[5,] 0.04870594 0.05200411

通过索引号，还原的dat的原始数据中


> src<-matrix(col1=dat[res$nn.idx[,1],1],col2=dat[res$nn.idx[,2],2])
> src
  col1 col2
1  5.1  3.5
2  4.9  3.1
3  4.7  3.2
4  4.6  3.2
5  4.9  3.6

3. 进行三维索引匹配

接下来，我们再尝试一下三维索引的匹配。


> # 三维数据集
> dat<-iris[,1:3]
> head(dat)
  Sepal.Length Sepal.Width Petal.Length
1          5.1         3.5          1.4
2          4.9         3.0          1.4
3          4.7         3.2          1.3
4          4.6         3.1          1.5
5          5.0         3.6          1.4
6          5.4         3.9          1.7

# 建树
> kdt <- KDTree$new(dat)

# 生成三维测试数据
> q_data <- iris[1:5,1:3] + array(rnorm(10)*0.3, dim=c(5,2))
> q_data
  Sepal.Length Sepal.Width Petal.Length
1     5.193700    3.404217     1.493700
2     5.078012    3.019615     1.578012
3     4.914997    3.498524     1.514997
4     4.593170    2.982210     1.493170
5     5.094704    3.149830     1.494704

# 获得匹配结果
> res<-kdt$query(query_X = q_data, k = 3)
> res
$nn.idx
     [,1] [,2] [,3]
[1,]   40   29   28
[2,]   26   35   10
[3,]   44    8   38
[4,]    4   46   13
[5,]   10   35   50

$nn.dists
           [,1]       [,2]       [,3]
[1,] 0.09400598 0.09400598 0.09619658
[2,] 0.08339090 0.21032310 0.21032310
[3,] 0.12022173 0.13098663 0.15409891
[4,] 0.11818578 0.22754310 0.22754310
[5,] 0.20104879 0.20104879 0.20121780

通过KDTree的，能快速的让我们从多维数据中，找到最紧邻的点，进行数据搜索。

本文的代码已上传到github:https://github.com/bsspirit/r-string-match/blob/main/kdtree.r

转载请注明出处：
http://blog.fens.me/r-kdtree/

Post Views: 88

Posted:

Jun 28, 2025

Tags:

ngram R 分词文本

Comments:

0 Comments

用R语言实现ngram算法

R的极客理想系列文章，涵盖了R的思想，使用，工具，创新等的一系列要点，以我个人的学习和体验去诠释R的强大。

关于作者：

张丹，分析师/程序员/Quant: R,Java,Nodejs
blog: http://blog.fens.me
email: bsspirit@gmail.com

转载请注明出处：
http://blog.fens.me/r-text-ngram/

前言

大语言模型的文字表达能力，让我们所惊叹算法的魅力。语言能力并不是AI与生俱来的，而且通过底层的各种算法像拼接积木似的组装出来的。我们需要有一个高质量的预料库，然后通过模型训练，你也能拥有文字表达能力。

ngram就给了我们，让惊叹变成现实的这种能力。

ngram算法介绍
用R语言实现ngram
生成式算法：用ngram生成一段文字

1. ngram算法介绍

n-gram是一种基于统计语言模型的算法，它的基本思想是将文本里面的内容按照字节进行大小为N的滑动窗口操作，形成了长度是N的字节片段序列。N就是将句子做切割，N个单词为一组。每一个字节片段称为gram，对所有gram的出现频度进行统计，并且按照事先设定好的阈值进行过滤，形成关键gram列表，也就是这个文本的向量特征空间，列表中的每一种gram就是一个特征向量维度。

如：A B A C A B B，可以切分为


P(A B A C A B B) = P(A)*P(B|A)*P(A|A,B)*P(C|A,B,A)…*P(B|A B A C A B)

为了简化问题，我们可以假设当前的字出现只跟前一个字有关，这样就形成了二元的模型。


P(A B A C A B B) = P(A)*P(B|A)*P(A|B)*…*P(B|B)

ngram模型基于这样一种假设，第N个词的出现只与前面N-1个词相关，而与其它任何词都不相关，整句的概率就是各个词出现概率的乘积。这些概率可以通过直接从语料中统计N个词同时出现的次数得到。常用的，一元为unigram，是二元的bi-gram，三元的tri-gram。

一元表示：P(A B A C A B B) = P(A)*P(B)*P(A)*P(C)*P(A)*P(B)*P(B)
二元表示：P(A B A C A B B) = P(A)*P(B|A)*P(A|A)*P(C|A)…*P(B|B)
三元表示：P(A B A C A B B) = P(A)*P(B|A)*P(A|A,B)*P(C|B,A)…*P(B|A,B)

当N值增大时：对单词的约束性更高，具有更高的辨识力，复杂度也随之增大。当Ｎ值减小时：词文本出现的次数概率更可靠，统计结果更可靠，但对词文本的约束性减小

为了考虑字词在开头和结尾的位置，可以在文本中加入 start 的 token 和 end 的 token。


P(A B A C A B B) = P(A|<start>)*P(B|A)*P(A|B)*…*P(B|B)*P(<end>|B)

N-gram 的使用方法:

文本预处理:
首先，对原始文本进行分词、去除停用词、词干提取等预处理操作，以便得到适合进行N-gram 统计的词序列。
生成N-grams:
根据设定的N 值，将预处理后的词序列拆分成若干个N-gram。
统计频率:
统计每个N-gram 在文本中出现的次数，并计算其频率。
构建语言模型:
利用统计得到的N-gram 频率信息，构建一个语言模型，用于预测下一个词的概率。
使用语言模型:
在实际应用中，可以使用构建好的语言模型来预测下一个词的出现概率，从而实现诸如文本生成、语音识别、机器翻译等任务。

2. 用R语言实现ngram

ngram是一个 R 包，用于构建 n-gram（即“分词”），以及根据给定文本输入的 n-gram 结构生成新文本（即“胡言乱语”）。该包可用于进行严肃的分析，或创建说些有趣话语的“机器人”。ngram包旨在以极快的速度对已标记的语料库进行标记化、汇总和汇总。由于其架构设计，我们还能够处理海量文本，并且性能扩展性非常好。基准测试和示例用法可在软件包简介中找到。

ngram包安装和加载


# 安装
> install.packages("ngram")

# 加载
> library(ngram)

创建文本变量x


# 创建变量
> x <- "A B A C A B B"

# 查看字符串属性
> string.summary(x)
Chars:       13
Letters:     7
Whitespace:  6
Punctuation: 0
Digits:      0
Words:       7
Sentences:   0
Lines:       1 
Wordlens:    0 7 
             9 1 
Senlens:     0 
             10 
Syllens:     0 3 
             9 1

进行ngram二元分词n=2，并预测下一个出现的词。


# ngram二元分词
> ng <- ngram (x , n =2)
> ng
An ngram object with 5 2-grams

查看ngram的分词预测，可以设置output=”full”时是打印所有的结果。使用output=”truncated”，只会显示前 5 个 n-gram。


# 查看分词结果
> print (ng , output ="full")
C A | 1 
B {1} | 

B A | 1 
C {1} | 

B B | 1 
NULL {1} | 

A C | 1 
A {1} | 

A B | 2 
B {1} | A {1} |

我们可以看到每个 3-gram 及其下一个可能的 “词”，以及每个词在给定 n-gram 之后的出现频率。

第一组C A 的下一个可能词是 B，因为在输入的字符串中，序列 C A 的后面只有 B。
第五组A B 的后面有一次 A 和一次 B。
第三组B B 是终结符，即后面什么也没有。

生成短语表，文本的 ngram 表示一旦生成，就可以非常简单地获取一些有趣的摘要信息。函数 get.phrasetable() 生成了一个 n-grams 表，以及它们在文本中的频率和比例。


> get.phrasetable ( ng )
  ngrams freq      prop
1   A B     2 0.3333333
2   C A     1 0.1666667
3   B A     1 0.1666667
4   B B     1 0.1666667
5   A C     1 0.1666667

AB，出现过2次，概率是0.33。其他组合，都只出现过一次，概率是0.16.

再分别生成n=1和n=3的短语表。


> get.phrasetable ( ngram (x , n =1) )
  ngrams freq      prop
1     A     3 0.4285714
2     B     3 0.4285714
3     C     1 0.1428571

> get.phrasetable ( ngram (x , n =3) )
  ngrams freq prop
1 C A B     1  0.2
2 A B A     1  0.2
3 A B B     1  0.2
4 B A C     1  0.2
5 A C A     1  0.2

另外还有2个工具函数


# 提取组合
> get.ngrams(ng)
[1] "C A" "B A" "B B" "A C" "A B"

# 查看原始的数据
> get.string(ng)
[1] "A B A C A B B"

使用babble()函数，通过ngrams来生成与输入字符串具有相同统计属性的新字符串。

随机生成3组字符。


> babble (ng , 10)
[1] "A C A B B B B A B B "

> babble (ng , 10)
[1] "C A B B C A B B A C "

> babble (ng , 20)
[1] "B A C A B B B A C A B B A B B B A C A B "

我们也可以指定种子生成相同的内容。


> babble (ng , 10 , seed =10)
[1] "A C A B B B B A B B "

> babble (ng , 10 , seed =10)
[1] "A C A B B B B A B B "

3. 生成式算法：用ngram生成一段文字

通过babble()，是不是看到生成式大模型的影子了，为什么模型能生成出来说法通顺的文字呢。

我们多给一些语言描述，让ngram进行算法识别。

生成语言文字。


x<-c(
+ "how are you",
+ "I like you",
+ "I love you",
+ "I think you're the best for me",
+ "We re good friends",
+ "We're all good"
+ )

# 拼接成一个句子
> x<-str_c(x,collapse = " ")
> x
[1] "how are you I like you I love you I think you're the best for me We re good friends We're all good"

构建ngram模型


> ng <- ngram (x , n=2)
> ng
An ngram object with 20 2-grams 

# 查看语言序列
> print (ng , output ="truncated")
the best | 1 
for {1} | 

for me | 1 
We {1} | 

friends We're | 1 
all {1} | 

are you | 1 
I {1} | 

I think | 1 
you're {1} | 

[[ ... results truncated ... ]]

查看短语概率表


> get.phrasetable ( ng )
           ngrams freq       prop
1          you I     3 0.13636364
2       the best     1 0.04545455
3         for me     1 0.04545455
4  friends We're     1 0.04545455
5        are you     1 0.04545455
6        I think     1 0.04545455
7   good friends     1 0.04545455
8         I like     1 0.04545455
9   think you're     1 0.04545455
10      like you     1 0.04545455
11      all good     1 0.04545455
12        I love     1 0.04545455
13         me We     1 0.04545455
14      love you     1 0.04545455
15         We re     1 0.04545455
16       how are     1 0.04545455
17       re good     1 0.04545455
18    you're the     1 0.04545455
19      best for     1 0.04545455
20     We're all     1 0.04545455

接下来就是神奇的时刻，自动生成10个短语。


> babble (ng , 10)
[1] "me We re good friends We're all good I love "

> babble (ng , 10)
[1] "for me We re good friends We're all good I "

> babble (ng , 10)
[1] "you're the best for me We re good friends We're "

> babble (ng , 10)
[1] "think you're the best for me We re good friends "

> babble (ng , 10)
[1] "We're all good I think you're the best for me "

> babble (ng , 10)
[1] "like you I like you I think you're the best "

看上去，很符合预期。虽然比不是现在的大语言模型，能生成完整的语句，但是已经有了生成式模型的影子了。

本文的代码已上传到github:https://github.com/bsspirit/r-string-match/blob/main/ngram.r

转载请注明出处：
http://blog.fens.me/r-text-ngram/

Post Views: 85

Posted:

Jun 27, 2025

Tags:

R TF-IDF 文本

Comments:

0 Comments

用R语言计算文本的TF-IDF

R的极客理想系列文章，涵盖了R的思想，使用，工具，创新等的一系列要点，以我个人的学习和体验去诠释R的强大。

关于作者：

张丹，分析师/程序员/Quant: R,Java,Nodejs
blog: http://blog.fens.me
email: bsspirit@gmail.com

转载请注明出处：
http://blog.fens.me/r-text-tf-idf/

前言

在互联网的今天，我们每天都会生产和消费大量的文本信息，如报告、文档、新闻、聊天、图书、小说、语音转化的文字等。海量的文本信息，不仅提供扩宽的研究对象和研究领域，也为商业使用带来了巨大的机会。

TF-IDF是一种通过计算词频，进行文本信息检索的一种方式，常用对文本数据进行向量化特征的描述。

什么是TF-IDF介绍
tidytext包计算TF-IDF
quanteda包计算TF-IDF

1. 什么是TF-IDF介绍

TF-IDF (词频-逆文档频率) 是一种在信息检索和文本挖掘中常用的加权技术。它衡量一个词语对于一个文档的重要性，通过结合词频(TF) 和逆文档频率(IDF) 来计算。

TF (词频): 表示词语在特定文档中出现的次数。一个词语在文档中出现的次数越多，通常认为它在该文档中越重要。
IDF (逆文档频率): 表示词语在整个语料库中的普遍程度。如果一个词语在很多文档中都出现，说明它比较常见，对区分文档的贡献就越小；反之，如果一个词语只出现在少数文档中，说明它对区分这些文档越重要。
TF-IDF 的计算: TF-IDF 值是TF 值和IDF 值的乘积。

公式:


TF (词频) = (词语在文档中出现的次数) / (文档中的总词数)
IDF (逆文档频率) = log(总文档数/ 包含该词语的文档数+ 1) (加1 是为了避免除以零的情况)
TF-IDF = TF * IDF

作用: TF-IDF 通过综合考虑词语在文档内的频率和在语料库中的普遍程度，能够有效地识别出对文档具有区分度的关键词。在搜索引擎中，TF-IDF 常被用于计算文档与用户查询的相关性，从而对搜索结果进行排序。

总结: TF-IDF 是一种简单而有效的文本特征提取方法，通过对词语的权重计算，可以帮助我们更好地理解和利用文本数据.

2. tidytext包计算TF-IDF

R语言中，有多个包都支持TF-IDF的计算。首先，我们先使用tidytext包。

安装tidytext包


# 安装tidytext包
> install.packages("tidytext")

# 加载tidytext包
> library(tidytext)

# 加载其他工具包
> library(dplyr)
> library(tibble)

定义10段文本数据，并进行编号。


# 定义文本数据
> ss <- c(
+     "R的极客理想系列文章，涵盖了R的思想，使用，工具，创新等的一系列要点，以我个人的学习和体验去诠释R的强大", 
+     "R语言作为统计学一门语言，一直在小众领域闪耀着光芒。", 
+     "现在已不仅仅是统计领域，教育，银行，电商，互联网….都在使用R语言。",
+     "直到大数据的爆发，R语言变成了一门炙手可热的数据分析的利器。",
+     "随着越来越多的工程背景的人的加入，R语言的社区在迅速扩大成长。",
+     "TF-IDF (词频-逆文档频率) 是一种在信息检索和文本挖掘中常用的加权技术。",
+     "它衡量一个词语对于一个文档的重要性，通过结合词频(TF) 和逆文档频率(IDF) 来计算。",
+     "TF (词频): 表示词语在特定文档中出现的次数。一个词语在文档中出现的次数越多，通常认为它在该文档中越重要。",
+     "IDF (逆文档频率): 表示词语在整个语料库中的普遍程度。如果一个词语在很多文档中都出现，说明它比较常见，对区分文档的贡献就越小；反之，如果一个词语只出现在少数文档中，说明它对区分这些文档越重要。",
+     "TF-IDF 的计算: TF-IDF 值是TF 值和IDF 值的乘积。"
+ ) 

# 转成tibble类型，并增加列编号
> s1<- ss %>% as_tibble() %>% rowid_to_column("ID")

# 查看s1变量
> s1
# A tibble: 10 × 2
      ID value                                    
   <int> <chr>                                    
 1     1 R的极客理想系列文章，涵盖了R的思想，使用，工具，创新等的一系列要点，以我个人的…
 2     2 R语言作为统计学一门语言，一直在小众领域闪耀着光芒。……
 3     3 现在已不仅仅是统计领域，教育，银行，电商，互联网….都在使用R语言。……
 4     4 直到大数据的爆发，R语言变成了一门炙手可热的数据分析的利器。……
 5     5 随着越来越多的工程背景的人的加入，R语言的社区在迅速扩大成长。……
 6     6 TF-IDF (词频-逆文档频率) 是一种在信息检索和文本挖掘中常用的加权技术。…
 7     7 它衡量一个词语对于一个文档的重要性，通过结合词频(TF) 和逆文档频率(IDF)…
 8     8 TF (词频): 表示词语在特定文档中出现的次数。一个词语在文档中出现的次数越多…
 9     9 IDF (逆文档频率): 表示词语在整个语料库中的普遍程度。如果一个词语在很多文…
10    10 TF-IDF 的计算: TF-IDF 值是TF 值和IDF 值的乘积。……

计算每个文档中的词频，用于计算tf-idf


# 计算文档中的词频
> ss_words <- s1 %>% 
+   unnest_tokens(words, value) %>% 
+   count(ID, words, sort = TRUE);ss_words
# A tibble: 191 × 3
      ID words     n
   <int> <chr> <int>
 1     1 的        5
 2     9 文        5
 3     9 档        5
 4     1 r         3
 5     4 的        3
 6     5 的        3
 7     8 在        3
 8     8 文        3
 9     8 档        3
10     9 在        3
# 181 more rows
# Use `print(n = ...)` to see more rows

使用bind_tf_idf()函数，计算每个词的tf,idf,tf-idf。

tf-idf 的思想是通过减少常用词的权重并增加在文档集合或语料库中不经常使用的词的权重，在这种情况下，我们找到每个文档内容的重要词。计算 tf-idf 会尝试查找文本中重要（即常见）但不太常见的单词。


# 计算tf-idf
> ss_tfidf <- ss_words %>% 
+   bind_tf_idf(ID, words, n)
> ss_tfidf
# A tibble: 191 × 6
      ID words      n    tf   idf tf_idf
   <int> <chr>  <int> <dbl> <dbl>  <dbl>
 1     1 的        5 0.278  1.68  0.466
 2     9 文        5 0.455  1.29  0.585
 3     9 档        5 0.455  1.29  0.585
 4     1 r         3 0.429  1.68  0.720
 5     4 的        3 0.167  2.13  0.354
 6     5 的        3 0.167  2.19  0.365
 7     8 在        3 0.375  1.85  0.695
 8     8 文        3 0.273  1.85  0.505
 9     8 档        3 0.273  1.85  0.505
10     9 在        3 0.375  1.29  0.483
# 181 more rows
# Use `print(n = ...)` to see more rows

# 以tf_idf列分值高倒序排序
> ss_tfidf %>%
+   arrange(desc(tf_idf))
# A tibble: 191 × 6
      ID words      n    tf   idf tf_idf
   <int> <chr>  <int> <dbl> <dbl>  <dbl>
 1    10 值         3     1  2.70   2.70
 2    10 乘         1     1  2.70   2.70
 3    10 积         1     1  2.70   2.70
 4     2 一         1     1  2.41   2.41
 5     2 一直在     1     1  2.41   2.41
 6     2 作为       1     1  2.41   2.41
 7     2 光芒       1     1  2.41   2.41
 8     2 学         1     1  2.41   2.41
 9     2 小众       1     1  2.41   2.41
10     2 闪耀着     1     1  2.41   2.41
# 181 more rows
# Use `print(n = ...)` to see more rows

通过tf-idf判断2个文本的相似性


# 加载widyr包
> library(widyr)

# 判断2段文本的相似性
> ss_tfidf %>% 
+   pairwise_similarity(ID, words, tf_idf, sort = TRUE)
# A tibble: 70 × 3
   item1 item2 similarity
   <int> <int>      <dbl>
 1     8     9     0.135 
 2     9     8     0.135 
 3     7    10     0.0907
 4    10     7     0.0907
 5     6    10     0.0769
 6    10     6     0.0769
 7     3     2     0.0620
 8     2     3     0.0620
 9     7     9     0.0596
10     9     7     0.0596
# 60 more rows
# Use `print(n = ...)` to see more rows

程序提示第8段和第9段文本最相似，查看第8段和第9段文本。


> ss[8]
[1] "TF (词频): 表示词语在特定文档中出现的次数。一个词语在文档中出现的次数越多，通常认为它在该文档中越重要。"

> ss[9]
[1] "IDF (逆文档频率): 表示词语在整个语料库中的普遍程度。如果一个词语在很多文档中都出现，说明它比较常见，对区分文档的贡献就越小；反之，如果一个词语只出现在少数文档中，说明它对区分这些文档越重要。"

3. quanteda包计算TF-IDF

我们再换另一个包quanteda来计算TF-IDF。quanteda包，是一个能力非常强大的文本处理包，详细内容请参考文章用R语言进行量化文本分析quanteda

安装和加载quanteda


# 安装
> install.pacakges("quanteda")
> install.pacakges("quanteda.textstats")

# 加载
> library("quanteda")
> library("quanteda.textstats")

使用上文中已建立的ss文档对象，提取关键词，形成词频矩阵。


> ssdfm
Document-feature matrix of: 10 documents, 144 features (84.51% sparse) and 0 docvars.
       features
docs    r 的 极 客 理想 系列 文章 ， 涵 盖了
  text1 3  5  1  1    1    1    1  5  1    1
  text2 1  0  0  0    0    0    0  1  0    0
  text3 1  0  0  0    0    0    0  4  0    0
  text4 1  3  0  0    0    0    0  1  0    0
  text5 1  3  0  0    0    0    0  1  0    0
  text6 0  1  0  0    0    0    0  0  0    0
[ reached max_ndoc ... 4 more documents, reached max_nfeat ... 134 more features ]

使用dfm_tfidf()函数，对词频矩阵计算tfidf值，形成tfidf矩阵。


> ssidf<-dfm_tfidf(ssdfm)
> ssidf
Document-feature matrix of: 10 documents, 144 features (84.51% sparse) and 0 docvars.
       features
docs          r         的 极 客 理想 系列 文章         ， 涵 盖了
  text1 0.90309 0.48455007  1  1    1    1    1 0.48455007  1    1
  text2 0.30103 0           0  0    0    0    0 0.09691001  0    0
  text3 0.30103 0           0  0    0    0    0 0.38764005  0    0
  text4 0.30103 0.29073004  0  0    0    0    0 0.09691001  0    0
  text5 0.30103 0.29073004  0  0    0    0    0 0.09691001  0    0
  text6 0       0.09691001  0  0    0    0    0 0           0    0
[ reached max_ndoc ... 4 more documents, reached max_nfeat ... 134 more features ]

用词频矩阵计算2个文档的相似性


> ssdfm %>%
+   textstat_simil(method = "cosine") %>%
+   as.matrix()
           text1      text2      text3     text4     text5      text6      text7      text8      text9     text10
text1  1.0000000 0.21426863 0.44799204 0.4716523 0.5079850 0.13525045 0.19705795 0.20087684 0.22392949 0.23823145
text2  0.2142686 1.00000000 0.40996003 0.2702264 0.2425356 0.04950738 0.07868895 0.08823529 0.11803342 0.04756515
text3  0.4479920 0.40996003 1.00000000 0.2197177 0.2366432 0.03450328 0.13710212 0.12298801 0.24678382 0.03314968
text4  0.4716523 0.27022641 0.21971769 1.0000000 0.4828079 0.15161961 0.15061881 0.20266981 0.13555693 0.25492496
text5  0.5079850 0.24253563 0.23664319 0.4828079 1.0000000 0.20412415 0.16222142 0.31529631 0.19466571 0.27456259
text6  0.1352504 0.04950738 0.03450328 0.1516196 0.2041241 1.00000000 0.46358632 0.44556639 0.36424640 0.28022427
text7  0.1970580 0.07868895 0.13710212 0.1506188 0.1622214 0.46358632 1.00000000 0.55082263 0.56578947 0.22269967
text8  0.2008768 0.08823529 0.12298801 0.2026698 0.3152963 0.44556639 0.55082263 1.00000000 0.72787276 0.19026060
text9  0.2239295 0.11803342 0.24678382 0.1355569 0.1946657 0.36424640 0.56578947 0.72787276 1.00000000 0.09544271
text10 0.2382314 0.04756515 0.03314968 0.2549250 0.2745626 0.28022427 0.22269967 0.19026060 0.09544271 1.00000000

用tfidf矩阵计算2个文档的相似性


> ssidf %>%
+   textstat_simil(method = "cosine") %>%
+   as.matrix()
             text1        text2        text3       text4       text5        text6       text7        text8       text9       text10
text1  1.000000000 0.0219479864 0.0513556447 0.024124188 0.028953788 0.0118764224 0.015076777 0.0064026405 0.006519969 0.0136248773
text2  0.021947986 1.0000000000 0.1217612800 0.075175409 0.041645241 0.0001912012 0.001083631 0.0009743142 0.001830469 0.0001785203
text3  0.051355645 0.1217612800 1.0000000000 0.018812586 0.022578816 0.0001504185 0.002943756 0.0023568679 0.005326873 0.0001404424
text4  0.024124188 0.0751754091 0.0188125856 1.000000000 0.026150152 0.0021071189 0.002852493 0.0038248671 0.002336975 0.0037986508
text5  0.028953788 0.0416452412 0.0225788162 0.026150152 1.000000000 0.0157598001 0.003423554 0.0678499967 0.021859872 0.0045591308
text6  0.011876422 0.0001912012 0.0001504185 0.002107119 0.015759800 1.0000000000 0.178921295 0.1558538111 0.128284299 0.1178464227
text7  0.015076777 0.0010836308 0.0029437558 0.002852493 0.003423554 0.1789212950 1.000000000 0.2790485085 0.271452809 0.0899040023
text8  0.006402640 0.0009743142 0.0023568679 0.003824867 0.067849997 0.1558538111 0.279048509 1.0000000000 0.421606371 0.0331304236
text9  0.006519969 0.0018304690 0.0053268734 0.002336975 0.021859872 0.1282842988 0.271452809 0.4216063707 1.000000000 0.0195965092
text10 0.013624877 0.0001785203 0.0001404424 0.003798651 0.004559131 0.1178464227 0.089904002 0.0331304236 0.019596509 1.0000000000

从2个相似性矩阵返回的结果来看，都是第8段和第9段更相似。

本文从TF-IDF的实现的角度，介绍了TF-IDF怎么使用R语言程序进行计算。这些计算就是把文本转成向量化数据的方法。

本文的代码已上传到github:https://github.com/bsspirit/r-string-match/blob/main/tfidf.r

转载请注明出处：
http://blog.fens.me/r-text-tf-idf/

Post Views: 82

Posted:

Jun 26, 2025

Tags:

annoy R 最近临算法

Comments:

0 Comments

用R语言实现近似最近邻搜索算法Annoy

R的极客理想系列文章，涵盖了R的思想，使用，工具，创新等的一系列要点，以我个人的学习和体验去诠释R的强大。

关于作者：

张丹，分析师/程序员/Quant: R,Java,Nodejs
blog: http://blog.fens.me
email: bsspirit@gmail.com

转载请注明出处：
http://blog.fens.me/r-annoy/

前言

从学习大模型到 RAG 技术，又回到了最基础的知识，如文本数据向量化，向量匹配，向量数据库等技术，因此需要继续研究基础知识。

本文就是对向量匹配算法的学习，通过近似最近邻搜索算法，可以对向量化的文字进行相似度匹配，从而进行RAG过程的高效检索。

Annoy近似最近邻搜索算法介绍
Annoy的算法过程
用R语言实现Annoy算法

1. Annoy近似最近邻搜索算法介绍

Annoy全称 Approximate Nearest Neighbors Oh Yeah，是一种适合实际应用的快速相似查找算法。Annoy 是通过建立一个二叉树来使得每个点查找时间复杂度是O(log n)，和kd树不同的是，Annoy没有对k维特征进行切分。

Annoy 算法的目标是建立一个数据结构能够在较短的时间内找到任何查询点的最近点，在精度允许的条件下通过牺牲准确率来换取比暴力搜索要快的多的搜索速度。

在搜索的业务场景下，基于一个现有的数据候选集（dataset），需要对新来的一个或者多个数据进行查询（query），返回在数据候选集中与该查询最相似的 Top K 数据。

最朴素的想法就是，每次来了一个新的查询数据（query），都遍历一遍数据候选集（dataset）里面的所有数据，计算出 query 与 dataset 中所有元素的相似度或者距离，然后精准地返回 Top K 相似的数据即可。

但是当数据候选集特别大的时候，遍历一遍数据候选集里面的所有元素就会耗费过多的时间，其时间复杂度是 O(n)。因此，计算机科学家们开发了各种各样的近似最近邻搜索方法（approximate nearest neighbors）来加快其搜索速度，在精确率和召回率上面就会做出一定的牺牲，但是其搜索速度相对暴力搜索有很大地提高。

在这个场景下，通常都是欧式空间里面的数据，支持的距离包括：Euclidean 距离，Manhattan 距离，Cosine 距离，Hamming 距离，Dot Product 距离

2. Annoy的算法过程

建立索引

随机选择两个点，以这两个节点为初始中心节点，执行聚类数为2的kmeans过程，最终产生收敛后两个聚类中心点。这两个聚类中心点之间连一条线段（灰色短线），建立一条垂直于这条灰线，并且通过灰线中心点的线（黑色粗线）。这条黑色粗线把数据空间分成两部分。

在多维空间的话，这条黑色粗线可以看成等距垂直超平面。在划分的子空间内进行不停的递归迭代继续划分，直到每个子空间最多只剩下K个数据节点。

通过多次递归迭代划分的话，最终原始数据会形成二叉树结构。二叉树底层是叶子节点记录原始数据节点，其他中间节点记录的是分割超平面的信息。

Annoy建立这样的二叉树结构是希望满足这样的一个假设:相似的数据节点应该在二叉树上位置更接近，一个分割超平面不应该把相似的数据节点分在二叉树的不同分支上。

查询过程

新来的一个点（用红色的叉表示），通过对二叉树的查找，我们可以找到所在的子平面，然后里面最多有 K = 10 个点。从二叉树的叶子节点来看，该区域只有 7 个点。

二叉树底层是叶子节点记录原始数据节点，其他中间节点记录的是分割超平面的信息。Annoy建立这样的二叉树结构是希望满足这样的一个假设:相似的数据节点应该在二叉树上位置更接近，一个分割超平面不应该把相似的数据节点分在二叉树的不同分支上。查找的过程就是不断看查询数据节点在分割超平面的哪一边。

从二叉树索引结构来看，就是从根节点不停的往叶子节点遍历的过程。通过对二叉树每个中间节点（分割超平面相关信息）和查询数据节点进行相关计算来确定二叉树遍历过程是往这个中间节点左子节点走还是右子节点走。

从二叉树的根结点遍历的路径如下所示：

返回最终近邻节点

每棵树都返回一堆近邻点后，如何得到最终的Top N相似集合呢？首先所有树返回近邻点都插入到优先队列中，求并集去重, 然后计算和查询点距离，最终根据距离值从近距离到远距离排序，返回Top N近邻节点集合

使用优先队列（priority queue）：将多棵树放入优先队列，逐一处理；并且通过阈值设定的方式，如果查询的点与二叉树中某个节点比较相似，那么就同时走两个分支，而不是只走一个分支；

使用森林（forest of trees）：构建多棵树，采用多个树同时搜索的方式，得到候选集 Top M（M > K），然后对这 M 个候选集计算其相似度或者距离，最终进行排序就可以得到近似 Top K 的结果。

返回多棵树的相似节点，在二叉树的结构：

参考文章：https://segmentfault.com/a/1190000013713357

3. 用R语言实现Annoy算法

在R语言中，我们可以使用RcppAnnoy包，来完成Annoy算法的构建。RcppAnnoy包的地址：https://github.com/cran/RcppAnnoy

Annoy 是一个小型、快速、轻量级的近似近邻库，特别注重内存的高效使用和加载预存索引的能力。Annoy 由 Erik Bernhardsson 编写。更多特性、（Python）API 和其他语言移植请参见其页面。Annoy 隶属于 Spotify 的 “让我们为您找到您可能喜欢的其他音乐 ”算法。

3.1 RcppAnnoy包安装

首先，进行RcppAnnoy的安装和加载，整个过程比较简单。


# 安装
> install.packages("RcppAnnoy")

# 加载
> library(RcppAnnoy)
> library(magrittr)  # 用于管道的工具包

3.2 生成100组向量化数据

接下来，让我们生成100组向量化数据。


# 定义每组向量数量为10
> n <- 10

# 创建基于欧式距离的annoy对象
> a <- new(AnnoyEuclidean, n)

# 设置随机种子（可以是任意数字）
> a$setSeed(42)

# 打开日志，1为打开，0为关闭
> a$setVerbose(1)

# 通过runif生成均匀分布的向量数据100组，并加入到annoy对象
> for (i in 1:100) a$addItem(i - 1, runif(n)) 
Reallocating to 1 nodes: old_address=(nil), new_address=0x000002ae4146ef80
Reallocating to 2 nodes: old_address=0x000002ae4146ef80, new_address=0x000002ae40818680
Reallocating to 3 nodes: old_address=0x000002ae40818680, new_address=0x000002ae3a1935f0
Reallocating to 5 nodes: old_address=0x000002ae3a1935f0, new_address=0x000002ae3dd07ab0
Reallocating to 7 nodes: old_address=0x000002ae3dd07ab0, new_address=0x000002ae416cb1d0
Reallocating to 10 nodes: old_address=0x000002ae416cb1d0, new_address=0x000002ae3dc514a0
Reallocating to 14 nodes: old_address=0x000002ae3dc514a0, new_address=0x000002ae3f9b5940
Reallocating to 19 nodes: old_address=0x000002ae3f9b5940, new_address=0x000002ae43b721b0
Reallocating to 26 nodes: old_address=0x000002ae43b721b0, new_address=0x000002ae407f2550
Reallocating to 35 nodes: old_address=0x000002ae407f2550, new_address=0x000002ae4527ce60
Reallocating to 46 nodes: old_address=0x000002ae4527ce60, new_address=0x000002ae40467470
Reallocating to 61 nodes: old_address=0x000002ae40467470, new_address=0x000002ae3bb29bf0
Reallocating to 80 nodes: old_address=0x000002ae3bb29bf0, new_address=0x000002ae405d1170
Reallocating to 105 nodes: old_address=0x000002ae405d1170, new_address=0x000002ae3b6afaa0

3.3 查看数据集

接下来，我们查看生成的数据。


# 查看有多少组数据
> a$getNItems()
[1] 100

# 取第0组向量数据，因为C++的程序索引是从0开始的，与R不同，R是从1开始的。
> a0<-a$getItemsVector(0);a0
 [1] 0.001761558 0.060019139 0.931653738 0.472722173 0.843278706 0.831824481 0.768858135
 [8] 0.603522480 0.558359802 0.525437832

# 取第1组向量数据
> a1<-a$getItemsVector(1);a1
 [1] 0.2386040 0.6162668 0.8655570 0.7643633 0.1878769 0.3723671 0.7563977 0.0877244
 [9] 0.6563932 0.7155924

# 取第2组向量数据
> a2<-a$getItemsVector(2);a2
 [1] 0.85908961 0.20982422 0.27540511 0.83535612 0.28062439 0.84796673 0.61870313
 [8] 0.24962090 0.62007779 0.05507875

3.4 验证计算结果
然后，我们可以计算不同组数据的相似度，使用欧式距离进行相似度判断。


# 计算第0组向量，与第0组向量的欧式距离
> a$getDistance(0, 1)
[1] 1.186404

# 手动计算，验证欧式距离的结果
> (a1-a0)^2 %>% sum %>% sqrt
[1] 1.186404

3.5 构建二叉树
完成验证后，最后我们生成二叉树的森林，生成50个。


> a$build(50)
pass 0...
Reallocating to 137 nodes: old_address=0x000002ae3b6afaa0, new_address=0x000002ae3ff11f40
pass 1...
Reallocating to 179 nodes: old_address=0x000002ae3ff11f40, new_address=0x000002ae403e0aa0
pass 2...
pass 3...
Reallocating to 234 nodes: old_address=0x000002ae403e0aa0, new_address=0x000002ae40642ee0
pass 4...
pass 5...
Reallocating to 305 nodes: old_address=0x000002ae40642ee0, new_address=0x000002ae400c8ca0
pass 6...
pass 7...
pass 8...
Reallocating to 397 nodes: old_address=0x000002ae400c8ca0, new_address=0x000002ae455f7010
pass 9...
pass 10...
pass 11...
pass 12...
Reallocating to 517 nodes: old_address=0x000002ae455f7010, new_address=0x000002ae412a7130
pass 13...
pass 14...
pass 15...
pass 16...
pass 17...
pass 18...
Reallocating to 673 nodes: old_address=0x000002ae412a7130, new_address=0x000002ae41f64010
pass 19...
pass 20...
pass 21...
pass 22...
pass 23...
pass 24...
pass 25...
Reallocating to 876 nodes: old_address=0x000002ae41f64010, new_address=0x000002ae400470e0
pass 26...
pass 27...
pass 28...
pass 29...
pass 30...
pass 31...
pass 32...
pass 33...
pass 34...
Reallocating to 1140 nodes: old_address=0x000002ae400470e0, new_address=0x000002ae414567f0
pass 35...
pass 36...
pass 37...
pass 38...
pass 39...
pass 40...
pass 41...
pass 42...
pass 43...
pass 44...
pass 45...
Reallocating to 1483 nodes: old_address=0x000002ae414567f0, new_address=0x000002ae401966c0
pass 46...
pass 47...
pass 48...
pass 49...
has 1294 nodes

这样我们就是完成了，Annoy算法索引的建立。接下来，我们使用树的能力，进行向量数据的相似度匹配。

3.6 找相近的数据
取与第0组最相近的top5的组


> a$getNNsByItem(0, 5)
[1]  0 55 54 31 11

# 同时返回距离值
> a$getNNsByItemList(0, 5, -1, TRUE)
$item
[1]  0 55 54 31 11

$distance
[1] 0.0000000 0.7477396 0.8218669 0.8747964 0.8862380

手动验证距离，分别取55,54,31,11组


# 获取数据
> a55<-a$getItemsVector(55);a55
 [1] 0.4020543 0.2822408 0.7524120 0.5547701 0.7722272 0.5120775 0.6099072 0.6606834
 [9] 0.6786938 0.1250148
> a54<-a$getItemsVector(54);a54
 [1] 0.1175388 0.4510850 0.7032202 0.3784515 0.3057182 0.7038317 0.6994157 0.7404361
 [9] 0.4291793 0.2053584
> a31<-a$getItemsVector(31);a31
 [1] 0.5639953 0.3184495 0.7659245 0.6226313 0.3918578 0.8645173 0.5496733 0.8533068
 [9] 0.5158110 0.6493025
> a11<-a$getItemsVector(11);a11
 [1] 0.26264703 0.20268030 0.72397888 0.42269590 0.64337742 0.62916356 0.05383677
 [8] 0.47857073 0.62450409 0.32770717

# 计算距离
> (a55-a0)^2 %>% sum %>% sqrt
[1] 0.7477395
> (a55-a0)^2 %>% sum %>% sqrt
[1] 0.7477395
> (a54-a0)^2 %>% sum %>% sqrt
[1] 0.8218669
> (a31-a0)^2 %>% sum %>% sqrt
[1] 0.8747964
> (a11-a0)^2 %>% sum %>% sqrt
[1] 0.886238

手动欧式距离计算结果，与a$getNNsByItem(0,5)结果一致。

3.7 减少遍历的树的数量

测试如果控制森林的数量，只遍历10棵树，而不是全部的100棵树。


> a$getNNsByItemList(0, 5, 10, TRUE)
$item
[1]  0 11 78 67 48

$distance
[1] 0.0000000 0.8862380 0.9109641 0.9520484 0.9523986

新得出的结果，就没有获得最优解，没有少了55 54 31，得出11为最接近。

3.8 生成一组新数据与原数据找相似度

生成新数据向量


# 新数据
> v <- runif(10);v
 [1] 0.33498066 0.70034783 0.07155333 0.51988688 0.69538152 0.71980116 0.73188773
 [8] 0.95337664 0.99446321 0.37988704

# 对比新数据找到原数据相似度最高的top5
> a$getNNsByVector(v, 5)
[1] 75 25 59 50 22

# 全量树匹配，并输出距离
> a$getNNsByVectorList(v, 5, -1, TRUE)
$item
[1] 75 25 59 50 22

$distance
[1] 0.6203443 0.7185830 0.8483184 0.8719595 0.8808730

3.9 保存模型

把模型在本地保存


# 保存模型
> a$save("./annoy01.ann")
unloaded
found 50 roots with degree 100

# 查看本地目录
> dir()
[1] "annoy.r"     "annoy01.ann"

# 重新加载模型
> a$load("./annoy01.ann")
found 50 roots with degree 100

本文我们了解了近似最近邻搜索算法Annoy的原理和实现，后面就可以针对向量化的文本数据，快速地进行相似度匹配。本文代码：https://github.com/bsspirit/r-string-match/blob/main/annoy.r

转载请注明出处：
http://blog.fens.me/r-annoy/

Post Views: 83

排行榜

Posted:

Tags:

Comments:

用R语言实现方差分析ANOVA

1. 方差分析介绍

2. 用R语言方差分析aov()函数

3. R语言实现方差分析

Posted:

Tags:

Comments:

用R语言实现KDTree多维索引

1. KD Tree算法介绍

2. 用R语言实现KD Tree

3. 进行三维索引匹配

Posted:

Tags:

Comments:

用R语言实现ngram算法

1. ngram算法介绍

2. 用R语言实现ngram

3. 生成式算法：用ngram生成一段文字

Posted:

Tags:

Comments:

用R语言计算文本的TF-IDF

1. 什么是TF-IDF介绍

2. tidytext包计算TF-IDF

3. quanteda包计算TF-IDF

Posted:

Tags:

Comments:

用R语言实现近似最近邻搜索算法Annoy

1. Annoy近似最近邻搜索算法介绍

2. Annoy的算法过程

3. 用R语言实现Annoy算法

站内导航

最新文章

最新评论

最热文章