Ch2 Data

Similarity & Distance

  • Similarity(相似性) :
    • 兩個Data Object數值有多相近
    • 值域 : 通常為0 ~ 1
  • Dissimilarity(相異性) :
    • 兩個Data Object數值差異多大
    • 值域 : 0 ~ 某上限值
  • Proximity(鄰近性) : 上面兩種之總稱
  • Euclidean Distance(歐基里德距離) : $d(x,y)=\sqrt{\sum_{k=1}^n (x_k-y_k)^2}$
  • Minkowski Distance(閔可夫斯基距離) : $d(x,y)=\sqrt[r]{\sum_{k=1}^n {|x_k-y_k|}^r}$
    • $r=1$ : Manhattan Distance(曼哈頓距離)/$L_1$ norm，e.g. Hamming Distance
    • $r=2$ : Euclidean Distance
    • $r \to \infty$ : Supremum Distance/$L_\infty$
  • Mahalanobis Distance(馬哈拉諾比斯距離) : $\text{mahalanobis}(x,y)=(x-y)^T {\sum}^{-1} (x-y)$
  • metric(測度) : 符合Common Properties的Distance
  • Cosine Similarity : $cos(d_1,d_2)=\frac{<d_1,d_2>}{|d_1||d_2|}$
  • Binary Vectors之間的Similarity :
    • $f_{xy}$ : $p$為$x$、$q$為$y$的Attribute數量
    • SMC(Simple Matching Coefficient / 簡單匹配係數) : $\frac{f_{11}+f_{00}}{f_{01}+f_{10}+f_{11}+f_{00}}$
    • J(Jaccard Coefficient / 雅卡爾係數) : $\frac{f_{11}}{f_{01}+f_{10}+f_{11}}$
  • Entropy(熵) :
    • Def : $$H(X)=-\sum_{i=1}^{n} p_i log_2 p_i$$
    • 作用 : $X$的測量平均需要多少個bits
    • Joint Entropy(聯合熵) : $H(X,Y)=-\sum_i \sum_j p_{ij} log_2 p_{ij}$
    • Mutual Information(互通資訊) : $$I(X,Y)=H(X)+H(Y)-H(X,Y)$$
  • Density(密度) :
    • Def : 測量Data Object在指定區域內相互接近的程度
    • 常用於Clustering與Anomaly Detection
    • Ex :
      • Euclidean Density : 每單位體積的point數
      • Probability Density : 估計資料的分布情況
      • Graph-based Density : 連接性

Data Preprocessing

  • Aggregation(聚合) :
    • Def : 合併2種以上的Attributes pr Objects成1種
    • 目的 : 資料減少、刻度改變、變異性低
  • Sampling(取樣) :
    • 如果Sample與原始資料有相同的特徵，則代表此Sample擁有代表性
    • 種類 :
      • Simple Random Sampling(簡單隨機取樣) : 取樣時有/無Replacement
      • Stratified Sampling(分層取樣) : 把資料切成多個Partitions，再從每個Partition取樣
  • Dimensionality Reduction(維度降低) :
    • 維度越高，則資料越稀疏
    • 目的 : 降低運算time與memory、容易視覺化、可能會移除不相關特徵或Noise
    • 技術 : Principal Components Analysis (PCA / 主成分分析)
      • Def : 找到一預測結果，能抓取資料中最大的變化量
  • Feature subset Selection :
    • Redundant features : 類似延伸屬性，e.g. 產品價格與其稅金
    • Irrelevant features : 與資料探勘目標無關之特徵，e.g. 預測學生GPA模型中的學生ID
  • Feature Creation :
    • Def : 創造新的Attribute，去提取資料中更重要的資訊
    • 常見方法 : 特徵提取、特徵建構、映射資料到新空間
  • Discretization(離散化) :
    • Def : Continuous Attribute → Ordinal Attribute
    • 種類 :
      • 非監督式離散化 : 從資料值中找出breaks
      • 監督式離散化 : 運用class labels找出breaks
  • Binarization(二值化) :
    • Def : Continuous Attribute → Categorical Attribute → Binary Attribute
    • 常用於相關性分析
  • Attribute Transformation :
    • Simple function
    • Normalization(正規化) : 調整Attribute中出現頻率、平均值、平方差與範圍的差異，以去除部需要/不常見的信號
    • Standardization(標準化)