Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15795#discussion_r90736515
--- Diff: docs/ml-features.md ---
@@ -1478,3 +1478,139 @@ for more details on the API.
{% include_example python/ml/chisq_selector_example.py %}
</div>
</div>
+
+# Locality Sensitive Hashing
+[Locality Sensitive
Hashing(LSH)](https://en.wikipedia.org/wiki/Locality-sensitive_hashing) is an
important class of hashing techniques, which is commonly used in clustering,
approximate nearest neighbor search and outlier detection with large datasets.
+
+The general idea of LSH is to use a family of functions (we call them LSH
families) to hash data points into buckets, so that the data points which are
close to each other are in the same buckets with high probability, while data
points that are far away from each other are very likely in different buckets.
A formal definition of LSH family is as follows:
+
+In a metric space `(M, d)`, where `M` is a set and `d` is a distance
function on `M`, an LSH family is a family of functions `h` that satisfy the
following properties:
+`\[
+\forall p, q \in M,\\
+d(p,q) < r1 \Rightarrow Pr(h(p)=h(q)) \geq p1\\
+d(p,q) > r2 \Rightarrow Pr(h(p)=h(q)) \leq p2
+\]`
+This LSH family is called `(r1, r2, p1, p2)`-sensitive.
+
+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.
+
+## Bucketed Random Projection for Euclidean Distance
+
+[Bucketed 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:
+`\[
+d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_i (x_i - y_i)^2}
+\]`
+Its LSH family projects features onto a random unit vector and divide the
projected results to hash buckets:
+`\[
+h(\mathbf{x}) = \lfloor \frac{\mathbf{x} \cdot \mathbf{v}}{r} \rfloor
+\]`
+where `v` is a normalized random unit vector and `r` is user-defined
bucket length. The bucket length can be used to control the average size of
hash buckets. A larger bucket length means higher probability for features to
be in the same bucket.
+
+Bucketed Random Projection accepts arbitrary vectors as input features,
and supports both sparse and dense vectors.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+Refer to the [RandomProjection Scala
docs](api/scala/index.html#org.apache.spark.ml.feature.RandomProjection)
+for more details on the API.
+
+{% include_example
scala/org/apache/spark/examples/ml/BucketedRandomProjectionLSHExample.scala %}
+</div>
+
+<div data-lang="java" markdown="1">
+
+Refer to the [RandomProjection Java
docs](api/java/org/apache/spark/ml/feature/RandomProjection.html)
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org
