{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/86744662","pull_request_review_id":7384062,"id":86744662,"diff_hunk":"@@ -1396,3 +1396,134 @@ for more details on the API.\n {% include_example python/ml/chisq_selector_example.py %}\n </div>\n </div>\n+\n+# Locality Sensitive Hashing\n+[Locality Sensitive Hashing(LSH)](https://en.wikipedia.org/wiki/Locality-sensitive_hashing) is a class of dimension reduction hash families, which can be used as both feature transformation and machine-learned ranking. Difference distance metric has its own LSH family class in `spark.ml`, which can transform feature columns to hash values as new columns. Besides feature transforming, `spark.ml` also implemented approximate nearest neighbor algorithm and approximate similarity join algorithm using LSH.\n+\n+In this section, we call a pair of input features a false positive if the two features are hashed into the same hash bucket but they are far away in distance, and we define false negative as the pair of features when their distance are close but they are not in the same hash bucket.\n+\n+## Random Projection for Euclidean Distance\n+**Note:** Please note that this is different than the [Random Projection for cosine distance](https://en.wikipedia.org/wiki/Locality-sensitive_hashing#Random_projection).\n+\n+[Random Projection](https://en.wikipedia.org/wiki/Locality-sensitive_hashing#Stable_distributions) is the LSH family in `spark.ml` for Euclidean distance. The Euclidean distance is defined as follows:\n+`\\[\n+d(\\mathbf{x}, \\mathbf{y}) = \\sqrt{\\sum_i (x_i - y_i)^2}\n+\\]`\n+Its LSH family projects features onto a random unit vector and divide the projected results to hash buckets:\n+`\\[\n+h(\\mathbf{x}) = \\lfloor \\frac{\\mathbf{x} \\cdot \\mathbf{v}}{r} \\rfloor\n+\\]`\n+where `v` is a normalized random unit vector and `r` is user-defined bucket length.\n+\n+The input features in Euclidean space are represented in vectors. Both sparse and dense vectors are supported.\n+\n+The bucket length can be used to trade off the performance of random projection. A larger bucket lowers the false negative rate but usually increases running time and false positive rate.\n+\n+<div class=\"codetabs\">\n+<div data-lang=\"scala\" markdown=\"1\">\n+\n+Refer to the [RandomProjection Scala docs](api/scala/index.html#org.apache.spark.ml.feature.RandomProjection)\n+for more details on the API.\n+\n+{% include_example scala/org/apache/spark/examples/ml/RandomProjectionExample.scala %}\n+</div>\n+\n+<div data-lang=\"java\" markdown=\"1\">\n+\n+Refer to the [RandomProjection Java docs](api/java/org/apache/spark/ml/feature/RandomProjection.html)\n+for more details on the API.\n+\n+{% include_example java/org/apache/spark/examples/ml/JavaRandomProjectionExample.java %}\n+</div>\n+</div>\n+\n+## MinHash for Jaccard Distance\n+[MinHash](https://en.wikipedia.org/wiki/MinHash) is the LSH family in `spark.ml` for Jaccard distance where input features are sets of natural numbers. Jaccard distance of two sets is defined by the cardinality of their intersection and union:\n+`\\[\n+d(\\mathbf{A}, \\mathbf{B}) = 1 - \\frac{|\\mathbf{A} \\cap \\mathbf{B}|}{|\\mathbf{A} \\cup \\mathbf{B}|}\n+\\]`\n+As its LSH family, MinHash applies a random [perfect hash function](https://en.wikipedia.org/wiki/Perfect_hash_function) `g` to each elements in the set and take the minimum of all hashed values:\n+`\\[\n+h(\\mathbf{A}) = \\min_{a \\in \\mathbf{A}}(g(a))\n+\\]`\n+\n+Input sets for MinHash is represented in vectors which dimension equals the total number of elements in the space. Each dimension of the vectors represents the status of an elements: zero value means the elements is not in the set; non-zero value means the set contains the corresponding elements. For example, `Vectors.sparse(10, Array[(2, 1.0), (3, 1.0), (5, 1.0)])` means there are 10 elements in the space. This set contains elem 2, elem 3 and elem 5.","path":"docs/ml-features.md","position":55,"original_position":55,"commit_id":"8c7971bdcff9eeedc9a97936b4c2e0aac93c4edf","original_commit_id":"8c7971bdcff9eeedc9a97936b4c2e0aac93c4edf","user":{"login":"srowen","id":822522,"avatar_url":"https://avatars.githubusercontent.com/u/822522?v=3","gravatar_id":"","url":"https://api.github.com/users/srowen","html_url":"https://github.com/srowen","followers_url":"https://api.github.com/users/srowen/followers","following_url":"https://api.github.com/users/srowen/following{/other_user}","gists_url":"https://api.github.com/users/srowen/gists{/gist_id}","starred_url":"https://api.github.com/users/srowen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/srowen/subscriptions","organizations_url":"https://api.github.com/users/srowen/orgs","repos_url":"https://api.github.com/users/srowen/repos","events_url":"https://api.github.com/users/srowen/events{/privacy}","received_events_url":"https://api.github.com/users/srowen/received_events","type":"User","site_admin":false},"body":"Same sort of comment: isn't the intuition that MinHash approximates the Jaccard similarity without actually computing it completely?\r\n\r\nThis may again reduce to my different understanding of the technique, but MinHash isn't a hashing technique per se. it relies on a given family of hash functions to approximate set similarity. I'm finding it a little hard to view it as an 'LSH family'","created_at":"2016-11-07T10:12:06Z","updated_at":"2016-11-07T10:23:55Z","html_url":"https://github.com/apache/spark/pull/15795#discussion_r86744662","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/15795","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/86744662"},"html":{"href":"https://github.com/apache/spark/pull/15795#discussion_r86744662"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/15795"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/15795","id":92536602,"html_url":"https://github.com/apache/spark/pull/15795","diff_url":"https://github.com/apache/spark/pull/15795.diff","patch_url":"https://github.com/apache/spark/pull/15795.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/15795","number":15795,"state":"open","locked":false,"title":"[SPARK-18081] Add user guide for Locality Sensitive Hashing(LSH)","user":{"login":"Yunni","id":6089987,"avatar_url":"https://avatars.githubusercontent.com/u/6089987?v=3","gravatar_id":"","url":"https://api.github.com/users/Yunni","html_url":"https://github.com/Yunni","followers_url":"https://api.github.com/users/Yunni/followers","following_url":"https://api.github.com/users/Yunni/following{/other_user}","gists_url":"https://api.github.com/users/Yunni/gists{/gist_id}","starred_url":"https://api.github.com/users/Yunni/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Yunni/subscriptions","organizations_url":"https://api.github.com/users/Yunni/orgs","repos_url":"https://api.github.com/users/Yunni/repos","events_url":"https://api.github.com/users/Yunni/events{/privacy}","received_events_url":"https://api.github.com/users/Yunni/received_events","type":"User","site_admin":false},"body":"## What changes were proposed in this pull request?\r\nThe user guide for LSH is added to ml-features.md, with several scala/java examples in spark-examples.\r\n\r\n## How was this patch tested?\r\nDoc has been generated through Jekyll, and checked through manual inspection.\r\n","created_at":"2016-11-07T07:43:20Z","updated_at":"2016-11-07T10:23:55Z","closed_at":null,"merged_at":null,"merge_commit_sha":"5a07453bff1b0a3347e8559c48bffe38e97439b5","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/15795/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/15795/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/15795/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/8c7971bdcff9eeedc9a97936b4c2e0aac93c4edf","head":{"label":"Yunni:SPARK-18081-lsh-guide","ref":"SPARK-18081-lsh-guide","sha":"8c7971bdcff9eeedc9a97936b4c2e0aac93c4edf","user":{"login":"Yunni","id":6089987,"avatar_url":"https://avatars.githubusercontent.com/u/6089987?v=3","gravatar_id":"","url":"https://api.github.com/users/Yunni","html_url":"https://github.com/Yunni","followers_url":"https://api.github.com/users/Yunni/followers","following_url":"https://api.github.com/users/Yunni/following{/other_user}","gists_url":"https://api.github.com/users/Yunni/gists{/gist_id}","starred_url":"https://api.github.com/users/Yunni/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Yunni/subscriptions","organizations_url":"https://api.github.com/users/Yunni/orgs","repos_url":"https://api.github.com/users/Yunni/repos","events_url":"https://api.github.com/users/Yunni/events{/privacy}","received_events_url":"https://api.github.com/users/Yunni/received_events","type":"User","site_admin":false},"repo":{"id":67909681,"name":"spark","full_name":"Yunni/spark","owner":{"login":"Yunni","id":6089987,"avatar_url":"https://avatars.githubusercontent.com/u/6089987?v=3","gravatar_id":"","url":"https://api.github.com/users/Yunni","html_url":"https://github.com/Yunni","followers_url":"https://api.github.com/users/Yunni/followers","following_url":"https://api.github.com/users/Yunni/following{/other_user}","gists_url":"https://api.github.com/users/Yunni/gists{/gist_id}","starred_url":"https://api.github.com/users/Yunni/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Yunni/subscriptions","organizations_url":"https://api.github.com/users/Yunni/orgs","repos_url":"https://api.github.com/users/Yunni/repos","events_url":"https://api.github.com/users/Yunni/events{/privacy}","received_events_url":"https://api.github.com/users/Yunni/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Yunni/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/Yunni/spark","forks_url":"https://api.github.com/repos/Yunni/spark/forks","keys_url":"https://api.github.com/repos/Yunni/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Yunni/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Yunni/spark/teams","hooks_url":"https://api.github.com/repos/Yunni/spark/hooks","issue_events_url":"https://api.github.com/repos/Yunni/spark/issues/events{/number}","events_url":"https://api.github.com/repos/Yunni/spark/events","assignees_url":"https://api.github.com/repos/Yunni/spark/assignees{/user}","branches_url":"https://api.github.com/repos/Yunni/spark/branches{/branch}","tags_url":"https://api.github.com/repos/Yunni/spark/tags","blobs_url":"https://api.github.com/repos/Yunni/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Yunni/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Yunni/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/Yunni/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Yunni/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/Yunni/spark/languages","stargazers_url":"https://api.github.com/repos/Yunni/spark/stargazers","contributors_url":"https://api.github.com/repos/Yunni/spark/contributors","subscribers_url":"https://api.github.com/repos/Yunni/spark/subscribers","subscription_url":"https://api.github.com/repos/Yunni/spark/subscription","commits_url":"https://api.github.com/repos/Yunni/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/Yunni/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/Yunni/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/Yunni/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/Yunni/spark/contents/{+path}","compare_url":"https://api.github.com/repos/Yunni/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Yunni/spark/merges","archive_url":"https://api.github.com/repos/Yunni/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Yunni/spark/downloads","issues_url":"https://api.github.com/repos/Yunni/spark/issues{/number}","pulls_url":"https://api.github.com/repos/Yunni/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/Yunni/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/Yunni/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Yunni/spark/labels{/name}","releases_url":"https://api.github.com/repos/Yunni/spark/releases{/id}","deployments_url":"https://api.github.com/repos/Yunni/spark/deployments","created_at":"2016-09-11T04:17:57Z","updated_at":"2016-09-11T04:18:21Z","pushed_at":"2016-11-07T07:24:49Z","git_url":"git://github.com/Yunni/spark.git","ssh_url":"git@github.com:Yunni/spark.git","clone_url":"https://github.com/Yunni/spark.git","svn_url":"https://github.com/Yunni/spark","homepage":null,"size":248673,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"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":"apache:master","ref":"master","sha":"9db06c442cf85e41d51c7b167817f4e7971bf0da","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","deployments_url":"https://api.github.com/repos/apache/spark/deployments","created_at":"2014-02-25T08:00:08Z","updated_at":"2016-11-07T10:00:38Z","pushed_at":"2016-11-07T09:49:27Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":607307,"stargazers_count":10633,"watchers_count":10633,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":9929,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":444,"forks":9929,"open_issues":444,"watchers":10633,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/15795"},"html":{"href":"https://github.com/apache/spark/pull/15795"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/15795"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/15795/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/15795/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/15795/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/8c7971bdcff9eeedc9a97936b4c2e0aac93c4edf"}}}}
{"actor":{"display_login":"srowen"}}