Finden Sie "komplementiert" Bit Vektoren Cluster

Question

Ich habe eine riesige Liste von Bit Vektoren (BV), die ich in Clustern gruppieren möchte.

Die Idee hinter diesen Clustern ist, in der Lage zu sein, später BVs von jedem Cluster zu wählen und sie zu kombinieren, um eine BV mit (fast) allen Einsen zu erzeugen (die maximiert werden müssen).

Stellen Sie sich zum Beispiel vor, die 1 bedeutet, dass eine App Up ist und 0 zu einem bestimmten Zeitpunkt in Knoten X unten ist. Wir wollen mit der App, die min Liste der Knoten finden Up:

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 

ich die verschiedenen Cluster-Algorithmen überprüft worden, aber ich habe eine gefunden, dass jede Spalte, weil in diesem Fall dieses „komplementäres“ Verhalten berücksichtigt der BV wird nicht auf ein Merkmal bezogen (bedeutet nur oben oder unten in einem bestimmten Zeitraum).

In Bezug auf andere Algorithmen wie K-Means oder hierarchische Clustering, ich habe nicht klar, ob ich diese Berücksichtigung für die spätere Gruppierung in den Clustering-Algorithmus aufnehmen kann.

Schließlich verwende ich die Hamming-Distanz, um die Intra-Cluster und die Inter-Cluster-Abstände zu bestimmen, da es scheint, die am besten geeignete Metrik für binäre Daten zu sein, aber die Ergebnisse zeigen mir, dass Cluster nicht eng gruppiert und getrennt sind Ich frage mich also, ob ich die am besten geeignete Gruppen/Approximationsmethode anwende oder ob ich die Eingabedaten vorher gruppieren soll.

Jeder Hinweis oder Idee in Bezug auf Gruppierung/Clustering-Methode oder Filtern von Daten wird begrüßt.

Answer 1

Dies klingt überhaupt nicht wie ein Clustering-Problem.

Keiner dieser Algorithmen wird Ihnen helfen.

Stattdessen würde ich dies lieber einen Matchmaking-Algorithmus nennen. Aber ich würde annehmen, dass es zumindest NP-hart ist (es ähnelt dem Set-Cover), um das wahre Optimum zu finden, also musst du eine schnelle Annäherung machen. Das Beste, was für Ihren Anwendungsfall spezifisch ist.

Auch Sie haben nicht angegeben (Sie schrieb + aber das ist wahrscheinlich nicht das, was Sie wollen), wie zwei 1s zu kombinieren. Ist es xor oder oder? Auch wenn es möglich ist, mehr als zwei zu kombinieren, und was kostet das? Eine Strategie wäre, den nächsten Nachbarn des inversen Bitvektors für jeden zu finden und immer das beste Paar zu kombinieren.