k-means 使用从 minhash 生成的签名矩阵
k-means using signature matrix generated from minhash
我在文档及其带状疱疹上使用了 minhash 从这些文档生成签名矩阵。我已经验证签名矩阵在比较已知相似文档(例如,两篇关于同一运动队的两篇文章或两篇关于同一世界赛事的文章)的 jaccard 距离时给出了正确的读数。
我的问题是:使用这个签名矩阵来执行 k 均值聚类是否有意义?
我已经尝试使用文档的签名向量并在迭代 kmeans 算法中计算这些向量的欧几里德距离,但我总是对我的集群产生胡说八道。我知道应该有两个集群(我的数据集是关于体育或商业的几千篇文章),最后我的两个集群总是随机的。我确信将单词散列为整数的随机性每次都会使距离函数发生偏差,并压倒两个签名矩阵中的相似散列值。
[编辑以突出问题]
TL;DR
简短回答:不,使用签名矩阵进行 K 均值聚类没有意义。至少,并非没有重大操纵。
一些解释
我在弄清楚如何自己做同样的事情(文本聚类)几天后才来到这里。我可能是错的,但我的看法是你犯了和我一样的错误:使用 MinHash 构建一个 [n_samples x n_perms]
矩阵,然后将其用作你 [=64] 的特征矩阵 X
=] k-means.
我猜你正在做类似的事情:
# THIS CODE IS AN EXAMPLE OF WRONG! DON'T IMPLEMENT!
import numpy as np
import MinHash
from sklearn.cluster import KMeans
# Get your data.
data = get_your_list_of_strings_to_cluster()
n_samples = len(data)
# Minhash all the strings
n_perms = 128
minhash_values = np.zeros((n_samples, n_perms), dtype='uint64')
minhashes = []
for index, string in enumerate(data):
minhash = MinHash(num_perm=n_perms)
for gram in ngrams(string, 3):
minhash.update("".join(gram).encode('utf-8'))
minhash_values[index, :] = minhash.hashvalues
# Compute clusters
clusterer = KMeans(n_clusters=8)
clusters = clusterer.fit_predict(minhash_values)
这将表现得可怕,因为致命的缺陷 - minhash_values
数组 不是 特征矩阵。每行基本上都是出现在该文本样本中的特征(散列)列表……但它们不是列对齐的,因此特征分散到错误的维度中。
要将其转换为 feature 矩阵,您必须查看 minhash_values
中的所有唯一哈希,然后创建一个矩阵 [n_samples x n_unique_hashes]
,(n_unique_hashes
是找到的独特特征的数量)将其设置为 1
,其中文本示例包含该特征,在其他地方设置为 0
。通常这个矩阵会很大而且稀疏。然后你可以聚类。
另一种文本聚类方式
但真是令人难以置信的麻烦!幸运的是,scikit-learn
可以提供帮助。它提供了一些非常easy to use and scalable vectorisers:
这样你的问题就很容易解决了:
# Imports
from sklearn.feature_extraction.text import HashingVectorizer
from sklearn.cluster import KMeans
# Get your data
data = get_your_list_of_strings_to_cluster()
# Get your feature matrix
text_features = HashingVectorizer(analyzer="word").fit_transform(data)
# Compute clusters
clusterer = KMeans(n_clusters=2)
clusters = clusterer.fit_predict(text_features)
好了。从那里:
- 微调你的矢量化器(也试试 TfidfVectorizer,调整输入参数等),
- 尝试其他聚类器(f/ex 我发现
HDBSCAN英里更好
比 kmeans - 更快、更健壮、更准确、调整更少)。
希望这对您有所帮助。
汤姆
我在文档及其带状疱疹上使用了 minhash 从这些文档生成签名矩阵。我已经验证签名矩阵在比较已知相似文档(例如,两篇关于同一运动队的两篇文章或两篇关于同一世界赛事的文章)的 jaccard 距离时给出了正确的读数。
我的问题是:使用这个签名矩阵来执行 k 均值聚类是否有意义?
我已经尝试使用文档的签名向量并在迭代 kmeans 算法中计算这些向量的欧几里德距离,但我总是对我的集群产生胡说八道。我知道应该有两个集群(我的数据集是关于体育或商业的几千篇文章),最后我的两个集群总是随机的。我确信将单词散列为整数的随机性每次都会使距离函数发生偏差,并压倒两个签名矩阵中的相似散列值。
[编辑以突出问题]
TL;DR
简短回答:不,使用签名矩阵进行 K 均值聚类没有意义。至少,并非没有重大操纵。
一些解释
我在弄清楚如何自己做同样的事情(文本聚类)几天后才来到这里。我可能是错的,但我的看法是你犯了和我一样的错误:使用 MinHash 构建一个 [n_samples x n_perms]
矩阵,然后将其用作你 [=64] 的特征矩阵 X
=] k-means.
我猜你正在做类似的事情:
# THIS CODE IS AN EXAMPLE OF WRONG! DON'T IMPLEMENT!
import numpy as np
import MinHash
from sklearn.cluster import KMeans
# Get your data.
data = get_your_list_of_strings_to_cluster()
n_samples = len(data)
# Minhash all the strings
n_perms = 128
minhash_values = np.zeros((n_samples, n_perms), dtype='uint64')
minhashes = []
for index, string in enumerate(data):
minhash = MinHash(num_perm=n_perms)
for gram in ngrams(string, 3):
minhash.update("".join(gram).encode('utf-8'))
minhash_values[index, :] = minhash.hashvalues
# Compute clusters
clusterer = KMeans(n_clusters=8)
clusters = clusterer.fit_predict(minhash_values)
这将表现得可怕,因为致命的缺陷 - minhash_values
数组 不是 特征矩阵。每行基本上都是出现在该文本样本中的特征(散列)列表……但它们不是列对齐的,因此特征分散到错误的维度中。
要将其转换为 feature 矩阵,您必须查看 minhash_values
中的所有唯一哈希,然后创建一个矩阵 [n_samples x n_unique_hashes]
,(n_unique_hashes
是找到的独特特征的数量)将其设置为 1
,其中文本示例包含该特征,在其他地方设置为 0
。通常这个矩阵会很大而且稀疏。然后你可以聚类。
另一种文本聚类方式
但真是令人难以置信的麻烦!幸运的是,scikit-learn
可以提供帮助。它提供了一些非常easy to use and scalable vectorisers:
这样你的问题就很容易解决了:
# Imports
from sklearn.feature_extraction.text import HashingVectorizer
from sklearn.cluster import KMeans
# Get your data
data = get_your_list_of_strings_to_cluster()
# Get your feature matrix
text_features = HashingVectorizer(analyzer="word").fit_transform(data)
# Compute clusters
clusterer = KMeans(n_clusters=2)
clusters = clusterer.fit_predict(text_features)
好了。从那里:
- 微调你的矢量化器(也试试 TfidfVectorizer,调整输入参数等),
- 尝试其他聚类器(f/ex 我发现 HDBSCAN英里更好 比 kmeans - 更快、更健壮、更准确、调整更少)。
希望这对您有所帮助。
汤姆