- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
我在文档及其带状疱疹上使用了 minhash,以从这些文档生成签名矩阵。我已验证签名矩阵在比较已知相似文档(例如,两篇关于同一运动队的两篇文章或两篇关于同一世界赛事的文章)的杰卡德距离时给出了正确的读数。
我的问题是:使用这个签名矩阵执行 k-means 聚类是否有意义?
我已经尝试使用文档的签名向量并在迭代 kmeans 算法中计算这些向量的欧几里德距离,但我总是对我的集群产生胡说八道。我知道应该有两个集群(我的数据集是关于体育或商业的几千篇文章),最后我的两个集群总是随机的。我相信,将单词散列为整数的随机性每次都会使距离函数发生偏差,并压倒两个签名矩阵中的相似散列值。
[编辑以突出问题]
最佳答案
简短回答:不,使用签名矩阵进行 K 均值聚类没有意义。至少,并非没有重大操纵。
我在弄清楚如何自己做同样的事情(文本聚类)几天后才来到这里。我可能是错的,但我的看法是你犯了同样的错误:使用 MinHash 构建一个 [n_samples x n_perms]
矩阵,然后将其用作特征矩阵 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
数组不是特征矩阵。每行基本上都是出现在该文本样本中的特征(散列)列表……但它们不是列对齐的,因此特征分散在错误的维度中。
要将其转换为特征矩阵,您必须查看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)
好了。从那里:
希望这对您有所帮助。
汤姆
关于python - k-means 使用从 minhash 生成的签名矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46867085/
我熟悉SimHash和MinHash的LSH(局部敏感哈希)技术。 SimHash对实际值数据使用余弦相似度。 MinHash计算二进制矢量上的相似度相似度。但是我无法决定哪个更适合使用。 我正在为网
我在实现 minhashing 时遇到问题。在纸上和阅读中我理解这个概念,但我的问题是排列“技巧”。代替置换集合矩阵和值的实现建议是:“选择 k(例如 100)个独立的哈希函数”,然后算法说: for
我目前正在使用 MinHashing 技术进行文档聚类。但是,我没有得到想要的结果,因为 MinHash 是对 Jaccard similarity 的粗略估计,它不符合我的要求。 这是我的场景: 我
我正在尝试寻找可以用于我的工作的 minhash 开源实现。 我需要的功能非常简单,给定一个集合作为输入,实现应该返回它的 minhash。 首选 Python 或 C 实现,以防万一我需要破解它才能
假设我有五组要聚类。我了解此处描述的 SimHashing 技术: https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhs
我正在用 Java 编写一个 minhashing 算法,它要求我生成任意数量的随机哈希函数(在我的例子中是 240 个哈希函数),并通过它运行任意数量的整数(目前是 2000 个)。 为了做到这一点
我正在尝试了解 LSH 的实现。我在 stackoverflow 上找到了这个 Can you suggest a good minhash implementation? 我尝试遵循 Duhaime
我在文档及其带状疱疹上使用了 minhash,以从这些文档生成签名矩阵。我已验证签名矩阵在比较已知相似文档(例如,两篇关于同一运动队的两篇文章或两篇关于同一世界赛事的文章)的杰卡德距离时给出了正确的读
我正在使用 Apache Spark ML LSH 的 approxSimilarityJoin 方法加入 2 个数据集,但我看到了一些奇怪的行为。 在(内部)连接之后,数据集有点偏斜,但是每次完成一
这篇文章很长,对此我深表歉意。 我一直在尝试实现chapter 3中讨论的Minhash LSH算法。通过使用 Spark (Java)。我正在使用这样的玩具问题: +--------+------+
我正在寻找一个 node.js/Javascript 模块,它将 minhash 算法应用于字符串或更大的文本,并为我返回该文本的“标识”或“特征”字节串或十六进制字符串。如果我将该算法应用于另一个相
我在用 : hadoop-1.2.1和mahout-distribution-0.8 当我尝试使用以下命令运行HASHMIN方法时: $MAHOUT_HOME/bin/mahout org.apach
我是一名优秀的程序员,十分优秀!