Clustering ~ 100 000 krótkich łańcuchów w języku Python

Chcę skupić ~ 100 000 krótkich łańcuchów przez coś w rodzaju odległości q-gramowej lub prostej "odległości między torebkami" lub może odległości Levenshteina w Pythonie. Planowałem wypełnić matrycę odległości (100 000 wybiera 2 porównania), a następnie hierarchicznie grupować z pyCluster. Ale napotykam na problemy z pamięcią, zanim jeszcze zejdę z ziemi. Na przykład matryca odległości jest za duża dla numpy.Clustering ~ 100 000 krótkich łańcuchów w języku Python

aa = numpy.zeros((100000, 100000)) 
ValueError: array is too big.

Czy wydaje się to rozsądną rzeczą do zrobienia? Czy jestem skazany na problemy z pamięcią w tym zadaniu? Dzięki za pomoc.

Źródło

2010-11-22 135498

10 miliardów to duża liczba. – nmichaels

Mam na myśli podejście do tego zabawnego problemu, ale tęsknię za niektórymi informacjami. Proszę szczegółowo opisać, co dokładnie próbujesz osiągnąć, a także dlaczego i możliwe założenia/ograniczenia. Oto 2 szczegółowe pytania. 1) Czy możesz replikować ciągi w swojej analizie? 2) Czy naprawdę potrzebujesz wszystkich dystansów 2 na 2 lub powiedzieć, że wystarczyłaby tylko część mniejszych odległości dla danego ciągu? Twoje zdrowie. – Morlock

100 000 * 100 000 * 32bity = 40 GB, które byłyby dużo partycji RAM, więc tak, musisz znaleźć inny sposób. (Nawet jeśli dane te można byłoby umieścić w pamięci, obliczenia zajmie zbyt dużo czasu.)

Jednym powszechnym i łatwym skrótem jest zgrupowanie małego losowego podzbioru danych, a po znalezieniu klastrów tego podzestawu, po prostu umieść pozostałe punkty w klastrach, w których najlepiej pasują.

Źródło

2010-11-22 02:35:31 tom10

Czy Twój komputer nie ma 4096 GB pamięci? –

Dzięki za obliczenia. Tak, obecne podejście wydaje się niemożliwe. – 135498

Przepraszam, po prostu czepiam się tutaj, dwa lata później: Ponieważ matryca odległości jest symetryczna, będzie to 20 GB. –

10 miliardów elementów to strasznie dużo. Nie wiem z q-gramów, ale jeśli ta matryca jest rzadka, można użyć dyktowania elementu 200,000-ish.

Źródło

2010-11-22 02:38:28 nmichaels

Przeczytałem o rzadkich matrycach.Niejasne, jeśli dane są skąpe, jak mówisz ... Będę musiał zrobić więcej testów. Również niejasne (dla mnie), czy pyCluster radzi sobie z rzadkimi matrycami. Dzięki za radę. – 135498

Co chcesz zrobić z danymi? Myślę, że to bardzo ważne pytanie. –

W zasadzie taka matryca nie byłaby rzadka. Jednym z problemów tworzenia tak rzadkiej macierzy jest ustalenie, czy jakiś element macierzy ma podlegać ocenie, czy nie. – cyborg

Czy potrzebujesz matrycy? Zakładam, że chcesz użyć matrycy do prędkości?

Mam algorytm k-średnich klastrów (zamiast hierarchicznego algorytmu klastra) i to oblicza odległości węzłów według potrzeb. Prawdopodobnie jest to jednak wykonalne tylko dla szybkich pomiarów odległości. I masz więcej danych niż ja - ale jesteś ograniczony ograniczeniami pamięci.

Źródło

2010-11-23 18:20:46 winwaed

Tak, coś takiego wydaje się być rozwiązaniem. Dzięki. – 135498

Jest to metoda uczenia maszynowego zwany do zatapiania, które można zasadniczo znaleźć rozwiązanie tego problemu przy użyciu O (n + m) pamięci zamiast O (N * M) (n = 10^5 pozycji, m = 10^5 funkcji). Niestety nie wiem o dostępnym kodzie źródłowym zaimplementowanym w O (m + n). Zobacz:

Osadzanie euklidesowej danych o współwystąpieniu. Amir Globerson, Gal Chechik, Fernando Pereira i Naftali Tishby. Journal of Machine Learning Research, JMLR, 8 (OCT), 2007. pdf/ Matlab code
Nie może być inne rozwiązania. Myślę, że powinieneś zadać to pytanie na forum osób uczących się na maszynie, np. https://stats.stackexchange.com/, lub nawet bardziej szczegółowo dla przetwarzania językowego: http://metaoptimize.com/qa/.

Źródło

2011-10-09 18:18:34 cyborg

Clustering ~ 100 000 krótkich łańcuchów w języku Python

Odpowiedz

Powiązane problemy