she*_*heß 10 string performance r levenshtein-distance
设置:我有关于人员及其父母姓名的数据,我想找到兄弟姐妹(父母姓名相同的人).
pdata<-data.frame(parents_name=c("peter pan + marta steward",
"pieter pan + marta steward",
"armin dolgner + jane johanna dough",
"jack jackson + sombody else"))
这里的预期输出将是一列,表示前两个观察属于X族,而第三和第四列各自属于一个独立的族.例如:
person_id parents_name family_id
1 "peter pan + marta steward", 1
2 "pieter pan + marta steward", 1
3 "armin dolgner + jane johanna dough", 2
4 "jack jackson + sombody else" 3
目前的方法:我对距离度量很灵活.目前,我使用Levenshtein编辑距离匹配obs,允许两个字符的差异.但是,如果它们运行得更快,其他变体如"最大公共子串"将会很好.
对于较小的子样本,我stringdist::stringdist在循环中使用stringdist::stringdistmatrix,但随着样本量的增加,这变得越来越低效.
一旦使用某个样本大小,矩阵版本就会爆炸.我极其低效的循环尝试是:
#create data of the same complexity using random last-names
#(4mio obs and ~1-3 kids per parents)
pdata<-data.frame(parents_name=paste0(rep(c("peter pan + marta ",
"pieter pan + marta ",
"armin dolgner + jane johanna ",
"jack jackson + sombody "),1e6),stringi::stri_rand_strings(4e6, 5)))
for (i in 1:nrow(pdata)) {
similar_fatersname0<-stringdist::stringdist(pdata$parents_name[i],pdata$parents_name[i:nrow(pdata)],nthread=4)<2
#[create grouping indicator]
}
我的问题:应该有很大的效率提升,例如,因为一旦我发现字符串在更容易评估的东西上有足够的不同,我就可以停止比较字符串,例如.字符串长度或第一个字.字符串长度变体已经起作用并且将复杂度降低了3倍.但那太少了.任何减少计算时间的建议都值得赞赏.
备注:
Jer*_*meE 10
有两个挑战:
A. Levenstein距离的并行执行 - 而不是顺序循环
B.比较的数量:如果我们的源列表有400万个条目,理论上我们应该运行16万亿Levenstein距离测量,这是不现实的,即使我们解决了第一个挑战.
为了清楚地使用语言,我们的定义如下
从技术上讲,目标是在400万个表达式列表中找到一系列匹配表达式.如果两个表达式的Levenstein距离小于2,则认为它们是匹配表达式.
实际上,我们创建了两个列表,它们是最初的400万个表达式列表的精确副本.然后我们称之为左列表和右列表.在复制列表之前,为每个表达式分配一个表达式id.我们的目标是在Right列表中找到Levenstein距离小于2的条目到Left列表的条目,不包括相同的条目(相同的表达式id).
我建议分两步解决这两个挑战.第一步将减少可能匹配表达式的列表,第二步将简化Levenstein距离测量,因为我们只查看非常接近的表达式.使用的技术是任何传统的数据库服务器,因为我们需要为数据集索引性能.
挑战A.
挑战A包括减少距离测量的数量.我们从最大值开始.16万亿(四百万到两个的力量),我们不应该超过几十或几亿.这里使用的技术包括在完整表达式中搜索至少一个相似的单词.根据数据的分布方式,这将大大减少可能的匹配对的数量.或者,根据所需的结果准确性,我们还可以搜索具有至少两个相似单词的对,或至少一半相似单词.
从技术上讲,我建议将表达式列表放在表格中.添加标识列以为每个表达式创建唯一ID,并创建12个字符列.然后解析表达式并将每个部分的每个单词放在一个单独的列中.这看起来像(我没有代表所有12列,但想法如下):
|id | expression | sect_a_w_1 | sect_a_w_2 | sect_b_w_1 |sect_b_w_2 |
|1 | peter pan + marta steward | peter | pan | marta |steward |
有空列(因为有很少的表达式有12个单词),但没关系.
然后我们复制表并在每个sect ...列上创建一个索引.我们运行12个连接,试图找到类似的单词,类似于
SELECT L.id, R.id
FROM left table L JOIN right table T
ON L.sect_a_w_1 = R.sect_a_w_1
AND L.id <> R.id
我们收集12个临时表中的输出并运行12个表的联合查询,以获得所有表达式的简短列表,这些表达式具有至少一个相同单词的潜在匹配表达式.这是我们挑战A的解决方案.我们现在有一个最可能的匹配对的简短列表.此列表将包含数百万条记录(左和右条目对),但不包含数十亿条记录.
挑战B
挑战B的目标是批量处理简化的Levenstein距离(而不是在循环中运行它).首先,我们应该就什么是简化的Levenstein距离达成一致.首先,我们同意两个表达式的levenstein距离是具有相同索引的两个表达式的所有单词的levenstein距离的总和.我的意思是两个表达式的Levenstein距离是它们的两个第一个单词的距离加上它们的两个第二个单词的距离等.其次,我们需要发明一个简化的Levenstein距离.我建议使用n-gram方法,只有2个字符的克数,其索引绝对差值小于2.
例如,彼得和彼特之间的距离计算如下
Peter
1 = pe
2 = et
3 = te
4 = er
5 = r_
Pieter
1 = pi
2 = ie
3 = et
4 = te
5 = er
6 = r_
彼得和彼得有4个常见的2克,指数绝对差值小于2'等','te','呃','r_'.有6个可能的2克的最大的两个词,距离那么6-4 = 2 - 的编辑距离也将是2,因为有"ETER"和一个字母插入"我"的一个举动.
这是一个近似值,并不适用于所有情况,但我认为在我们的情况下它会很好地工作.如果我们对结果的质量不满意,我们可以尝试3克或4克或允许大于2克的序列差异.但是这个想法是每对执行的计算量比传统的Levenstein算法少得多.
然后我们需要将其转换为技术解决方案.我之前做过的是:首先隔离单词:因为我们只需要测量单词之间的距离,然后将每个表达式的这些距离相加,我们可以通过在列表上运行一个不同的选择来进一步减少计算次数.单词(我们已经准备了上一节中的单词列表).
这种方法需要一个映射表,它跟踪表达式id,section id,word id和word的单词序列号,以便在进程结束时计算原始表达式距离.
然后,我们有一个更短的新列表,并包含2克距离度量相关的所有单词的交叉连接.然后我们想批量处理这个2克距离测量,我建议在SQL连接中进行.这需要一个预处理步骤,包括创建一个新的临时表,它将每2克存储在一个单独的行中 - 并跟踪单词Id,单词序列和节类型
从技术上讲,这是通过切片用串选择,像这样的一个系列(或环)的单词列表完成(假定字清单表 - 有两个副本,一个向左,一个向右 - 包含2列word_id和字):
INSERT INTO left_gram_table (word_id, gram_seq, gram)
SELECT word_id, 1 AS gram_seq, SUBSTRING(word,1,2) AS gram
FROM left_word_table
然后
INSERT INTO left_gram_table (word_id, gram_seq, gram)
SELECT word_id, 2 AS gram_seq, SUBSTRING(word,2,2) AS gram
FROM left_word_table
等等.
会使"管家"的东西看起来像这样(假设单词id为152)
| pk | word_id | gram_seq | gram |
| 1 | 152 | 1 | st |
| 2 | 152 | 2 | te |
| 3 | 152 | 3 | ew |
| 4 | 152 | 4 | wa |
| 5 | 152 | 5 | ar |
| 6 | 152 | 6 | rd |
| 7 | 152 | 7 | d_ |
不要忘记在word_id,gram和gram_seq列上创建索引,并且可以使用左右克列表的连接来计算距离,其中ON看起来像
ON L.gram = R.gram
AND ABS(L.gram_seq + R.gram_seq)< 2
AND L.word_id <> R.word_id
距离是两个单词中最长的一个减去匹配的克数.SQL可以非常快速地进行这样的查询,我认为一台具有8 GB RAM的简单计算机可以在合理的时间范围内轻松完成数亿行.
然后,只需加入映射表来计算每个表达式中单词到单词距离的总和,就可以得到总表达式到表达式距离.
stringdist无论如何,您正在使用该包,是否stringdist::phonetic()适合您的需求？它计算每个字符串的soundex代码,例如:
phonetic(pdata$parents_name)
[1] "P361" "P361" "A655" "J225"
Soundex是一种经过验证的方法(差不多100年)用于散列名称,这意味着您不需要比较每一对观察结果.
你可能想要更进一步,为父亲和母亲分别为名字和姓氏做索引.
我的建议是使用数据科学方法来识别仅使用stringdist进行比较的相似(相同群集)名称.
我修改了一些生成"parents_name"的代码,在接近现实的场景中增加了第一和第二名称的可变性.
num<-4e6
#Random length
random_l<-round(runif(num,min = 5, max=15),0)
#Random strings in the first and second name
parent_rand_first<-stringi::stri_rand_strings(num, random_l)
order<-sample(1:num, num, replace=F)
parent_rand_second<-parent_rand_first[order]
#Paste first and second name
parents_name<-paste(parent_rand_first," + ",parent_rand_second)
parents_name[1:10]
这里开始真正的分析,首先从名称中提取特征,例如全局长度,第一个长度,第二个长度,元音和辅音的数字,包括第一个和第二个名称(以及任何其他感兴趣的名称).
之后绑定所有这些功能并在大量集群中集群化data.frame(例如1000)
features<-cbind(nchars,nchars_first,nchars_second,nvowels_first,nvowels_second,nconsonants_first,nconsonants_second)
n_clusters<-1000
clusters<-kmeans(features,centers = n_clusters)
仅在每个群集内应用stringdistmatrix(包含类似的几个名称)
dist_matrix<-NULL
for(i in 1:n_clusters)
{
cluster_i<-clusters$cluster==i
parents_name<-as.character(parents_name[cluster_i])
dist_matrix[[i]]<-stringdistmatrix(parents_name,parents_name,"lv")
}
在dist_matrix中,您拥有群集中每个元素的距离,并且您可以使用此距离分配family_id.
要计算每个群集中的距离(在此示例中),代码大约需要1秒(取决于群集的维度),在15分钟内计算所有距离.
警告:dist_matrix增长得非常快,如果你要在di里面分析它来循环提取famyli_id然后你可以丢弃它,你的代码会更好.
您可以通过不比较所有几行来改进。相反，创建一个新变量将有助于决定是否值得比较。
例如，创建一个新变量“score”，其中包含在parents_name中使用的字母的有序列表（例如，如果“peter pan + marta Steward”，则分数将为“ademnprstw”），并仅计算分数匹配的行之间的距离。
当然，您可以找到一个更适合您需要的分数，并稍微改进以在并非所有使用的字母都是常见的情况下进行比较。
| 归档时间： |
|
| 查看次数： |
2303 次 |
| 最近记录： |