Trouver des vecteurs binaires "complémentés" clusters

Question

J'ai une énorme liste de vecteurs binaires (BV) que je veux regrouper en grappes.

L'idée derrière ces clusters est de pouvoir choisir plus tard les BV de chaque cluster et de les combiner pour générer un BV avec (presque) tout-un (qui doit être maximisé). Par exemple, imaginez que le 1 signifie qu'une application est Up et 0 est en panne dans le nœud X à un moment donné. Nous voulons trouver la liste min des noeuds pour avoir l'application 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 

J'ai vérifiais les différents algorithmes de cluster, mais je ne avons trouvé un qui prend en compte ce comportement « complémentaire » parce que dans ce cas, chaque colonne de la BV n'est pas référée à une caractéristique (ne signifie que vers le haut ou vers le bas dans un laps de temps spécifique). En ce qui concerne d'autres algorithmes comme les k-means ou le clustering hiérarchique, je ne sais pas si je peux inclure dans l'algorithme de clustering cette considération pour le regroupement ultérieur. Enfin, j'utilise la distance de Hamming pour déterminer les distances intra-cluster et inter-cluster étant donné que cela semble être la métrique la plus appropriée pour les données binaires mais les résultats montrent que les clusters ne sont pas étroitement groupés et séparés entre eux donc je me demande si j'applique la méthode de groupe/approximation la plus appropriée ou même si je devrais filtrer les données d'entrée regroupant précédemment. Tout indice ou idée concernant la méthode de regroupement/regroupement ou les données de filtrage est le bienvenu.

Answer 1

Cela ne ressemble en rien à un problème de clustering.

Aucun de ces algorithmes ne vous aidera. Au lieu de cela, je préfère appeler cela un algorithme de création de correspondance. Mais je suppose qu'il est au moins NP-difficile (il ressemble à la couverture de jeu) pour trouver l'optimum réel, de sorte que vous aurez besoin de venir avec une approximation rapide. Meilleur quelque chose de spécifique à votre cas d'utilisation.

Aussi vous n'avez pas spécifié (vous avez écrit + mais ce n'est probablement pas ce que vous voulez) comment combiner deux 1s. Est-ce xor ou or? Ni s'il est possible d'en combiner plus de deux, et quel en est le coût. Une stratégie consisterait à trouver le plus proche voisin du bitvector inverse pour chacun et à toujours combiner la meilleure paire.