Data: Attributes, Quality, Similarity & Preprocessing

1. What is Data? Objects & Attributes

Slide 4：Dataset is a collection of data objects and their attributes.

• Attribute：object 嘅 property 或 characteristic（例如人嘅 eye color、temperature）。別名：variable、field、characteristic、dimension、feature。
• 一組 attributes 描述一個 Object。別名：record、point、case、observation、sample、entity、instance。

用表格諗：每一行係一個 object，每一欄係一個 attribute。

1.1 Attribute Values (Slide 5)

Attribute values 係分配俾某 object 嘅某 attribute 嘅數字或符號。要分清 attribute 同 attribute values：

• 同一個 attribute 可以 map 去唔同 values：例如 height 可以用 feet 或 meters 量度。
• 唔同 attributes 可以 map 去同一組 values：例如 ID 同 age 都係 integers。
• 但 values 嘅 properties 可以唔同：ID 冇上限，age 有最大同最小值；計 ID 嘅平均冇意義，計 age 平均就有。

2. Types of Attributes (NOIR)

ExamSlide 6–7 將 attributes 分四類，視乎佢擁有邊啲 properties / operations：

• Distinctness：$=, \neq$
• Order：$\lt, \gt$
• Differences are meaningful：$+, -$
• Ratios are meaningful：$\times, \div$

2.1 Ratio vs Interval (Slide 8)

Slide 問：「10° 係咪 5° 嘅兩倍熱？」

• Celsius / Fahrenheit：唔係！因為 0°C 唔係「冇溫度」，零點係人為設定。10°C = 283.15K，5°C = 278.15K，比例只係 1.018。所以 Celsius 只係 interval：差（10 − 5 = 5 度）有意義，比例冇意義。
• Kelvin：0K 係絕對零度（真正嘅「冇」），所以 10K 真係 5K 嘅兩倍 → ratio。
• Height above average：Bill 高過平均 3 inches，Bob 高過平均 6 inches，Bob 係咪「兩倍高」過 Bill？唔係——零點係「平均身高」而唔係「0 高度」，同 Celsius 情況一樣，屬 interval。

2.2 Discrete vs Continuous (Slide 10)

2.3 Key Messages for Attribute Types (Slide 11)

• 你選擇嘅 operations 要對你嘅 data type 係 "meaningful"。
• Distinctness、order、meaningful intervals、meaningful ratios 只係 data 嘅四種 properties。
• 你見到嘅 data type（通常係數字或字串）未必反映晒所有 properties，甚至可能暗示唔存在嘅 properties（例如 zip code 係數字，但計平均冇意義）。
• 分析可能依賴其他 properties，例如好多統計分析只依賴 distribution。
• 有時 meaningful 由 statistical significance 衡量，但最終由 domain 決定。

3. Characteristics & Types of Data Sets

3.1 Important Characteristics of Data (Slide 12)

• Dimensionality（attributes 數目）：高維 data 帶來好多挑戰（見 §10 curse of dimensionality）。
• Sparsity：只有「出現」先算數（only presence counts），例如 transaction data 大部分 items 都係 0。
• Resolution：patterns 取決於 scale（例如以「日」睇天氣同以「年」睇氣候見到嘅 pattern 唔同）。
• Size：分析類型可能取決於 data 大小。

3.2 Types of Data Sets (Slides 13–23)

4. Data Quality (Section 2.1)

Slide 24：Poor data quality negatively affects many data processing efforts. Thomas C. Redman (2004) 估計差劣 data quality 令一般公司損失至少 10%（更可能係 20%）revenue。

Data Mining 例子：用差劣 data 建一個偵測 loan risk 嘅 classification model，結果：

• 一啲 credit-worthy 嘅申請人被拒絕貸款（誤判為高風險）
• 更多貸款批俾會 default 嘅人

Slide 25 提出三個問題：有咩 data quality 問題？點偵測？點處理？問題例子：Noise and outliers、Missing values、Duplicate data、Wrong data、Fake data。

4.1 Noise (Slide 26)

• 對 objects：noise 係一個外來 (extraneous) 嘅 object。
• 對 attributes：noise 指原本數值被修改 (modification of original values)。
• 例子：電話線差時聲音失真、電視雪花 ("snow")。
• Slide 圖：兩條不同頻率嘅 sine waves、合併後嘅波、再加 random noise → 原 signal 嘅 magnitude 同 shape 被扭曲。

4.2 Outliers (Slide 27)

Outliers are data objects with characteristics that are considerably different than most of the other data objects in the data set.

• Case 1：Outliers 係 noise，干擾分析 → 要處理 / 移除。
• Case 2：Outliers 正正係分析目標 → 例如 credit card fraud、intrusion detection（Anomaly Detection）。

4.3 Missing Values (Slides 28–29)

原因：(1) 資料冇收集到（例如人哋拒絕提供年齡同體重）；(2) Attribute 唔適用於所有 cases（例如小朋友冇 annual income）。

處理方法：

• Eliminate data objects 或 variables（刪 row / 刪 column）
• Estimate missing values（例如 time series of temperature 用前後值估；census results）
• Ignore the missing value during analysis

ExamSlide 29：三種 missingness 機制：

import pandas as pd
from sklearn.impute import SimpleImputer, KNNImputer

df = pd.DataFrame({"age": [25, None, 40, 35], "income": [20, 30, None, 50]})
df.dropna()                                   # Eliminate data objects
SimpleImputer(strategy="mean").fit_transform(df)  # 用 attribute 本身 mean 填
KNNImputer(n_neighbors=2).fit_transform(df)       # 用其他 attributes 相似嘅 rows 估計

4.4 Duplicate Data (Slide 30)

• Data set 可能有完全重複或幾乎重複嘅 objects。
• 合併來自 heterogeneous sources 嘅 data 時係主要問題，例如同一個人有多個 email addresses。
• Data cleaning：處理 duplicate data 嘅過程。
• Slide 問：幾時唔應該移除 duplicate data？——例如兩個真係唔同嘅人碰巧所有 attributes 都一樣（同名同年齡）；或者 transaction data 入面同一客戶買兩次同一樣嘢，每次都係真實購買，刪咗會低估銷量。

5. Similarity & Dissimilarity (Section 2.2)

Slide 32 定義：

Proximity refers to a similarity or dissimilarity（兩者統稱）。

5.1 Simple Attributes (Slide 33)

對單一 attribute，兩個 objects $x$、$y$ 嘅 similarity $s$ 同 dissimilarity $d$（教科書標準表）：

例：Ordinal attribute quality = {poor, fair, OK, good, wonderful} → {0,1,2,3,4}，$n = 5$。$x = \text{good}$ (3)、$y = \text{fair}$ (1)：$d = |3-1|/4 = 0.5$，$s = 0.5$。

6. Distance Measures

6.1 Euclidean Distance (Slides 34–35)

其中 $n$ 係 dimensions（attributes）數目，$x_k$、$y_k$ 係 objects $\mathbf{x}$、$\mathbf{y}$ 嘅第 $k$ 個 attributes。Standardization is necessary, if scales differ.

6.2 Minkowski Distance (Slides 36–38)

Minkowski Distance 係 Euclidean Distance 嘅推廣 (generalization)：

$r$ 係參數。Slide 37 例子：

6.3 Worked example：四點 distance matrices

Slide 35 同 38 用四點例子展示 distance matrix（圖片未能擷取）。以下用 4 點自行計算：$p_1 = (0, 2)$、$p_2 = (2, 0)$、$p_3 = (3, 1)$、$p_4 = (5, 1)$。

例如 $d(p_1, p_2)$：差 = (2, −2)。$L_1 = 2 + 2 = 4$；$L_2 = \sqrt{4+4} = 2.828$；$L_\infty = \max(2, 2) = 2$。

$d(p_1, p_4)$：差 = (5, −1)。$L_1 = 6$；$L_2 = \sqrt{25+1} = 5.099$；$L_\infty = 5$。

import numpy as np
from scipy.spatial.distance import cdist
P = np.array([[0, 2], [2, 0], [3, 1], [5, 1]])
print(cdist(P, P, "cityblock"))   # L1
print(cdist(P, P, "euclidean"))   # L2
print(cdist(P, P, "chebyshev"))   # L∞ (supremum)
print(cdist(P, P, "minkowski", p=3))

6.4 Mahalanobis Distance (Slides 39–40)

其中 $\Sigma$ 係 data 嘅 covariance matrix（有啲版本會再開平方根）。佢考慮咗 attributes 之間嘅 correlation 同各自嘅 variance：沿住 data 分佈「長軸」方向嘅差距會被打折，沿「短軸」方向嘅差距會被放大。

Slide 39 例子：圖中兩個紅點，Euclidean distance 係 14.7，但 Mahalanobis distance 只係 6——因為兩點雖然直線距離遠，但係沿住 data 嘅主要分佈方向排列，以 data 嘅分佈嚟講其實「唔算遠」。Slide 40 例子：$\text{Mahal}(A, B) = 2.27$、$\text{Mahal}(A, C) = 2$。

6.5 Common Properties of a Distance (Slide 41)

Exam設 $d(\mathbf{x},\mathbf{y})$ 為兩點之間嘅 distance：

驗證 triangle inequality（用上面 L2 表）：$d(p_1, p_4) = 5.099 \le d(p_1, p_3) + d(p_3, p_4) = 3.162 + 2 = 5.162$ ✓。

6.6 Common Properties of a Similarity (Slide 42)

1. $s(\mathbf{x},\mathbf{y}) = 1$（或 maximum similarity）only if $\mathbf{x}=\mathbf{y}$。呢條唔一定成立，例如 cosine：$x = (1, 2)$ 同 $y = (2, 4)$ 唔相等，但 $\cos = 1$。
2. Symmetry：$s(\mathbf{x},\mathbf{y}) = s(\mathbf{y},\mathbf{x})$ for all $\mathbf{x},\mathbf{y}$。

7. Similarity Between Binary Vectors: SMC vs Jaccard

Slide 43：當 objects $x$、$y$ 只有 binary attributes，先數四個 quantities：

• $f_{01}$：$x$ 係 0、$y$ 係 1 嘅 attributes 數目
• $f_{10}$：$x$ 係 1、$y$ 係 0
• $f_{00}$：$x$ 係 0、$y$ 係 0
• $f_{11}$：$x$ 係 1、$y$ 係 1

x = 1 0 0 0 0 0 0 0 0 0
y = 0 0 0 0 0 0 1 0 0 1

再練習：$x = 1\ 1\ 0\ 1\ 0$、$y = 1\ 0\ 0\ 1\ 1$ → $f_{11}=2, f_{10}=1, f_{01}=1, f_{00}=1$；$SMC = 3/5 = 0.6$；$JC = 2/4 = 0.5$。

8. Cosine Similarity

Slide 45：如果 $d_1$、$d_2$ 係兩個 document vectors：

$\langle d_1, d_2\rangle$ 係 inner product（dot product），$\|d\|$ 係 vector 嘅長度 $\sqrt{\sum d_k^2}$。

d1 = 3 2 0 5 0 0 0 2 0 0
d2 = 1 0 0 0 0 0 0 1 0 2

import numpy as np
d1 = np.array([3,2,0,5,0,0,0,2,0,0]); d2 = np.array([1,0,0,0,0,0,0,1,0,2])
print(d1 @ d2 / (np.linalg.norm(d1) * np.linalg.norm(d2)))   # 0.3150

9. Information-based Measures: Entropy & Mutual Information

9.1 Information and Probability (Slide 46)

• Information 同一件事（event）嘅可能結果有關：傳送訊息、擲硬幣、量度一個 data。
• 越確定嘅結果，包含越少 information，反之亦然。例如一個兩面都係 head 嘅硬幣，擲出 head 冇提供任何 information。
• 量化嚟講：結果嘅 probability 越細，提供嘅 information 越多。
• Entropy 係最常用嘅量度。

9.2 Entropy (Slides 47–50)

對一個有 $n$ 個可能結果 $x_1,\dots,x_n$、概率 $p_1,\dots,p_n$ 嘅 variable $X$：

ExamEntropy 介乎 0 同 $\log_2 n$，單位係 bits：即平均需要幾多 bits 去表示 $X$ 嘅一個 observation。所有結果機會均等時 entropy 最大（$\log_2 n$）；只有一個結果必然發生時 entropy = 0。（約定 $0 \log_2 0 = 0$）

Coin 例子 (slide 48)：head 概率 $p$，tail 概率 $q = 1-p$：

• Fair coin $p = q = 0.5$：$H = -0.5(-1) - 0.5(-1) = 1$ bit
• $p = 1$ 或 $q = 1$：$H = 0$
• Slide 問：fair four-sided die 嘅 entropy？答：4 個結果各 1/4，$H = -4 \times \frac14 \log_2 \frac14 = -\log_2 \frac14 = \mathbf{2}$ bits（= $\log_2 4$，最大值）。

Sample data 版本 (slide 50)：有 $m$ 個 observations，第 $i$ 類有 $m_i$ 個：

Continuous data 計算較難。

9.3 Mutual Information (Slides 51–55)

Mutual Information = 一個 variable 提供關於另一個 variable 嘅 information：

$H(X,Y)$ 係 joint entropy，$p_{ij}$ 係 $X$ 第 $i$ 個值同 $Y$ 第 $j$ 個值同時出現嘅概率。Discrete variables 好易計。Discrete variables 嘅 maximum $MI = \log_2(\min(n_X, n_Y))$。

Slide 53（完全依賴）：Undergrad 50 / Grad 50；Grade A 50 / B 50；joint：Undergrad-A 50、Grad-B 50、其餘 0。$H(\text{Status}) = 1$、$H(\text{Grade}) = 1$、$H(\text{Status}, \text{Grade}) = 1$ → $I = 1 + 1 - 1 = \mathbf{1}$。知道 status 就完全知道 grade。（此時 $I = H(X) = H(Y)$，亦等於 maximum $\log_2 \min(2,2) = 1$。）

Slide 54（獨立）：四個組合各 25 → $H(\text{Status}, \text{Grade}) = 2$ → $I = 1 + 1 - 2 = \mathbf{0}$。兩者完全冇關係。

9.4 Maximal Information Coefficient (MIC) (Slide 56)

出自 Reshef et al. (2011, Science)，將 mutual information 應用於兩個 continuous variables：

1. 考慮將 variables 分成 discrete categories 嘅所有可能 binnings，限制 $n_X \times n_Y \le N^{0.6}$（$n_X$、$n_Y$ 係 X、Y 嘅 bins 數，$N$ 係樣本數）。
2. 計每個 binning 嘅 mutual information。
3. 用 $\log_2(\min(n_X, n_Y))$ normalize（令結果喺 0 至 1）。
4. 取最高值。

10. Combining Similarities (Slides 57–58)

當 attributes 類型各異但需要一個整體 similarity：

1. 對第 $k$ 個 attribute 計一個喺 [0, 1] 嘅 similarity $s_k(\mathbf{x},\mathbf{y})$。
2. 定義 indicator $\delta_k$：$\delta_k = 0$ 如果第 $k$ 個 attribute 係 asymmetric attribute 而兩個 objects 都係 0，或者其中一個 object 喺該 attribute 有 missing value；否則 $\delta_k = 1$。
3. 計算：

Using Weights (slide 58)：可能唔想所有 attributes 一視同仁，用 non-negative weights $\omega_k$：

亦可定義 weighted distance：$d(\mathbf{x},\mathbf{y}) = \left(\sum_{k=1}^{n} w_k |x_k-y_k|^r\right)^{1/r}$。

11. Data Preprocessing (Section 2.3)

Slide 60 列出六種 preprocessing：Aggregation、Sampling、Dimensionality Reduction、Feature subset selection、Discretization and Binarization、Attribute Transformation。

11.1 Aggregation (Slides 61–63)

Combining two or more attributes (or objects) into a single attribute (or object). 目的：

• Data reduction：減少 attributes 或 objects 數目（例：PCA、Factor Analysis）。
• Change of scale：cities 合併成 regions / states / countries；days 合併成 weeks / months / years（例：moving average、kernel smoothing）。
• More "stable" data：aggregated data tends to have less variability。

Australia 降雨例子（1982–1993，3,030 個 0.5° × 0.5° grid cells）：比較「average monthly precipitation 嘅 standard deviation」同「average yearly precipitation 嘅 standard deviation」嘅 histograms → 年平均嘅 variability 比月平均細（單位：cm）。

import pandas as pd
# 每日數據 aggregate 成每月 → 變化較細、較穩定
monthly = df.groupby(df["date"].dt.to_period("M"))["rain"].mean()

11.2 Sampling (Slides 64–67)

Sampling 係 data reduction 嘅主要技術，用於初步探索同最終分析。

• Statisticians sample：因為取得全部 data 太貴或太耗時。
• Data Mining sample：因為處理全部 data 太貴或太耗時。

Sample Size (slide 66)：圖示 8000、2000、500 點——sample 太細會失去 data 嘅結構（例如 clusters 變得唔清楚）。

Types of Sampling (slide 67)：

df.sample(n=500, replace=False, random_state=0)     # without replacement
df.sample(n=500, replace=True, random_state=0)      # with replacement
df.groupby("cls", group_keys=False).apply(lambda g: g.sample(frac=0.1))  # stratified

11.3 Curse of Dimensionality (Slide 68)

ExamWhen dimensionality increases, data becomes increasingly sparse in the space that it occupies. Clustering 同 outlier detection 依賴嘅 density 同 distance 定義變得冇咁有意義。

Slide 實驗：隨機產生 500 點，計任何兩點之間 max distance 同 min distance 嘅差（相對差）。隨住維度上升，呢個相對差趨向 0 → 「最近」同「最遠」嘅點距離差唔多，nearest neighbor 失去意義。

11.4 Dimensionality Reduction (Slides 69–70)

Purpose：避免 curse of dimensionality；減少演算法所需時間同 memory；令 data 更易 visualize；可能幫助消除 irrelevant features 或減少 noise。

Techniques：Principal Components Analysis (PCA)、Singular Value Decomposition (SVD)、Factor Analysis、其他（supervised 同 non-linear techniques）。

PCA：Goal is to find a projection that captures the largest amount of variation in data。Slide 70 圖示 $x_1$、$x_2$ 平面上一條方向 $e$（data 分佈最闊嘅方向），將點投影落 $e$ 上就由 2 維變 1 維而保留最多 variance。詳細內容會喺最後一章講。

11.5 Feature Subset Selection (Slide 71)

另一種減少 dimensionality 嘅方法（揀 subset，而唔係創造新 features）：

• Redundant features：重複其他 attributes 嘅大部分或全部資訊。例：產品 purchase price 同已付 sales tax（highly correlated）。
• Irrelevant features：對當前 data mining task 冇用嘅資訊。例：student ID 對預測 GPA 通常無關。
• 有好多技術，特別係 classification 同 regression 嘅 variable selection。

11.6 Discretization (Slides 72–79)

ExamDiscretization is the process of converting a continuous attribute into an ordinal attribute：潛在無限多個值被 map 去少數 categories。常用於 classification，因為好多 classification algorithms 喺 independent 同 dependent variables 都只有少數值時表現最好。

Iris 例子（slides 73–75）：Iris data set（Douglas Fisher；R: iris）有 3 個 classes（Setosa、Versicolour、Virginica）同 4 個 attributes（sepal width / length、petal width / length）。將 petal width / length discretize 成 low / medium / high 後：

• Petal width low 或 petal length low → Setosa
• Petal width medium 或 petal length medium → Versicolour
• Petal width high 或 petal length high → Virginica

點樣知道最好嘅 discretization？

• Unsupervised discretization：只喺 data values 搵 breaks（例：petal length）。
• Supervised discretization：用 class labels 去搵 breaks（例如揀令每個 bin 入面 class 最純、entropy 最低嘅切點）。

Discretization Without Using Class Labels（slides 76–79）：data 有四組點同兩個 outliers（一維，加咗 random y 減少重疊）：

import pandas as pd
x = pd.Series([1, 2, 3, 4, 5, 10, 11, 12, 40, 50])
pd.cut(x, bins=3)     # equal interval width
pd.qcut(x, q=3)       # equal frequency

11.7 Binarization (Slide 80)

• 將 continuous 或 categorical attribute map 成一個或多個 binary variables。
• 通常用於 association analysis（需要 asymmetric binary attributes）。
• 常見做法：先將 continuous attribute 轉成 categorical，再將 categorical 轉成一組 binary attributes。
• 例子：eye color；height measured as {low, medium, high} → 三個 binary 欄 height_low、height_medium、height_high。

pd.get_dummies(pd.Series(["low", "high", "medium", "low"]), prefix="height")

11.8 Attribute Transformation (Slide 81)

An attribute transform is a function that maps the entire set of values of a given attribute to a new set of replacement values such that each old value can be identified with one of the new values.

• Simple functions：$x^k$、$\log(x)$、$e^x$、$|x|$（slide 上符號係圖片，此為教科書標準例子）。例如 income 好 right-skewed，用 $\log$ 可以壓縮大數。
• Normalization：調整 attributes 之間喺 frequency of occurrence、mean、variance、range 上嘅差異；亦可移除 unwanted common signal（例如 seasonality）。
• 喺 statistics，standardization 指減 mean 再除以 standard deviation。

from sklearn.preprocessing import StandardScaler, MinMaxScaler
StandardScaler().fit_transform(df[["height", "income"]])   # z-score（注意 sklearn 用 population sd, ddof=0）
MinMaxScaler().fit_transform(df[["height", "income"]])

自我測驗 Self-test

一頁總結 Cheat sheet