Data Mining（二）：數據預處理

• 2021 年 1 月 5 日
• AI
• 數據挖掘應用

數據品質評估指標

• 準確性
• 完整性
• 一致性
• 時效性
• 可信性
• 可解釋性

數據清理

數據清理（data cleaning）：通過填寫缺失的值，光滑雜訊數據，識別並刪除離群點並解決不一致性來清理數據。數據清洗通常是一個兩步迭代過程，包括偏差檢測和數據變換。

缺失值

• 忽略元組
• 人工填寫缺失值
• 使用一個全局變數填充缺失值
• 使用數據的中心度量填充缺失值：對於對稱數據分布，選擇均值；而傾斜數據分布使用中位數
• 使用與給定元組數同一類的所有樣本的屬性均值或中位數
• 使用最有可能的值填充：通過回歸、決策樹等

雜訊數據

雜訊（noise）是被測量的變數的隨機誤差或方差。

數據光滑技術：

• 分箱（binning）：分箱方法通過考察數據的鄰近值來光滑有序數據值（局部光滑）。有序數據分享後，可分別根據箱均值、箱中位數、箱邊界光滑
• 回歸（regression）：用一個函數你和數據來光滑數據，包括線性回歸和多元線性回歸
• 離群點分析（outlier analysis）：可通過聚類的方法檢測離群點

數據集成

數據集成（data integration）：集成多個資料庫、數據立方體或文件以分析來自多個數據源的數據。

• 實體識別問題
• 屬性冗餘
• 元組重複
• 數據值衝突

實體識別問題

將來自現實世界的多個資訊源的等價實體進行匹配，例如異名同義屬性名的匹配。

• 屬性的元數據包括名字、含義、數據類型和屬性的允許取值範圍，以及處理空白、零和Null值的空值規則

冗餘和相關性分析

冗餘：一個屬性可有另一個或一組屬性導出；或是屬性和維命名的不一致也可能導致冗餘。

部分冗餘可由相關分析檢測，即度量一個屬性在多大程度上蘊涵另一個。

• 標稱數據，使用卡方檢驗\chi ^2進行相關分析；

  • 

  • 將兩個屬性描述數據表為相依表，列為屬性A的c個值，行為屬性B的r個值，見上圖；

  • \chi^{2}=\sum_{i=1}^{c} \sum_{j=1}^{r} \frac{\left(o_{i j}-e_{i j}\right)^{2}}{e_{i j}}，其中o_{i j}是聯合事件(A_i,B_j)的觀測頻度（即實際計數），e_{i j}是(A_i,B_j)的期望頻度，e_{i j}=\frac{\operatorname{count}\left(A=a_{i}\right) \times \operatorname{count}\left(B=b_{j}\right)}{n}，其中n是數據元組的個數，\operatorname{count}\left(A=a_{i}\right)是A中具有值a_i的元組個數，\operatorname{count}\left(B=b_{j}\right)是B中具有值b_j的元組個數；

  • 根據\chi ^2分布的百分點表，查找自由度(r-1)\times(c-1)下的顯著水平，計算值大於該值，拒絕假設，兩屬性相關，反之獨立。

    

  • \chi ^2統計檢驗假設A和B是獨立的；

  • 對\chi ^2值貢獻最大的單元是實際計數與期望技術很不相同的單元。

• 數值數據，使用相關係數和協方差進行相關分析。

  • 屬性A和B的相關係數（Pearson積矩係數）：r_{A, B}=\frac{\sum_{i=1}^{n}\left(a_{i}-\bar{A}\right)\left(b_{i}-\bar{B}\right)}{n \sigma_{A} \sigma_{B}}=\frac{\sum_{i=1}^{n}\left(a_{i} b_{i}\right)-n \bar{A} \bar{B}}{n \sigma_{A} \sigma_{B}}，其中，n為元組個數，\bar A、\bar B分別為對應均值，\sigma_{A}、 \sigma_{B}分別為A/B的標準差。
    • r_{A,B}取值範圍為[-1,1]，該值大於0時，表示正相關，值越大相關性越高；反之亦然。
    • 散點圖可用來觀測屬性之間的相關性；
    • 相關性並不蘊涵因果關係。
  • 屬性A和B的協方差：\operatorname{Cov}(A, B)=E((A-\bar{A})(B-\bar{B}))=\frac{\sum_{i=1}^{n}\left(a_{i}-\bar{A}\right)\left(b_{i}-\bar{B}\right)}{n}=E(A·B)-\bar A \bar B。
    • r_{A,B}=\frac{\operatorname{Cov}(A,B)}{\sigma_a \sigma_b}；
    • 如果A和B獨立，E(A,B)=E(A)·E(B)，Cov(A,B)=0；然而，其逆不成立，即某些隨機變數對的協方差可能為0，卻是非獨立的；
    • 方差是協方差的特殊情況，其中兩個屬性相同，即屬性與其自身的協方差。

數據歸約

數據歸約（data reduction）：得到數據集的簡化表示，它小得多，但能夠產生同樣的分析結果。

• 花費在數據歸約上的時間不應超過或「抵消」在規約後的數據上挖掘所節省的時間。

維歸約

維歸約：減少所考慮的隨機變數數量或屬性的個數。

小波變換

離散小波變換（DWT）是一種線性訊號處理技術，用於將數據向量X變換為不同的數值小波係數向量X^{‘}，兩個向量具有相同的長度。

• 小波係數：一個訊號無論進行連續小波變換（CWT）或是離散小波變換（DWT），變換完的結果就叫小波係數；小波係數是沒有量綱單位的結果，需要經過重構這些係數得到實際有量綱的訊號。
• 雖然小波變換後的數據與原數據長度相等，但小波變換後的數據可以截短，進存放一部分最強的小波係數，就能保留近似的壓縮數據；
• DWT也可用於消除雜訊，而不會光滑掉數據的主要特徵；
• 給定一組小波係數，使用所用的DWT的逆，可以構造原數據的近似；
• 與離散傅里葉變換（DFT）相比，DWT是一種更好的有損壓縮（相同數目係數時DWT更接近原數據；相同近似下DWT需要的空間更小）；小波空間相比DFT的局部性更好，有助於保留局部細節；只有一種DFT，擔憂若干族DWT；
• DWT一般使用層次金字塔演算法，在每次迭代時數據減半，計算速度很快。
  1. 輸入數據向量的長度L必須為2的整數冪，必要時在數據後添加0；
  2. 每個變換應用兩個函數，第一個求和或加權平均進行數據光滑；第二個進行加權差分，提取數據的細節特徵；
  3. 兩個函數分別作用於原數據的所有數據點對(x_{2i},x_{2i+1})，得到兩個長度為L/2的數據集，分別代表輸入數據的光滑後的版本或低頻版本和它的高頻內容；
  4. 遞歸上述過程，直到得到的結果數據集的長度為2；
  5. 由以上迭代得到的數據集中選擇的值被指定為數據變換的小波係數。
• 對輸入數據應用矩陣乘法，也可以得到小波係數；通過將矩陣分解成幾個稀疏矩陣的乘積，對於長度為n的輸入向量，「快速DWT」演算法的複雜度為O(n)。

主成分分析

主成分分析PCA：將n維特徵映射到k維上，這k維是全新的正交特徵也被稱為主成分，是在原有n維特徵的基礎上重新構造出來的k維特徵。基本過程為：

• 對數據規範化，使得每個屬性都落入相同的區間，避免較大定義域屬性對其他屬性的支配；

• PCA計算k個標準正交向量，作為規範化輸入數據的基（輸入數據是主成分的線性組合）；

  • 計算數據矩陣的協方差矩陣；
  • 計算協方差矩陣的特徵值和特徵向量；
    • 特徵值分解協方差矩陣
    • 奇異值分解協方差矩陣
  • 選擇特徵值最大（即方差最大）的k個特徵所對應的特徵向量組成矩陣；
  • 將數據矩陣轉換到新的空間當中，實現數據特徵的降維。

• 與小波變換相比，PCA可以更好的處理稀疏數據，而小波變換更適合高維數據。

屬性子集選擇

屬性子集選擇（特徵子集選擇）：檢測並刪除不相關、弱相關或冗餘的屬性或維。

• 屬性子集選擇通常使用壓縮搜索空間的啟發式演算法，例如典型的貪心演算法：
  • 逐步向前選擇：每一步在原屬性集中確定最好的屬性，將其加入歸約集；
  • 逐步向後刪除：每一步刪除現有屬性集中最差的屬性；
  • 逐步向前選擇和逐步向後刪除的組合：每一步選擇一個最好的屬性，並刪除剩餘屬性中最差的屬性；
  • 決策樹歸納：由給定的數據構造決策樹，不出現在樹中的所有屬性被認為是「無意義」屬性，出現在樹中的屬性形成規約後的屬性子集。
• 屬性構造：通過組合屬性（如高度和寬度組合為面積屬性），發現屬性間聯繫的缺失資訊。

數量歸約

數量規約：用替代的、較小的數據表示形式替換原數據。

• 參數方法：使用模型估計數據，只需存放模型參數而不是實際數據；
• 非參數方法

參數方法

回歸和對數-線性模型

• 線性回歸：利用線性回歸方程的最小二乘函數對一個或多個自變數和因變數之間關係進行建模的一種回歸分析，包括簡單線性回歸和多元線性回歸。
• 對數線性模型：在線性模型的基礎上通過複合函數（sigmoid/softmax/entropy ）將其映射到概率區間，使用對數損失構建目標函數，包括邏輯回歸、最大熵模型和條件隨機場等。

非參數方法

直方圖

• 等寬直方圖：每個桶的區間範圍一致；
• 等頻直方圖：每個桶大致包含相同個數的鄰近數據樣本。

聚類

聚類：將對象劃分為群或簇，使得同一個簇內的對象相似，而與其他簇內的對象相異。

• 簇品質的度量：
  • 直徑——卒中兩個對象的最大距離；
  • 形心距離——簇中每個對象到簇形心的平均距離。

抽樣

• 無放回簡單隨機抽樣SRSWOR

• 有放回簡單隨機抽樣SRSWR

• 簇抽樣

• 分層抽樣：數據分層（分類）後，在每層按比例取樣

• 採用抽樣進行數據規約的好處：花費時間正比於樣本集的大小，而不是數據集的大小，因此抽樣複雜度可能亞線性（sublinear）於數據的大小；

• 對於固定大小的樣本，抽樣複雜度隨數據維數線性增加，而其他技術複雜度呈指數增加。

數據壓縮

數據壓縮：使用變換，得到原數據的規約或「壓縮」表示。如果原數據可由壓縮後的數據重構，而不損失任何資訊，稱為無損壓縮，否則是有損的。

數據變換與數據離散化

數據變換（data transformation）：包括規範化、數據離散化和概念分層產生等。

數據規範化

規範化：把數據屬性按比例縮放，使之落入一個特定的小區間。

• 最小-最大規範化：x^{‘}_{i}=\frac{x_i-min}{mxa-min}(max_{new}-min_{new})+min_{new}；
  • 最小-最大規範化保持原始數據之間的聯繫；
  • 規範化後區間範圍[min_{new},max_{new}]。
• z分數規範化（零均值規範化）：x^{‘}_{i}=\frac{x_i-\bar x}{\sigma_x}；
  • 當數據的最大最小值未知，或離群值左右最小-最大化規範時，使用該方法；
  • 規範化後的區間範圍[\frac{x_{min}-\bar{x}}{\sigma_x},\frac{x_{max}-\bar{x}}{\sigma_x}]。
  • 上式中的標準差\sigma_x可以用均值絕對偏差s_x替換，s_{x}=\frac{1}{n}\left(\left|x_{1}-\bar{x}\right|+\left|x_{2}-\bar{x}\right|+\cdots+\left|x_{n}-\bar{x}\right|\right)，這樣x^{‘}_{i}=\frac{x_i-\bar x}{s_x}；
  • 對於離群點，均值絕對偏差s_x比標準差\sigma_x更加魯棒。
• 小數定標規範化：通過移動數據的小數點未知進行規範化，x_{i}^{‘}=\frac{x_i}{10^j}，其中j是使得max(|x_i^{‘}|)<1成立得最小整數；
  • 規範化後的區間範圍(-1,1)。

數據離散化

• 通過分箱離散化：等寬或等頻分箱，用箱均值或中位數替換箱中的每個值，將屬性離散化；
• 通過直方圖分析離散化：等寬直方圖或等頻直方圖；
• 通過聚類、決策樹和相關分析離散化
  • 聚類——自頂向下的劃分策略或自底向上的合併策略；非監督的；
  • 決策樹——自頂向下的劃分方法；有監督的；主要思想是，選擇劃分點使得一個給定的結果分區包含儘可能多的同類元組，其中，熵是最常用的劃分點度量；
  • 相關性度量可用於離散化——例如ChiMerge是一種基於\chi^{2}的離散化方法。
    • ChiMerge是自底向上的策略；有監督的；
    • ChiMerge過程如下：初始時，將數據按序排好，將數值屬性的每個值看作一個區間；對每個相鄰區間進行\chi^{2}檢驗；將具有最小\chi^{2}值的相鄰區間合併在一起；遞歸合併過程，直到滿足預定義的終止條件。
• 標稱數據的概念分層
  • 基於模式定義或每個屬性的不同值個數產生；
  • 啟發式規則：定義在較高概念層的屬性（如country）與定義在較低概念層的屬性（如street）相比，一般包含較少的不同值，因此，可以根據給定屬性集中每個屬性不同值的個數，自動地產生概念分層，但並不絕對。

TODO

• 小波變換
• 主成分分析（基於特徵值 vs 基於SVD）//blog.csdn.net/program_developer/article/details/80632779
• 簡單線性回歸模型 //zhuanlan.zhihu.com/p/73494604
• 多元線性回歸 //zhuanlan.zhihu.com/p/48541799 //zhuanlan.zhihu.com/p/124902625
• 對數線性模型 //zhuanlan.zhihu.com/p/112816694

參考

1. 《數據挖掘：概念與技術》第三章
2. 小波係數 //blog.csdn.net/hai_girl/article/details/85105540
3. 小波變換通俗解釋 //blog.sina.com.cn/s/blog_13bb711fd0102w9x1.html
4. 白話解釋「差分」、「一階差分」 //zhuanlan.zhihu.com/p/46699931