Repository: spark Updated Branches: refs/heads/branch-2.1 b098b4845 -> 28f698b48
[SPARK-18081][ML][DOCS] Add user guide for Locality Sensitive Hashing(LSH) ## What changes were proposed in this pull request? The user guide for LSH is added to ml-features.md, with several scala/java examples in spark-examples. ## How was this patch tested? Doc has been generated through Jekyll, and checked through manual inspection. Author: Yunni <[email protected]> Author: Yun Ni <[email protected]> Author: Joseph K. Bradley <[email protected]> Author: Yun Ni <[email protected]> Closes #15795 from Yunni/SPARK-18081-lsh-guide. (cherry picked from commit 34777184cd8cab61e1dd25d0a4d5e738880a57b2) Signed-off-by: Joseph K. Bradley <[email protected]> Project: http://git-wip-us.apache.org/repos/asf/spark/repo Commit: http://git-wip-us.apache.org/repos/asf/spark/commit/28f698b4 Tree: http://git-wip-us.apache.org/repos/asf/spark/tree/28f698b4 Diff: http://git-wip-us.apache.org/repos/asf/spark/diff/28f698b4 Branch: refs/heads/branch-2.1 Commit: 28f698b4845e6497d060270ba790cc60dc7e1a6e Parents: b098b48 Author: Yunni <[email protected]> Authored: Sat Dec 3 16:58:15 2016 -0800 Committer: Joseph K. Bradley <[email protected]> Committed: Sat Dec 3 16:58:25 2016 -0800 ---------------------------------------------------------------------- docs/ml-features.md | 111 +++++++++++++++++++ .../JavaBucketedRandomProjectionLSHExample.java | 98 ++++++++++++++++ .../examples/ml/JavaMinHashLSHExample.java | 70 ++++++++++++ .../ml/BucketedRandomProjectionLSHExample.scala | 80 +++++++++++++ .../spark/examples/ml/MinHashLSHExample.scala | 77 +++++++++++++ 5 files changed, 436 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/spark/blob/28f698b4/docs/ml-features.md ---------------------------------------------------------------------- diff --git a/docs/ml-features.md b/docs/ml-features.md index 9eecc13..3ecf700 100644 --- a/docs/ml-features.md +++ b/docs/ml-features.md @@ -9,6 +9,7 @@ This section covers algorithms for working with features, roughly divided into t * Extraction: Extracting features from "raw" data * Transformation: Scaling, converting, or modifying features * Selection: Selecting a subset from a larger set of features +* Locality Sensitive Hashing (LSH): This class of algorithms combines aspects of feature transformation with other algorithms. **Table of Contents** @@ -1450,3 +1451,113 @@ 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 ("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. An LSH family is formally defined 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) \leq r1 \Rightarrow Pr(h(p)=h(q)) \geq p1\\ +d(p,q) \geq r2 \Rightarrow Pr(h(p)=h(q)) \leq p2 +\]` +This LSH family is called `(r1, r2, p1, p2)`-sensitive. + +In Spark, different LSH families are implemented in separate classes (e.g., `MinHash`), and APIs for feature transformation, approximate similarity join and approximate nearest neighbor are provided in each class. + +In LSH, we define a false positive as a pair of distant input features (with `$d(p,q) \geq r2$`) which are hashed into the same bucket, and we define a false negative as a pair of nearby features (with `$d(p,q) \leq r1$`) which are hashed into different buckets. + +## LSH Operations + +We describe the major types of operations which LSH can be used for. A fitted LSH model has methods for each of these operations. + +### Feature Transformation +Feature transformation is the basic functionality to add hashed values as a new column. This can be useful for dimensionality reduction. Users can specify input and output column names by setting `inputCol` and `outputCol`. + +LSH also supports multiple LSH hash tables. Users can specify the number of hash tables by setting `numHashTables`. This is also used for [OR-amplification](https://en.wikipedia.org/wiki/Locality-sensitive_hashing#Amplification) in approximate similarity join and approximate nearest neighbor. Increasing the number of hash tables will increase the accuracy but will also increase communication cost and running time. + +The type of `outputCol` is `Seq[Vector]` where the dimension of the array equals `numHashTables`, and the dimensions of the vectors are currently set to 1. In future releases, we will implement AND-amplification so that users can specify the dimensions of these vectors. + +### Approximate Similarity Join +Approximate similarity join takes two datasets and approximately returns pairs of rows in the datasets whose distance is smaller than a user-defined threshold. Approximate similarity join supports both joining two different datasets and self-joining. Self-joining will produce some duplicate pairs. + +Approximate similarity join accepts both transformed and untransformed datasets as input. If an untransformed dataset is used, it will be transformed automatically. In this case, the hash signature will be created as `outputCol`. + +In the joined dataset, the origin datasets can be queried in `datasetA` and `datasetB`. A distance column will be added to the output dataset to show the true distance between each pair of rows returned. + +### Approximate Nearest Neighbor Search +Approximate nearest neighbor search takes a dataset (of feature vectors) and a key (a single feature vector), and it approximately returns a specified number of rows in the dataset that are closest to the vector. + +Approximate nearest neighbor search accepts both transformed and untransformed datasets as input. If an untransformed dataset is used, it will be transformed automatically. In this case, the hash signature will be created as `outputCol`. + +A distance column will be added to the output dataset to show the true distance between each output row and the searched key. + +**Note:** Approximate nearest neighbor search will return fewer than `k` rows when there are not enough candidates in the hash bucket. + +## LSH Algorithms + +### Bucketed Random Projection for Euclidean Distance + +[Bucketed Random Projection](https://en.wikipedia.org/wiki/Locality-sensitive_hashing#Stable_distributions) is an LSH family 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 feature vectors `$\mathbf{x}$` onto a random unit vector `$\mathbf{v}$` and portions the projected results into hash buckets: +`\[ +h(\mathbf{x}) = \Big\lfloor \frac{\mathbf{x} \cdot \mathbf{v}}{r} \Big\rfloor +\]` +where `r` is a user-defined bucket length. The bucket length can be used to control the average size of hash buckets (and thus the number of buckets). A larger bucket length (i.e., fewer buckets) increases the probability of features being hashed to the same bucket (increasing the numbers of true and false positives). + +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 [BucketedRandomProjectionLSH Scala docs](api/scala/index.html#org.apache.spark.ml.feature.BucketedRandomProjectionLSH) +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 [BucketedRandomProjectionLSH Java docs](api/java/org/apache/spark/ml/feature/BucketedRandomProjectionLSH.html) +for more details on the API. + +{% include_example java/org/apache/spark/examples/ml/JavaBucketedRandomProjectionLSHExample.java %} +</div> +</div> + +### MinHash for Jaccard Distance +[MinHash](https://en.wikipedia.org/wiki/MinHash) is an LSH family 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: +`\[ +d(\mathbf{A}, \mathbf{B}) = 1 - \frac{|\mathbf{A} \cap \mathbf{B}|}{|\mathbf{A} \cup \mathbf{B}|} +\]` +MinHash applies a random hash function `g` to each element in the set and take the minimum of all hashed values: +`\[ +h(\mathbf{A}) = \min_{a \in \mathbf{A}}(g(a)) +\]` + +The input sets for MinHash are represented as binary vectors, where the vector indices represent the elements themselves and the non-zero values in the vector represent the presence of that element in the set. While both dense and sparse vectors are supported, typically sparse vectors are recommended for efficiency. 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. All non-zero values are treated as binary "1" values. + +**Note:** Empty sets cannot be transformed by MinHash, which means any input vector must have at least 1 non-zero entry. + +<div class="codetabs"> +<div data-lang="scala" markdown="1"> + +Refer to the [MinHashLSH Scala docs](api/scala/index.html#org.apache.spark.ml.feature.MinHashLSH) +for more details on the API. + +{% include_example scala/org/apache/spark/examples/ml/MinHashLSHExample.scala %} +</div> + +<div data-lang="java" markdown="1"> + +Refer to the [MinHashLSH Java docs](api/java/org/apache/spark/ml/feature/MinHashLSH.html) +for more details on the API. + +{% include_example java/org/apache/spark/examples/ml/JavaMinHashLSHExample.java %} +</div> +</div> http://git-wip-us.apache.org/repos/asf/spark/blob/28f698b4/examples/src/main/java/org/apache/spark/examples/ml/JavaBucketedRandomProjectionLSHExample.java ---------------------------------------------------------------------- diff --git a/examples/src/main/java/org/apache/spark/examples/ml/JavaBucketedRandomProjectionLSHExample.java b/examples/src/main/java/org/apache/spark/examples/ml/JavaBucketedRandomProjectionLSHExample.java new file mode 100644 index 0000000..ca3ee5a --- /dev/null +++ b/examples/src/main/java/org/apache/spark/examples/ml/JavaBucketedRandomProjectionLSHExample.java @@ -0,0 +1,98 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.spark.examples.ml; + +import org.apache.spark.sql.SparkSession; + +// $example on$ +import java.util.Arrays; +import java.util.List; + +import org.apache.spark.ml.feature.BucketedRandomProjectionLSH; +import org.apache.spark.ml.feature.BucketedRandomProjectionLSHModel; +import org.apache.spark.ml.linalg.Vector; +import org.apache.spark.ml.linalg.Vectors; +import org.apache.spark.ml.linalg.VectorUDT; +import org.apache.spark.sql.Dataset; +import org.apache.spark.sql.Row; +import org.apache.spark.sql.RowFactory; +import org.apache.spark.sql.types.DataTypes; +import org.apache.spark.sql.types.Metadata; +import org.apache.spark.sql.types.StructField; +import org.apache.spark.sql.types.StructType; +// $example off$ + +public class JavaBucketedRandomProjectionLSHExample { + public static void main(String[] args) { + SparkSession spark = SparkSession + .builder() + .appName("JavaBucketedRandomProjectionLSHExample") + .getOrCreate(); + + // $example on$ + List<Row> dataA = Arrays.asList( + RowFactory.create(0, Vectors.dense(1.0, 1.0)), + RowFactory.create(1, Vectors.dense(1.0, -1.0)), + RowFactory.create(2, Vectors.dense(-1.0, -1.0)), + RowFactory.create(3, Vectors.dense(-1.0, 1.0)) + ); + + List<Row> dataB = Arrays.asList( + RowFactory.create(4, Vectors.dense(1.0, 0.0)), + RowFactory.create(5, Vectors.dense(-1.0, 0.0)), + RowFactory.create(6, Vectors.dense(0.0, 1.0)), + RowFactory.create(7, Vectors.dense(0.0, -1.0)) + ); + + StructType schema = new StructType(new StructField[]{ + new StructField("id", DataTypes.IntegerType, false, Metadata.empty()), + new StructField("keys", new VectorUDT(), false, Metadata.empty()) + }); + Dataset<Row> dfA = spark.createDataFrame(dataA, schema); + Dataset<Row> dfB = spark.createDataFrame(dataB, schema); + + Vector key = Vectors.dense(1.0, 0.0); + + BucketedRandomProjectionLSH mh = new BucketedRandomProjectionLSH() + .setBucketLength(2.0) + .setNumHashTables(3) + .setInputCol("keys") + .setOutputCol("values"); + + BucketedRandomProjectionLSHModel model = mh.fit(dfA); + + // Feature Transformation + model.transform(dfA).show(); + // Cache the transformed columns + Dataset<Row> transformedA = model.transform(dfA).cache(); + Dataset<Row> transformedB = model.transform(dfB).cache(); + + // Approximate similarity join + model.approxSimilarityJoin(dfA, dfB, 1.5).show(); + model.approxSimilarityJoin(transformedA, transformedB, 1.5).show(); + // Self Join + model.approxSimilarityJoin(dfA, dfA, 2.5).filter("datasetA.id < datasetB.id").show(); + + // Approximate nearest neighbor search + model.approxNearestNeighbors(dfA, key, 2).show(); + model.approxNearestNeighbors(transformedA, key, 2).show(); + // $example off$ + + spark.stop(); + } +} http://git-wip-us.apache.org/repos/asf/spark/blob/28f698b4/examples/src/main/java/org/apache/spark/examples/ml/JavaMinHashLSHExample.java ---------------------------------------------------------------------- diff --git a/examples/src/main/java/org/apache/spark/examples/ml/JavaMinHashLSHExample.java b/examples/src/main/java/org/apache/spark/examples/ml/JavaMinHashLSHExample.java new file mode 100644 index 0000000..9dbbf6d --- /dev/null +++ b/examples/src/main/java/org/apache/spark/examples/ml/JavaMinHashLSHExample.java @@ -0,0 +1,70 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.spark.examples.ml; + +import org.apache.spark.sql.SparkSession; + +// $example on$ +import java.util.Arrays; +import java.util.List; + +import org.apache.spark.ml.feature.MinHashLSH; +import org.apache.spark.ml.feature.MinHashLSHModel; +import org.apache.spark.ml.linalg.VectorUDT; +import org.apache.spark.ml.linalg.Vectors; +import org.apache.spark.sql.Dataset; +import org.apache.spark.sql.Row; +import org.apache.spark.sql.RowFactory; +import org.apache.spark.sql.types.DataTypes; +import org.apache.spark.sql.types.Metadata; +import org.apache.spark.sql.types.StructField; +import org.apache.spark.sql.types.StructType; +// $example off$ + +public class JavaMinHashLSHExample { + public static void main(String[] args) { + SparkSession spark = SparkSession + .builder() + .appName("JavaMinHashLSHExample") + .getOrCreate(); + + // $example on$ + List<Row> data = Arrays.asList( + RowFactory.create(0, Vectors.sparse(6, new int[]{0, 1, 2}, new double[]{1.0, 1.0, 1.0})), + RowFactory.create(1, Vectors.sparse(6, new int[]{2, 3, 4}, new double[]{1.0, 1.0, 1.0})), + RowFactory.create(2, Vectors.sparse(6, new int[]{0, 2, 4}, new double[]{1.0, 1.0, 1.0})) + ); + + StructType schema = new StructType(new StructField[]{ + new StructField("id", DataTypes.IntegerType, false, Metadata.empty()), + new StructField("keys", new VectorUDT(), false, Metadata.empty()) + }); + Dataset<Row> dataFrame = spark.createDataFrame(data, schema); + + MinHashLSH mh = new MinHashLSH() + .setNumHashTables(1) + .setInputCol("keys") + .setOutputCol("values"); + + MinHashLSHModel model = mh.fit(dataFrame); + model.transform(dataFrame).show(); + // $example off$ + + spark.stop(); + } +} http://git-wip-us.apache.org/repos/asf/spark/blob/28f698b4/examples/src/main/scala/org/apache/spark/examples/ml/BucketedRandomProjectionLSHExample.scala ---------------------------------------------------------------------- diff --git a/examples/src/main/scala/org/apache/spark/examples/ml/BucketedRandomProjectionLSHExample.scala b/examples/src/main/scala/org/apache/spark/examples/ml/BucketedRandomProjectionLSHExample.scala new file mode 100644 index 0000000..686cc39 --- /dev/null +++ b/examples/src/main/scala/org/apache/spark/examples/ml/BucketedRandomProjectionLSHExample.scala @@ -0,0 +1,80 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// scalastyle:off println +package org.apache.spark.examples.ml + +// $example on$ +import org.apache.spark.ml.feature.BucketedRandomProjectionLSH +import org.apache.spark.ml.linalg.Vectors +// $example off$ +import org.apache.spark.sql.SparkSession + +object BucketedRandomProjectionLSHExample { + def main(args: Array[String]): Unit = { + // Creates a SparkSession + val spark = SparkSession + .builder + .appName("BucketedRandomProjectionLSHExample") + .getOrCreate() + + // $example on$ + val dfA = spark.createDataFrame(Seq( + (0, Vectors.dense(1.0, 1.0)), + (1, Vectors.dense(1.0, -1.0)), + (2, Vectors.dense(-1.0, -1.0)), + (3, Vectors.dense(-1.0, 1.0)) + )).toDF("id", "keys") + + val dfB = spark.createDataFrame(Seq( + (4, Vectors.dense(1.0, 0.0)), + (5, Vectors.dense(-1.0, 0.0)), + (6, Vectors.dense(0.0, 1.0)), + (7, Vectors.dense(0.0, -1.0)) + )).toDF("id", "keys") + + val key = Vectors.dense(1.0, 0.0) + + val brp = new BucketedRandomProjectionLSH() + .setBucketLength(2.0) + .setNumHashTables(3) + .setInputCol("keys") + .setOutputCol("values") + + val model = brp.fit(dfA) + + // Feature Transformation + model.transform(dfA).show() + // Cache the transformed columns + val transformedA = model.transform(dfA).cache() + val transformedB = model.transform(dfB).cache() + + // Approximate similarity join + model.approxSimilarityJoin(dfA, dfB, 1.5).show() + model.approxSimilarityJoin(transformedA, transformedB, 1.5).show() + // Self Join + model.approxSimilarityJoin(dfA, dfA, 2.5).filter("datasetA.id < datasetB.id").show() + + // Approximate nearest neighbor search + model.approxNearestNeighbors(dfA, key, 2).show() + model.approxNearestNeighbors(transformedA, key, 2).show() + // $example off$ + + spark.stop() + } +} +// scalastyle:on println http://git-wip-us.apache.org/repos/asf/spark/blob/28f698b4/examples/src/main/scala/org/apache/spark/examples/ml/MinHashLSHExample.scala ---------------------------------------------------------------------- diff --git a/examples/src/main/scala/org/apache/spark/examples/ml/MinHashLSHExample.scala b/examples/src/main/scala/org/apache/spark/examples/ml/MinHashLSHExample.scala new file mode 100644 index 0000000..f4fc3cf --- /dev/null +++ b/examples/src/main/scala/org/apache/spark/examples/ml/MinHashLSHExample.scala @@ -0,0 +1,77 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// scalastyle:off println +package org.apache.spark.examples.ml + +// $example on$ +import org.apache.spark.ml.feature.MinHashLSH +import org.apache.spark.ml.linalg.Vectors +// $example off$ +import org.apache.spark.sql.SparkSession + +object MinHashLSHExample { + def main(args: Array[String]): Unit = { + // Creates a SparkSession + val spark = SparkSession + .builder + .appName("MinHashLSHExample") + .getOrCreate() + + // $example on$ + val dfA = spark.createDataFrame(Seq( + (0, Vectors.sparse(6, Seq((0, 1.0), (1, 1.0), (2, 1.0)))), + (1, Vectors.sparse(6, Seq((2, 1.0), (3, 1.0), (4, 1.0)))), + (2, Vectors.sparse(6, Seq((0, 1.0), (2, 1.0), (4, 1.0)))) + )).toDF("id", "keys") + + val dfB = spark.createDataFrame(Seq( + (3, Vectors.sparse(6, Seq((1, 1.0), (3, 1.0), (5, 1.0)))), + (4, Vectors.sparse(6, Seq((2, 1.0), (3, 1.0), (5, 1.0)))), + (5, Vectors.sparse(6, Seq((1, 1.0), (2, 1.0), (4, 1.0)))) + )).toDF("id", "keys") + + val key = Vectors.sparse(6, Seq((1, 1.0), (3, 1.0))) + + val mh = new MinHashLSH() + .setNumHashTables(3) + .setInputCol("keys") + .setOutputCol("values") + + val model = mh.fit(dfA) + + // Feature Transformation + model.transform(dfA).show() + // Cache the transformed columns + val transformedA = model.transform(dfA).cache() + val transformedB = model.transform(dfB).cache() + + // Approximate similarity join + model.approxSimilarityJoin(dfA, dfB, 0.6).show() + model.approxSimilarityJoin(transformedA, transformedB, 0.6).show() + // Self Join + model.approxSimilarityJoin(dfA, dfA, 0.6).filter("datasetA.id < datasetB.id").show() + + // Approximate nearest neighbor search + model.approxNearestNeighbors(dfA, key, 2).show() + model.approxNearestNeighbors(transformedA, key, 2).show() + // $example off$ + + spark.stop() + } +} +// scalastyle:on println --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
