scipy에서 pairwise distance를 계산할 때 메모리 오류가 발생합니다.

Question

14039 명의 사용자 벡터로 구성된 내 데이터 집합에 계층 적 클러스터링을 적용하려고합니다. 각 벡터에는 10 개의 기능이 있습니다. 각 기능은 기본적으로 해당 사용자가 태그 한 태그의 빈도입니다. 클러스터링을 위해 Scipy API를 사용하고 있습니다. 이제이 14039 명의 사용자 사이의 쌍 거리를 계산하고 링크 매트릭스 함수에 거리 매트릭스를 전달해야합니다.

import scipy.cluster.hierarchy as sch 
    Y = sch.distance.pdist(allUserVector,'cosine') 
    set_printoptions(threshold='nan') 
    print Y 

하지만 내 프로그램은 나를 MemoryError의 거리 매트릭스를

File "/usr/lib/pymodules/python2.7/numpy/core/numeric.py", line 1424, in array_str 
    return array2string(a, max_line_width, precision, suppress_small, ' ', "", str) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 306, in array2string 
    separator, prefix) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 210, in _array2string 
    format_function = FloatFormat(data, precision, suppress_small) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 392, in __init__ 
    self.fillFormat(data) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 399, in fillFormat 
    non_zero = absolute(data.compress(not_equal(data, 0) & ~special)) 
MemoryError 

어떤 생각을 계산하면서 어떻게이 문제를 해결하는 준다? 내 데이터 세트가 너무 큽니까? 하지만 클러스터링 14k 사용자가 너무 많은 메모리 오류가 발생합니다 shouldnt 같아요. i3 및 4GB 램에서 실행 중입니다. DBScan 클러스터링도 적용해야하지만 거리 매트릭스도 입력해야합니다.

의견을 보내 주시면 감사하겠습니다.

편집 : Y를 인쇄 할 때만 오류가 발생합니다. 왜 그런가?

Answer 1

글쎄, 계층 적 클러스터링은 큰 데이터 세트에 대해서는별로 의미가 없습니다. 그것은 실제로 제 의견으로는 대부분 교과서 예제입니다. 계층 적 클러스터링의 문제점은 실제로 합리적인 클러스터를 구축하지 않는다는 것입니다. 그것은 dendrogram을 만들지 만, 14000 개의 객체로 dendrogram은 꽤 쓸모 없게됩니다. 그리고 계층 적 클러스터링의 구현은 매우 드물지만, 멍멍 모양에서 감각적 인 클러스터를 추출하는 방법은 거의 없습니다. 또한 일반적으로 계층 적 클러스터링은 복잡하므로 크기가 큰 데이터 집합의 경우 실제적으로 확장이 어려워집니다 (O(n^3)).

기술적으로는 이 아닙니다.에는 거리 매트릭스가 필요합니다. 사실, 거리 매트릭스를 사용하면 이 될 것입니다. 거리 매트릭스 계산은 이미 O(n^2)입니다.그 다음에도 DBSCAN에 대한 메모리 비용은 O(n^2)으로 안전 할 수 있습니다. 거리를 계산할 때마다 거리를 두 번 계산하면됩니다. DBSCAN은 각 포인트를 한 번 방문하기 때문에 대칭성 이득을 제외하고는 거리 매트릭스를 사용하면 아무런 이점이 없습니다. 그리고 기술적으로 DBSCAN은 어떤 오브젝트가 엡실론 임계 값 아래인지 알아야하기 때문에 캐싱 트릭을 사용하여이를 줄일 수도 있습니다. 엡실론을 합리적으로 선택하면 이웃 집합을 즉시 관리하는 것이 거리 매트릭스 계산과 동일한 CPU 비용으로 O(n^2)보다 훨씬 적은 메모리를 사용하게됩니다.

실제로 DBSCAN (모든 대문자, btw은 약어가 아니기 때문에 철자가 맞지 않음) 구현은 인덱스 구조를 지원해야하며 O(n log n) 런타임에서 실행되어야합니다.

http://elki.dbs.ifi.lmu.de/wiki/Benchmarking에 대해서는 110250 개체 데이터 집합 및 8 차원에서 DBSCAN을 실행하며 인덱스가없는 변형은 인덱스가 219 인 인덱스가 1446 초입니다. 인덱스 구축을 포함하여 약 7 배 빠릅니다. (그러나 그것은 파이썬이 아닙니다.) 마찬가지로, OPTICS는 인덱스로 5 배 더 빠릅니다. 그리고 실험에서의 kmeans 구현은 WEKA kmeans보다 약 6 배 빠르고 메모리 사용량이 훨씬 적습니다. 단일 링크 계층 적 클러스터링은 최적화 된 O(n^2) 구현입니다. 실제로 지금까지 본 적이있는 유일한 것은 매트릭스 편집 방식 인 순진한 O(n^3)이 아닙니다. 파이썬을 뛰어 넘으면 좋은 선택 일 수 있습니다.

Answer 2

실제로 RAM이 부족할 수도 있습니다. N 객체 사이의 쌍 방향 거리를 찾는 것은 N^2 거리를 저장하는 것을 의미합니다. 귀하의 경우, N^2는 14039^2 = 1.97 * 10^8이 될 것입니다. 각 거리가 단지 4 바이트 만 취한다고 가정하면 (800MB까지 움직일 수있는 일종의 데이터 구조로 유지되어야하므로 거의 확실하지 않습니다). 통역사가 함께 일할 수있는 많은 기억이 있습니다. 32 비트 아키텍처는 최대 2GB의 프로세스 메모리 만 허용하며 원시 데이터는 그 중 약 50 %를 차지합니다. 데이터 구조의 오버 헤드로 인해 그보다 훨씬 높은 사용법을 볼 수 있습니다. SciPy/numpy 뒤에있는 메모리 모델을 모르기 때문에 얼마만큼 말할 수는 없습니다.

데이터 세트를 더 작은 세트로 분해하거나 전체 거리 매트릭스를 구성하지 않겠습니다. 보다 관리하기 쉬운 덩어리 (약 1000 개의 요소로 구성된 14 개의 하위 집합)로 나누고 각 덩어리와 모든 벡터 사이에 가장 가까운 이웃을 수행 할 수 있습니다. 한 번 (14000 * 1000, 14000 * 14000 대신 14 번).

편집 : AGF는 모두 계산에 완전히 맞다 : 당신의 편집을 놓친하고, 문제는 아마 당신의 행렬을 나타냅니다 거대한 문자열을 구축하려고 할 때에 대해 제공됩니다. 부동 소수점 값을 인쇄하고 요소 당 10자를 인쇄하고 문자열이 문자 당 1 바이트로 저장된다고 가정하면 문자열에 대해 정확히 2GB의 메모리 사용량을 볼 수 있습니다.