分類技術(shù)概論及前沿問題

1、分類技術(shù)概論及前沿問題,2020/7/30,1,主要內(nèi)容,2020/7/30,2,數(shù)據(jù)分類的簡含義,我們都曾經(jīng)有這樣的經(jīng)驗(yàn)，在人流攢動(dòng)的電影院門口等待相約而至的朋友，通過找尋與識別，能夠在人群中一下子發(fā)現(xiàn)熟悉的臉，其實(shí)這個(gè)過程就是一個(gè)數(shù)據(jù)分類的過程。 相較于要發(fā)現(xiàn)的知識完全未知的無監(jiān)督學(xué)習(xí)，數(shù)據(jù)分類是一種典型的有監(jiān)督的機(jī)器學(xué)習(xí)方法，目的是從一組已知類別的數(shù)據(jù)中發(fā)現(xiàn)分類模型，以預(yù)測新數(shù)據(jù)的未知類別。,2020/7/30,3,2020/7/30,4,用剛才我們提到的尋找朋友的過程舉例，首先從自己熟知的朋友身上提取特點(diǎn)，比如臉型、身材、穿著等，這就形成了一個(gè)簡單的分類模型。 然后在電影院門前對每一個(gè)

2、發(fā)現(xiàn)的陌生人進(jìn)行判斷，“是朋友”或者“不是朋友”，從而對新數(shù)據(jù)進(jìn)行了預(yù)測。,x,x,分類技術(shù)的應(yīng)用,2020/7/30,5,信用卡審批,科學(xué)研究,銀行,醫(yī)療,商業(yè),圖形處理,有效性分析,故障檢測,醫(yī)療診斷,目標(biāo)市場定位,工業(yè),數(shù)據(jù)分類技術(shù),數(shù)據(jù)分類的過程,2020/7/30,6,一個(gè)完整的數(shù)據(jù)分類過程一般包括模型構(gòu)造、模型測試和模型應(yīng)用三個(gè)步驟，具體來說，我們可以將數(shù)據(jù)分成兩個(gè)數(shù)據(jù)集，分別是訓(xùn)練集和測試集，用于模型構(gòu)造和模型測試。整體的步驟說明如下。,2020/7/30,7,數(shù)據(jù)分類的過程詳解,2020/7/30,8,數(shù)據(jù)分類方法介紹,現(xiàn)在我們使用的分類方法中比較常用的有決策樹方法、神經(jīng)網(wǎng)絡(luò)方

3、法、遺傳算法、支持向量機(jī)，除此以外還有粗糙集理論以及貝葉斯分類等方法，上圖詳細(xì)列出了現(xiàn)階段正在使用的各種分類方法，下面將對重要方法進(jìn)行介紹。,2020/7/30,9,2020/7/30,10,決策樹分類法,所謂“決策樹”，顧名思義，它具有樹狀結(jié)構(gòu)，根據(jù)層次的不同，節(jié)點(diǎn)分為根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)三類，每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)樣本集，根節(jié)點(diǎn)作為“樹根”，對應(yīng)的是整個(gè)樣本集，內(nèi)部節(jié)點(diǎn)類似于樹干枝杈，對應(yīng)樣本子集，葉節(jié)點(diǎn)就相當(dāng)于樹葉了，對應(yīng)一個(gè)類標(biāo)志。根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)含有一個(gè)對于樣本屬性的測試，根據(jù)測試的結(jié)果將樣本集劃分為兩個(gè)或者多個(gè)子集，每個(gè)子集形成一個(gè)分支，由葉節(jié)點(diǎn)內(nèi)的類標(biāo)志來標(biāo)識，就像樹不斷分散的枝杈

4、莖葉一樣，如右圖所示。,我們用制造廠商經(jīng)常使用會(huì)員分類案例來進(jìn)一步說明決策樹的使用方法，在分類模型中，以年齡作為屬性，根節(jié)點(diǎn)對應(yīng)的是整個(gè)樣本集即所有參與某自行車廠商調(diào)查的顧客，內(nèi)部節(jié)點(diǎn)對應(yīng)樣本子集，比如年齡在67歲以上的顧客群體。根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)含有一個(gè)對于樣本屬性的測試，即對年齡加以限制的測試。 使用1000個(gè)會(huì)員事例訓(xùn)練模型后得到的決策樹分類如下：,2020/7/30,11,圖中矩形表示一個(gè)拆分節(jié)點(diǎn)，矩形中文字是拆分條件。矩形顏色深淺代表此節(jié)點(diǎn)包含事例的數(shù)量，顏色越深包含的事例越多，如全部節(jié)點(diǎn)包含所有的1000個(gè)事例，顏色最深。,節(jié)點(diǎn)中的條包含兩種顏色，紅色和藍(lán)色，分別表示此節(jié)點(diǎn)中的事例購

5、買和不購買自行車的比例。這樣一來，便可以通過條件得出在哪個(gè)年齡段的哪些地區(qū)的人，最容易購買自行車，至此建立了模型。,隨后可以從新導(dǎo)入一批已知數(shù)據(jù)進(jìn)行模型測試，完成這個(gè)步驟，如果模型可用，便將其他的會(huì)員在分類模型中查找就可預(yù)測會(huì)員購買自行車的概率有多大，隨后自行車廠商就可以有選擇性的投遞廣告冊。,神經(jīng)網(wǎng)絡(luò)分類法,人類的大腦有近1000億個(gè)神經(jīng)元和十倍于此的神經(jīng)膠質(zhì)細(xì)胞。神經(jīng)網(wǎng)絡(luò)是一種具有若干連續(xù)處理結(jié)點(diǎn)的并行計(jì)算系統(tǒng)，它建立了一種數(shù)學(xué)模型，試圖去模仿人類的大腦。 神經(jīng)網(wǎng)絡(luò)將每一個(gè)連接看作一個(gè)處理單元，這些處理單元結(jié)點(diǎn)通常稱作神經(jīng)元，來表明腦神經(jīng)之間的關(guān)系。,2020/7/30,12,2020/7

6、/30,13,神經(jīng)元采用一系列數(shù)學(xué)函數(shù)，通過匯總和轉(zhuǎn)換對數(shù)據(jù)進(jìn)行處理，一個(gè)神經(jīng)元的功能有限，但若干個(gè)神經(jīng)元連接起來形成系統(tǒng)后，就可以創(chuàng)建一個(gè)智能模型，神經(jīng)元可以有許多種不同的方式互連，為了更精確地?cái)M合需要對建立模型的數(shù)據(jù)反復(fù)訓(xùn)練若干次，甚至上千次。 下圖是神經(jīng)網(wǎng)絡(luò)算法模擬人類大腦神經(jīng)元的詳細(xì)示例。,2020/7/30,14,為了更具體地明確神經(jīng)網(wǎng)絡(luò)算法的概念，我們用銀行對用戶劃分推廣不同的信用卡案例做分析。下圖中每個(gè)橢圓型節(jié)點(diǎn)接受輸入數(shù)據(jù)，將數(shù)據(jù)處理后輸出。輸入層節(jié)點(diǎn)接受客戶信息的輸入，然后將數(shù)據(jù)傳遞給隱藏層，隱藏層將數(shù)據(jù)傳遞給輸出層，輸出層輸出客戶屬于哪類信用卡。這類似于人腦神經(jīng)元受到刺激時(shí)

7、，神經(jīng)脈沖從一個(gè)神經(jīng)元傳遞到另一個(gè)神經(jīng)元。,在大量客戶事例輸入后，模型會(huì)不斷調(diào)整，使之更吻合真實(shí)情況，就像是人腦通過在同一脈沖反復(fù)刺激下改變神經(jīng)鍵連接強(qiáng)度來進(jìn)行學(xué)習(xí)。,2020/7/30,15,遺傳算法,“物競天擇，適者生存”是達(dá)爾文生物進(jìn)化論的基本原理，解釋了物種總是向著更適應(yīng)自然界的方向進(jìn)化的規(guī)律，只有適應(yīng)自然環(huán)境的個(gè)體才能幸存下來，繁衍后代，適應(yīng)力差的會(huì)在競爭中被淘汰。遺傳算法（Genetic Algorithms）從字面上看便是繼承生物學(xué)的，它模擬大自然中種群在選擇壓力下的演化，從而得到問題的一個(gè)近似解。,2020/7/30,16,遺傳算法流程,在遺傳算法中，對于一個(gè)最優(yōu)化問題，一定數(shù)

8、量的候選解（稱為個(gè)體）的抽象表示（稱為染色體）使得種群向更好的解進(jìn)化。進(jìn)化從完全隨機(jī)個(gè)體的種群開始，之后一代一代發(fā)生。在每一代中，整個(gè)種群的適應(yīng)度被評價(jià)，從當(dāng)前種群中隨機(jī)地選擇多個(gè)個(gè)體，通過自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當(dāng)前種群，具體的流程見右圖。,2020/7/30,17,為了使理解更加容易，我們引用網(wǎng)絡(luò)上面一個(gè)有趣的例子。首先，我們知道生物個(gè)體長什么樣子很大程度上是由染色體上的基因決定的。同樣，如果我們把100個(gè)半透明三角形組成的東西看成一個(gè)生物個(gè)體，比如扇貝，我們也可以說它的樣子是由這些三角形的具體位置和顏色決定的。所以，我們可以把一個(gè)一個(gè)的半透明三角形看

9、作是這些扇貝的“基因”。而組成扇貝的這100個(gè)基因就組成了每個(gè)扇貝個(gè)體的“染色體”。,程序的目的，是讓由100個(gè)三角形組成的扇貝，最終看上去像是Firefox的圖標(biāo)，我們模擬生物界的繁衍行為，選擇兩個(gè)原有的扇貝，然后從這兩個(gè)扇貝的染色體中隨機(jī)選取一共100個(gè)基因組成新個(gè)體的染色體。在定義好基因，寫好繁衍、變異、評價(jià)適應(yīng)性、淘汰和終止的代碼之后，我們隨機(jī)產(chǎn)生一個(gè)適當(dāng)大小的種群，然后讓它這樣一代代的繁衍、變異和淘汰下去，到最后終止時(shí)會(huì)看到右上角圖的結(jié)果。,2020/7/30,18,支持向量機(jī),簡單概括，支持向量機(jī)用線性分類器劃分樣本空間，但是也可以處理線性不可分的情況。可分的時(shí)候存在超平面把訓(xùn)練集

10、一分為二，支持向量機(jī)能找到一個(gè)最優(yōu)的決策面，把訓(xùn)練集最好地分割成兩類樣本，對于線性不可分的情況則是用核函數(shù)把樣本映射到一個(gè)高維空間中，然后在這個(gè)空間中尋找超平面分割兩種類別，正如右圖所示，左邊的是復(fù)雜的低維空間樣本分散，線性不可分，但通過核函數(shù)的映射，可以建立一個(gè)簡單的高維空間，在里面尋找到超平面。,2020/7/30,19,統(tǒng)計(jì)分類法,統(tǒng)計(jì)分類,貝葉斯分類算法,回歸算法,貝葉斯網(wǎng)絡(luò),線性回歸,邏輯回歸,樸素貝葉斯,2020/7/30,20,粗糙集理論,1982年，波蘭科學(xué)家Z.Pawlak提出了粗糙集理論，用來表示不精確或者不確定的概念。眾所周知，精確的概念有確定的邊界或者說外延，比如說“人

11、”，而不精確的概念外延是沒有確定邊界的，比如“發(fā)達(dá)國家”。粗糙集理論把一個(gè)集合的個(gè)體分為肯定屬于、肯定不屬于以及無法確定三類，通過上近似和下近似（見下圖）運(yùn)算，一個(gè)不精確的概念可以用一組精確的概念表示出來。,2020/7/30,21,K-近鄰算法,K-近鄰算法把一組已知類別的歷史數(shù)據(jù)作為訓(xùn)練樣本集，根據(jù)已知樣本的類別對新樣本進(jìn)行分類。 它的思想如下：首先，計(jì)算新樣本與訓(xùn)練樣本之間的距離，找到距離最近的K個(gè)鄰居，然后根據(jù)這些鄰居所屬的類別來判斷新樣本的類別，如果它們都屬于同一個(gè)類別，那么新樣本也是這個(gè)類別的，否則，對每個(gè)候選類別進(jìn)行評分，按照某種規(guī)則確定新樣本的類別。下圖以不同像素焦距的相機(jī)價(jià)格

12、舉例，要求出新樣本的價(jià)格，可以通過訓(xùn)練樣本的值進(jìn)行判斷。,2020/7/30,22,2020/7/30,23,評價(jià)分類方法的標(biāo)準(zhǔn),上文中介紹了許多分類方法，不同的分類方法有自己的特點(diǎn)，分類的效果和數(shù)據(jù)有關(guān)，有的數(shù)據(jù)噪聲大，有的存在缺失，有的分布系數(shù)，有的屬性間的相關(guān)性強(qiáng)，有的屬性是離散的，有的屬性是連續(xù)的或者混合的，因此，通用的分類方法并不存在。對于一個(gè)分類方法進(jìn)行評價(jià)要考慮一下幾個(gè)方面的問題。,2020/7/30,24,常用分類方法評述,2020/7/30,25,2020/7/30,26,2020/7/30,27,2020/7/30,28,人臉識別系統(tǒng)定義,人臉識別作為圖像分析與理解的一個(gè)應(yīng)

13、用領(lǐng)域，在近些年得到了研究界及向光領(lǐng)域的充分重視，在公安（罪犯識別等）、安全驗(yàn)證系統(tǒng)、信用卡驗(yàn)證、醫(yī)學(xué)、檔案管理、視頻會(huì)議、人機(jī)交互系統(tǒng)等方面都有著巨大應(yīng)用前景。特別是在奧運(yùn)會(huì)中，人臉識別技術(shù)了很大發(fā)展。右圖是北京奧運(yùn)會(huì)中人臉識別系統(tǒng)的日常運(yùn)行。,2020/7/30,29,人臉識別的步驟,在人臉識別領(lǐng)域內(nèi)，近期比較前沿的技術(shù)為S.Rowels等人提出的LLE算法，此算法主要在特征提取中起作用，不僅能夠有效地發(fā)現(xiàn)數(shù)據(jù)的非線性結(jié)構(gòu)，同時(shí)還具有平移、旋轉(zhuǎn)不變性。四川大學(xué)采用這種非線性降維方法提取人臉特征，然后將提取出來的特征輸入到BP神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練得到人臉的類間判別信息，最后進(jìn)行人臉識別，該方法承接國家自然科學(xué)基金委的奧運(yùn)重點(diǎn)項(xiàng)目，研究結(jié)果已經(jīng)在北京奧運(yùn)會(huì)中得以體現(xiàn)。,2020/7/30,30,四川大學(xué)LLE與BP神經(jīng)網(wǎng)絡(luò)算法流程,利用四川大學(xué)的新近研究方法進(jìn)行人臉識別的