<p dir="auto">I'm trying to perform hierarchical clustering on sparse observation matrix. The matrix represents movie ratings for a number of users. However, running <code class="notranslate">linkage([ndarray], method='single')</code><br>
causes infinite recursion and <code class="notranslate">linkage([ndarray], method='single', metric='cosine')</code> crashes. <code class="notranslate">ward</code> works fine.</p>
<p dir="auto">Cheers.</p>
<h3 dir="auto">Reproducing code example:</h3>
<p dir="auto">Data source: <a href="https://www.librec.net/datasets/filmtrust.zip" rel="nofollow">https://www.librec.net/datasets/filmtrust.zip</a><br>
Data format (<code class="notranslate">ratings.dat</code>):</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="[...]
36 6 4
36 250 3.5
36 219 3.5
36 234 3
36 211 4
[...]"><pre class="notranslate"><code class="notranslate">[...]
36 6 4
36 250 3.5
36 219 3.5
36 234 3
36 211 4
[...]
</code></pre></div>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="import numpy as np

from scipy.sparse import dok_matrix
from scipy.cluster import hierarchy

def load_ratings(path):
    ratings = {}
    items = set([])

    with open(path, 'r') as data:
        for line in data.readlines():
            rating = [e for e in line.replace('\n', '').split(' ')]
            items.add(int(rating[1]))

            if not int(rating[0]) in ratings:
                ratings[int(rating[0])] = {}

            ratings[int(rating[0])][int(rating[1])] = float(rating[2])

    return (ratings, items)

ratings, items = load_ratings('ratings.txt')

R = dok_matrix((max(items) + 1, max(ratings) + 1), dtype=np.float32)

for user in ratings:
    for item in ratings[user]:
        R[item, user] = ratings[user][item]

R = R.transpose().toarray()
Z = hierarchy.linkage(R, method='single')

# This exceeds maximum recursion depth
hierarchy.dendrogram(Z)"><pre class="notranslate"><code class="notranslate">import numpy as np

from scipy.sparse import dok_matrix
from scipy.cluster import hierarchy

def load_ratings(path):
    ratings = {}
    items = set([])

    with open(path, 'r') as data:
        for line in data.readlines():
            rating = [e for e in line.replace('\n', '').split(' ')]
            items.add(int(rating[1]))

            if not int(rating[0]) in ratings:
                ratings[int(rating[0])] = {}

            ratings[int(rating[0])][int(rating[1])] = float(rating[2])

    return (ratings, items)

ratings, items = load_ratings('ratings.txt')

R = dok_matrix((max(items) + 1, max(ratings) + 1), dtype=np.float32)

for user in ratings:
    for item in ratings[user]:
        R[item, user] = ratings[user][item]

R = R.transpose().toarray()
Z = hierarchy.linkage(R, method='single')

# This exceeds maximum recursion depth
hierarchy.dendrogram(Z)
</code></pre></div>
<p dir="auto">Input matrix (<code class="notranslate">R</code>):</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="[[ 0.   0.   0.  ...,  0.   0.   0. ]
 [ 0.   2.   4.  ...,  0.   0.   0. ]
 [ 0.   0.   0.  ...,  0.   0.   0. ]
 ..., 
 [ 0.   0.   0.  ...,  0.   0.   0. ]
 [ 0.   0.   4.  ...,  0.   0.   0. ]
 [ 0.   1.5  3.  ...,  0.   0.   0. ]]"><pre class="notranslate"><code class="notranslate">[[ 0.   0.   0.  ...,  0.   0.   0. ]
 [ 0.   2.   4.  ...,  0.   0.   0. ]
 [ 0.   0.   0.  ...,  0.   0.   0. ]
 ..., 
 [ 0.   0.   0.  ...,  0.   0.   0. ]
 [ 0.   0.   4.  ...,  0.   0.   0. ]
 [ 0.   1.5  3.  ...,  0.   0.   0. ]]
</code></pre></div>
<h3 dir="auto">Error message 1</h3>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="[...]
651, in _dendrogram_calculate_info
    above_threshold_color=above_threshold_color)
  File &quot;/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py&quot;, line 2651, in _dendrogram_calculate_info
    above_threshold_color=above_threshold_color)
  File &quot;/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py&quot;, line 2651, in _dendrogram_calculate_info
    above_threshold_color=above_threshold_color)
  File &quot;/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py&quot;, line 2618, in _dendrogram_calculate_info
    above_threshold_color=above_threshold_color)
  File &quot;/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py&quot;, line 2530, in _dendrogram_calculate_info
    leaf_label_func, i, labels)
  File &quot;/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py&quot;, line 2403, in _append_singleton_leaf_node
    ivl.append(str(int(i)))
RecursionError: maximum recursion depth exceeded while getting the str of an object"><pre class="notranslate"><code class="notranslate">[...]
651, in _dendrogram_calculate_info
    above_threshold_color=above_threshold_color)
  File "/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py", line 2651, in _dendrogram_calculate_info
    above_threshold_color=above_threshold_color)
  File "/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py", line 2651, in _dendrogram_calculate_info
    above_threshold_color=above_threshold_color)
  File "/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py", line 2618, in _dendrogram_calculate_info
    above_threshold_color=above_threshold_color)
  File "/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py", line 2530, in _dendrogram_calculate_info
    leaf_label_func, i, labels)
  File "/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py", line 2403, in _append_singleton_leaf_node
    ivl.append(str(int(i)))
RecursionError: maximum recursion depth exceeded while getting the str of an object
</code></pre></div>
<h3 dir="auto">Error message 2 (with <code class="notranslate">metric='cosine'</code>)</h3>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="Traceback (most recent call last):
  File &quot;cosine_similarity.py&quot;, line 100, in &lt;module&gt;
    Z = hierarchy.linkage(R, metric='cosine')
  File &quot;/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py&quot;, line 676, in linkage
    raise ValueError(&quot;The condensed distance matrix must contain only finite values.&quot;)
ValueError: The condensed distance matrix must contain only finite values."><pre class="notranslate"><code class="notranslate">Traceback (most recent call last):
  File "cosine_similarity.py", line 100, in &lt;module&gt;
    Z = hierarchy.linkage(R, metric='cosine')
  File "/home/siegmeyer/.local/lib/python3.5/site-packages/scipy/cluster/hierarchy.py", line 676, in linkage
    raise ValueError("The condensed distance matrix must contain only finite values.")
ValueError: The condensed distance matrix must contain only finite values.
</code></pre></div>
<h3 dir="auto">Scipy/Numpy/Python version information:</h3>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="0.19.0 1.12.1 sys.version_info(major=3, minor=5, micro=2, releaselevel='final', serial=0)"><pre class="notranslate"><code class="notranslate">0.19.0 1.12.1 sys.version_info(major=3, minor=5, micro=2, releaselevel='final', serial=0)
</code></pre></div>
<p dir="auto"><em>Original ticket <a href="http://projects.scipy.org/scipy/ticket/612" rel="nofollow">http://projects.scipy.org/scipy/ticket/612</a> on 2008-02-26 by trac user rspringuel, assigned to <a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/users/cournape/hovercard" data-octo-click="hovercard-link-click" data-octo-dimensions="link_type:self" href="https://github.com/cournape">@cournape</a>.</em></p>
<p dir="auto">The current cluster package for scipy implements only k-means clustering for a euclidean distance metric with centroids computed as the mean of the members of each cluster.</p>
<p dir="auto">Pycluster implements 8 different distance metrics, three different centroid methods (mean, median, and medoid) and four different clustering algorithms (k-means, agglomerative hierarchical, SOM, and PCA) but contains non-BSD style license compatible elements and so cannot be incorporated into scipy.</p>
<p dir="auto">Using Pycluster as a model, I have written a clustering package from scratch that duplicates most of its functionality and expands on it in certain areas as well.</p>
<p dir="auto">I have also endevored to design the package to make future expansions easy and straight forward.</p>
<p dir="auto">To date what I have written supports the following:</p>
<p dir="auto">Distances:<br>
euclidean<br>
normalized euclidean<br>
city block (aka manhattan)<br>
normalized city block<br>
hamming (aka simple mapping coefficient)<br>
pearson<br>
absolute pearson<br>
uncentered pearson<br>
arccosine of pearson<br>
absolute uncentered pearson<br>
spearman<br>
kendall<br>
modified simple matching coefficent of Rogers and Tanimoto<br>
modified simple matching coefficent of Sokal and Sneath<br>
jaccard coefficent<br>
modified jaccard coefficent of Dice<br>
modified jaccard coefficent of Sokal and Sneath<br>
general Minkowski metric<br>
Chebychev distance</p>
<p dir="auto">Centroids:<br>
arithmetic mean<br>
median<br>
absolute mean<br>
geometric mean<br>
harmonic mean<br>
quadratic mean<br>
mediod (using any of the above distances)</p>
<p dir="auto">Clustering algorithms:<br>
k-means<br>
c-means (fuzzy clustering)<br>
agglomerative hierarchical</p>
<p dir="auto">Additional distances, centroid methods, and clustering algorithms may be added as my work requires them.</p>
<p dir="auto">Since I have written all of this code from scratch, I control the license to it and have elected to release it under a BSD-style license so that it can be incorporated into scipy.</p>
<p dir="auto">What I have written obviously greatly expands on the functionality of the current cluster package, but it is written entirely in python as so may be slower than what is currently present where the functionality overlaps (hence the quotation marks around "better" in the title of this ticket).</p>
<p dir="auto">Note: All of the centroid methods are based on my statistical functions submitted in ticket <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="13649624" data-permission-text="Title is private" data-url="https://github.com/scipy/scipy/issues/1131" data-hovercard-type="issue" data-hovercard-url="/scipy/scipy/issues/1131/hovercard" href="https://github.com/scipy/scipy/issues/1131">gh-1131</a> and so the code would have to be revised should those stats functions not be incorporated into scipy.</p>