{"action":"created","comment":{"url":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/comments/26735776","id":26735776,"diff_hunk":"@@ -0,0 +1,452 @@\n+## hclust.jl (c) 2014 David A. van Leeuwen \n+## Hierarchical clustering, similar to R's hclust()\n+\n+## Algorithms are based upon C. F. Olson, Parallel Computing 21 (1995) 1313--1325. \n+\n+## This seems to work like R's implementation, but it is extremely inefficient\n+## This probably scales O(n^3) or worse. We can use it to check correctness\n+\n+## This is also in types.jl, but that is not read...\n+## Mostly following R's hclust class\n+type Hclust{T<:Real}\n+    merge::Matrix{Int}\n+    height::Vector{T}\n+    order::Vector{Int}\n+    labels::Vector\n+    method::Symbol\n+end\n+\n+function hclust_n3{T<:Real}(d::Matrix{T}, method::Function)\n+    @assert size(d,1) == size(d,2)\n+    if !issym(d)\n+        d += d'                 # replaces d, which must be symmetric\n+    end\n+    mr = Int[]                  # min row\n+    mc = Int[]                  # min col\n+    h = T[]                     # height\n+    nc = size(d,1)              # number of clusters\n+    cl = -[1:nc]                # segment to cluster attribution, initially negative\n+    next = 1                    # next cluster label\n+    while next < nc \n+        min = Inf\n+        mi = mj = 0\n+        cli = unique(cl)\n+        mask = BitVector(nc)\n+        for j in 1:length(cli)           # loop over for lower triangular indices, i>j\n+            cols = cl .== cli[j]\n+            for i in (j+1):length(cli)\n+                rows = cl.==cli[i]\n+                distance = method(d[rows,cols])\n+                if distance < min\n+                    min = distance\n+                    mi = cli[i]\n+                    mj = cli[j]\n+                    mask = cols | rows\n+                end\n+            end\n+        end \n+        ## simulate R's order\n+        if mi < 0 && mj < 0 && mi > mj ||\n+            mi > 0 && mj > 0 && mi < mj ||\n+            mi < 0 && mj > 0\n+            push!(mr, mi)\n+            push!(mc, mj)\n+        else\n+            push!(mr, mj)\n+            push!(mc, mi)\n+        end\n+        push!(h, min)\n+        cl[mask] = next\n+        next += 1\n+    end\n+    hcat(mr, mc), h\n+end\n+\n+## Efficient single link algorithm, according to Olson, O(n^2), fig 2. \n+## Verified against R's implementation, correct, and about 2.5 x faster\n+## For each i < j compute D(i,j) (this is already given)\n+## For each 0 < i <= n compute Nearest Neighbor N(i)\n+## Repeat n-1 times\n+##   find i,j that minimize D(i,j)\n+##   merge clusters i and j\n+##   update D(i,j) and N(i) accordingly\n+function hclust_minimum{T<:Real}(d::Matrix{T})\n+    @assert size(d,1) == size(d,2)\n+    ## For each i < j compute d[i,j] (this is already given) --- we need a local copy\n+    if !issym(d)","path":"src/hclust.jl","position":76,"original_position":76,"commit_id":"cb802d8aef56e4590dd1c02c6a62efc447174c45","original_commit_id":"cb802d8aef56e4590dd1c02c6a62efc447174c45","user":{"login":"davidavdav","id":5497303,"avatar_url":"https://avatars.githubusercontent.com/u/5497303?v=3","gravatar_id":"","url":"https://api.github.com/users/davidavdav","html_url":"https://github.com/davidavdav","followers_url":"https://api.github.com/users/davidavdav/followers","following_url":"https://api.github.com/users/davidavdav/following{/other_user}","gists_url":"https://api.github.com/users/davidavdav/gists{/gist_id}","starred_url":"https://api.github.com/users/davidavdav/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davidavdav/subscriptions","organizations_url":"https://api.github.com/users/davidavdav/orgs","repos_url":"https://api.github.com/users/davidavdav/repos","events_url":"https://api.github.com/users/davidavdav/events{/privacy}","received_events_url":"https://api.github.com/users/davidavdav/received_events","type":"User","site_admin":false},"body":"I am not too happy with issym() myself as it takes some time.  ","created_at":"2015-03-19T08:26:53Z","updated_at":"2015-03-19T08:26:53Z","html_url":"https://github.com/JuliaStats/Clustering.jl/pull/32#discussion_r26735776","pull_request_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/32","_links":{"self":{"href":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/comments/26735776"},"html":{"href":"https://github.com/JuliaStats/Clustering.jl/pull/32#discussion_r26735776"},"pull_request":{"href":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/32"}}},"pull_request":{"url":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/32","id":22604728,"html_url":"https://github.com/JuliaStats/Clustering.jl/pull/32","diff_url":"https://github.com/JuliaStats/Clustering.jl/pull/32.diff","patch_url":"https://github.com/JuliaStats/Clustering.jl/pull/32.patch","issue_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/32","number":32,"state":"open","locked":false,"title":"Inclusion of Hclust into Clustering.jl","user":{"login":"davidavdav","id":5497303,"avatar_url":"https://avatars.githubusercontent.com/u/5497303?v=3","gravatar_id":"","url":"https://api.github.com/users/davidavdav","html_url":"https://github.com/davidavdav","followers_url":"https://api.github.com/users/davidavdav/followers","following_url":"https://api.github.com/users/davidavdav/following{/other_user}","gists_url":"https://api.github.com/users/davidavdav/gists{/gist_id}","starred_url":"https://api.github.com/users/davidavdav/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davidavdav/subscriptions","organizations_url":"https://api.github.com/users/davidavdav/orgs","repos_url":"https://api.github.com/users/davidavdav/repos","events_url":"https://api.github.com/users/davidavdav/events{/privacy}","received_events_url":"https://api.github.com/users/davidavdav/received_events","type":"User","site_admin":false},"body":"Hi, \r\n\r\nFollowing the suggestions from the METATDATA maintainers, I made a patch for Clustering to absorb the package Hclust (Hierarchical clustering along the lines of R's hclust() and cutree()), sice this is also does a form of clustering.  This keeps the number of packages down.  \r\n\r\nI did not further integrate the code, it seems to be reasonably independent of the existing code in Clustering. \r\n\r\n---david\r\n\r\n","created_at":"2014-10-11T15:17:41Z","updated_at":"2015-03-19T08:26:53Z","closed_at":null,"merged_at":null,"merge_commit_sha":"ab55c8d0373fd986b03f9315693331bd4931ccfe","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/32/commits","review_comments_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/32/comments","review_comment_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/comments{/number}","comments_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/32/comments","statuses_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/statuses/cb802d8aef56e4590dd1c02c6a62efc447174c45","head":{"label":"davidavdav:master","ref":"master","sha":"cb802d8aef56e4590dd1c02c6a62efc447174c45","user":{"login":"davidavdav","id":5497303,"avatar_url":"https://avatars.githubusercontent.com/u/5497303?v=3","gravatar_id":"","url":"https://api.github.com/users/davidavdav","html_url":"https://github.com/davidavdav","followers_url":"https://api.github.com/users/davidavdav/followers","following_url":"https://api.github.com/users/davidavdav/following{/other_user}","gists_url":"https://api.github.com/users/davidavdav/gists{/gist_id}","starred_url":"https://api.github.com/users/davidavdav/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davidavdav/subscriptions","organizations_url":"https://api.github.com/users/davidavdav/orgs","repos_url":"https://api.github.com/users/davidavdav/repos","events_url":"https://api.github.com/users/davidavdav/events{/privacy}","received_events_url":"https://api.github.com/users/davidavdav/received_events","type":"User","site_admin":false},"repo":{"id":15310385,"name":"Clustering.jl","full_name":"davidavdav/Clustering.jl","owner":{"login":"davidavdav","id":5497303,"avatar_url":"https://avatars.githubusercontent.com/u/5497303?v=3","gravatar_id":"","url":"https://api.github.com/users/davidavdav","html_url":"https://github.com/davidavdav","followers_url":"https://api.github.com/users/davidavdav/followers","following_url":"https://api.github.com/users/davidavdav/following{/other_user}","gists_url":"https://api.github.com/users/davidavdav/gists{/gist_id}","starred_url":"https://api.github.com/users/davidavdav/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davidavdav/subscriptions","organizations_url":"https://api.github.com/users/davidavdav/orgs","repos_url":"https://api.github.com/users/davidavdav/repos","events_url":"https://api.github.com/users/davidavdav/events{/privacy}","received_events_url":"https://api.github.com/users/davidavdav/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/davidavdav/Clustering.jl","description":"Basic functions for clustering data: k-means, dp-means, etc.","fork":true,"url":"https://api.github.com/repos/davidavdav/Clustering.jl","forks_url":"https://api.github.com/repos/davidavdav/Clustering.jl/forks","keys_url":"https://api.github.com/repos/davidavdav/Clustering.jl/keys{/key_id}","collaborators_url":"https://api.github.com/repos/davidavdav/Clustering.jl/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/davidavdav/Clustering.jl/teams","hooks_url":"https://api.github.com/repos/davidavdav/Clustering.jl/hooks","issue_events_url":"https://api.github.com/repos/davidavdav/Clustering.jl/issues/events{/number}","events_url":"https://api.github.com/repos/davidavdav/Clustering.jl/events","assignees_url":"https://api.github.com/repos/davidavdav/Clustering.jl/assignees{/user}","branches_url":"https://api.github.com/repos/davidavdav/Clustering.jl/branches{/branch}","tags_url":"https://api.github.com/repos/davidavdav/Clustering.jl/tags","blobs_url":"https://api.github.com/repos/davidavdav/Clustering.jl/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/davidavdav/Clustering.jl/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/davidavdav/Clustering.jl/git/refs{/sha}","trees_url":"https://api.github.com/repos/davidavdav/Clustering.jl/git/trees{/sha}","statuses_url":"https://api.github.com/repos/davidavdav/Clustering.jl/statuses/{sha}","languages_url":"https://api.github.com/repos/davidavdav/Clustering.jl/languages","stargazers_url":"https://api.github.com/repos/davidavdav/Clustering.jl/stargazers","contributors_url":"https://api.github.com/repos/davidavdav/Clustering.jl/contributors","subscribers_url":"https://api.github.com/repos/davidavdav/Clustering.jl/subscribers","subscription_url":"https://api.github.com/repos/davidavdav/Clustering.jl/subscription","commits_url":"https://api.github.com/repos/davidavdav/Clustering.jl/commits{/sha}","git_commits_url":"https://api.github.com/repos/davidavdav/Clustering.jl/git/commits{/sha}","comments_url":"https://api.github.com/repos/davidavdav/Clustering.jl/comments{/number}","issue_comment_url":"https://api.github.com/repos/davidavdav/Clustering.jl/issues/comments{/number}","contents_url":"https://api.github.com/repos/davidavdav/Clustering.jl/contents/{+path}","compare_url":"https://api.github.com/repos/davidavdav/Clustering.jl/compare/{base}...{head}","merges_url":"https://api.github.com/repos/davidavdav/Clustering.jl/merges","archive_url":"https://api.github.com/repos/davidavdav/Clustering.jl/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/davidavdav/Clustering.jl/downloads","issues_url":"https://api.github.com/repos/davidavdav/Clustering.jl/issues{/number}","pulls_url":"https://api.github.com/repos/davidavdav/Clustering.jl/pulls{/number}","milestones_url":"https://api.github.com/repos/davidavdav/Clustering.jl/milestones{/number}","notifications_url":"https://api.github.com/repos/davidavdav/Clustering.jl/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/davidavdav/Clustering.jl/labels{/name}","releases_url":"https://api.github.com/repos/davidavdav/Clustering.jl/releases{/id}","created_at":"2013-12-19T11:46:49Z","updated_at":"2014-11-20T16:44:40Z","pushed_at":"2014-11-20T16:44:40Z","git_url":"git://github.com/davidavdav/Clustering.jl.git","ssh_url":"git@github.com:davidavdav/Clustering.jl.git","clone_url":"https://github.com/davidavdav/Clustering.jl.git","svn_url":"https://github.com/davidavdav/Clustering.jl","homepage":null,"size":256,"stargazers_count":0,"watchers_count":0,"language":"Julia","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"JuliaStats:master","ref":"master","sha":"b4ac970e7c122d0f8ca28fec3d34ff007c163256","user":{"login":"JuliaStats","id":2761531,"avatar_url":"https://avatars.githubusercontent.com/u/2761531?v=3","gravatar_id":"","url":"https://api.github.com/users/JuliaStats","html_url":"https://github.com/JuliaStats","followers_url":"https://api.github.com/users/JuliaStats/followers","following_url":"https://api.github.com/users/JuliaStats/following{/other_user}","gists_url":"https://api.github.com/users/JuliaStats/gists{/gist_id}","starred_url":"https://api.github.com/users/JuliaStats/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JuliaStats/subscriptions","organizations_url":"https://api.github.com/users/JuliaStats/orgs","repos_url":"https://api.github.com/users/JuliaStats/repos","events_url":"https://api.github.com/users/JuliaStats/events{/privacy}","received_events_url":"https://api.github.com/users/JuliaStats/received_events","type":"Organization","site_admin":false},"repo":{"id":6841256,"name":"Clustering.jl","full_name":"JuliaStats/Clustering.jl","owner":{"login":"JuliaStats","id":2761531,"avatar_url":"https://avatars.githubusercontent.com/u/2761531?v=3","gravatar_id":"","url":"https://api.github.com/users/JuliaStats","html_url":"https://github.com/JuliaStats","followers_url":"https://api.github.com/users/JuliaStats/followers","following_url":"https://api.github.com/users/JuliaStats/following{/other_user}","gists_url":"https://api.github.com/users/JuliaStats/gists{/gist_id}","starred_url":"https://api.github.com/users/JuliaStats/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JuliaStats/subscriptions","organizations_url":"https://api.github.com/users/JuliaStats/orgs","repos_url":"https://api.github.com/users/JuliaStats/repos","events_url":"https://api.github.com/users/JuliaStats/events{/privacy}","received_events_url":"https://api.github.com/users/JuliaStats/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/JuliaStats/Clustering.jl","description":"A Julia package for data clustering","fork":false,"url":"https://api.github.com/repos/JuliaStats/Clustering.jl","forks_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/forks","keys_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/keys{/key_id}","collaborators_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/teams","hooks_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/hooks","issue_events_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/events{/number}","events_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/events","assignees_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/assignees{/user}","branches_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/branches{/branch}","tags_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/tags","blobs_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/git/refs{/sha}","trees_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/git/trees{/sha}","statuses_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/statuses/{sha}","languages_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/languages","stargazers_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/stargazers","contributors_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/contributors","subscribers_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/subscribers","subscription_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/subscription","commits_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/commits{/sha}","git_commits_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/git/commits{/sha}","comments_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/comments{/number}","issue_comment_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/comments{/number}","contents_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/contents/{+path}","compare_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/compare/{base}...{head}","merges_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/merges","archive_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/downloads","issues_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues{/number}","pulls_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls{/number}","milestones_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/milestones{/number}","notifications_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/labels{/name}","releases_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/releases{/id}","created_at":"2012-11-24T15:47:36Z","updated_at":"2015-03-14T16:32:21Z","pushed_at":"2015-01-26T02:58:12Z","git_url":"git://github.com/JuliaStats/Clustering.jl.git","ssh_url":"git@github.com:JuliaStats/Clustering.jl.git","clone_url":"https://github.com/JuliaStats/Clustering.jl.git","svn_url":"https://github.com/JuliaStats/Clustering.jl","homepage":"","size":684,"stargazers_count":29,"watchers_count":29,"language":"Julia","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":27,"mirror_url":null,"open_issues_count":13,"forks":27,"open_issues":13,"watchers":29,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/32"},"html":{"href":"https://github.com/JuliaStats/Clustering.jl/pull/32"},"issue":{"href":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/32"},"comments":{"href":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/32/comments"},"review_comments":{"href":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/32/comments"},"review_comment":{"href":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/32/commits"},"statuses":{"href":"https://api.github.com/repos/JuliaStats/Clustering.jl/statuses/cb802d8aef56e4590dd1c02c6a62efc447174c45"}}}}