

# Measuring similarity with distance metrics

To measure similarity between two objects, we need a distance metric. A distance metric is a mathematical function that measures the difference between two objects. There are several distance metrics commonly used in similarity search, including:

- Euclidean distance
- Manhattan distance
- Pearson correlation coefficient
- Cosine similarity
- Jaccard similarity

Consider two points in a 2D space: (2, 3) and (5, 7). The Euclidean distance between these two points can be calculated using the formula:

$$
d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}
$$

In this case, the Euclidean distance between the points (2, 3) and (5, 7) is:

$$
d = \sqrt{(5 - 2)^2 + (7 - 3)^2} = \sqrt{29}
$$

## Exercise
Calculate the Euclidean distance between the points (1, 2) and (4, 6).



# Cosine similarity

Cosine similarity is a measure of similarity between two non-zero vectors by calculating the cosine of the angle between them. It is widely used in text search and information retrieval. The cosine similarity between two vectors A and B is defined as:

$$
\text{similarity}(A, B) = \frac{A \cdot B}{\|A\| \|B\|}
$$

where $A \cdot B$ is the dot product of A and B, and $\|A\|$ and $\|B\|$ are the magnitudes of A and B, respectively.

Let A = (1, 2, 3) and B = (2, 3, 4). The cosine similarity between A and B can be calculated as follows:

$$
\text{similarity}(A, B) = \frac{A \cdot B}{\|A\| \|B\|} = \frac{(1 \cdot 2) + (2 \cdot 3) + (3 \cdot 4)}{\sqrt{1^2 + 2^2 + 3^2} \sqrt{2^2 + 3^2 + 4^2}} = \frac{20}{\sqrt{14} \sqrt{29}} \approx 0.92
$$

## Exercise
Instructions:

Calculate the cosine similarity between the vectors A = (1, 2, 3) and B = (2, 3, 4).

### Solution
None



# Jaccard similarity

Jaccard similarity is a measure of similarity between two sets. It is defined as the size of the intersection divided by the size of the union of the two sets. The Jaccard similarity coefficient is a measure of how similar two sets are, with 1 indicating a perfect match and 0 indicating no similarity at all.

Let A = {1, 2, 3} and B = {2, 3, 4}. The Jaccard similarity between A and B can be calculated as follows:

$$
\text{similarity}(A, B) = \frac{|A \cap B|}{|A \cup B|} = \frac{2}{4} = 0.5
$$

## Exercise
Instructions:

Calculate the Jaccard similarity between the sets A = {1, 2, 3} and B = {2, 3, 4}.

### Solution
None



# Vector space model

The vector space model is a mathematical model used to represent text documents as points in a high-dimensional space. Each document is represented as a vector, where each component corresponds to a term in the document. The similarity between two documents is then measured using distance metrics, such as Euclidean distance or cosine similarity.

Consider two documents:

Document 1: "The cat is on the mat."
Document 2: "The dog is on the log."

We can represent these documents in a vector space model as follows:

Document 1: (1, 1, 1, 1, 1, 0)
Document 2: (1, 1, 1, 1, 0, 1)

The Euclidean distance between these two documents is:

$$
d = \sqrt{(1 - 1)^2 + (1 - 1)^2 + (1 - 1)^2 + (1 - 1)^2 + (0 - 0)^2 + (0 - 1)^2} = \sqrt{1}
$$

The cosine similarity between these two documents is:

$$
\text{similarity}(A, B) = \frac{A \cdot B}{\|A\| \|B\|} = \frac{5}{\sqrt{5} \sqrt{5}} = 1
$$

## Exercise
Instructions:

Calculate the Euclidean distance and cosine similarity between the documents "The cat is on the mat." and "The dog is on the log."

### Solution
None



# Local sensitive hashing

Local sensitive hashing is an algorithm for approximating nearest neighbor search in high-dimensional spaces. It is particularly useful for large datasets where exact nearest neighbor search is computationally expensive. The algorithm works by dividing the space into a grid and using a hash function to map each point to a cell in the grid. The algorithm then returns the points in the same cell as the query point as approximate nearest neighbors.

Consider a dataset of 3D points:

- P1 = (1, 1, 1)
- P2 = (2, 2, 2)
- P3 = (3, 3, 3)
- P4 = (4, 4, 4)

We can divide the space into a 2D grid and use a hash function to map each point to a cell in the grid. For example, we can use the hash function:

$$
\text{hash}(x, y, z) = \lfloor x / 2 \rfloor \times 2 + \lfloor y / 2 \rfloor \times 2 + \lfloor z / 2 \rfloor
$$

The points P1 and P2 would be mapped to the same cell, as would P3 and P4. The local sensitive hashing algorithm would then return P1 and P2 as approximate nearest neighbors for the query point P1.

## Exercise
Instructions:

Calculate the hash values for the points P1, P2, P3, and P4 using the given hash function.

### Solution
None



# Min-Hash

Min-Hash is a probabilistic algorithm for finding the similarity between two sets. It works by hashing the elements of the sets and keeping track of the minimum hash value for each set. The similarity between two sets is then calculated as the number of common hash values divided by the total number of hash values.

Let A = {1, 2, 3} and B = {2, 3, 4}. The Min-Hash similarity between A and B can be calculated as follows:

- Hash the elements of A and B using a hash function. For example, we can use the hash function:

$$
\text{hash}(x) = x \mod 4
$$

- Keep track of the minimum hash value for each set:

$$
\text{min hash}(A) = \min(\text{hash}(1), \text{hash}(2), \text{hash}(3)) = 1
$$

$$
\text{min hash}(B) = \min(\text{hash}(2), \text{hash}(3), \text{hash}(4)) = 2
$$

- Calculate the similarity between A and B:

$$
\text{similarity}(A, B) = \frac{\text{min hash}(A) \cap \text{min hash}(B)}{\text{min hash}(A) \cup \text{min hash}(B)} = \frac{1}{2} = 0.5
$$

## Exercise
Instructions:

Calculate the Min-Hash similarity between the sets A = {1, 2, 3} and B = {2, 3, 4}.

### Solution
None



# Applications of similarity search

Similarity search has a wide range of applications, including:

- Text search and information retrieval
- Image search and recognition
- DNA sequence analysis
- Recommender systems
- Social network analysis
- Spam detection

Similarity search can be used to find similar documents in a large collection of documents, such as a search engine. For example, a search query for "similarity search" might return a list of documents containing relevant information.

## Exercise
Instructions:

Describe a real-world scenario where similarity search can be applied.

### Solution
None



# Nearest neighbor search

Nearest neighbor search is a technique for finding the nearest points or nearest vectors in a high-dimensional space. It is commonly used in machine learning and data mining applications, such as image recognition, speech recognition, and recommendation systems. The k-nearest neighbors algorithm is a popular nearest neighbor search algorithm, where the "k" nearest points to a query point are returned.

Consider a dataset of 3D points:

- P1 = (1, 1, 1)
- P2 = (2, 2, 2)
- P3 = (3, 3, 3)
- P4 = (4, 4, 4)

The nearest neighbor to the query point P1 using the Euclidean distance metric is P2.

## Exercise
Instructions:

Find the nearest neighbor to the query point P1 using the Euclidean distance metric.

### Solution
None



# Text classification and clustering

Text classification and clustering are techniques used to group similar text documents or words together. Text classification is used to assign a document to a predefined category, while clustering is used to discover hidden patterns or relationships in the data. Both techniques can be applied to text data using similarity search algorithms, such as cosine similarity or Min-Hash.

Consider a dataset of documents with predefined categories:

- Document 1: "The cat is on the mat." (Category: Animal)
- Document 2: "The dog is on the log." (Category: Animal)
- Document 3: "The sun is shining." (Category: Weather)

We can use cosine similarity to measure the similarity between the documents and assign them to categories based on their similarity.

## Exercise
Instructions:

Classify the document "The sun is shining." using cosine similarity.

### Solution
None



# Recommender systems

Recommender systems are algorithms used to make predictions about the interests of a user based on the preferences or behavior of similar users. They are commonly used in online platforms, such as movie recommendation, product recommendation, or social media platforms. Similarity search algorithms, such as cosine similarity or Min-Hash, can be used to measure the similarity between users or items.

Consider a movie recommendation system with the following user preferences:

- User 1: Likes movies: "The Matrix", "Inception", "Interstellar"
- User 2: Likes movies: "The Matrix", "The Dark Knight", "Batman Begins"
- User 3: Likes movies: "Inception", "The Dark Knight", "The Lord of the Rings"

We can use cosine similarity to measure the similarity between the users' preferences and recommend movies to User 1 based on their similarity to other users.

## Exercise
Instructions:

Recommend movies to User 1 using cosine similarity.

### Solution
None