查找「補充」位矢量集羣

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。它是異或還是？也不可能將兩個以上的組合在一起，以及這樣做的成本是多少。一種策略是找到每個逆位矢量的最近鄰，並總是組合最好的對。