ruby - 具有自定义距离的一维字符串聚类 - ruby

Question

我有一系列字符串，它们是来自多个商店的产品名称。现在，无论列出的商店如何，我都需要对该数组进行集群以获得包含相同产品的集群。

例如：

data = ["Laptop Asus xd45jkl", 
        "Laptop Acer d3000",
        "Notebooh Hp hxsss", 
        "Laptop Asus xd45jkl intel core i7", 
        "Laptop Acer d3000 intel core i5 4gb RAM"
]
desired_output = [["Laptop Asus xd45jkl", Laptop Asus xd45jkl intel core i7],
          ["Laptop Acer d3000", "Laptop Acer d3000 intel core i5 4gb RAM"]
          [""Notebooh Hp hxsss""]
         ]

作为产品名称之间的距离，我认为 JaroWinkler 从amatch gem。有没有类似 k-means 的算法或其他算法可以产生这个字符串数组的聚类？

Answer 1

我想到了这样的事情：

data = ["Laptop Asus xd45jkl", "Laptop Acer d3000", "Notebooh Hp hxsss", "Laptop Asus xd45jkl intel core i7", "Laptop Acer d3000 intel core i5 4gb RAM" ]
clusters = Hash.new

data.each do |item|
    brand =  item.split[1]
    clusters[brand] = [] if clusters[brand].nil?
    clusters[brand] << item
end

clusters.map! { |k, v| v }

我不确定这是否符合 k-means以及它在大型数据集上的性能。

编辑： 50,000 个项目大约需要 2 秒。