在python中发现字符串“motifs”

数据挖掘 Python 聚类 数据清理 文本
2022-03-04 08:15:10

我有数百万来自不同来源的字符串,它们往往表现出一些共同的模式。有没有办法提取这些常见的图案?

例如,在包含字符串的(数百万个)列表中

['rs12346','rs1212122',...,'sxs-rs333',...,'kgp222']

..有没有办法提取以下模式?

  • 'rs' 加上一位或多位数字
  • 'sxs-rs' 加上一位或多位数字
  • 'kgp' 加上一位或多位数字

其他一些参数:

  • 事先清理不是一种选择
  • 可以进行一些手动调整(例如,由于外部知识而手动更改模式)
  • 可以容忍异常(即分类少于 100% 的字符串)
  • 一个理想的解决方案是使用内置的 python 库。
2个回答

假设字母表示“图案”并且数字被认为是数字而不是确切的数字,这就是我要做的:

首先 - 将数字转换为数字占位符 ( #)

import re
s = re.sub("\d",s,"#")

然后我会将字符串转换为 char 级别的 bag-of-bigrams 向量

from sklearn.feature_extraction.text import CountVectorizer
vecs = CountVectorizer(s, analyzer="char_wb", ngram_range=(1,3))

经过这两个步骤,我们从任何字符串中得到了一个稀疏向量:

'ab123' --> {" a":1,"ab":1,"b#","##":2,"# ":1}

接下来,我们要将这些向量转换为成对距离矩阵并按该距离进行聚类。

from sklearn.metrics.pairwise import pairwise_distances
from scipy.cluster import  hierarchy
def link_cluster(X, threshold=0.1, metric="cosine", algo="average"):
    X = X.todense()
    Z = hierarchy.linkage(X, algo, metric=metric)
    C = hierarchy.fcluster(Z,threshold, criterion="distance")
    return C

你的最终结果是

C = link_cluster(vecs)

我认为答案还取决于您的用例。如果您只想检测这类字符串,我会专注于适合我需要的启发式规则,而不是创建一个学习识别字符串模式的系统。

但是,如果您的目标是根据当前模式生成类似类型的字符串或在文本流中查找新字符串,您应该寻找正则表达式生成器。有这个关于一般正则表达式的资源列表,您应该专注于手头任务的生成器。

对于过去的类似任务,我使用了一个在线免费工具,该工具将生成一个正则表达式(如果可能),尽可能多地满足您的示例字符串。所以你可以试一试,作为一个快速的解决方案。

无论哪种方式,我都会首先进行一些数据探索(例如,数字和字母是否也混合在一起,或者数字总是出现在字母/符号等之后),以便更好地理解手头的问题。此外,这可能会导致简单的启发式规则足以作为粗略的解决方案,或者至少是一个简单的基线系统,我将根据它“推销”机器学习模型。