數(shù)據(jù)挖掘相關(guān)的數(shù)學(xué)基礎(chǔ)

面對(duì)復(fù)雜數(shù)據(jù)，數(shù)據(jù)挖掘的基本流程是：首先對(duì)原始數(shù)據(jù)進(jìn)行填補(bǔ)遺漏、消除異常、平滑噪聲等處理，提高數(shù)據(jù)挖掘的有效性和準(zhǔn)確性。然后使用專門的算法對(duì)原始數(shù)據(jù)進(jìn)行歸納抽象，去掉取之過多且不均勻的屬性和概念層次樹中不存在的屬性，最終得到一個(gè)關(guān)系模型。當(dāng)新的數(shù)據(jù)加入數(shù)據(jù)集中時(shí)，可以根據(jù)該關(guān)系模型決定新數(shù)據(jù)的分類和處理模式。同時(shí)，新數(shù)據(jù)也將帶來對(duì)整體模型的變化，數(shù)據(jù)和模型處于動(dòng)態(tài)對(duì)應(yīng)的狀態(tài)。

從以上過程中可以明顯感到，所謂數(shù)據(jù)挖掘，就是一個(gè)典型的數(shù)學(xué)建模過程。當(dāng)然，這里已經(jīng)有較為成熟的工具、方法和理論。例如，統(tǒng)計(jì)機(jī)器學(xué)習(xí)所需要的主要理論和技術(shù):泛函分析、逼近論與測度論、統(tǒng)計(jì)理論、VC維理論、覆蓋數(shù)、描述長度理論與算法復(fù)雜度研究、核方法、非線性規(guī)劃技術(shù)、幾何變換。下文簡要介紹涉及的數(shù)學(xué)學(xué)科。

1. 線性代數(shù)和統(tǒng)計(jì)學(xué)

在這個(gè)建模過程中，基礎(chǔ)是兩大數(shù)學(xué)學(xué)科：線性代數(shù)和統(tǒng)計(jì)學(xué)。這代表了機(jī)器學(xué)習(xí)中最主流的兩大類方法的基礎(chǔ)。一種是以研究函數(shù)和變換為重點(diǎn)的代數(shù)方法，比如降維，特征值提取等，一種是以研究統(tǒng)計(jì)模型和樣本分布為重點(diǎn)的統(tǒng)計(jì)方法，比如圖模型、信息理論模型等。它們側(cè)重雖有不同，但是常常是共同使用的，對(duì)于代數(shù)方法，往往需要統(tǒng)計(jì)上的解釋，對(duì)于統(tǒng)計(jì)模型，其具體計(jì)算則需要代數(shù)的幫助。以代數(shù)和統(tǒng)計(jì)為出發(fā)點(diǎn)，繼續(xù)往深處走，我們會(huì)發(fā)現(xiàn)需要更多的數(shù)學(xué)。傳統(tǒng)的統(tǒng)計(jì)學(xué)所研究的主要是漸進(jìn)理論(大樣本情況下的統(tǒng)計(jì)性質(zhì))，而樣本數(shù)目通常有限(甚至還十分有限)。人們過去一直采用樣本數(shù)目無窮為假設(shè)條件推導(dǎo)各種算法，然后將算法用于樣本較小的情況，希望能有較好的效果，然而，算法往往不令人滿意。由此，人們提出了學(xué)習(xí)的推廣能力（泛化能力）的重要問題。過去多數(shù)工作集中在對(duì)大樣本統(tǒng)計(jì)學(xué)習(xí)方法的改進(jìn)和修改，或利用啟發(fā)式方法設(shè)計(jì)特殊算法。

2、微積分

微積分只是數(shù)學(xué)分析體系的基礎(chǔ)。其基礎(chǔ)性作用不言而喻。機(jī)器學(xué)習(xí)研究的大部分問題是在連續(xù)的度量空間進(jìn)行的，無論代數(shù)還是統(tǒng)計(jì)，在研究優(yōu)化問題的時(shí)候，對(duì)一個(gè)映射的微分或者梯度的分析總是不可避免。

3、泛函分析

泛函分析體現(xiàn)了數(shù)學(xué)模型從特殊到一般的發(fā)展過程。

函數(shù)在19世紀(jì)前期的定義還是數(shù)與數(shù)的對(duì)應(yīng)關(guān)系，空間的概念也只有歐幾里德空間。十九世紀(jì)以來，數(shù)學(xué)的發(fā)展進(jìn)入了一個(gè)新的階段。這就是，由于對(duì)歐幾里得第五公理的研究，引出了非歐幾何這門新的學(xué)科；對(duì)于代數(shù)方程求解的一般思考，最后建立并發(fā)展了群論；對(duì)數(shù)學(xué)分析的研究又建立了集合論。這些新的理論都為用統(tǒng)一的觀點(diǎn)把古典分析的基本概念和方法一般化準(zhǔn)備了條件。泛函分析作為數(shù)學(xué)分析的分支，將函數(shù)擴(kuò)展到函數(shù)與函數(shù)之間的關(guān)系，乃至任意兩個(gè)集合之間的關(guān)系，空間則從有限維空間拓展到無限維空間。

在這個(gè)地方，函數(shù)以及其所作用的對(duì)象之間存在的對(duì)偶關(guān)系扮演了非常重要的角色。機(jī)器學(xué)習(xí)發(fā)展至今，也在向無限維延伸——從研究有限維向量的問題到以無限維的函數(shù)為研究對(duì)象。內(nèi)核學(xué)習(xí)和高斯過程是其中典型的例子。

4、測度理論

這是和實(shí)分析關(guān)系非常密切的學(xué)科。概率本身就是一種測度。測度理論對(duì)于機(jī)器學(xué)習(xí)的意義是根本的，現(xiàn)代統(tǒng)計(jì)學(xué)整個(gè)就是建立在測度理論的基礎(chǔ)之上——雖然初級(jí)的概率論教科書一般不這樣引入。在一些統(tǒng)計(jì)方面的文章中它們會(huì)把統(tǒng)計(jì)的公式改用測度來表達(dá)，這樣做有兩個(gè)好處：所有的推導(dǎo)和結(jié)論不用分別給連續(xù)分布和離散分布各自寫一遍了，這兩種東西都可以用同一的測度形式表達(dá)：連續(xù)分布的積分基于Lebesgue測度，離散分布的求和基于計(jì)數(shù)測度，而且還能推廣到那種既不連續(xù)又不離散的分布中去。而且，即使是連續(xù)積分，如果不是在歐氏空間進(jìn)行，而是在更一般的拓?fù)淇臻g（比如微分流形或者變換群），那么就不能使用傳統(tǒng)的黎曼積分了，需要使用，比如哈爾測度或者Lebesgue-Stieltjes積分。

5、拓?fù)鋵W(xué)

這是學(xué)術(shù)中很基礎(chǔ)的學(xué)科。它一般不直接提供方法，但是它的很多概念和定理是其它數(shù)學(xué)分支的基石?？春芏鄤e的數(shù)學(xué)的時(shí)候，會(huì)經(jīng)常接觸這樣一些概念：開集，閉集，連續(xù)函數(shù)度量空間,柯西序列,鄰接性,連續(xù)性。很多這些也許在大學(xué)一年級(jí)就學(xué)習(xí)過一些，當(dāng)時(shí)是基于極限的概念獲得的。但是看過拓?fù)鋵W(xué)之后，對(duì)這些概念的認(rèn)識(shí)會(huì)有根本性的拓展。值得一提的是，計(jì)算機(jī)學(xué)科的基礎(chǔ)布爾代數(shù)與拓?fù)鋵W(xué)有重要的聯(lián)系。

6、圖論

圖，由于它在表述各種關(guān)系的強(qiáng)大能力以及優(yōu)雅的理論，高效的算法，越來越受到數(shù)據(jù)挖掘領(lǐng)域的歡迎。而從目前我所接觸的范圍內(nèi)，圖論僅在數(shù)據(jù)結(jié)構(gòu)這門課中提到過。經(jīng)典圖論，在數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)最重要應(yīng)用就是圖模型了，它被成功運(yùn)用于分析統(tǒng)計(jì)網(wǎng)絡(luò)的結(jié)構(gòu)和規(guī)劃統(tǒng)計(jì)推斷。例如，分析社交網(wǎng)絡(luò)的用戶關(guān)系，常用鄰接鏈表和鄰接矩陣綜合表示。在遍歷時(shí)也離不開深度優(yōu)先和廣度優(yōu)先算法。