查找“补充”位矢量集群

Question

我有一个庞大的位矢量（BV）列表，我想要在集群中组合。

这个集群背后的想法是能够从每个集群中选择较晚的BVs，并将它们组合以生成BV（几乎）全部（必须最大化）的BV。

例如，想象1表示应用程序已启动，0在特定时刻在节点X中关闭。我们想找到节点的分列表具有应用最多：

App BV for node X in cluster 1: 1 0 0 1 0 0 

    App BV for node Y in cluster 2: 0 1 1 0 1 0 

    Combined BV for App (X+Y):  1 1 1 1 1 0 

我一直在检查不同的簇算法，但我没有发现，因为在这种情况下，每列一个，考虑到这种“互补”的行为的BV没有被称为一个特征（仅仅意味着在一个特定的时间范围内向上或向下）。

关于其他算法，如k均值或层次聚类，我没有清楚我是否可以在聚类算法中包含这种考虑以用于以后的分组。

最后，我使用海明距离来确定簇内和簇间距离，因为它似乎是二进制数据中最适合的度量标准，但结果表明，簇之间没有紧密分组并且分离他们所以我想知道我是否应用了最适合的组/近似方法，或者即使我应该过滤先前分组的输入数据。

欢迎关于分组/聚类方法或筛选数据的任何线索或想法。

Answer 1

这听起来并不像聚类问题。

这些算法都不会对您有所帮助。

相反，我宁愿将它称为匹配制作算法。但是我认为它至少是NP-hard（它类似于封面）以找到真正的最佳值，所以你需要提出一个快速的近似值。最适合您的用例的东西。

另外你还没有指定（你写的+，但可能不是你想要的）如何结合两个1。它是异或还是？也不可能将两个以上的组合在一起，以及这样做的成本是多少。一种策略是找到每个逆位矢量的最近邻，并总是组合最好的对。