我正在尝试寻找一个minhash开源实现,我可以利用它来完成我的工作.

我需要的功能非常简单,给定一个输入,实现应返回其minhash.

python或C实现将是首选,以防万一我需要破解它为我工作.

任何指针都会有很大的帮助.

问候.

有没有允许LSH在Elasticsearch上的插件？如果是的话,你能指点我的位置,并告诉我一些如何使用它？谢谢

编辑:我发现ES使用MinHash插件.我怎么能用这个比较文件呢？找到重复的好设置是什么？

我熟悉SimHash和MinHash的LSH(Locality Sensitive Hashing)技术.SimHash使用余弦相似性而不是实值数据.MinHash计算二元向量的相似度.但我不能决定使用哪一个更好.

我正在为一个网站创建一个后端系统,以查找半结构化文本数据的近似副本.例如,每条记录都有标题,位置和简短的文字说明(<500字).

除了特定的语言实现,哪种算法最适合绿地生产系统？

我正在使用MinHash算法在图像之间找到类似的图像.我遇到过这篇文章,How can I recognize slightly modified images?它指出了MinHash算法.

我在这篇博文中使用了C#实现Set Similarity and Min Hash.

但在尝试使用实现时,我遇到了两个问题.

• 我应该将universe值设置为什么值？
• 传递图像字节数组时HashSet,它只包含不同的字节值; 从而比较1~256的值.

universeMinHash的这个是什么？
我该怎么做才能改进C#MinHash实现？

由于HashSet<byte>包含的值高达256,因此相似度值总是为1.

以下是使用C#MinHash实现的源代码Set Similarity and Min Hash:

class Program
{
    static void Main(string[] args)
    {
        var imageSet1 = GetImageByte(@".\Images\01.JPG");
        var imageSet2 = GetImageByte(@".\Images\02.TIF");
        //var app = new MinHash(256);
        var app = new MinHash(Math.Min(imageSet1.Count, imageSet2.Count));
        double imageSimilarity = app.Similarity(imageSet1, imageSet2);
        Console.WriteLine("similarity = {0}", imageSimilarity);
    }

    private static HashSet<byte> GetImageByte(string …

问题很简单:我需要根据Redis的表示找到最佳策略来实现准确的HyperLogLog联合 - 这包括在导出数据结构以供其他地方使用时处理它们的稀疏/密集表示.

两个策略

有两种策略,其中一种似乎要简单得多.我已经看过实际的Redis源代码了,我遇到了一些麻烦(在我自己的C中并不大),从精确和高效的角度来看,使用内置的结构/例程或开发自己的内容是否更好.对于它的价值,我愿意牺牲空间和某种程度上的错误(stdev + -2%)以追求效率与极大的集合.

1.包容性原则

到目前为止,两者中最简单的 - 基本上我只是将无损联合(PFMERGE)与此原理结合使用来计算重叠的估计.在许多情况下,测试似乎表明这种运行是可靠的,尽管我无法准确处理非常高的效率和准确性(某些情况下会产生20-40%的错误,这在这个用例中是不可接受的).

基本上:

aCardinality + bCardinality - intersectionCardinality

或者,在多组情况下......

aCardinality + (bCardinality x cCardinality) - intersectionCardinality

似乎在许多情况下都能很好地准确地工作,但我不知道我是否相信它.虽然Redis有许多内置的低基数修饰符,旨在规避已知的HLL问题,但我不知道野生不准确(使用包含/排除)的问题是否仍然存在大量差异很大的问题......

2. Jaccard Index Intersection/MinHash

这种方式似乎更有趣,但我的一部分感觉它可能与Redis的一些现有优化计算重叠(即,我没有从头开始实现我自己的HLL算法).

通过这种方法,我将使用MinHash算法的随机抽样箱(我不认为LSH实现值得麻烦).这将是一个单独的结构,但通过使用minhash获取集合的Jaccard索引,您可以有效地将union基数乘以该索引以获得更准确的计数.

问题是,我不太熟悉HLL,虽然我很想深入研究Google论文,但我需要在短期内实现可行的实施.有可能我忽略了Redis现有优化的一些基本考虑因素,或者在算法本身中,它允许计算上便宜的交叉点估计具有相当宽松的置信区间.

因此,我的问题:

如果我愿意牺牲空间(并且在很小程度上,精确度),如何使用redis最有效地获得N个巨大(数十亿)集的计算上便宜的交叉估计？

我正在实现一个近邻搜索应用程序，它将找到相似的文档。到目前为止，我已经阅读了很多有关LSH的资料（LSH背后的理论有些令人困惑，我还不能100％理解它）。

我的代码能够使用minhash函数计算签名矩阵（我已经接近尾声了）。我也将签名策略应用于签名矩阵。但是，我不明白如何将一个带中的（列的）签名向量散列到存储桶中。

我的最后一个问题可能是最重要的一个，但我不得不问一些introduction问题：

问题1：哈希函数是否只会将相同的向量映射到相同的存储桶？（假设我们有足够的水桶）

问题2：哈希函数是否应将相似的向量映射到同一存储桶？如果是，那么这种相似性的程度/定义是多少，因为我不是在计算比较，而是在进行哈希处理。

q3：根据上面的问题，我应该使用哪种哈希表算法？

q4：我认为我的最弱点是我不知道如何生成将向量作为输入并选择存储桶作为输出的哈希函数。我可以根据q1和q2自己实现一个...关于为LSH生成哈希函数的任何建议bucketing？

我已经阅读了许多使用min-hash实现LSH(局部敏感哈希)的教程,文档和代码片段.

LSH试图通过散列随机子集并在这些子集上进行聚合来找到两组的Jaccard系数.我查看了code.google.com中的实现,但也无法理解他们的方法.我理解Google新闻个性化的文章:可扩展的在线协同过滤,但我无法理解那里的任何实现.

有人可以用简单的话来解释我如何用MinHash实现LSH吗？

我正在使用 Apache Spark ML LSH 的 approxSimilarityJoin 方法加入 2 个数据集，但我看到了一些奇怪的行为。

在（内部）连接之后，数据集有点偏斜，但是每次完成一个或多个任务都需要花费过多的时间。

正如您所看到的，每个任务的中位数是 6 毫秒（我在较小的源数据集上运行它进行测试），但 1 个任务需要 10 分钟。它几乎不使用任何 CPU 周期，它实际上连接了数据，但是速度太慢了。下一个最慢的任务在 14 秒内运行，有 4 倍多的记录并且实际上溢出到磁盘。

如果你看

连接本身是根据 minhash 规范和 udf 计算匹配对之间的 jaccard 距离的 pos & hashValue (minhash) 上的两个数据集之间的内部连接。

分解哈希表：

modelDataset.select(
      struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))

杰卡德距离函数：

modelDataset.select(
      struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))

连接处理过的数据集：

 override protected[ml] def keyDistance(x: Vector, y: Vector): Double = {
    val xSet = x.toSparse.indices.toSet
    val ySet = y.toSparse.indices.toSet
    val intersectionSize = xSet.intersect(ySet).size.toDouble
    val unionSize = xSet.size + ySet.size - intersectionSize
    assert(unionSize > 0, "The …

我在实现minhashing时遇到问题.在纸上和从阅读中我理解这个概念,但我的问题是排列"技巧".而不是置换集合和值的矩阵,实现的建议是:"选择k(例如100)独立散列函数"然后算法说:

for each row r 
    for each column c 
        if c has 1 in row r 
           for each hash function h_i  do
            if h_i(r) is a smaller value than M (i, c) then
            M(i, c) := h_i(r)

在不同的小例子和教学书中,他们只使用两个或三个哈希函数的形式(h = a*x + b mod p).这很容易找到,但在实践中如何做,我怎样才能找到100个这样的独立功能.

在这里的Java示例中,仅从一个散列函数而不是多散列函数生成散列值,而与行索引无关.区别在哪里？我现在的问题是如何找到这些独立的哈希函数,或者如果只有一个哈希函数的方法如何在算法中处理这些值？

我正在用Java编写一个minhashing算法,它要求我生成任意数量的随机散列函数(在我的情况下为240个散列函数),并通过它运行任意数量的整数(目前为2000).

为了做到这一点,我一直在为240个散列函数中的每一个生成随机数a,b和c(从1到2001的范围).然后,我的哈希函数返回h =((a*x)+ b)%c,其中h是返回值,x是通过它运行的整数之一.

这是随机散列的有效实现,还是有更常见/可接受的方式来实现它？

这篇文章提出了类似的问题,但我仍然对答案的措辞感到困惑: Minhash实现如何为排列找到哈希函数

我正在尝试实现 LSH spark 以在包含 50000 行和每行约 5000 个特征的非常大的数据集上为每个用户找到最近的邻居。这是与此相关的代码。

    MinHashLSH mh = new MinHashLSH().setNumHashTables(3).setInputCol("features")
                        .setOutputCol("hashes");

    MinHashLSHModel model = mh.fit(dataset);

    Dataset<Row> approxSimilarityJoin = model .approxSimilarityJoin(dataset, dataset, config.getJaccardLimit(), "JaccardDistance");

    approxSimilarityJoin.show();

作业卡在 approxSimilarityJoin() 函数上，永远不会超出它。请让我知道如何解决它。

在 (name_id, name) 组合的数据帧上调用 Spark 的 MinHashLSH 的 approxSimilarityJoin 时，我遇到了问题。

我尝试解决的问题的摘要：

我有一个包含大约 3000 万个公司名称唯一（name_id、name）组合的数据框。其中一些名称指的是同一家公司，但 (i) 拼写错误，和/或 (ii) 包含其他名称。对每个组合执行模糊字符串匹配是不可能的。为了减少模糊字符串匹配组合的数量，我在 Spark 中使用 MinHashLSH。我的预期方法是使用具有相对较大 Jaccard 阈值的 approxSimilarityJoin（自连接），这样我就能够对匹配的组合运行模糊匹配算法，以进一步改善歧义消除。

我所采取的步骤摘要：

1. 使用 CountVectorizer 为每个名称创建字符计数向量，
2. 使用 MinHashLSH 及其 approxSimilarityJoin 并进行以下设置：
   • 哈希表数=100
   • 阈值=0.3（approxSimilarityJoin 的杰卡德阈值）
3. 在 approxSimilarityJoin 之后，我删除重复的组合（其中认为存在匹配的组合 (i,j) 和 (j,i)，然后删除 (j,i)）
4. 删除重复的组合后，我使用 FuzzyWuzzy 包运行模糊字符串匹配算法，以减少记录数量并提高名称的歧义性。
5. 最终，我在剩余的边 (i,j) 上运行连接组件算法，以匹配哪些公司名称属于一起。

使用的部分代码：

    id_col = 'id'
    name_col = 'name'
    num_hastables = 100
    max_jaccard = 0.3
    fuzzy_threshold = 90
    fuzzy_method = fuzz.token_set_ratio

    # Calculate edges using minhash practices
    edges = MinHashLSH(inputCol='vectorized_char_lst', outputCol='hashes', numHashTables=num_hastables).\
        fit(data).\ …