从3.7小时到0.2秒，解决大型数据集的模糊匹配 |
您所在的位置：网站首页 › Python处理数据模糊查询替换 › 从3.7小时到0.2秒，解决大型数据集的模糊匹配 |
从3.7小时到0.2秒，解决大型数据集的模糊匹配
全文共4812字，预计学习时长10分钟 相同但不同。数据的模糊匹配是许多数据科学工作流程中必须的第一步。真实世界中的数据十分杂乱。整理这些杂乱的数据集非常困难，并且会浪费大量用于数据分析本身的时间。 本文重点阐述了模糊匹配，以及如何通过下列方式自动化解决数据科学工作流程中的疑难问题： 1. 删除重复数据。合并数据集中相似的类别或项目（比如，可能需要将“D J Trump”，“D. Trump”和“Donald Trump”当作同一个条目”）。 2. 记录链接。关联某个特定实体的相关数据集（比如，把关于“D J Trump”的记录链接到他的维基百科页面）。 通过使用一种自然语言处理领域中的特殊手段，可以对大型数据集进行以上两种处理。  大型数据集的模糊匹配问题 可以执行模糊匹配的算法很多，但它们难以处理包含几千条记录的中型数据集。 原因是这些算法把每一条记录和数据集中的其他所有记录做对比。在计算机科学中，这一算法的运行时间随数据集大小呈平方增长。这会阻碍算法处理较大的数据集。  运行时间随数据集大小呈平方增长时记录条数和所需操作次数的对比。一个仅包含1万条记录的数据集需要1亿次操作。 更糟糕的是，字符串的长度也会影响大多数字符串匹配函数的效率。所以当比较两段较长的文本时，函数的运行速度会更慢。 用著名的NLP算法解决此问题 这个问题的解决方案来自一个著名的自然语言处理算法，也就是词频-逆文本频率指数算法（简称tf-idf）。从1972年起这个算法就被用于处理语言问题。 这是一个简单的算法。它把文本划分成信息块（或者称为项目），计算给定文本中每个信息块的出现次数，然后基于这个信息块在数据集所有文本中的罕见程度加权。这将把有意义的词语从常见词语中分离出来。 虽然信息块一般指完整的单词，但这并不妨碍数据工程师把同样的技术应用于词语中的字符组合。比如，可以把每个单词分成三个字符组合。对于单词“Department”来说，输出的结果是： ' De', 'Dep', 'epa','par', 'art', 'rtm', 'tme', 'men', 'ent', 'nt ' 可以把这些信息块放在一个矩阵中进行比对，寻找相似的组合。由于重点关注数据集中较少见的字母组合，这种方式理应既高效又高质。来验证这一点吧！ 实例 文中用来测试这个算法的例子是一组在ContractsFinder（https://www.gov.uk/contracts-finder）网站上公布过合同的公共机构。这些机构的名称非常杂乱，而且似乎是通过自由文本字段录入的。  数据集的一部分，其中总共有3561家机构。智能删除重复数据 首先研究删除相似组合的方式。使用Python的Scikit-Learn库，这个过程将变得十分轻松： 1. 编写一个函数把字符串分割成字符组合 2. 使用Scikit-Learn创建这些字符的tf-idf矩阵 3. 通过余弦相似性展示整个数据集中的相似组合 ngram函数 下面的函数被用于清理文本数据，也用于把文本拆分成片段。代码中的注释指出了每一行代码的意图。 ngram函数既对原始字符串进行清洗，又将其拆分成字符组合。 应用该函数并建立tf-idf矩阵 Scikit库中Tf-idf实现的优点在于它允许加入自定义函数。程序员因此得以导入已创建的函数，并用短短几行代码构建矩阵。 from sklearn.feature_extraction.text import TfidfVectorizer org_names = names['buyer'].unique() vectorizer = TfidfVectorizer(min_df=1, analyzer=ngrams) tf_idf_matrix = vectorizer.fit_transform(org_names)通过余弦相似性寻找相似组合 可以使用Scikit中的余弦相似性函数。但由于这个函数将返回每一个项目和每一个样本的相似性，它并非寻找相似记录组合最有效的方法。此处将使用一种更快的实现来代替它。 import numpy as np from scipy.sparse import csr_matrix !pip install sparse_dot_topn import sparse_dot_topn.sparse_dot_topn as ct def awesome_cossim_top(A, B, ntop, lower_bound=0): # force A and B as a CSR matrix. # If they have already been CSR,there is no overhead A = A.tocsr() B = B.tocsr() M, _ = A.shape _, N = B.shape idx_dtype = np.int32 nnz_max = M*ntop indptr = np.zeros(M+1,dtype=idx_dtype) indices = np.zeros(nnz_max,dtype=idx_dtype) data = np.zeros(nnz_max,dtype=A.dtype) ct.sparse_dot_topn( M, N, np.asarray(A.indptr,dtype=idx_dtype), np.asarray(A.indices,dtype=idx_dtype), A.data, np.asarray(B.indptr,dtype=idx_dtype), np.asarray(B.indices,dtype=idx_dtype), B.data, ntop, lower_bound, indptr, indices, data) return csr_matrix((data,indices,indptr),shape=(M,N))把这些代码组合在一起，可以得到下面的结果：  像变魔术一样！这个算法非常适用于识别重复记录。结果看起来很不错，那么运行速度如何呢？下面把一个较为传统的分析相似组合的方法与使用fuzzywuzzy库的方法做比较： !pip install fuzzywuzzy from fuzzywuzzy import fuzz from fuzzywuzzy import process t1 = time.time() print(process.extractOne('Ministry of Justice', org_names)) #org names is ourlist of organisation names t = time.time()-t1 print("SELFTIMED:", t) print("Estimated hours to complete for full dataset:",(t*len(org_names))/60/60) Outputs: SELFTIMED: 3.7s Estimated hrs to complete for full dataset: 3.78hrs使用传统方法需要至少3.7小时的运行时间。那么前文中提到的算法需要多久呢？ import time t1 = time.time() matches = awesome_cossim_top(tf_idf_matrix, tf_idf_matrix.transpose(), 10,0.85) t = time.time()-t1 print("SELFTIMED:", t) Outputs: SELFTIMED: 0.19s预计运行时间从3.7小时缩短到了大约0.2秒（几乎是66000倍的效率提升！） 记录链接和其他处理方式 如果想要使用这种办法来处理其他数据源，上面大部分的代码都可以重复使用。下面将展示实现这一点的方式，并使用KNN算法衡量相似性。 接下来需要添加的数据集是由国家统计办公室(ONS)创建的一系列“干净”的机构名称。  准备添加的数据集正如下列代码所展现的，这个方法唯一的不同之处在于，通过学习“干净”的数据集创建的tdif矩阵，处理杂乱的数据。 随后，getNearestN算法使用Scikit的KNN实现来找到数据集中最相似的组合： from sklearn.metrics.pairwise import cosine_similarity from sklearn.feature_extraction.text import TfidfVectorizer import re clean_org_names = pd.read_excel('Gov Orgs ONS.xlsx') clean_org_names = clean_org_names.iloc[:, 0:6] org_name_clean = clean_org_names['Institutions'].unique() print('Vecorizing the data - this could take a few minutes for largedatasets...') vectorizer = TfidfVectorizer(min_df=1, analyzer=ngrams, lowercase=False) tfidf = vectorizer.fit_transform(org_name_clean) print('Vecorizing completed...') from sklearn.neighbors import NearestNeighbors nbrs = NearestNeighbors(n_neighbors=1, n_jobs=-1).fit(tfidf) org_column = 'buyer' #column to match against in the messy data unique_org = set(names[org_column].values) # set used for increased performance ###matching query: def getNearestN(query): queryTFIDF_ =vectorizer.transform(query) distances, indices =nbrs.kneighbors(queryTFIDF_) return distances, indices import time t1 = time.time() print('getting nearest n...') distances, indices = getNearestN(unique_org) t = time.time()-t1 print("COMPLETED IN:", t) unique_org = list(unique_org) #need to convert back to a list print('finding matches...') matches = [] for i,j in enumerate(indices): temp = [round(distances[i][0],2),clean_org_names.values[j][0][0],unique_org[i]] matches.append(temp) print('Building data frame...') matches = pd.DataFrame(matches, columns=['Match confidence (lower isbetter)','Matched name','Origional name']) print('Done')代码结果如下：  并不是所有项目都在数据集中出现。幸好可以添加一个相似性阈值来筛选有效配对。这个例子指出，并不是所有项目都在两个数据集中同时出现。但是KNN算法依然可以用于寻找最相似的配对。在这种情况下，需要一个相似性阈值来定义有效的配对。 使用这种方式，将3651个项目和包含大约3000个项目的干净数据集进行匹配，只需要不到1秒。  留言 点赞 关注 我们一起分享AI学习与发展的干货 欢迎关注全平台AI垂类自媒体 “读芯术” |
【本文地址】
今日新闻 |
推荐新闻 |