Cluster les Big Data dans R et l'échantillonnage est-il pertinent?

13

Je suis nouveau dans la science des données et j'ai du mal à trouver des clusters dans un ensemble de données avec 200 000 lignes et 50 colonnes en R.

Étant donné que les données ont des variables numériques et nominales, des méthodes comme K-means qui utilise la mesure de distance euclidienne ne semblent pas être un choix approprié. Je me tourne donc vers PAM, agnes et hclust qui accepte une matrice de distance en entrée.

La méthode de marguerite peut fonctionner sur des données de type mixte mais la matrice de distance est tout simplement trop grande: 200 000 fois 200 000 est beaucoup plus grande que 2 ^ 31-1 (la limite de longueur de vecteur avant R 3.0.0.)

Le nouveau R 3.0.0 publié hier prend en charge les vecteurs longs avec une longueur supérieure à 2 ^ 31-1. Mais une double matrice de 200 000 par 200 000 nécessite une RAM continue supérieure à 16 Go, ce qui n'est pas possible sur ma machine.

J'ai lu des informations sur le calcul parallèle et le package bigmemory et je ne sais pas s'ils vont aider: si j'utilise daisy, cela générera une grande matrice qui ne peut de toute façon pas tenir en mémoire.

J'ai également lu un article sur l'échantillonnage: l'échantillonnage est-il pertinent à l'époque des «mégadonnées»?

Donc, dans mon cas, est-il pertinent d'utiliser l'échantillonnage sur l'ensemble de données, de regrouper l'échantillon et de déduire ensuite la structure de l'ensemble de données?

Pouvez-vous me donner quelques suggestions? Je vous remercie!

À propos de ma machine:

R version 3.0.0 (2013-04-03)

Plate-forme: x86_64-w64-mingw32 / x64 (64 bits)

Système d'exploitation: Windows 7 64 bits

RAM: 16,0 Go

r clustering sampling large-data Communauté
la source
La seule méthode de clustering que je connaisse qui concerne les mégadonnées (par exemple des millions de cas) et qui peut accepter des variables nominales avec des variables numériques est le cluster TwoStep trouvé dans SPSS.
ttnphns

Réponses:

4

O(n3)O(n2)

PAM lui-même ne devrait pas nécessiter une matrice de distances complète, mais l'algorithme est connu pour évoluer mal, car il doit ensuite (rec) calculer toutes les distances par paires au sein de chaque cluster à chaque itération pour trouver les éléments les plus centraux. C'est beaucoup moins si vous avez un grand nombre de clusters, mais néanmoins assez cher!

O(nlogn)

Cependant, pour la plupart de ces algorithmes, vous devez d'abord vous assurer que votre fonction de distance est vraiment bonne; vous devez ensuite envisager des moyens d'accélérer les requêtes en utilisant des index appropriés.

Notez également que dans de nombreux cas - et cela peut très bien s'appliquer à PAM - vous pouvez d'abord exécuter l'algorithme sur un échantillon , puis l'affiner uniquement sur l'ensemble de données complet. Si votre échantillon est représentatif, des algorithmes tels que k-means et PAM devraient vous donner essentiellement le même résultat que sur l'ensemble de données complet.

A QUIT - Anony-Mousse
la source
N'aidera pas l'OP ici, mais au cas où quelqu'un d'autre viendrait avec des numéros d'échantillons "intermédiaires": il y a aussi fastcluster pour R (voir math.stanford.edu/~muellner/fastcluster.html ).
cbeleites prend en charge Monica le
Salut Anony-Mousse, pourriez-vous s'il vous plaît me pointer vers certains des algorithmes qui utilisent l'accélération de la structure d'index? Merci beaucoup!
Par exemple, DBSCAN peut être bien accéléré avec des index qui prennent en charge les requêtes de plage epsilon. Cela signifie probablement aussi un regroupement de postes. L'OPTIQUE, qui peut également être accélérée de cette façon, peut être considérée comme une version plus avancée du clustering de liens (vous pouvez l'appeler "clustering de liens de densité hiérarchique")
Has QUIT - Anony-Mousse
2

essayez la fonction CLARA du package de cluster dans R. Elle implémente un algorithme de type pam en sous-échantillonnant vos données (assurez-vous de fournir des tailles de sous-échantillon qui ont du sens pour vos données car les valeurs par défaut sont délibérément trop petites). Cela fonctionne particulièrement bien si les périodes intermédiaires de vos données peuvent être représentées par un petit échantillon du total des données (c'est-à-dire qu'il y a relativement moins de grappes dans l'ensemble de données). De cette façon, vous pouvez regrouper efficacement avec un petit échantillon aléatoire et ajouter des points à la solution de regroupement précalculée.

http://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/CLARA

zzk
la source
salut zzk, merci pour la réponse. J'ai lu sur clara avant mais il semble qu'il ne fournisse que des métriques euclidiennes et manhattan. Le principal problème est que mon ensemble de données comporte des variables numériques et nominales. Il n'est donc pas approprié d'utiliser ni métrique pour la mesure de distance.
ah oui, c'est aussi une limitation pour moi actuellement. Je crois que la méthode peut être effectuée sur n'importe quelle distance arbitraire, mais je n'ai pas encore pris la peine de parcourir le code source pour voir s'il peut être modifié.
zzk
0

Vous pouvez également appliquer une analyse de correspondance multiple sur vos variables qualitatives et effectuer des transformations en une variable numérique.

Alvaro
la source
2
Cela semble être une bonne idée, mais cela peut être un peu rare. Pouvez-vous étoffer cela un peu pour expliquer ce que c'est et pourquoi cela aiderait?
gung - Rétablir Monica