作者 | Luke Whyte
来源 | Medium
编辑 | 代码医生团队
这是一个常见的电子表格或数据库问题：
代码语言：javascript复制 ----- -------------------
| row | fullname |
----- -------------------
| 1 | John F. Doe |
| 2 | Esquivel, Mara |
| 3 | Doe, John F |
| 4 | Whyte, Luke |
| 5 | Doe, John Francis |
----- ------------------- 第1,3和5行可能指的是拼写和格式略有偏差的同一个人。在小型数据集中，可以手动清洁细胞。但是在庞大的数据集中呢？如何梳理成千上万的文本条目并将类似的实体分组？
理想情况下，有一种简单的方法来添加第三列，如下所示：
代码语言：javascript复制 ----- ------------------- ---------------
| row | fullname | name_groups |
----- ------------------- ---------------
| 1 | John F. Doe | Doe John F |
| 2 | Esquivel, Mara | Esquivel Mara |
| 3 | Doe, John F | Doe John F |
| 4 | Whyte, Luke | Whyte Luke |
| 5 | Doe, John Francis | Doe John F |
----- ------------------- --------------- 好吧，那就是要做的事情。
TLDR：为此构建了一个工具。可以在此处安装Python模块。但是如果想了解这个工具背后的概念请继续阅读。
https://github.com/lukewhyte/textpack
将讨论的主题：
- 使用TF-IDF和N-Grams构建文档术语矩阵
- 使用余弦相似度计算字符串之间的接近度
- 使用哈希表将发现转换为电子表格中的“组”列
在本教程中，将使用美国劳工部工资盗窃调查的这个数据集。它包含了从1984年到2018年由于最低工资或加班违规而对雇主进行的每次DOL调查。
https://data.world/lukewhyte/us-dept-of-labor-wage-theft-investigations
数据包括一legal_name列，列出了被调查公司的名称。但是，输入格式变化很大：
代码语言：javascript复制 ----- ----------------------
| row | legal_name |
----- ----------------------
| 1 | Wal-mart Inc |
| 2 | Walmart Stores Inc. |
| 3 | Wal-mart stores Inc |
| 4 | Wal-Mart stores Inc. |
----- ---------------------- 将对条目进行规范化和分组，legal_name然后使用组进行快速分析。
第一步：使用TF-IDF和N-Grams构建文档术语矩阵
在这里面临的最大挑战是，专栏中的每个条目都需要与其他条目进行比较。因此，一张400,000行的纸张需要400,000²的计算。
如果可以使用矩阵乘法进行同步计算会更快，可以使用文档术语矩阵，TF-IDF和N-Grams。
定义这些术语：
文件术语矩阵
文档术语矩阵本质上是Bag of Words（BOW）概念的延伸，喜欢这个概念，因为它听起来就像是一个蒙面男子会在芝麻街偷窃的东西。
BOW涉及计算字符串中单词的频率。所以鉴于这句话：
“Rhode Island is neither a road nor is it an island. Discuss.”
可以生成这样的BOW表示：
代码语言：javascript复制 --------- -------
| term | count |
--------- -------
| rhode | 1 |
| island | 2 |
| is | 2 |
| neither | 1 |
| a | 1 |
| road | 1 |
| nor | 1 |
| it | 1 |
| an | 1 |
| discuss | 1 |
--------- ------- 文档术语矩阵（DTM）将BOW扩展为多个字符串（或者在命名中，“多个文档”）。想象一下，有以下三个字符串：
- “Even my brother has needs”
- “My brother needs a lift”
- “Bro, do you even lift?”
DTM可能如下所示：
每个条目的值通过计算每个单词在每个字符串中出现的次数来确定。
上述方法的问题在于，诸如“the”，“is”和“if”之类的微不足道的词语往往比重要词语更频繁地出现，这可能会扭曲分析。
因此可以为它们分配TF-IDF分数，而不是计算单词，该分数评估每个单词对DTM的重要性。
TF-IDF
为了计算TF-IDF分数，将术语在单个文档中出现的次数（术语频率或TF）乘以术语对整个语料库的重要性（逆文档频率或IDF） - 单词出现的文档越多在这个词中，人们认为这个词在区分文件方面的价值就越低。
重要的是，对于文档术语矩阵中的每个单词，如果用TF-IDF分数替换单词计数，可以在检查字符串相似性时更有效地权衡单词。
N元
最后将解决这个问题：
Burger King是两个字。BurgerKing应该是两个单词，但计算机会将其视为一个单词。因此，当计算文档术语矩阵时，这些术语将不匹配。
N-gram是一种将字符串分成较小块的方法，其中块N大小。所以如果设置N到3得到：
['Bur'，'urg'，'rge'，'ger'，'er'，'r K'，'Ki'，'Kin'，'ing']
和：
['Bur'，'urg'，'rge'，'ger'，'erK'，'rKi'，'Kin'，'ing']
它比原始字符串重叠得多。
因此当构建文档术语矩阵时，计算N-Grams的TF-IDF分数而不是单词。
最后一些代码：
以下是使用N-Grams构建文档术语矩阵作为列标题和值的TF-IDF分数的代码：
代码语言：javascript复制import re
import pandas as pd
from sklearn.feature_extraction.text import TfidfVectorizer
# Import your data to a Pandas.DataFrame
df = pd.read_csv('./dol-data.csv')
# Grab the column you'd like to group, filter out duplicate values
# and make sure the values are Unicode
vals = df['legal_name'].unique().astype('U')
# Write a function for cleaning strings and returning an array of ngrams
def ngrams_analyzer(string):
string = re.sub(r'[,-./]', r'', string)
ngrams = zip(*[string[i:] for i in range(5)]) # N-Gram length is 5
return [''.join(ngram) for ngram in ngrams]
# Construct your vectorizer for building the TF-IDF matrix
vectorizer = TfidfVectorizer(analyzer=ngrams_analyzer)
# Build the matrix!!!
tfidf_matrix = vectorizer.fit_transform(vals)在第6行，将CSV转换为Pandas DataFrame。
第10行从legal_name数据集的列中提取唯一值，并将它们放在一维NumPy数组中。
在第14行，编写了用于构建5个字符N-Grams的函数。使用正则表达式过滤掉一些字符。
第20行传递ngrams_analyzer给将用于构建矩阵的TF-IDF矢量化器。
最后在第23行，构建了文档术语矩阵。
稀疏与密集矩阵以及如何使计算机崩溃
上述代码的结果tfidf_matrix是压缩稀疏行（CSR）矩阵。
出于目的，要知道任何大多数零值的矩阵都是稀疏矩阵。这与大多数非零值的密集矩阵不同。
N-Grams矩阵有237,573行和389,905列。前10行和列如下所示：
这很稀疏。没有理由将所有这些零存储在内存中。如果这样做，就有可能耗尽RAM并触发一个MemoryError。
输入CSR矩阵，该矩阵仅存储矩阵的非零值和对其原始位置的引用。
重要的是CSR格式可以节省内存，同时仍允许快速行访问和矩阵乘法。
步骤二：使用余弦相似度计算字符串之间的接近度
余弦相似度是0和1之间的度量，用于确定类似字符串的长度，而不管它们的长度如何。
它测量多维空间中字符串之间角度的余弦。该值越接近1（余弦为0°），字符串相似度越高。
采取以下三个字符串：
- I love dogs
- I love love love love love love love dogs
- I hate hate hate cats
并将它们放在文档术语矩阵中：
然后在多维空间上绘制此矩阵，其中每个维度对应于我们的四个术语之一。这可能看起来像这样：
如果看看点之间的距离，“I love dogs”和“I hate cats”实际上比“I love dogs”和“I love … love dogs”更接近彼此。
然而，如果看一下点线之间的角度 -余弦距离 - 可以看到“I love dogs”和“I love … love dogs”之间的角度远小于“I love dogs”之间的角度和“I hate cats”。
因此字符串1和字符串2之间的余弦相似性将比字符串1和字符串3之间的余弦相似性更高（更接近1）。
这是一个更深入的解释。
在Python中计算余弦相似度
可以使用scikit-learn来计算余弦相似度。这将返回具有余弦相似度值的成对矩阵，如：
然后将通过相似性阈值（例如0.75或0.8）过滤此矩阵，以便对认为代表相同实体的字符串进行分组。
但是如果使用由ING Bank的数据科学家构建的这个模块，可以在构建矩阵时按照相似性阈值进行过滤。该方法比scikit-learn更快，并返回内存密集度较低的CSR矩阵供使用。
https://github.com/ing-bank/sparse_dot_topn
所以在脚本中添加以下内容：
代码语言：javascript复制# Import IGN's awesome_cossim_topn module
from sparse_dot_topn import awesome_cossim_topn
# The arguments for awesome_cossim_topn are as follows:
### 1. Our TF-IDF matrix
### 2. Our TF-IDF matrix transposed (allowing us to build a pairwise cosine matrix)
### 3. A top_n filter, which allows us to filter the number of matches returned, which isn't useful for our purposes
### 4. This is our similarity threshold. Only values over 0.8 will be returned
cosine_matrix = awesome_cossim_topn(
tf_idf_matrix,
tf_idf_matrix.transpose(),
vals.size,
0.8
)现在有一个CSR矩阵，表示所有字符串之间的余弦相似性。是时候把它带回家了。
第三步：构建一个哈希表，将发现转换为电子表格中的“组”列
现在要构建一个Python字典，其中包含legal_name列中每个唯一字符串的键。
最快的方法是将CSR矩阵转换为坐标（COO）矩阵。COO矩阵是稀疏矩阵的另一种表示。
例如如果有这个稀疏矩阵：
代码语言：javascript复制 ------------
| 0,0,0,4 |
| 0,1,0,0 |
| 0,0,0,0 |
| 3,0,0,7 |
------------ 将其转换为COO矩阵，它会成为一个对象，具有三个属性- ，，row -分别包含以下三个数组，：coldata
- [0, 1, 3, 3]：每个非零值的行索引（0索引）
- [3, 1, 0, 3]：每个非零值的列索引（0索引）
- [4, 1, 3, 7]：来自矩阵的非零值
因此可以说值4（存储在matrix.data[0]）的坐标是(0,3)（存储在(matrix.row[0],matrix.col[0]）中。
构建COO矩阵并使用它来填充字典：
代码语言：javascript复制# Build a coordinate matrix from a cosine matrix
coo_matrix = cosine_matrix.tocoo()
# Instaniate our lookup hash table
group_lookup = {}
def find_group(row, col):
# If either the row or the col string have already been given
# a group, return that group. Otherwise return none
if row in group_lookup:
return group_lookup[row]
elif col in group_lookup:
return group_lookup[col]
else:
return None
def add_vals_to_lookup(group, row, col):
# Once we know the group name, set it as the value
# for both strings in the group_lookup
group_lookup[row] = group
group_lookup[col] = group
def add_pair_to_lookup(row, col):
# in this function we'll add both the row and the col to the lookup
group = find_group(row, col) # first, see if one has already been added
if group is not None:
# if we already know the group, make sure both row and col are in lookup
add_vals_to_lookup(group, row, col)
else:
# if we get here, we need to add a new group.
# The name is arbitrary, so just make it the row
add_vals_to_lookup(row, row, col)
# for each row and column in coo_matrix
# if they're not the same string add them to the group lookup
for row, col in zip(coo_matrix.row, coo_matrix.col):
if row != col:
# Note that what is passed to add_pair_to_lookup is the string at each index
# (eg: the names in the legal_name column) not the indices themselves
add_pair_to_lookup(vals[row], vals[col])在第2行，将余弦矩阵转换为坐标矩阵。
在第39-43行，遍历坐标矩阵，为非零值拉出行和列索引 - 记住它们都具有超过0.8的余弦相似性 - 然后将它们转换为它们的字符串值。
为了澄清，通过一个简单的示例进一步解开第39-43行。再次，取这个余弦矩阵：
如果使用awesome_cossim_topn阈值设置为0.8 构建它，然后将其转换为COO矩阵，可以像这样表示：
代码语言：javascript复制 (row, col) | data
------------|------
(0,0) | 1
(0,2) | 0.84
(1,1) | 1
(2,0) | 0.84
(2,2) | 1vals等于['Walmart', 'Target', 'Wal-mart stores']。
因此在循环内，首先(row, col)对通过的row != col条件是(0, 2)，再通到add_pair_to_lookup作为(vals[0], vals[2)或('Walmart', 'Wal-mart stores')。
继续这个例子，在所有的字符串通过之后add_pair_to_lookup，最终得到：
代码语言：javascript复制>>> group_lookup
{
'Walmart': 'Walmart',
'Wal-mart stores': 'Walmart'
}没有类似于'Target'的字符串，因此没有分配组。
矢量化Panda
最后，可以在Pandas中使用矢量化功能，将每个legal_name值映射到GroupDataFrame中的新列并导出新的CSV。
由于Pandas函数可以同时对整个数组进行操作 - 而不是依次对各个值进行操作 - 因此这个过程非常快：
代码语言：javascript复制df['Group'] = df['legal_name'].map(group_lookup).fillna(df['legal_name'])
df.to_csv('./dol-data-grouped.csv')该fillna方法允许在没有密钥时替换该legal_name值。Groupgroup_lookup
把它们放在一起：
代码语言：javascript复制import re
import pandas as pd
from sklearn.feature_extraction.text import TfidfVectorizer
from sparse_dot_topn import awesome_cossim_topn
# Import your data to a Pandas.DataFrame
df = pd.read_csv('./dol-data.csv')
# Instaniate our lookup hash table
group_lookup = {}
# Write a function for cleaning strings and returning an array of ngrams
def ngrams_analyzer(string):
string = re.sub(r'[,-./]', r'', string)
ngrams = zip(*[string[i:] for i in range(5)]) # N-Gram length is 5
return [''.join(ngram) for ngram in ngrams]
def find_group(row, col):
# If either the row or the col string have already been given
# a group, return that group. Otherwise return none
if row in group_lookup:
return group_lookup[row]
elif col in group_lookup:
return group_lookup[col]
else:
return None
def add_vals_to_lookup(group, row, col):
# Once we know the group name, set it as the value
# for both strings in the group_lookup
group_lookup[row] = group
group_lookup[col] = group
def add_pair_to_lookup(row, col):
# in this function we'll add both the row and the col to the lookup
group = find_group(row, col) # first, see if one has already been added
if group is not None:
# if we already know the group, make sure both row and col are in lookup
add_vals_to_lookup(group, row, col)
else:
# if we get here, we need to add a new group.
# The name is arbitrary, so just make it the row
add_vals_to_lookup(row, row, col)
# Construct your vectorizer for building the TF-IDF matrix
vectorizer = TfidfVectorizer(analyzer=ngrams_analyzer)
# Grab the column you'd like to group, filter out duplicate values
# and make sure the values are Unicode
vals = df['legal_name'].unique().astype('U')
# Build the matrix!!!
tfidf_matrix = vectorizer.fit_transform(vals)
cosine_matrix = awesome_cossim_topn(tf_idf_matrix, tf_idf_matrix.transpose(), vals.size, 0.8)
# Build a coordinate matrix
coo_matrix = cosine_matrix.tocoo()
# for each row and column in coo_matrix
# if they're not the same string add them to the group lookup
for row, col in zip(coo_matrix.row, coo_matrix.col):
if row != col:
add_pair_to_lookup(vals[row], vals[col])
df['Group'] = df['legal_name'].map(group_lookup).fillna(df['legal_name'])
df.to_csv('./dol-data-grouped.csv')剩下要做的就是将这些数据放入数据透视表中，看看哪些雇主欠（d）雇员的工资最多。
剧透警报：这是沃尔玛。183项调查导致他们同意支付近4100万美元的拖欠工资。
最后一点
如果希望按两列或更多列而不是一列进行分组，则可以创建一个临时列，以便在DataFrame中对每个列连接成单个字符串的条目进行分组：
代码语言：javascript复制columns_to_group = ['legal_name', 'address']
df['grouper'] = df[
columns_to_group.pop(0)
].astype(str).str.cat(
df[columns_to_group].astype(str)
)然后你会设置vals为：
代码语言：javascript复制vals = df['grouper'].unique().astype('U')并且，在最后导出时，删除该列：
代码语言：javascript复制df.drop(columns=['grouper']).to_csv('./dol-data-grouped.csv')再次创建了一个Python模块来完成所有这些工作。
https://github.com/lukewhyte/textpack
