J'ai 2 000 000 points dans un espace de 100 dimensions. Comment puis-je les regrouper en K (par exemple, 1000) clusters?

Le problème est le suivant. J'ai M images et extrait N caractéristiques pour chaque image, et la dimensionnalité de chaque fonctionnalité est L. Ainsi, j'ai M * N caractéristiques (2.000.000 pour mon cas) et chaque fonctionnalité a L dimensionnalité (100 pour mon cas). J'ai besoin de regrouper ces caractéristiques M * N en K groupes. Comment puis-je le faire? Merci.J'ai 2 000 000 points dans un espace de 100 dimensions. Comment puis-je les regrouper en K (par exemple, 1000) clusters?

Source

2010-11-11 Jie

Souhaitez-vous 1000 clusters d'images, de fonctionnalités ou de paires (image, fonctionnalité)?
Dans tous les cas, il semble que vous deviez réduire les données et utiliser des méthodes plus simples.

Une possibilité est à deux passes K-cluster:
a) divisé les 2 millions de points de données en 32 groupes,
b) diviser chacune de celles-ci en 32 plus.
Si cela fonctionne, les clusters résultants 32^2 = 1024 pourraient être assez bon pour votre but.

Ensuite, avez-vous vraiment besoin de 100 coordonnées? Pourriez-vous deviner les 20 plus importants, ou juste essayer des sous-ensembles aléatoires de 20?

Il y a une énorme littérature: Google +image "dimension reduction" donne ~ 70000 hits.

Source

2010-11-30 14:56:10 denis

merci pour votre suggestion. Je l'ai juste fait comme vous l'avez suggéré en K-cluster à deux passages. La performance est très bonne. – Jie

Bonne; à peu près combien de temps at-il couru? (Et que diriez-vous de cliquer sur "accepter"?) – denis

Il m'a fallu environ 8 heures. – Jie

Vous avez tagué la question "k-means". Pourquoi ne pouvez-vous pas utiliser k-means? Est-ce une question d'efficacité? (Personnellement, j'ai seulement utilisé k-means en 2 dimensions) Ou est-ce une question de comment encoder l'algorithme k-means?

Vos valeurs sont-elles discrètes (par exemple, catégories) ou continues (par exemple, une valeur de coordonnées)? Si ce dernier, alors k-means devrait être bien dans ma compréhension. Pour le regroupement de valeurs discrètes, un algorithme différent sera nécessaire - peut-être un regroupement hiérarchique?

Source

2010-11-11 13:59:13 winwaed

Merci pour winwaed. Je manque souvent de mémoire si j'ai utilisé "k-means". Il m'est même pas possible de charger les données en mémoire (les fonctionnalités du fichier texte sont d'environ 1.5G). Mon PC est avec 2G RAM. J'ai utilisé matlab pour cette tâche. Quand j'ai chargé 37.5% des données de fonctionnalité, matlab m'a dit que j'avais de la mémoire. – Jie

Il s'agit donc d'un problème de taille/d'efficacité. Est-il possible de partitionner vos données en trois ou quatre partitions qui peuvent être traitées en blocs séparés? – winwaed

Oui, il est possible de partitionner les données en plusieurs partitions. Je les ai divisés en 20 partitions parce que la matrice de distance coûterait beaucoup de mémoire. Un autre problème est de savoir comment combiner efficacement les clusters de ces 20 partitions? Il n'est également pas clair combien cette méthode de partition affecterait les performances de la mise en cluster. – Jie

Les algorithmes EM-tree et K-tree dans le projet LMW-tree peuvent entraîner des problèmes de cluster aussi importants. Notre résultat le plus récent est de regrouper 733 millions de pages Web en 600 000 grappes. Il existe également une variante de streaming de l'arborescence EM où l'ensemble de données est diffusé à partir du disque pour chaque itération.

Source

2015-05-17 05:15:11

J'ai 2 000 000 points dans un espace de 100 dimensions. Comment puis-je les regrouper en K (par exemple, 1000) clusters?

Répondre

Questions connexes