計算scipy中成對距離時的內存錯誤

我正在嘗試將層次聚類應用於由14039個用戶組成的數據集。每個矢量具有10個特徵，其中每個特徵基本上是由該用戶標記的標籤的頻率。我使用Scipy API進行聚類。現在我需要計算這14039個用戶之間的成對距離，並將距離矩陣傳遞給聯動函數。計算scipy中成對距離時的內存錯誤

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用戶不應該太多，它應該導致內存錯誤。我在i3和4 Gb Ram上運行它。我也需要應用DBScan集羣，但也需要距離矩陣作爲輸入。

任何建議表示讚賞。

編輯：只有當我打印Y時纔會出錯。任何想法爲什麼？

來源

2012-04-11 Maxwell

好吧，層次聚類對於大型數據集並沒有多大意義。在我看來，它實際上大多是一本教科書的例子。層次聚類的問題是它並不真正構建明智的聚類。它構建樹狀圖，但有14000個樹狀圖變得幾乎不可用。很少有層次聚類的實現方法從樹形圖中提取可感知的聚類有不平凡的方法。另外，在一般情況下，層次聚類的複雜性爲O(n^3)，這使得它對於大型數據集來說真的很糟糕。

DBSCAN在技術上確實是而不是需要一個距離矩陣。實際上，當你使用距離矩陣時，將會是slow，因爲計算距離矩陣已經是O(n^2)。即使如此，您仍然可以通過計算動態距離來計算DBSCAN的內存開銷，代價是每次計算兩次距離。 DBSCAN每訪問一次，所以除了對稱增益之外，使用距離矩陣幾乎沒有任何好處。從技術上講，你可以做一些簡潔的緩存技巧，甚至可以減少這種技巧，因爲DBSCAN也只需要知道哪些對象低於epsilon閾值。當合理選擇epsilon時，在計算距離矩陣的相同CPU成本下，即時管理鄰居組將使用比O(n^2)少得多的內存。但是應該支持索引結構，然後運行在O(n log n)運行環境中.DBSCAN的任何一個非常好的實現（它是拼寫全部大寫，順便說一句，因爲它是一個縮寫，而不是掃描）。

在http://elki.dbs.ifi.lmu.de/wiki/Benchmarking上，他們在110250對象數據集和8維上運行DBSCAN，非索引變量需要1446秒，索引只有219，這比索引編譯快了大約7倍。（然而，這不是python）類似地，OPTICS的索引速度是它的5倍。他們在我的實驗中的kmeans實現比WEKA kmeans快6倍，並且使用的內存少得多。他們的單鏈接層次聚類也是一個優化的實現。其實我目前看到的唯一一個並不是天真的O(n^3)矩陣編輯方法。如果你願意超越python，那可能是一個不錯的選擇。

來源

2012-04-12 05:34:53

這可能是你真的用完了RAM。找出N個對象之間的成對距離意味着存儲N^2個距離。在你的情況下，N^2將會是14039^2 = 1.97 * 10^8。如果我們假設每個距離只需要4個字節（這幾乎肯定不是這種情況，因爲它們必須保存在某種可能具有非恆定開銷的數據結構中），這可以達到800兆字節。對於口譯員來說，這是很多記憶。 32位體系結構只允許高達2 GB的進程內存，而您的原始數據佔用了大約50％。隨着數據結構的開銷，你可能會看到比這更高的用法 - 我不能說多少，因爲我不知道SciPy/numpy背後的內存模型。

我會嘗試打破你的數據集成更小的集合，或不構建全距離矩陣。你可以把它分解成更易於管理的塊（比如說，包含大約1000個元素的14個子集），並且在每個塊和所有向量之間做最近鄰居 - 然後你可以在任何時候將內存加載到內存中一次（14000 * 1000,14次而不是14000 * 14000次）。

編輯： agf在這兩方面都是完全正確的：我錯過了你的編輯，當它試圖構建代表矩陣的巨型字符串時，問題可能就出現了。如果它正在打印浮點值，並且我們假設每個元素打印了10個字符，並且每個字符存儲了一個字節的字符串，那麼您僅僅爲字符串查找了2 GB的內存使用情況。

來源

2012-04-11 23:55:01

我想你錯過了他的編輯。只有在嘗試打印整個距離矩陣時纔會出錯。它正在構建耗盡他的記憶的巨大絃樂。 – agf 2012-04-12 00:09:24

我做到了。答案更新以反映編輯。謝謝！ – 2012-04-12 04:38:08

預先編輯的答案對於相關問題確實很有幫助。請保留這個答案，以便我可以將其他問題鏈接到它。 – ximiki 2018-01-23 16:36:29

計算scipy中成對距離時的內存錯誤

回答

相關問題