Data Mining Exercise 3

📏 Distance & Similarity Measures

If we don't have these "rulers", the computer won't know how "similar" or "different" data A is from data B.

And if it doesn't know similarity/difference, it cannot do:

• 📊 Clustering
• 🎯 Recommendation

Let's look at calculations with "Real-world Scenarios (Use Cases)" that will make you see the clear picture.

📝 Problem 2.1: Data in the same direction, but different magnitude

Input: $x = (1,1,1,1)$ and $y = (2,2,2,2)$

🧮 1. Calculation

📐 Euclidean Distance

$d(x,y) = \sqrt{(1-2)^2 + (1-2)^2 + (1-2)^2 + (1-2)^2} = \sqrt{1+1+1+1} = \sqrt{4} = \mathbf{2}$

Cosine Similarity

$\cos(x,y) = \frac{x \cdot y}{||x|| ||y||} = \frac{(1\times2 + 1\times2 + 1\times2 + 1\times2)}{\sqrt{4} \times \sqrt{16}} = \frac{8}{2 \times 4} = \mathbf{1.0}$

📈 Correlation

🌍 2. Real-world Scenario

Context: Analyzing word frequency in documents (Text Mining)

Suppose vectors represent frequency of words "Data", "Mining", "KDD", "AI" in documents:

• Document x: Each word 1 time (Short abstract)
• Document y: Each word 2 times (Full article, same content as x but twice as long)

💡 Application:

If you build a Search Engine or Plagiarism Detection, you should use Cosine because we care about "content", not the "length" of the document.

📝 Problem 2.2: Binary data (0/1) that are opposite

Input: $x = (0,1,0,1)$ and $y = (1,0,1,0)$

🧮 1. Calculation

📐 Euclidean Distance

$d(x,y) = \sqrt{(0-1)^2 + (1-0)^2 + (0-1)^2 + (1-0)^2} = \sqrt{1+1+1+1} = \mathbf{2}$

📊 Cosine Similarity

$\cos(x,y) = \frac{(0\times1 + ...)}{||x|| ||y||} = \frac{0}{\sqrt{2} \times \sqrt{2}} = \mathbf{0}$

🔗 Jaccard Similarity

• M₁₁ (Both have 1) = 0
• M₀₁ or M₁₀ (Only one has 1) = 4

$J = \frac{M_{11}}{M_{01} + M_{10} + M_{11}} = \frac{0}{4} = \mathbf{0}$

📈 Correlation

Calculated to be -1.0 (Perfect Negative Correlation) because when $x$ is 1, $y$ is always 0 (opposite direction).

🌍 2. Real-world Scenario

Context: Recommender System or Market Basket Analysis

Suppose vectors represent buying 4 items: {Milk, Beer, Diapers, Snacks}

• Customer x: Bought (Beer, Snacks) → (0,1,0,1)
• Customer y: Bought (Milk, Diapers) → (1,0,1,0)

💡 Application:

In KDD, if we want to do Clustering (grouping customers):

• ✅ If using Euclidean → Distance is 2 (seems not a lot)
• ✅ If using Jaccard or Cosine → Will clearly state it is 0 (clearly different groups)

🔄 Summary of relation to KDD Process

These formulas are the Engine working behind the scenes of Data Mining steps.

1️⃣ Preprocessing Step

🔍 Deduplication:

• Question: How do we know if 2 customer records in the database are the same person with a typo?
• Solution: Use String Similarity (similar to Cosine/Jaccard) to compare characters. If similar > 90%, merge them.

2️⃣ Data Mining Step

📊 Clustering (e.g. K-Means):

• The algorithm must know which point is "closest" to the center.
• Must use Euclidean Distance to measure distance to group data together.

🎯 Classification (e.g. K-Nearest Neighbors - KNN):

• Will guess which group a new customer belongs to.
• Must find the "nearest neighbors" (first 5 people) by using these Distance formulas to measure who is closest.

📋 Decision Guide Summary Table

| Formula | Focus | Application | | ------

-------- | ---------------------------------- | --------------------------------------------------------------------------- | | Euclidean | Measures physical distance | General continuous numerical data, geographical distance (GPS) | | Cosine | Measures direction (ignores magnitude) | Text Mining (documents), search, user profile comparison | | Jaccard | Measures set overlap | Market Basket Analysis, Binary data (0/1) | | Correlation| Measures linear relationship | Stock analysis, finding Feature relationships (Feature Selection) |