數(shù)據(jù)挖掘:理論與算法筆記2-數(shù)據(jù)預(yù)處理

上一篇: 數(shù)據(jù)挖掘:理論與算法筆記1-走進(jìn)數(shù)據(jù)科學(xué)
下一篇: [數(shù)據(jù)挖掘:理論與算法筆記3-從貝葉斯到?jīng)Q策樹(shù)]
(http://www.itdecent.cn/p/61e5ea13dfc8)

2. 數(shù)據(jù)預(yù)處理: 抽絲剝繭，去偽存真

2.1 數(shù)據(jù)清洗

數(shù)據(jù)缺失有以下幾種類型
a. Missing completely at random: 缺失的概率是隨機(jī)的，比如門店的計(jì)數(shù)器因?yàn)閿嚯姅嗑W(wǎng)等原因在某個(gè)時(shí)段數(shù)據(jù)為空。
b. Missing conditionally at random: 數(shù)據(jù)是否缺失取決于另外一個(gè)屬性，比如一些女生不愿意填寫(xiě)自己的體重。
c. Not missing at random: 數(shù)據(jù)缺失與自身的值有關(guān)，比如高收入的人可能不愿意填寫(xiě)收入。

處理的辦法也有幾種類型
a. 刪數(shù)據(jù)，如果缺失數(shù)據(jù)的記錄占比比較小，直接把這些記錄刪掉完事。
b. 手工填補(bǔ)，或者重新收集數(shù)據(jù)，或者根據(jù)domain knowledge來(lái)補(bǔ)數(shù)據(jù)。
c. 自動(dòng)填補(bǔ)，簡(jiǎn)單的就是均值填充，或者再加一個(gè)概率分布看起來(lái)更真實(shí)些，也可以結(jié)合實(shí)際情況通過(guò)公式計(jì)算，比如門店計(jì)數(shù)缺失，我們就是參考過(guò)往的客流數(shù)據(jù)，轉(zhuǎn)化數(shù)據(jù)，缺失時(shí)段的銷售額，用一個(gè)簡(jiǎn)單公式自動(dòng)計(jì)算回補(bǔ)。

Outlier(離群點(diǎn))

Outlier在數(shù)據(jù)挖掘中是一件很麻煩的事情，比如我們收集了一堆身高數(shù)據(jù)，其中有一個(gè)人是姚明，他的身高值就會(huì)顯得特別突兀。這對(duì)某些算法影響很大，比如最小二乘，

2.2 異常值與重復(fù)數(shù)據(jù)監(jiān)測(cè)

局部離群點(diǎn)因子(Local Outlier Factor, LOF)

對(duì)比某一點(diǎn)的局部密度和臨近區(qū)域的密度, A點(diǎn)的局部密度遠(yuǎn)低于其臨近區(qū)域的密度，所以A就是一個(gè)離群點(diǎn)

LOF算法邏輯如下:
a. 計(jì)算k-distance of A：點(diǎn)A的第k距離，也就距離A第k遠(yuǎn)的點(diǎn)的距離，不包括A, 記為k-distance(p)

b. 計(jì)算k-distance neighborhood of A：點(diǎn)A的第k距離鄰域，就是A的第k距離以內(nèi)的所有點(diǎn)，包括第k距離, 記為Nk(A) [k為下角標(biāo)]

c. 計(jì)算reachability-distance：可達(dá)距離，若小于第k距離，則可達(dá)距離為第k距離，若大于第k距離，則可達(dá)距離為真實(shí)距離

d. 計(jì)算local reachability density：局部可達(dá)密度, 密度越高則可達(dá)距離之和越小，而LRD越大

e. 計(jì)算local outlier factor: 局部離群因子

下圖來(lái)自wikipedia, 上面的數(shù)字標(biāo)明了相應(yīng)點(diǎn)的LOF得分，可以讓人對(duì)LOF有一個(gè)直觀的印象。

Duplicate Records

如果高度疑似的樣本是挨著的，就可以用滑動(dòng)窗口對(duì)比，為了讓相似記錄相鄰，可以每條記錄生成一個(gè)hash key, 根據(jù)key去排序。

2.3 類型轉(zhuǎn)換與采樣

經(jīng)過(guò)了缺失填充和去重，有了error free的數(shù)據(jù)集之后還需要做一些轉(zhuǎn)換工作，比如說(shuō)類型。數(shù)據(jù)類型有Continues，Discrete，Ordinal(比如優(yōu)良中差), Nominal(比如職業(yè)), Nominal比較特殊，我們用one-hot encoding就好了。

采樣

為了解決數(shù)據(jù)庫(kù)IO瓶頸，可以通過(guò)對(duì)數(shù)據(jù)采樣來(lái)降低時(shí)間復(fù)雜度，Aggregation也是減少數(shù)據(jù)量的一種方式。

大多數(shù)機(jī)器學(xué)習(xí)算法假設(shè)數(shù)據(jù)是均勻分布的，實(shí)際上經(jīng)常會(huì)遇到不平衡數(shù)據(jù)集，，此時(shí)多數(shù)類主導(dǎo)少數(shù)類，分類器更偏向于多數(shù)類。當(dāng)數(shù)據(jù)量足夠大的時(shí)候應(yīng)當(dāng)考慮減少多數(shù)類的大小來(lái)平衡數(shù)據(jù)集，這叫欠采樣，當(dāng)數(shù)據(jù)量不足時(shí)應(yīng)該嘗試增加稀有樣本數(shù)量來(lái)平衡數(shù)據(jù)集，這叫過(guò)采樣。如果少數(shù)類樣本實(shí)在采集不到了，考慮通過(guò)隨機(jī)過(guò)采樣算法合成少數(shù)類，比如SMOTE(Synthetic Minority Oversampling Technique)

整體準(zhǔn)確率不適用與不平衡數(shù)據(jù)集，需要引入新的度量模式比如G-mean, 它會(huì)看正類上的準(zhǔn)確率，再看負(fù)類上的準(zhǔn)確率，然后兩者相乘。

另一種度量模式是F-measure, 常見(jiàn)于衡量推薦算法。F-Measure是Precision和Recall加權(quán)調(diào)和平均:

當(dāng)參數(shù)α=1時(shí)就是最常見(jiàn)的F1

2.4 數(shù)據(jù)描述與可視化

正則化

因?yàn)閿?shù)據(jù)的衡量單位不一，可以用Normalization把數(shù)據(jù)映射到[0.1]區(qū)間，常見(jiàn)的有min-max normalization和z-score normalization.

均值度量

數(shù)據(jù)的一般性描述有mean, median, mode, variance.
mean是均值，median取數(shù)據(jù)排序后在中間位置的值，避免因?yàn)闃O端離群點(diǎn)影響客觀評(píng)價(jià), mode是出現(xiàn)頻率最高的元素，其實(shí)用的比較少，variance則是衡量數(shù)據(jù)集與其均值的偏離。

數(shù)據(jù)相關(guān)性

統(tǒng)計(jì)學(xué)之父Pearson有兩個(gè)相關(guān)系數(shù)公式
Pearson correlation coefficient如下:

r是一個(gè)-1到1之間的值，r>0則正相關(guān)，r<0則負(fù)相關(guān), 注意r=0嚴(yán)格意義也不能說(shuō)不相關(guān)，只能說(shuō)非線性相關(guān)。

Pearson chi-square公式如下:

這兩公式都是計(jì)算相關(guān)性的，顯然前者適用與有metric data的情況，后者適用于分類統(tǒng)計(jì)的情況。

可視化

一維數(shù)據(jù)圓餅圖，柱狀圖；二維數(shù)據(jù)散點(diǎn)圖；三維數(shù)據(jù)用三維坐標(biāo)呈現(xiàn)；高維數(shù)據(jù)需要先做轉(zhuǎn)換或映射，比如用matlab的Box Plots，也可以用平行坐標(biāo)呈現(xiàn)。

最后介紹了兩個(gè)軟件
CiteSpace(呈現(xiàn)文章引用情況), Gephi可以把元素之間關(guān)系用網(wǎng)絡(luò)形式展現(xiàn)(如社交關(guān)系)，下圖為Gephi生成:


要對(duì)Gephi了解更多可以看底部reference中知乎的一篇文章。

2.5 特征選擇

這節(jié)開(kāi)始介紹Feature Selection和Feature Extraction兩個(gè)核心算法
當(dāng)我們做特定分析的時(shí)候，可能屬性非常多，但有些屬性是不相關(guān)的，有些屬性是重復(fù)的，所以我們需要用Feature Selection挑選出來(lái)最相關(guān)的屬性降低問(wèn)題難度。

熵增益(Entropy Information Gain)

假設(shè)我們遇到的特定問(wèn)題是要猜測(cè)某個(gè)人的性別，男女比例的概率各一半，如果沒(méi)有任何額外信息我們隨機(jī)猜測(cè)的結(jié)果只能是五五分。再假設(shè)有60%的人不抽煙，40%的人是煙民，而且抽煙的人95%是男人，5%是女人，不抽煙的人當(dāng)中80%是女人，20%是男人。知道一個(gè)是否抽煙以后再判斷他/她的性別就有把握多了。

此處引入熵(Entropy)的概率來(lái)衡量系統(tǒng)的不確定性，下圖第一行是計(jì)算熵的公式，如果不知道是否抽煙的信息，則熵值為1，即不確定性最高。然后分別計(jì)算出不抽煙人群的熵值為0.7219，抽煙人群的熵值為0.2864，整體熵值為0.5477， 1-0.5477=0.4523, 這個(gè)數(shù)字就是信息增量(Information Gain)

Branch and Bound(分支定界)

如果我們想從n個(gè)屬性中挑選出m個(gè)最優(yōu)屬性，需要注意算法復(fù)雜度會(huì)隨n的增長(zhǎng)呈現(xiàn)指數(shù)級(jí)爆炸增長(zhǎng)，計(jì)算量會(huì)變得非常大，為了降低復(fù)雜度這里引入了分支定界的剪枝算法。比如我們要從5個(gè)屬性中挑選出兩個(gè)相關(guān)性最強(qiáng)的屬性，可以先畫(huà)一個(gè)top-down的搜索樹(shù)，每當(dāng)往下推一層就減少一個(gè)屬性，根據(jù)屬性的單調(diào)性假設(shè)，屬性越少效能越低，所以如果發(fā)現(xiàn)節(jié)點(diǎn)(1,3,4,5)小于左邊某個(gè)只有兩個(gè)屬性的節(jié)點(diǎn)(2,3)的效能，則可以忽略節(jié)點(diǎn)(1,3,4,5)下面的計(jì)算，把這一整支都直接刪除，從而減少計(jì)算量。

特征選擇還有sequential forward, sequential backward, simulated annealing(模擬退火), tabu search(競(jìng)技搜索), genetic algorithms(遺傳算法)等方式去優(yōu)化。

2.6 主成分分析

這一節(jié)講Feature Extraction, 圖像深度識(shí)別提取edge就屬于Feature Extraction.

Principal Component Analysis(主成分分析)

PCA又是Pearson最早提出的，主要目的是降維，分析主成分提取最大的個(gè)體差異變量，削減回歸分析和聚類分析中變量的數(shù)目，方式是通過(guò)正交變換將一系列可能線性相關(guān)的變量轉(zhuǎn)換為一組線性不相關(guān)的新變量。

我們先看一個(gè)二維圖像的例子，左邊是原始數(shù)據(jù)，橫軸和縱軸可以當(dāng)作高和寬，經(jīng)過(guò)轉(zhuǎn)換，實(shí)際是把坐標(biāo)順時(shí)針轉(zhuǎn)動(dòng)了45度，這樣一來(lái)縱軸的差異就很小了, 這需要一點(diǎn)線性代數(shù)知識(shí)來(lái)生成轉(zhuǎn)置矩陣。

下面講一點(diǎn)數(shù)學(xué)(稍微有點(diǎn)繞，還求助了師兄，我真是愧為數(shù)學(xué)系的)，我們希望Y是一個(gè)對(duì)角陣，如果要讓坐標(biāo)變化就要讓原矩陣X乘以一個(gè)旋轉(zhuǎn)矩陣P, n只是一個(gè)scale可以忽略。要確保Y是一個(gè)對(duì)角陣，那么P和Q必須互逆，即Q就是P的轉(zhuǎn)置矩陣。

從另外一個(gè)角度再看，我們希望原點(diǎn)和映射點(diǎn)的距離的平方和最小，即目標(biāo)函數(shù)J(e)最小，經(jīng)過(guò)幾步推到可以看到要讓J(e)最小其實(shí)也就是要讓右下角的S最大。

這就成了一個(gè)帶條件的約束問(wèn)題，可以用拉格朗日乘數(shù)法來(lái)求解。對(duì)e進(jìn)行求導(dǎo)，S是一個(gè)方陣，e是一個(gè)向量，λ是一個(gè)數(shù)值(也就是拉格朗日乘數(shù))，所以這是一個(gè)矩陣分解問(wèn)題。再看上一張圖的推導(dǎo)，其實(shí)我們就是要將λ最大化，而λ也就是特征值。

再看一個(gè)三維圖像的例子，經(jīng)過(guò)映射，pc1的差異最明顯，而pc3被拋棄了，從而變成了二維圖像

我們甚至可以看一個(gè)17維的轉(zhuǎn)換，英國(guó)各地人民對(duì)食物的偏好

經(jīng)過(guò)PCA轉(zhuǎn)換后會(huì)發(fā)現(xiàn)北愛(ài)爾蘭是個(gè)離群點(diǎn)

看回前面的表確實(shí)北愛(ài)爾蘭人吃更多fresh patatoes, 但是少消耗很多fresh fruits, cheese, fish and alcoholic drinks

想像一下，不管多少維空間，我們可以用一根投影軸線插進(jìn)去，讓空間中的每個(gè)點(diǎn)與這個(gè)線上某個(gè)點(diǎn)的距離的平方和最小，線上的這個(gè)點(diǎn)就是高維空間的投影了。

2.7 線性判別分析

PCA屬于非監(jiān)督學(xué)習(xí)，不考慮class information, 如果是有標(biāo)簽的數(shù)據(jù)我們就要用LDA了, 它能夠保留區(qū)分信息。

Linear Discriminant Analysis

LDA的原理是，將帶上標(biāo)簽的數(shù)據(jù)(點(diǎn))，通過(guò)投影的方法，投影到維度更低的空間中，使得投影后的點(diǎn)，會(huì)形成按類別區(qū)分，一簇一簇的情況，相同類別的點(diǎn)，將會(huì)在投影后的空間中更接近。雖然也是降維，但好的LDA算法對(duì)不同類別是有明顯的區(qū)分度的。


LDA的目標(biāo)函數(shù)如下: 分類的目標(biāo)是，使得類別內(nèi)的點(diǎn)距離越近越好（集中），類別間的點(diǎn)越遠(yuǎn)越好。分母表示每一個(gè)類別內(nèi)的方差之和，方差越大表示一個(gè)類別內(nèi)的點(diǎn)越分散，分子為兩個(gè)類別各自的中心點(diǎn)的距離的平方，我們最大化J(w)就可以求出最優(yōu)的w了, 求解同樣會(huì)用到拉格朗日乘數(shù)法

具體的推導(dǎo)我就偷懶省去了，有興趣的可以看底部reference中的鏈接。

上一篇: 數(shù)據(jù)挖掘:理論與算法筆記1-走進(jìn)數(shù)據(jù)科學(xué)
下一篇: [數(shù)據(jù)挖掘:理論與算法筆記3-從貝葉斯到?jīng)Q策樹(shù)]
(http://www.itdecent.cn/p/61e5ea13dfc8)

references:
機(jī)器學(xué)習(xí)-異常檢測(cè)算法（二）：Local Outlier Factor
局部異常因子算法-LOF
Local outlier factor
Fast Branch & Bound Algorithm in Feature Selection
Principal Component AnalysisExplained Visually
降維算法二：LDA（Linear Discriminant Analysis）
介紹用Gephi進(jìn)行數(shù)據(jù)可視化

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 機(jī)器學(xué)習(xí)是做NLP和計(jì)算機(jī)視覺(jué)這類應(yīng)用算法的基礎(chǔ)，雖然現(xiàn)在深度學(xué)習(xí)模型大行其道，但是懂一些傳統(tǒng)算法的原理和它們之間...
    在河之簡(jiǎn)閱讀 20,913評(píng)論 4贊 65
  • 機(jī)器學(xué)習(xí)是做NLP和計(jì)算機(jī)視覺(jué)這類應(yīng)用算法的基礎(chǔ)，雖然現(xiàn)在深度學(xué)習(xí)模型大行其道，但是懂一些傳統(tǒng)算法的原理和它們之間...
    城市中迷途小書(shū)童閱讀 1,186評(píng)論 0贊 11
  • 一日一景 幽深古巷草上墻， 半技秋葉映淺黃。 文人騷客常造訪， 千年文脈個(gè)中藏。
    吉光片羽_9bc2閱讀 589評(píng)論 5贊 20
  • 心里忐忑，一直以來(lái)都害怕被落單，每次都要花很大的力氣融入一個(gè)集體，真的很尷尬，明天會(huì)好過(guò)嗎，咬緊牙關(guān)一直往前沖吧，...
    符小喵閱讀 175評(píng)論 0贊 0
  • 雨中花 細(xì)絲穿花針， 繡出新江城。 百卉沾露珠， 搖曳弄精神。 人流滿街巷， 傘花綻繽紛。 喜看紅濕處， 油然放歌...
    紅葉陳建華閱讀 153評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容