數(shù)據(jù)挖掘分類

數(shù)據(jù)挖掘分類Classification

主要用于對離散得數(shù)據(jù)進(jìn)行預(yù)測分為兩步:根據(jù)訓(xùn)練集,構(gòu)造分類模型(訓(xùn)練集中每個元組得分類標(biāo)號事先已經(jīng)知道)估計(jì)分類模型得準(zhǔn)確性,如果其準(zhǔn)確性可以接受得話,則利用她來對未來數(shù)據(jù)進(jìn)行分類Prediction:構(gòu)造、使用模型來對某個樣本得值進(jìn)行估計(jì),例如預(yù)測某個不知道得值或者缺失值主要用于對連續(xù)或有序得數(shù)據(jù)進(jìn)行預(yù)測Typicalapplications信譽(yù)評估醫(yī)學(xué)診斷性能預(yù)測Classificationvs、Prediction2Classification—ATwo-StepProcess

模型構(gòu)造階段:describingasetofpredeterminedclasses假定每個元組/樣本都屬于某個預(yù)定義得類,這些類由分類標(biāo)號屬性所定義用來構(gòu)造模型得元組/樣本集被稱為訓(xùn)練集(trainingset)模型一般表示為:分類規(guī)則,決策樹或者數(shù)學(xué)公式模型使用階段:forclassifyingfutureorunknownobjects估計(jì)模型得準(zhǔn)確性用一些已知分類標(biāo)號得測試集和由模型進(jìn)行分類得結(jié)果進(jìn)行比較兩個結(jié)果相同所占得比率稱為準(zhǔn)確率測試集和訓(xùn)練集必須不相關(guān)如果準(zhǔn)確性可以接受得話,使用模型來對那些不知道分類標(biāo)號得數(shù)據(jù)進(jìn)行分類。3ClassificationProcess(1):ModelConstructionTrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’Classifier(Model)4ClassificationProcess(2):UsetheModelinPredictionClassifierTestingDataUnseenData(Jeff,Professor,4)Tenured?5分類和預(yù)測相關(guān)問題(1):數(shù)據(jù)預(yù)處理數(shù)據(jù)清洗對數(shù)據(jù)進(jìn)行預(yù)處理,去掉噪聲,對缺失數(shù)據(jù)進(jìn)行處理(用某個最常用得值代替或者根據(jù)統(tǒng)計(jì)用某個最可能得值代替)相關(guān)分析(特征選擇)去掉某些不相關(guān)得或者冗余得屬性數(shù)據(jù)轉(zhuǎn)換對數(shù)據(jù)進(jìn)行概括(如將連續(xù)得值離散成若干個區(qū)域,將街道等上升到城市)對數(shù)據(jù)進(jìn)行規(guī)范化,將某個屬性得值縮小到某個指定得范圍之內(nèi)6分類和預(yù)測相關(guān)問題(2):對分類方法進(jìn)行評價準(zhǔn)確性:分類準(zhǔn)確性和預(yù)測準(zhǔn)確性速度和可伸縮性構(gòu)造模型得時間(訓(xùn)練時間)使用模型得時間(分類/預(yù)測時間)魯棒性能夠處理噪聲和缺失數(shù)據(jù)可伸縮性對磁盤級得數(shù)據(jù)庫有效

易交互性模型容易理解,具有較好得洞察力7VisualizationofaDecisionTreeinSGI/MineSet3、017十月20248大家有疑問的，可以詢問和交流可以互相討論下，但要小聲點(diǎn)Supervisedvs、UnsupervisedLearningSupervisedlearning(classification)Supervision:Thetrainingdata(observations,measurements,etc、)areacpaniedbylabelsindicatingtheclassoftheobservationsNewdataisclassifiedbasedonthetrainingsetUnsupervisedlearning(clustering)TheclasslabelsoftrainingdataisunknownGivenasetofmeasurements,observations,etc、withtheaimofestablishingtheexistenceofclassesorclustersinthedata10簡單例子分類兩歲寶寶,給她看幾個水果,并告訴她:紅得圓得就是蘋果,橘黃得圓得就是橘子(建模型)拿一個水果問寶寶:這個水果,紅得圓得,就是什么？(用模型)聚類兩歲寶寶,給她一堆水果,告訴她:根據(jù)顏色分成兩堆。寶寶會將蘋果分成一堆,橘子分成一堆。假如告訴她:根據(jù)大小分成3堆,則寶寶會根據(jù)大小分成3堆,蘋果和橘子可能會放在一起。11主要內(nèi)容分類和預(yù)測貝葉斯分類、神經(jīng)網(wǎng)絡(luò)分類預(yù)測12BayesianClassification就是一種基于統(tǒng)計(jì)得分類方法,用來預(yù)測諸如某個樣本屬于某個分類得概率有多大基于Bayes理論研究發(fā)現(xiàn),Na?veBayesClassifier在性能上和DecisionTree、NeuralNetworkclassifiers相當(dāng)。在應(yīng)用于大數(shù)據(jù)集時,具有較高得準(zhǔn)確率和速度Na?veBayesClassifier假設(shè)屬性值之間就是獨(dú)立得,因此可以簡化很多計(jì)算,故稱之為Na?ve。當(dāng)屬性值之間有依賴關(guān)系時,采用BayesianBeliefNetworks進(jìn)行分類。13BayesianTheorem:Basics假設(shè)X就是未知分類標(biāo)號得樣本數(shù)據(jù)H代表某種假設(shè),例如X屬于分類C

P(H|X):給定樣本數(shù)據(jù)X,假設(shè)H成立得概率例如,假設(shè)樣本數(shù)據(jù)由各種水果組成,每種水果都可以用形狀和顏色來描述。如果用X代表紅色并且就是圓得,H代表X屬于蘋果這個假設(shè),則P(H|X)表示,已知X就是紅色并且就是圓得,則X就是蘋果得概率。14BayesianTheorem:BasicsP(H):拿出任一個水果,不管她什么顏色,也不管她什么形狀,她屬于蘋果得概率P(X):拿出任一個水果,不管她就是什么水果,她就是紅色并且就是圓得概率P(X|H):一個水果,已知她就是一個蘋果,則她就是紅色并且就是圓得概率。15BayesianTheorem:Basics現(xiàn)在得問題就是,知道數(shù)據(jù)集里每個水果得顏色和形狀,看她屬于什么水果,求出屬于每種水果得概率,選其中概率最大得。也就就是要算:P(H|X)但事實(shí)上,其她三個概率,P(H)、P(X)、P(X|H)都可以由已知數(shù)據(jù)得出,而P(H|X)無法從已知數(shù)據(jù)得出Bayes理論可以幫助我們:16Na?veBayesClassifier每個數(shù)據(jù)樣本用一個n維特征向量表示,描述由屬性對樣本得n個度量。假定有m個類。給定一個未知得數(shù)據(jù)樣本X(即,沒有類標(biāo)號),分類法將預(yù)測X屬于具有最高后驗(yàn)概率(條件X下)得類。即,樸素貝葉斯分類將未知得樣本分配給類Ci,當(dāng)且僅當(dāng):這樣,我們最大化。其最大得類Ci稱為最大后驗(yàn)假定。根據(jù)貝葉斯定理:

17Na?veBayesClassifier由于P(X)對于所有類為常數(shù),只需要最大即可。如果類得先驗(yàn)概率未知,則通常假定這些類就是等概率得;即,。并據(jù)此只對最大化。否則,我們最大化。類得先驗(yàn)概率可以用計(jì)算;其中,si就是類C中得訓(xùn)練樣本數(shù),而s就是訓(xùn)練樣本總數(shù)。18Na?veBayesClassifier給定具有許多屬性得數(shù)據(jù)集,計(jì)算得開銷可能非常大。為降低計(jì)算得開銷,可以樸素地假設(shè)屬性間不存在依賴關(guān)系。這樣,

概率,,…,可以由訓(xùn)練樣本估計(jì),其中,(a)

如果Ak就是分類屬性,則;其中sik就是在屬性Ak上具有值xk得類Ci得訓(xùn)練樣本數(shù),而si就是Ci中得訓(xùn)練樣本數(shù)(b)

如果就是連續(xù)值屬性,則通常假定該屬性服從高斯分布。因而,

其中,給定類Ci得訓(xùn)練樣本屬性Ak得值,就是屬性Ak得高斯密度函數(shù),而分別為平均值和標(biāo)準(zhǔn)差。19Na?veBayesClassifier為對未知樣本X分類,對每個類Ci,計(jì)算。樣本X被指派到類Ci,當(dāng)且僅當(dāng):

換言之,X被指派到其最大得類Ci。20TrainingdatasetClass:C1:buys_puter=‘yes’C2:buys_puter=‘no’DatasampleX=(age<=30,Ine=medium,Student=yesCredit_rating=Fair)21Na?veBayesianClassifier:AnExampleputeP(X|Ci)foreachclass

P(buys_puter=“yes”)=9/14=0、643 P(buys_puter=“no”)=5/14=0、357

P(age=“<30”|buys_puter=“yes”)=2/9=0、222P(age=“<30”|buys_puter=“no”)=3/5=0、6P(ine=“medium”|buys_puter=“yes”)=4/9=0、444P(ine=“medium”|buys_puter=“no”)=2/5=0、4P(student=“yes”|buys_puter=“yes)=6/9=0、667P(student=“yes”|buys_puter=“no”)=1/5=0、2P(credit_rating=“fair”|buys_puter=“yes”)=6/9=0、667P(credit_rating=“fair”|buys_puter=“no”)=2/5=0、4X=(age<=30,ine=medium,student=yes,credit_rating=fair)

P(X|Ci):P(X|buys_puter=“yes”)=0、222x0、444x0、667x0、667=0、044P(X|buys_puter=“no”)=0、6x0、4x0、2x0、4=0、019P(X|Ci)*P(Ci):P(X|buys_puter=“yes”)*P(buys_puter=“yes”)=0、044x0、643=0、028

P(X|buys_puter=“no”)*P(buys_puter=“no”)=0、019x0、357=0、007Therefore,Xbelongstoclass“buys_puter=yes” 22Na?veBayesianClassifier:ments優(yōu)點(diǎn)易于實(shí)現(xiàn)多數(shù)情況下結(jié)果較滿意缺點(diǎn)假設(shè):屬性間獨(dú)立,丟失準(zhǔn)確性實(shí)際上,屬性間存在依賴處理依賴BayesianBeliefNetworks23主要內(nèi)容分類和預(yù)測貝葉斯分類、神經(jīng)網(wǎng)絡(luò)分類預(yù)測24神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)就是以模擬人腦神經(jīng)元得數(shù)學(xué)模型為基礎(chǔ)而建立得,她由一系列神經(jīng)元組成,單元之間彼此連接。25神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)有三個要素:拓?fù)浣Y(jié)構(gòu)、連接方式、學(xué)習(xí)規(guī)則可以從這三方面對神經(jīng)網(wǎng)絡(luò)進(jìn)行分類26神經(jīng)網(wǎng)絡(luò)得拓?fù)渖窠?jīng)網(wǎng)絡(luò)得拓?fù)浣Y(jié)構(gòu):神經(jīng)網(wǎng)絡(luò)得單元通常按照層次排列,根據(jù)網(wǎng)絡(luò)得層次數(shù),可以將神經(jīng)網(wǎng)絡(luò)分為單層神經(jīng)網(wǎng)絡(luò)、兩層神經(jīng)網(wǎng)絡(luò)、三層神經(jīng)網(wǎng)絡(luò)等結(jié)構(gòu)簡單得神經(jīng)網(wǎng)絡(luò),在學(xué)習(xí)時收斂得速度快,但準(zhǔn)確度低。神經(jīng)網(wǎng)絡(luò)得層數(shù)和每層得單元數(shù)由問題得復(fù)雜程度而定。問題越復(fù)雜,神經(jīng)網(wǎng)絡(luò)得層數(shù)就越多。例如,兩層神經(jīng)網(wǎng)絡(luò)常用來解決線性問題,而多層網(wǎng)絡(luò)就可以解決多元非線性問題27神經(jīng)網(wǎng)絡(luò)得連接神經(jīng)網(wǎng)絡(luò)得連接:包括層次之間得連接和每一層內(nèi)部得連接,連接得強(qiáng)度用權(quán)來表示。根據(jù)層次之間得連接方式,分為:前饋式網(wǎng)絡(luò):連接就是單向得,上層單元得輸出就是下層單元得輸入,如反向傳播網(wǎng)絡(luò)反饋式網(wǎng)絡(luò):除了單項(xiàng)得連接外,還把最后一層單元得輸出作為第一層單元得輸入,如Hopfield網(wǎng)絡(luò)根據(jù)連接得范圍,分為:全連接神經(jīng)網(wǎng)絡(luò):每個單元和相鄰層上得所有單元相連局部連接網(wǎng)絡(luò):每個單元只和相鄰層上得部分單元相連28神經(jīng)網(wǎng)絡(luò)得學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)得學(xué)習(xí)根據(jù)學(xué)習(xí)方法分:感知器:有監(jiān)督得學(xué)習(xí)方法,訓(xùn)練樣本得類別就是已知得,并在學(xué)習(xí)得過程中指導(dǎo)模型得訓(xùn)練認(rèn)知器:無監(jiān)督得學(xué)習(xí)方法,訓(xùn)練樣本類別未知,各單元通過競爭學(xué)習(xí)。根據(jù)學(xué)習(xí)時間分:離線網(wǎng)絡(luò):學(xué)習(xí)過程和使用過程就是獨(dú)立得在線網(wǎng)絡(luò):學(xué)習(xí)過程和使用過程就是同時進(jìn)行得根據(jù)學(xué)習(xí)規(guī)則分:相關(guān)學(xué)習(xí)網(wǎng)絡(luò):根據(jù)連接間得激活水平改變權(quán)系數(shù)糾錯學(xué)習(xí)網(wǎng)絡(luò):根據(jù)輸出單元得外部反饋改變權(quán)系數(shù)自組織學(xué)習(xí)網(wǎng)絡(luò):對輸入進(jìn)行自適應(yīng)地學(xué)習(xí)29基于神經(jīng)網(wǎng)絡(luò)得分類方法神經(jīng)網(wǎng)絡(luò)經(jīng)常用于分類神經(jīng)網(wǎng)絡(luò)得分類知識體現(xiàn)在網(wǎng)絡(luò)連接上,被隱式地存儲在連接得權(quán)值中。神經(jīng)網(wǎng)絡(luò)得學(xué)習(xí)就就是通過迭代算法,對權(quán)值逐步修改得優(yōu)化過程,學(xué)習(xí)得目標(biāo)就就是通過改變權(quán)值使訓(xùn)練集得樣本都能被正確分類。30基于神經(jīng)網(wǎng)絡(luò)得分類方法神經(jīng)網(wǎng)絡(luò)特別適用于下列情況得分類問題:數(shù)據(jù)量比較小,缺少足夠得樣本建立模型數(shù)據(jù)得結(jié)構(gòu)難以用傳統(tǒng)得統(tǒng)計(jì)方法來描述分類模型難以表示為傳統(tǒng)得統(tǒng)計(jì)模型31基于神經(jīng)網(wǎng)絡(luò)得分類方法缺點(diǎn):需要很長得訓(xùn)練時間,因而對于有足夠長訓(xùn)練時間得應(yīng)用更合適。需要大量得參數(shù),這些通常主要靠經(jīng)驗(yàn)確定,如網(wǎng)絡(luò)拓?fù)?。可解釋性差。該特點(diǎn)使得神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘得初期并不看好。

32基于神經(jīng)網(wǎng)絡(luò)得分類方法優(yōu)點(diǎn):分類得準(zhǔn)確度高并行分布處理能力強(qiáng)分布存儲及學(xué)習(xí)能力高對噪音數(shù)據(jù)有很強(qiáng)得魯棒性和容錯能力最流行得基于神經(jīng)網(wǎng)絡(luò)得分類算法就是80年代提出得后向傳播算法。

33后向傳播算法后向傳播算法在多路前饋神經(jīng)網(wǎng)絡(luò)上學(xué)習(xí)。

34定義網(wǎng)絡(luò)拓?fù)?/p>

在開始訓(xùn)練之前,用戶必須說明輸入層得單元數(shù)、隱藏層數(shù)(如果多于一層)、每一隱藏層得單元數(shù)和輸出層得單元數(shù),以確定網(wǎng)絡(luò)拓?fù)洹?/p>

35定義網(wǎng)絡(luò)拓?fù)?/p>

對訓(xùn)練樣本中每個屬性得值進(jìn)行規(guī)格化將有助于加快學(xué)習(xí)過程。通常,對輸入值規(guī)格化,使得她們落入0、0和1、0之間。離散值屬性可以重新編碼,使得每個域值一個輸入單元。例如,如果屬性A得定義域?yàn)?a0,a1,a2),則可以分配三個輸入單元表示A。即,我們可以用I0,I1,I2作為輸入單元。每個單元初始化為0。如果A=a0,則I0置為1;如果A=a1,I1置1;如此下去。一個輸出單元可以用來表示兩個類(值1代表一個類,而值0代表另一個)。如果多于兩個類,則每個類使用一個輸出單元。36定義網(wǎng)絡(luò)拓?fù)潆[藏層單元數(shù)設(shè)多少個“最好”,沒有明確得規(guī)則。網(wǎng)絡(luò)設(shè)計(jì)就是一個實(shí)驗(yàn)過程,并可能影響準(zhǔn)確性。權(quán)得初值也可能影響準(zhǔn)確性。如果某個經(jīng)過訓(xùn)練得網(wǎng)絡(luò)得準(zhǔn)確率太低,則通常需要采用不同得網(wǎng)絡(luò)拓?fù)浠蚴褂貌煌贸跏紮?quán)值,重復(fù)進(jìn)行訓(xùn)練。

37后向傳播算法后向傳播算法學(xué)習(xí)過程:迭代地處理一組訓(xùn)練樣本,將每個樣本得網(wǎng)絡(luò)預(yù)測與實(shí)際得類標(biāo)號比較。每次迭代后,修改權(quán)值,使得網(wǎng)絡(luò)預(yù)測和實(shí)際類之間得均方差最小。這種修改“后向”進(jìn)行。即,由輸出層,經(jīng)由每個隱藏層,到第一個隱藏層(因此稱作后向傳播)。盡管不能保證,一般地,權(quán)將最終收斂,學(xué)習(xí)過程停止。

算法終止條件:訓(xùn)練集中被正確分類得樣本達(dá)到一定得比例,或者權(quán)系數(shù)趨近穩(wěn)定。38后向傳播算法后向傳播算法分為如下幾步:初始化權(quán)向前傳播輸入向后傳播誤差39后向傳播算法初始化權(quán)網(wǎng)絡(luò)得權(quán)通常被初始化為很小得隨機(jī)數(shù)(例如,范圍從-1、0到1、0,或從-0、5到0、5)。每個單元都設(shè)有一個偏置(bias),偏置也被初始化為小隨機(jī)數(shù)。

對于每一個樣本X,重復(fù)下面兩步:向前傳播輸入向后傳播誤差40向前傳播輸入計(jì)算各層每個單元得輸入和輸出。輸入層:輸出=輸入=樣本X得屬性;即,對于單元j,Oj

=Ij=Xj隱藏層和輸出層:輸入=前一層得輸出得線性組合,即,對于單元j,Ij=∑wijOi+θj

i輸出=41向后傳播誤差計(jì)算各層每個單元得誤差。向后傳播誤差,并更新權(quán)和偏置計(jì)算各層每個單元得誤差。輸出層單元j,誤差

Oj就是單元j得實(shí)際輸出,而Tj就是j得真正輸出。隱藏層單元j,誤差

wjk就是由j到下一層中單元k得連接得權(quán)Errk就是單元k得誤差42向后傳播誤差更新權(quán)和偏差,以反映傳播得誤差。 權(quán)由下式更新: 其中,

wij就是權(quán)wij得改變。l就是學(xué)習(xí)率,通常取0和1之間得值。 偏置由下式更新: 其中,

j就是偏置

j得改變。

43后向傳播算法OutputnodesInputnodesHiddennodesOutputvectorInputvector:xiwijExample設(shè)學(xué)習(xí)率為0、9。訓(xùn)練樣本X={1,0,1}類標(biāo)號為1x1x2x3w14w15w24w25W34w35w46w56

4

5

61010、2-0、30、40、1-0、50、2-0、3-0、2-0、40、20、1單元j凈輸入Ij輸出Oj4560、2+0-0、5-0、4=-0、7-0、3+0+0、2+0、2=0、1(-0、3)(0、332)-(0、2)(0、525)+0、1=-0、1051+(1+e0、7)=0、3321+(1+e-0、1)=0、5251+(1+e-0、105)=0、474單元jErrj654(0、474)(1-0、474)(1-0、474)=0、1311(0、525)(1-0、525)(0、1311)(-0、2)=-0、0065(0、332)(1-0、332)(0、1311)(-0、3)=-0、02087權(quán)或偏差新值w46w56w14w15w24w25w34w35

6

5

4-0、3+(0、9)(0、1311)(0、332)=-0、261-0、2+(0、9)(0、1311)(0、525)=-0、1380、2+(0、9)(-0、0087)(1)=0、192-0、3+(0、9)(0、0065)(1)=-0、3060、4+(0、9)(-0、0087)(0)=0、40、1+(0、9)(-0、0065)(0)=0、1-0、5+(0、9)(-0、0087)(1)=-0、5080、2+(0、9)(-0、0065)(1)=0、1940、1+(0、9)(0、1311)=0、2180、2+(0、9)(-0、0065)=0、194-0、4+(0、9)(-0、0087)=-0、40817十月202445主要內(nèi)容分類和預(yù)測貝葉斯分類、神經(jīng)網(wǎng)絡(luò)分類預(yù)測