1Chapter6.分類:AdvancedMethods貝葉斯信念網(wǎng)絡(luò)后向傳播分類ClassificationbyBackpropagation支持向量機SupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)其他分類方法AdditionalTopicsRegardingClassificationSummary1Chapter6.分類:AdvancedMetho12貝葉斯信念網(wǎng)絡(luò)Bayesianbeliefnetworks(又稱為Bayesiannetworks,probabilisticnetworks):允許變量子集間定義類條件獨立(有向無環(huán))因果關(guān)系的圖模型表示變量間的依賴關(guān)系給出了一個聯(lián)合概率分布

Nodes:隨機變量Links:依賴關(guān)系X,Y是Z的雙親,YistheparentofPZ和P間沒有依賴關(guān)系

沒有環(huán)2貝葉斯信念網(wǎng)絡(luò)Bayesianbeliefnetwor23貝葉斯信念網(wǎng)絡(luò):AnExampleFamilyHistory(FH)LungCancer(LC)PositiveXRaySmoker(S)EmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.10.9CPT:ConditionalProbabilityTableforvariableLungCancer:顯示父母的每個可能組合的條件概率從CPT推倒X的特定值得概率3貝葉斯信念網(wǎng)絡(luò):AnExampleFamilyLung34訓(xùn)練貝葉斯網(wǎng)路:幾種方案Scenario1:給定網(wǎng)絡(luò)結(jié)構(gòu)和所有變量觀察：只計算CPTScenario2:網(wǎng)絡(luò)結(jié)構(gòu)已知,某些變量隱藏:梯度下降法(貪心爬山),i.e.,沿著準則函數(shù)的最速下降方向搜索解權(quán)重初始化為隨機值每次迭代中,似乎是對目前的最佳解決方案前進，沒有回溯每次迭代中權(quán)重被更新，并且收斂到局部最優(yōu)解Scenario3:網(wǎng)絡(luò)結(jié)構(gòu)未知,所有變量可知:搜索模型空間構(gòu)造網(wǎng)絡(luò)拓撲Scenario4:未知結(jié)構(gòu),隱藏變量:目前沒有好的算法D.Heckerman.ATutorialonLearningwithBayesianNetworks.InLearninginGraphicalModels,M.Jordan,ed..MITPress,2019.4訓(xùn)練貝葉斯網(wǎng)路:幾種方案Scenario1:給定網(wǎng)絡(luò)結(jié)構(gòu)45Chapter6.分類:AdvancedMethodsBayesianBeliefNetworksClassificationbyBackpropagationSupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)OtherClassificationMethodsAdditionalTopicsRegardingClassificationSummary5Chapter6.分類:AdvancedMetho56用反向傳播分類反向傳播:一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法

最早是由心理學(xué)家和神經(jīng)學(xué)家開創(chuàng)的，開發(fā)和測試神經(jīng)元計算模擬神經(jīng)網(wǎng)絡(luò):一組連接的輸入/輸出單元，其中每個連接都與一個權(quán)重關(guān)聯(lián)通過調(diào)整權(quán)重來學(xué)習(xí),能夠輸入元組的正確類別標號又被稱為連接者學(xué)習(xí)connectionistlearning6用反向傳播分類反向傳播:一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法67神經(jīng)網(wǎng)絡(luò)作為分類器弱點學(xué)習(xí)時間很長

需要很多參數(shù)（常靠經(jīng)驗確定）,如網(wǎng)絡(luò)的結(jié)構(gòu)可解釋性差:很難解釋權(quán)重和網(wǎng)絡(luò)中“隱藏單元”的含義優(yōu)勢對噪音數(shù)據(jù)的高承受能力分類未經(jīng)訓(xùn)練的模式的能力非常適合處理連續(xù)值的輸入/輸出成功地應(yīng)用于現(xiàn)實數(shù)據(jù),e.g.,手寫字符識別算法是固有并行的已經(jīng)發(fā)展了一些從訓(xùn)練好的神經(jīng)網(wǎng)路提取規(guī)則的技術(shù)7神經(jīng)網(wǎng)絡(luò)作為分類器弱點78多層前饋神經(jīng)網(wǎng)絡(luò)輸出層輸入層隱藏層OutputvectorInputvector:Xwij8多層前饋神經(jīng)網(wǎng)絡(luò)輸出層輸入層隱藏層Outputvect89多層前饋神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)的輸入對應(yīng)于每個訓(xùn)練元組的測量屬性

輸入同時傳給稱作輸入層的單元加權(quán)后同時傳遞給隱藏層隱藏層的數(shù)目是任意的,通常只有一個最后一個隱藏層的輸出權(quán)重后作為輸入傳遞給稱為輸出層，此處給出網(wǎng)絡(luò)的預(yù)測前饋feed-forward:權(quán)重都不反饋到輸入單元或前一層的輸出單元從統(tǒng)計學(xué)觀點,網(wǎng)絡(luò)進行一個非線性回歸；給定足夠的隱藏單元和訓(xùn)練數(shù)據(jù),可以逼近任何函數(shù)9多層前饋神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)的輸入對應(yīng)于每個訓(xùn)練元組的測量屬性910定義網(wǎng)絡(luò)拓撲確定網(wǎng)絡(luò)拓撲:給定輸入層的單元數(shù),隱藏層數(shù)(if>1),每個隱藏層的單元數(shù),輸出層的單元數(shù)規(guī)格化訓(xùn)練元組的輸入值[0.0—1.0]對于離散值，可重新編碼，每個可能的值一個輸入單元并初始化0輸出,如果涉及超過兩個類別則一個輸出單元對應(yīng)一個類別一旦一個訓(xùn)練好的網(wǎng)絡(luò)其準確率達不到要求時，用不同的網(wǎng)絡(luò)拓撲和初始值重新訓(xùn)練網(wǎng)絡(luò)10定義網(wǎng)絡(luò)拓撲確定網(wǎng)絡(luò)拓撲:給定輸入層的單元數(shù),隱藏層1011反向傳播Backpropagation迭代地處理訓(xùn)練數(shù)據(jù)&比較網(wǎng)絡(luò)的預(yù)測值和實際的目標值對每個訓(xùn)練元組,修改權(quán)重最小化目標的預(yù)測值和實際值之間的meansquarederror這種修改后向進行:從輸出層開始,通過每個隱藏層直到第一個隱藏層步驟初始化權(quán)重為一個小的隨機數(shù),以及偏倚biases向前傳播輸入(應(yīng)用激勵函數(shù))向后傳播誤差(更新權(quán)重和偏倚)停止條件(當誤差非常小,etc.)11反向傳播Backpropagation迭代地處理訓(xùn)練數(shù)據(jù)1112神經(jīng)元:一個隱藏/輸出層單元

一個n-維輸入向量x被映射到變量y，通過非線性函數(shù)映射單元的輸入是前一層的輸出.被乘上權(quán)重后求和且加上此單元的偏倚.然后應(yīng)用一個非線性激勵函數(shù).mkf輸入向量xoutputy激勵weightvectorw?w0w1wnx0x1xnbias權(quán)重和12神經(jīng)元:一個隱藏/輸出層單元一個n-維輸入向量x被映12后向傳播算法后向傳播算法1314效率和可解釋性向后傳播的效率:每次迭代O(|D|*w),|D|為元組數(shù)，w

個權(quán)重,最壞的情況下迭代的次數(shù)可能是元組數(shù)的指數(shù)為了更容易理解:通過網(wǎng)絡(luò)修剪提取規(guī)則簡化網(wǎng)絡(luò)結(jié)構(gòu)，去除對訓(xùn)練的網(wǎng)絡(luò)有最弱影響的權(quán)重連接對連接,單元,or活躍值聚類輸入和活躍值集合用來推導(dǎo)描述輸入和隱藏層間關(guān)系的規(guī)則Sensitivityanalysis:評估一個給定的輸入變量對網(wǎng)絡(luò)輸出的影響。從中獲得的知識可以表示為規(guī)則。IFX減少5%THENY增加…14效率和可解釋性向后傳播的效率:每次迭代O(|D|*1415Chapter6.分類:AdvancedMethods貝葉斯信念網(wǎng)絡(luò)后向傳播分類ClassificationbyBackpropagation支持向量機SupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)其他分類方法AdditionalTopicsRegardingClassificationSummary15Chapter6.分類:AdvancedMeth1516分類:一個數(shù)學(xué)映射Classification:預(yù)測分類的類標簽E.g.,個人主頁分類xi=(x1,x2,x3,…),yi=+1or–1x1:#ofword“homepage”x2:#ofword“welcome”

xX=n,yY={+1,–1},推導(dǎo)一個函數(shù)f:XY

線性分類二元分類問題紅線上面的點屬于class‘x’下面的點屬于class‘o’Examples:SVM,Perceptron,ProbabilisticClassifiersxxxxxxxxxxooooooooooooo16分類:一個數(shù)學(xué)映射Classification:預(yù)測分類1617SVM—SupportVectorMachines一個相對新的分類方法，適用于linearandnonlineardata使用一個非線性映射把原始訓(xùn)練數(shù)據(jù)變換到高維空間中在新的維上,搜索線性優(yōu)化分離超平面hyperplane(i.e.,“決策邊界”)用一個合適的足夠高維的映射,兩類數(shù)據(jù)總是可以被超平面分開SVM使用supportvectors(“基本”選練元組)和邊緣margins(由支持向量定義)發(fā)現(xiàn)超平面17SVM—SupportVectorMachines一1718SVM—歷史和應(yīng)用Vapnikandcolleagues(1992)—基礎(chǔ)工作來自于Vapnik&Chervonenkis’statisticallearningtheoryin1960sFeatures:訓(xùn)練慢但是準確度高，由于能夠建模非線性決策邊界(marginmaximization)Usedfor:分類和數(shù)值預(yù)測應(yīng)用:手寫數(shù)字識別,objectrecognition,speakeridentification,基準時間序列預(yù)測檢驗

18SVM—歷史和應(yīng)用Vapnikandcolleagu1819支持向量機的一般哲學(xué)SupportVectorsSmallMargin邊界LargeMargin19支持向量機的一般哲學(xué)SupportVectorsSma1922十二月2022DataMining:ConceptsandTechniques20SVM—MarginsandSupportVectors17十二月2022DataMining:Concep2021SVM—當數(shù)據(jù)線性可分時mD為(X1,y1),…,(X|D|,y|D|),其中Xi

帶標簽yi的訓(xùn)練元組有無數(shù)條直線(hyperplanes)可以分離兩個類，但我們需要發(fā)現(xiàn)最好的一個(對未知數(shù)據(jù)有最小化的分類誤差)SVMsearchesforthehyperplanewiththelargestmargin,i.e.,maximummarginalhyperplane(MMH)21SVM—當數(shù)據(jù)線性可分時mD為(X1,y1),…,2122SVM—線性可分一個分離超平面可以寫成W●X+b=0W={w1,w2,…,wn}權(quán)重向量和標量b(bias)對于2-D，可以寫成w0+w1x1+w2x2=0超平面定義了邊緣的邊界:H1:w0+w1x1+w2x2≥1foryi=+1,andH2:w0+w1x1+w2x2≤–1foryi=–1任何一個位于超平面H1orH2(i.e.,thesidesdefiningthemargin)的樣本為supportvectors最大邊緣是2/‖w‖→max是一個

constrained(convex)quadraticoptimizationproblem:二次目標函數(shù)和線性約束

QuadraticProgramming(QP)Lagrangianmultipliers22SVM—線性可分一個分離超平面可以寫成2223WhyIsSVMEffectiveonHighDimensionalData?訓(xùn)練后的分類器的complexity由支持向量數(shù)而不是數(shù)據(jù)維度刻畫支持向量supportvectors是基本的/臨界的訓(xùn)練元組—離決策邊界最近(MMH)如果其他的樣本刪掉后重新訓(xùn)練仍然會發(fā)現(xiàn)相同的分離超平面支持向量的數(shù)目可用于計算（svm分類器）期望誤差率的上界(upper),其獨立于數(shù)據(jù)維度一個只有少量支持向量的svm有很好的推廣性能,即使數(shù)據(jù)的維度很高時23WhyIsSVMEffectiveonHigh2324SVM—線性不可分把原始輸入數(shù)據(jù)變換到一個更高維的空間Searchforalinearseparatinghyperplaneinthenewspace24SVM—線性不可分把原始輸入數(shù)據(jù)變換到一個更高維的空間2425SVM:不同的核函數(shù)計算變換后數(shù)據(jù)的點積,數(shù)學(xué)上等價于應(yīng)用一個核函數(shù)K(Xi,Xj)于原始數(shù)據(jù),i.e.,K(Xi,Xj)=Φ(Xi)Φ(Xj)TypicalKernelFunctionsSVM也可用于多類數(shù)據(jù)(>2)和回歸分析(需要附加參數(shù))25SVM:不同的核函數(shù)計算變換后數(shù)據(jù)的點積,數(shù)學(xué)上等2526SVMvs.NeuralNetworkSVM

DeterministicalgorithmNicegeneralizationpropertiesHardtolearn–使用quadraticprogrammingtechniques批量學(xué)習(xí)UsingkernelscanlearnverycomplexfunctionsNeuralNetworkNondeterministicalgorithmGeneralizeswellbutdoesn’thavestrongmathematicalfoundationCaneasilybelearnedinincrementalfashionTolearncomplexfunctions—usemultilayerperceptron(nontrivial)26SVMvs.NeuralNetworkSVM Ne2627SVMRelatedLinksSVMWebsite:/RepresentativeimplementationsLIBSVM:anefficientimplementationofSVM,multi-classclassifications,nu-SVM,one-classSVM,includingalsovariousinterfaceswithjava,python,etc.SVM-light:simplerbutperformanceisnotbetterthanLIBSVM,supportonlybinaryclassificationandonlyinCSVM-torch:anotherrecentimplementationalsowritteninC27SVMRelatedLinksSVMWebsite2728Chapter6.惰性學(xué)習(xí)BayesianBeliefNetworksClassificationbyBackpropagationSupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)OtherClassificationMethodsAdditionalTopicsRegardingClassificationSummary28Chapter6.惰性學(xué)習(xí)BayesianBeli2829Lazyvs.EagerLearningLazyvs.eagerlearningLazylearning(e.g.,基于實例的學(xué)習(xí)):僅存儲數(shù)據(jù)(或稍加處理)直到碰到檢驗元組才開始處理Eagerlearning(前面介紹的方法):給定訓(xùn)練數(shù)據(jù),在遇到待處理的新數(shù)據(jù)前構(gòu)造分類模型Lazy:訓(xùn)練用時很少，預(yù)測時用時多準確性惰性學(xué)習(xí)方法可以有效地利用更豐富的假設(shè)空間，使用多個局部線性函數(shù)來對目標函數(shù)形成一個隱式的全局逼近Eager:必須限于一個假設(shè)，它覆蓋了整個實例空間29Lazyvs.EagerLearningLazy2930LazyLearner:基于實例的方法Instance-basedlearning:Storetrainingexamplesanddelaytheprocessing(“l(fā)azyevaluation”)untilanewinstancemustbeclassified典型的方法k-nearestneighborapproach實例表示為歐氏空間中的點.LocallyweightedregressionConstructslocalapproximation基于案例的推理Case-basedreasoning使用符號表示和知識為基礎(chǔ)的推理30LazyLearner:基于實例的方法Instance3031k-最近鄰算法所有的樣本對應(yīng)于n-D空間的點通過Euclideandistance,dist(X1,X2)定義最近鄰居目標函數(shù)可以是discrete-orreal-值對于離散值,k-NN返回與目標元組最近的k個訓(xùn)練樣本的多數(shù)類Vonoroidiagram:thedecisionsurfaceinducedby1-NNforatypicalsetoftrainingexamples

._+_xq+__+__+.....31k-最近鄰算法所有的樣本對應(yīng)于n-D空間的點._3132k-NNAlgorithm的討論k-NN：元組的未知實值的預(yù)測時返回與未知元組k個最近鄰居的平均值（對應(yīng)屬性）Distance-weightednearestneighboralgorithm根據(jù)與目標元組的距離權(quán)重組合k個近鄰的貢獻GivegreaterweighttocloserneighborsRobusttonoisydatabyaveragingk-nearestneighborsCurseofdimensionality:鄰居間的距離會被無關(guān)聯(lián)的屬性影響

坐標軸伸縮或去除次要的屬性32k-NNAlgorithm的討論k-NN：元組的未知實3233基于案例的推理(CBR)CBR:使用一個問題解的數(shù)據(jù)庫來求解新問題存儲符號描述(tuplesorcases)—不是Euclideanspace的點應(yīng)用:

顧客-服務(wù)臺(產(chǎn)品有關(guān)的診斷),合法裁決Methodology實例表示為復(fù)雜的符號描述(e.g.,functiongraphs)搜索相似的案例,組合多個返回的例子Tightcouplingbetweencaseretrieval,knowledge-basedreasoning,andproblemsolvingChallengesFindagoodsimilaritymetricIndexingbasedonsyntacticsimilaritymeasure,andwhenfailure,backtracking,andadaptingtoadditionalcases33基于案例的推理(CBR)CBR:使用一個問題解的數(shù)據(jù)3334Chapter6.分類:其他方法BayesianBeliefNetworksClassificationbyBackpropagationSupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)OtherClassificationMethodsAdditionalTopicsRegardingClassificationSummary34Chapter6.分類:其他方法Bayesian3435遺傳算法(GA)GeneticAlgorithm:模仿生物進化使用隨機產(chǎn)生的規(guī)則組成一個最初的population每個規(guī)則有一系列位表示E.g.,ifA1and?A2thenC2canbeencodedas100如果一個屬性有k>2個值,使用k位基于適者生存原理,最適合的規(guī)則及其后代組成新的種群規(guī)則的擬合度用它在訓(xùn)練樣本的準確率來評估通過交叉和突變來產(chǎn)生后代此過程持續(xù)下去，直到種群P進化到其中的每個規(guī)則滿足給定的擬合度閾值算法慢，但易于并行35遺傳算法(GA)GeneticAlgorithm:3536FuzzySetApproachesFuzzylogic使用[0.0,1.0]真值來表示類的成員的隸屬度

屬性值被轉(zhuǎn)化成模糊值.Ex.:對于每個離散類別收入{low,medium,high}，x

被分配一個模糊的隸屬值,e.g.$49K屬于“mediumincome”0.15，屬于“highincome”的隸屬值是0.96模糊隸屬值的和不一定等于1.每個可用的規(guī)則為類的隸屬貢獻一票通常,對每個預(yù)測分類的真值求和,并組合這些值36FuzzySetApproachesFuzzylo3637Chapter6.分類:AdvancedMethodsBayesianBeliefNetworksClassificationbyBackpropagationSupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)OtherClassificationMethodsAdditionalTopicsRegardingClassificationSummary37Chapter6.分類:AdvancedMeth37多類分類分類時設(shè)計多個類別(i.e.,>2Classes)Method1.One-vs.-all(OVA):每次學(xué)習(xí)一個分類器

給定m個類,訓(xùn)練m個分類其，每個類別一個分類器j:把類別j的元組定義為

positive&其他的為negative為分類樣本X,所有分類器投票來集成Method2.All-vs.-all(AVA):為每一對類別學(xué)習(xí)一個分類器Givenmclasses,constructm(m-1)/2binaryclassifiers使用兩個類別的元組訓(xùn)練一個分類器為分類元組X,每個分類器投票.XisassignedtotheclasswithmaximalvoteComparisonAll-vs.-alltendstobesuperiortoone-vs.-allProblem:Binaryclassifierissensitivetoerrors,anderrorsaffectvotecount38多類分類分類時設(shè)計多個類別(i.e.,>2Class38多類分類的Error-CorrectingCodes最初目的是在數(shù)據(jù)傳輸?shù)耐ㄓ嵢蝿?wù)中通過探索數(shù)據(jù)冗余來修正誤差。例:A7-bitcodewordassociatedwithclasses1-439ClassError-Corr.CodewordC11111111C20000111C30011001C40101010給定未知元組X,7個分類器的結(jié)果為:0001010Hammingdistance:#兩個碼字間不同位數(shù)的和H(X,C1)=5,檢查[1111111]&[0001010]間不同位數(shù)和H(X,C2)=3,H(X,C3)=3,H(X,C4)=1,thusC4asthelabelforX

Error-correctingcodescancorrectupto(h-1)/h1-biterror,wherehistheminimumHammingdistancebetweenanytwocodewordsIfweuse1-bitperclass,itisequiv.toone-vs.-allapproach,thecodeareinsufficienttoself-correctWhenselectingerror-correctingcodes,thereshouldbegoodrow-wiseandcol.-wiseseparationbetweenthecodewords多類分類的Error-CorrectingCodes最初目39半監(jiān)督分類Semi-supervised:使用有標簽和無標簽數(shù)據(jù)構(gòu)造分類器Self-training:BuildaclassifierusingthelabeleddataUseittolabeltheunlabeleddata,andthosewiththemostconfidentlabelpredictionareaddedtothesetoflabeleddata重復(fù)以上過程Adv:容易理解;disadv:可能增大誤差Co-training:Usetwoormoreclassifierstoteacheachother每個學(xué)習(xí)者使用元組的相互獨立的特征集合來訓(xùn)練一個好的分類器F1然后f1andf2

用來預(yù)測未知元組X的類別標簽Teacheachother:Thetuplehavingthemostconfidentpredictionfromf1isaddedtothesetoflabeleddataforf2,&viceversaOthermethods,e.g.,jointprobabilitydistributionoffeaturesandlabels40半監(jiān)督分類Semi-supervised:使用有標簽和無標40主動學(xué)習(xí)ActiveLearning獲取類標簽是昂貴Activelearner:queryhuman(oracle)forlabelsPool-basedapproach:UsesapoolofunlabeleddataL:D中有標簽的樣本子集,U:D的一個未標記數(shù)據(jù)集使用一個查詢函數(shù)小心地從U選擇1或多個元組，并咨詢標簽anoracle(ahumanannotator)ThenewlylabeledsamplesareaddedtoL,andlearnamodelGoal:AchievehighaccuracyusingasfewlabeleddataaspossibleEvaluatedusinglearningcurves:Accuracyasafunctionofthenumberofinstancesqueried(#oftuplestobequeriedshouldbesmall)Researchissue:Howtochoosethedatatuplestobequeried?Uncertaintysampling:choosetheleastcertainonesReduceversionspace,thesubsetofhypothesesconsistentw.thetrainingdataReduceexpectedentropyoverU:Findthegreatestreductioninthetotalnumberofincorrectpredictions41主動學(xué)習(xí)ActiveLearning獲取類標簽是昂貴4141遷移學(xué)習(xí)：概念框架Transferlearning:ExtractknowledgefromoneormoresourcetasksandapplytheknowledgetoatargettaskTraditionallearning:每一個任務(wù)建立分類器Transferlearning:Buildnewclassifierbyapplyingexistingknowledgelearnedfromsourcetasks42TraditionalLearningFrameworkTransferLearningFramework遷移學(xué)習(xí)：概念框架Transferlearning:Ex42遷移學(xué)習(xí):MethodsandApplications應(yīng)用:數(shù)據(jù)過時或分布的變化時,e.g.,Webdocumentclassification,e-mailspamfilteringInstance-basedtransferlearning:ReweightsomeofthedatafromsourcetasksanduseittolearnthetargettaskTrAdaBoost(TransferAdaBoost)假定源和目標數(shù)據(jù)用相同的屬性和類別描述,butratherdiff.distributionsRequireonlylabelingasmallamountoftargetdata訓(xùn)練中使用源數(shù)據(jù):Whenasourcetupleismisclassified,reducetheweightofsuchtupelssothattheywillhavelesseffectonthesubsequentclassifierResearchissuesNegativetransfer:WhenitperformsworsethannotransferatallHeterogeneoustransferlearning:TransferknowledgefromdifferentfeaturespaceormultiplesourcedomainsLarge-scaletransferlearning43遷移學(xué)習(xí):MethodsandApplications4344Chapter6.分類:頻繁模式BayesianBeliefNetworksClassificationbyBackpropagationSupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)OtherClassificationMethodsAdditionalTopicsRegardingClassificationSummary44Chapter6.分類:頻繁模式BayesianB4445關(guān)聯(lián)分類關(guān)聯(lián)分類:主要步驟挖掘關(guān)于頻繁模式(屬性-值對的聯(lián)結(jié))和類標簽間的強關(guān)聯(lián)產(chǎn)生以下形似的關(guān)聯(lián)規(guī)則

P1^p2…^pl

“Aclass=C”(conf,sup)組織規(guī)則，形成基于規(guī)則的分類器為什么有效?

可以發(fā)現(xiàn)（在多個屬性間）高置信度的關(guān)聯(lián)，可以克服決策樹規(guī)約引入的約束,決策樹一次考慮一個屬性研究發(fā)現(xiàn)，關(guān)聯(lián)分類通常比某些傳統(tǒng)的分類方法更精確,例如C4.545關(guān)聯(lián)分類關(guān)聯(lián)分類:主要步驟4546典型的關(guān)聯(lián)分類方法CBA(ClassificationBasedonAssociations:Liu,Hsu&Ma,KDD’98)挖掘可能關(guān)聯(lián)規(guī)則：Cond-set(屬性-值的集合)classlabel建立分類器:基于置信度和支持度的下降序組織規(guī)則CMAR(ClassificationbasedonMultipleAssociationRules:Li,Han,Pei,ICDM’01)分類:多個規(guī)則的統(tǒng)計分析CPAR(ClassificationbasedonPredictiveAssociationRules:Yin&Han,SDM’03)產(chǎn)生預(yù)測性規(guī)則(FOIL-likeanalysis)允許覆蓋的元組以降低權(quán)重形式保留下來構(gòu)造新規(guī)則（根據(jù)期望準確率）使用最好的k個規(guī)則預(yù)測更有效（產(chǎn)生規(guī)則少）,精確性類似CMAR46典型的關(guān)聯(lián)分類方法CBA(Classification4647頻繁模式vs.單個特征(a)Austral(c)Sonar(b)CleveFig.1.InformationGainvs.PatternLength某些頻繁模式的判別能力高于單個特征.47頻繁模式vs.單個特征(a)Austral(c)4748經(jīng)驗結(jié)果

(a)Austral(c)Sonar(b)BreastFig.2.InformationGainvs.PatternFrequency48經(jīng)驗結(jié)果(a)Austral(c)Sonar(b)4849特征選擇FeatureSelection給定頻繁模式集合,存在non-discriminative和redundant的模式,他們會引起過度擬合我們希望選出discriminativepatterns，并且去除冗余借用MaximalMarginalRelevance(MMR)的概念A(yù)documenthashighmarginalrelevanceifitisbothrelevanttothequeryandcontainsminimalmarginalsimilaritytopreviouslyselecteddocuments49特征選擇FeatureSelection給定頻繁模式集4950實驗結(jié)果5050實驗結(jié)果505051ScalabilityTests51ScalabilityTests5152基于頻繁模式的分類H.Cheng,X.Yan,J.Han,andC.-W.Hsu,“DiscriminativeFrequentPatternAnalysisforEffectiveClassification”,ICDE'07Accuracyissue問題IncreasethediscriminativepowerIncreasetheexpressivepowerofthefeaturespaceScalabilityissue問題ItiscomputationallyinfeasibletogenerateallfeaturecombinationsandfilterthemwithaninformationgainthresholdEfficientmethod(DDPMine:FPtreepruning):H.Cheng,X.Yan,J.Han,andP.S.Yu,"DirectDiscriminativePatternMiningforEffectiveClassification",ICDE'0852基于頻繁模式的分類H.Cheng,X.Yan,J5253DDPMineEfficiency:RuntimePatClassHarmonyDDPMinePatClass:ICDE’07PatternClassificationAlg.53DDPMineEfficiency:RuntimeP5354SummaryEffectiveandadvancedclassificationmethodsBayesianbeliefnetwork(probabilisticnetworks)Backpropagation(Neuralnetworks)SupportVectorMachine(SVM)Pattern-basedclassificationOtherclassificationmethods:lazylearners(KNN,case-basedreasoning),geneticalgorithms,roughsetandfuzzysetapproachesAdditionalTopicsonClassificationMulticlassclassificationSemi-supervisedclassificationActivelearningTransferlearning54SummaryEffectiveandadvance5455References(1)C.M.Bishop,NeuralNetworksforPatternRecognition.OxfordUniversityPress,2019C.J.C.Burges.ATutorialonSupportVectorMachinesforPatternRecognition.DataMiningandKnowledgeDiscovery,2(2):121-168,2019H.Cheng,X.Yan,J.Han,andC.-W.Hsu,DiscriminativeFrequentpatternAnalysisforEffectiveClassification,ICDE'07H.Cheng,X.Yan,J.Han,andP.S.Yu,DirectDiscriminativePatternMiningforEffectiveClassification,ICDE'08N.CristianiniandJ.Shawe-Taylor,IntroductiontoSupportVectorMachinesandOtherKernel-BasedLearningMethods,CambridgeUniversityPress,2000A.J.Dobson.AnIntroductiontoGeneralizedLinearModels.Chapman&Hall,1990G.DongandJ.Li.Efficientminingofemergingpatterns:Discoveringtrendsanddifferences.

KDD'9955References(1)C.M.Bishop,5556References(2)R.O.Duda,P.E.Hart,andD.G.Stork.PatternClassification,2ed.JohnWiley,2019T.Hastie,R.Tibshirani,andJ.Friedman.TheElementsofStatisticalLearning:DataMining,Inference,andPrediction.Springer-Verlag,2019S.Haykin,NeuralNetworksandLearningMachines,PrenticeHall,2019D.Heckerman,D.Geiger,andD.M.Chickering.LearningBayesiannetworks:Thecombinationofknowledgeandstatisticaldata.MachineLearning,2019.V.Kecman,LearningandSoftComputing:SupportVectorMachines,NeuralNetworks,andFuzzyLogic,MITPress,2019W.Li,J.Han,andJ.Pei,CMAR:AccurateandEfficientClassificationBasedonMultipleClass-AssociationRules,ICDM'01T.-S.Lim,W.-Y.Loh,andY.-S.Shih.Acomparisonofpredictionaccuracy,complexity,andtrainingtimeofthirty-threeoldandnewclassificationalgorithms.MachineLearning,200056References(2)R.O.Duda,P.5657References(3)B.Liu,W.Hsu,andY.Ma.Integratingclassificationandassociationrulemining,p.80-86,KDD’98.T.M.Mitchell.MachineLearning.McGrawHill,2019.D.E.Rumelhart,andJ.L.McClelland,editors,ParallelDistributedProcessing,MITPress,1986.P.Tan,M.Steinbach,andV.Kumar.IntroductiontoDataMining.AddisonWesley,2019.S.M.WeissandN.Indurkhya.PredictiveDataMining.MorganKaufmann,2019.I.H.WittenandE.Frank.DataMining:PracticalMachineLearningToolsandTechniques,2ed.MorganKaufmann,2019.X.YinandJ.Han.CPAR:Classificationbasedonpredictiveassociationrules.SDM'03H.Yu,J.Yang,andJ.Han.ClassifyinglargedatasetsusingSVMwithhierarchicalclusters.KDD'03.57References(3)B.Liu,W.Hsu5722十二月2022DataMining:ConceptsandTechniques58SVM—IntroductoryLiterature“StatisticalLearningTheory”byVapnik:extremelyhardtounderstand,containingmanyerrorstoo.C.

J.

C.Burges.ATutorialonSupportVectorMachinesforPatternRecognition.KnowledgeDiscoveryandDataMining,2(2),2019.BetterthantheVapnik’sbook,butstillwrittentoohardforintroduction,andtheexamplesaresonot-intuitiveThebook“AnIntroductiontoSupportVectorMachines”byN.CristianiniandJ.Shawe-TaylorAlsowrittenhardforintroduction,buttheexplanationaboutthemercer’stheoremisbetterthanaboveliteraturesTheneuralnetworkbookbyHaykinsContainsonenicechapterofSVMintroduction17十二月2022DataMining:Concep5859NotesaboutSVM—IntroductoryLiterature“StatisticalLearningTheory”byVapnik:difficulttounderstand,containingmanyerrors.C.

J.

C.Burges.ATutorialonSupportVectorMachinesforPatternRecognition.KnowledgeDiscoveryandDataMining,2(2),2019.EasierthanVapnik’sbook,butstillnotintroductorylevel;theexamplesarenotsointuitiveThebookAnIntroductiontoSupportVectorMachinesbyCristianini

and

Shawe-TaylorNotintroductorylevel,buttheexplanationaboutMercer’sTheoremisbetterthanaboveliteraturesNeuralNetworksandLearningMachinesbyHaykinContainsanicechapteronSVMintroduction59NotesaboutSVM—Introductory5960Chapter6.分類:AdvancedMethods貝葉斯信念網(wǎng)絡(luò)后向傳播分類ClassificationbyBackpropagation支持向量機SupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)其他分類方法AdditionalTopicsRegardingClassificationSummary1Chapter6.分類:AdvancedMetho6061貝葉斯信念網(wǎng)絡(luò)Bayesianbeliefnetworks(又稱為Bayesiannetworks,probabilisticnetworks):允許變量子集間定義類條件獨立(有向無環(huán))因果關(guān)系的圖模型表示變量間的依賴關(guān)系給出了一個聯(lián)合概率分布

Nodes:隨機變量Links:依賴關(guān)系X,Y是Z的雙親,YistheparentofPZ和P間沒有依賴關(guān)系

沒有環(huán)2貝葉斯信念網(wǎng)絡(luò)Bayesianbeliefnetwor6162貝葉斯信念網(wǎng)絡(luò):AnExampleFamilyHistory(FH)LungCancer(LC)PositiveXRaySmoker(S)EmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.10.9CPT:ConditionalProbabilityTableforvariableLungCancer:顯示父母的每個可能組合的條件概率從CPT推倒X的特定值得概率3貝葉斯信念網(wǎng)絡(luò):AnExampleFamilyLung6263訓(xùn)練貝葉斯網(wǎng)路:幾種方案Scenario1:給定網(wǎng)絡(luò)結(jié)構(gòu)和所有變量觀察：只計算CPTScenario2:網(wǎng)絡(luò)結(jié)構(gòu)已知,某些變量隱藏:梯度下降法(貪心爬山),i.e.,沿著準則函數(shù)的最速下降方向搜索解權(quán)重初始化為隨機值每次迭代中,似乎是對目前的最佳解決方案前進，沒有回溯每次迭代中權(quán)重被更新，并且收斂到局部最優(yōu)解Scenario3:網(wǎng)絡(luò)結(jié)構(gòu)未知,所有變量可知:搜索模型空間構(gòu)造網(wǎng)絡(luò)拓撲Scenario4:未知結(jié)構(gòu),隱藏變量:目前沒有好的算法D.Heckerman.ATutorialonLearningwithBayesianNetworks.InLearninginGraphicalModels,M.Jordan,ed..MITPress,2019.4訓(xùn)練貝葉斯網(wǎng)路:幾種方案Scenario1:給定網(wǎng)絡(luò)結(jié)構(gòu)6364Chapter6.分類:AdvancedMethodsBayesianBeliefNetworksClassificationbyBackpropagationSupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)OtherClassificationMethodsAdditionalTopicsRegardingClassificationSummary5Chapter6.分類:AdvancedMetho6465用反向傳播分類反向傳播:一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法

最早是由心理學(xué)家和神經(jīng)學(xué)家開創(chuàng)的，開發(fā)和測試神經(jīng)元計算模擬神經(jīng)網(wǎng)絡(luò):一組連接的輸入/輸出單元，其中每個連接都與一個權(quán)重關(guān)聯(lián)通過調(diào)整權(quán)重來學(xué)習(xí),能夠輸入元組的正確類別標號又被稱為連接者學(xué)習(xí)connectionistlearning6用反向傳播分類反向傳播:一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法6566神經(jīng)網(wǎng)絡(luò)作為分類器弱點學(xué)習(xí)時間很長

需要很多參數(shù)（?？拷?jīng)驗確定）,如網(wǎng)絡(luò)的結(jié)構(gòu)可解釋性差:很難解釋權(quán)重和網(wǎng)絡(luò)中“隱藏單元”的含義優(yōu)勢對噪音數(shù)據(jù)的高承受能力分類未經(jīng)訓(xùn)練的模式的能力非常適合處理連續(xù)值的輸入/輸出成功地應(yīng)用于現(xiàn)實數(shù)據(jù),e.g.,手寫字符識別算法是固有并行的已經(jīng)發(fā)展了一些從訓(xùn)練好的神經(jīng)網(wǎng)路提取規(guī)則的技術(shù)7神經(jīng)網(wǎng)絡(luò)作為分類器弱點6667多層前饋神經(jīng)網(wǎng)絡(luò)輸出層輸入層隱藏層OutputvectorInputvector:Xwij8多層前饋神經(jīng)網(wǎng)絡(luò)輸出層輸入層隱藏層Outputvect6768多層前饋神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)的輸入對應(yīng)于每個訓(xùn)練元組的測量屬性

輸入同時傳給稱作輸入層的單元加權(quán)后同時傳遞給隱藏層隱藏層的數(shù)目是任意的,通常只有一個最后一個隱藏層的輸出權(quán)重后作為輸入傳遞給稱為輸出層，此處給出網(wǎng)絡(luò)的預(yù)測前饋feed-forward:權(quán)重都不反饋到輸入單元或前一層的輸出單元從統(tǒng)計學(xué)觀點,網(wǎng)絡(luò)進行一個非線性回歸；給定足夠的隱藏單元和訓(xùn)練數(shù)據(jù),可以逼近任何函數(shù)9多層前饋神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)的輸入對應(yīng)于每個訓(xùn)練元組的測量屬性6869定義網(wǎng)絡(luò)拓撲確定網(wǎng)絡(luò)拓撲:給定輸入層的單元數(shù),隱藏層數(shù)(if>1),每個隱藏層的單元數(shù),輸出層的單元數(shù)規(guī)格化訓(xùn)練元組的輸入值[0.0—1.0]對于離散值，可重新編碼，每個可能的值一個輸入單元并初始化0輸出,如果涉及超過兩個類別則一個輸出單元對應(yīng)一個類別一旦一個訓(xùn)練好的網(wǎng)絡(luò)其準確率達不到要求時，用不同的網(wǎng)絡(luò)拓撲和初始值重新訓(xùn)練網(wǎng)絡(luò)10定義網(wǎng)絡(luò)拓撲確定網(wǎng)絡(luò)拓撲:給定輸入層的單元數(shù),隱藏層6970反向傳播Backpropagation迭代地處理訓(xùn)練數(shù)據(jù)&比較網(wǎng)絡(luò)的預(yù)測值和實際的目標值對每個訓(xùn)練元組,修改權(quán)重最小化目標的預(yù)測值和實際值之間的meansquarederror這種修改后向進行:從輸出層開始,通過每個隱藏層直到第一個隱藏層步驟初始化權(quán)重為一個小的隨機數(shù),以及偏倚biases向前傳播輸入(應(yīng)用激勵函數(shù))向后傳播誤差(更新權(quán)重和偏倚)停止條件(當誤差非常小,etc.)11反向傳播Backpropagation迭代地處理訓(xùn)練數(shù)據(jù)7071神經(jīng)元:一個隱藏/輸出層單元

一個n-維輸入向量x被映射到變量y，通過非線性函數(shù)映射單元的輸入是前一層的輸出.被乘上權(quán)重后求和且加上此單元的偏倚.然后應(yīng)用一個非線性激勵函數(shù).mkf輸入向量xoutputy激勵weightvectorw?w0w1wnx0x1xnbias權(quán)重和12神經(jīng)元:一個隱藏/輸出層單元一個n-維輸入向量x被映71后向傳播算法后向傳播算法7273效率和可解釋性向后傳播的效率:每次迭代O(|D|*w),|D|為元組數(shù)，w

個權(quán)重,最壞的情況下迭代的次數(shù)可能是元組數(shù)的指數(shù)為了更容易理解:通過網(wǎng)絡(luò)修剪提取規(guī)則簡化網(wǎng)絡(luò)結(jié)構(gòu)，去除對訓(xùn)練的網(wǎng)絡(luò)有最弱影響的權(quán)重連接對連接,單元,or活躍值聚類輸入和活躍值集合用來推導(dǎo)描述輸入和隱藏層間關(guān)系的規(guī)則Sensitivityanalysis:評估一個給定的輸入變量對網(wǎng)絡(luò)輸出的影響。從中獲得的知識可以表示為規(guī)則。IFX減少5%THENY增加…14效率和可解釋性向后傳播的效率:每次迭代O(|D|*7374Chapter6.分類:AdvancedMethods貝葉斯信念網(wǎng)絡(luò)后向傳播分類ClassificationbyBackpropagation支持向量機SupportVectorMachinesClassificationbyUsingFrequentPatternsLazyLearners(orLearningfromYourNeighbors)其他分類方法AdditionalTopicsRegardingClassificationSummary15Chapter6.分類:AdvancedMeth7475分類:一個數(shù)學(xué)映射Classification:預(yù)測分類的類標簽E.g.,個人主頁分類xi=(x1,x2,x3,…),yi=+1or–1x1:#ofword“homepage”x2:#ofword“welcome”

xX=n,yY={+1,–1},推導(dǎo)一個函數(shù)f:XY

線性分類二元分類問題紅線上面的點屬于class‘x’下面的點屬于class‘o’Examples:SVM,Perceptron,ProbabilisticClassifiersxxxxxxxxxxooooooooooooo16分類:一個數(shù)學(xué)映射Classification:預(yù)測分類7576SVM—SupportVectorMachines一個相對新的分類方法，適用于linearandnonlineardata使用一個非線性映射把原始訓(xùn)練數(shù)據(jù)變換到高維空間中在新的維上,搜索線性優(yōu)化分離超平面hyperplane(i.e.,“決策邊界”)用一個合適的足夠高維的映射,兩類數(shù)據(jù)總是可以被超平面分開SVM使用supportvectors(“基本”選練元組)和邊緣margins(由支持向量定義)發(fā)現(xiàn)超平面17SVM—SupportVectorMachines一7677SVM—歷史和應(yīng)用Vapnikandcolleagues(1992)—基礎(chǔ)工作來自于Vapnik&Chervonenkis’statisticallearningtheoryin1960sFeatures:訓(xùn)練慢但是準確度高，由于能夠建模非線性決策邊界(marginmaximization)Usedfor:分類和數(shù)值預(yù)測應(yīng)用:手寫數(shù)字識別,objectrecognition,speakeridentification,基準時間序列預(yù)測檢驗

18SVM—歷史和應(yīng)用Vapnikandcolleagu7778支持向量機的一般哲學(xué)SupportVectorsSmallMargin邊界LargeMargin19支持向量機的一般哲學(xué)SupportVectorsSma7822十二月2022DataMining:ConceptsandTechniques79SVM—MarginsandSupportVectors17十二月2022DataMining:Concep7980SVM—當數(shù)據(jù)線性可分時mD為(X1,y1),…,(X|D|,y|D|),其中Xi

帶標簽yi的訓(xùn)練元組有無數(shù)條直線(hyperplanes)可以分離兩個類，但我們需要發(fā)現(xiàn)最好的一個(對未知數(shù)據(jù)有最小化的分類誤差)SVMsearchesforthehyperplanewiththelargestmargin,i.e.,maximummarginalhyperplane(MMH)21SVM—當數(shù)據(jù)線性可分時mD為(X1,y1),…,8081SVM—線性可分一個分離超平面可以寫成W●X+b=0W={w1,w2,…,wn}權(quán)重向量和標量b(bias)對于2-D，可以寫成w0+w1x1+w2x2=0超平面定義了邊緣的邊界:H1:w0+w1x1+w2x2≥1foryi=+1,andH2:w0+w1x1+w2x2≤–1foryi=–1任何一個位于超平面H1orH2(i.e.,thesidesdefiningthemargin)的樣本為supportvectors最大邊緣是2/‖w‖→max是一個

cons