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

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

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

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

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

P(H|X):給定樣本數(shù)據(jù)X,假設H成立得概率例如,假設樣本數(shù)據(jù)由各種水果組成,每種水果都可以用形狀和顏色來描述。如果用X代表紅色并且就是圓得,H代表X屬于蘋果這個假設,則P(H|X)表示,已知X就是紅色并且就是圓得,則X就是蘋果得概率。14BayesianTheorem:BasicsP(H):拿出任一個水果,不管她什么顏色,也不管她什么形狀,她屬于蘋果得概率P(X):拿出任一個水果,不管她就是什么水果,她就是紅色并且就是圓得概率P(X|H):一個水果,已知她就是一個蘋果,則她就是紅色并且就是圓得概率。15BayesianTheorem:Basics現(xiàn)在得問題就是,知道數(shù)據(jù)集里每個水果得顏色和形狀,看她屬于什么水果,求出屬于每種水果得概率,選其中概率最大得。也就就是要算:P(H|X)但事實上,其她三個概率,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(即,沒有類標號),分類法將預測X屬于具有最高后驗概率(條件X下)得類。即,樸素貝葉斯分類將未知得樣本分配給類Ci,當且僅當:這樣,我們最大化。其最大得類Ci稱為最大后驗假定。根據(jù)貝葉斯定理:

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

概率,,…,可以由訓練樣本估計,其中,(a)

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

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

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

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

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

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

34定義網(wǎng)絡拓撲

在開始訓練之前,用戶必須說明輸入層得單元數(shù)、隱藏層數(shù)(如果多于一層)、每一隱藏層得單元數(shù)和輸出層得單元數(shù),以確定網(wǎng)絡拓撲。

35定義網(wǎng)絡拓撲

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

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

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

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

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

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

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

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

wij就是權wij得改變。l就是學習率,通常取0和1之間得值。 偏置由下式更新: 其中,

j就是偏置

j得改變。

43后向傳播算法OutputnodesInputnodesHiddennodesOutputvectorInputvector:xiwijExample設學習率為0、9。訓練樣本X={1,0,1}類標號為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權或偏差新值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)容分類和預測貝葉斯分類、神經(jīng)網(wǎng)絡分類預測