清華大學(xué)大數(shù)據(jù)課程數(shù)據(jù)挖掘技術(shù)學(xué)習(xí)教案

1、會計學(xué)1清華大學(xué)清華大學(xué)(qn hu d xu)大數(shù)據(jù)課程數(shù)大數(shù)據(jù)課程數(shù)據(jù)挖掘技術(shù)據(jù)挖掘技術(shù)第一頁，共145頁。第1頁/共145頁第二頁，共145頁。第2頁/共145頁第三頁，共145頁。第3頁/共145頁第四頁，共145頁。Not previously known, surprising (used to remove redundant rules) 第4頁/共145頁第五頁，共145頁。1.數(shù)據(jù)量大2.缺乏理論知識3.數(shù)據(jù)挖掘可以幫助產(chǎn)生新的假說或者(huzh)使數(shù)據(jù)變得有意義第5頁/共145頁第六頁，共145頁。 苦惱: 淹沒在數(shù)據(jù)中 ; 不能制定合適的決策! n模式模式n趨勢趨勢n事

2、實事實n關(guān)系關(guān)系n模型模型n關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則n序列序列n目標(biāo)市場目標(biāo)市場n資金分配資金分配n貿(mào)易選擇貿(mào)易選擇n在哪兒做廣告在哪兒做廣告n銷售的地理位置銷售的地理位置n金融金融n經(jīng)濟經(jīng)濟n政府政府n人口統(tǒng)計人口統(tǒng)計n生命周期生命周期第6頁/共145頁第七頁，共145頁。數(shù)數(shù)據(jù)據(jù)挖挖掘掘輔輔助助社社會會管管理理促促進進民民生生改改善善支支持持商商業(yè)業(yè)決決策策推推動動科科技技進進步步第7頁/共145頁第八頁，共145頁。第8頁/共145頁第九頁，共145頁。Debt$40KQ QQ QQ QQ QI II I1 12 23 34 45 56 6factor 1factor 2factor n神經(jīng)網(wǎng)絡(luò)

3、神經(jīng)網(wǎng)絡(luò) Neural Networks Neural Networks聚類分析聚類分析 Clustering ClusteringOpenAccntAdd NewProductDecreaseUsage?Time序列序列(xli)(xli)分析分析 Sequence Analysis Sequence Analysis決策樹決策樹 Decision Trees Decision Trees 傾向性分析(fnx) 客戶保留 客戶生命周期管理 目標(biāo)市場 價格彈性分析 客戶細(xì)分 市場細(xì)分 傾向性分析 客戶保留 目標(biāo)市場 欺詐檢測關(guān)聯(lián)分析關(guān)聯(lián)分析 Association Association 市場

4、組合分析 套裝產(chǎn)品分析 目錄設(shè)計 交叉銷售第9頁/共145頁第十頁，共145頁。知識表示（可視化和知識表示技術(shù)）第10頁/共145頁第十一頁，共145頁。correct?可解釋性:how easily the data can be understood?第11頁/共145頁第十二頁，共145頁。第12頁/共145頁第十三頁，共145頁。第13頁/共145頁第十四頁，共145頁。第14頁/共145頁第十五頁，共145頁。第15頁/共145頁第十六頁，共145頁。第16頁/共145頁第十七頁，共145頁。smooth by fitting the data into regression fun

5、ctions第17頁/共145頁第十八頁，共145頁。Managing categorical attributes can be tricky.第18頁/共145頁第十九頁，共145頁。第19頁/共145頁第二十頁，共145頁。 每個簇中的數(shù)據(jù)用其中心值代替 忽略孤立點 先通過(tnggu)聚類等方法找出孤立點。這些孤立點可能包含有用的信息。 人工再審查這些孤立點第20頁/共145頁第二十一頁，共145頁。 通過構(gòu)造函數(shù)來符合數(shù)據(jù)變化的趨勢，這樣可以用一個變量(binling)預(yù)測另一個變量(binling)。 線性回歸 多線性回歸 非線性回歸XY2211XXY33221XXXYxyy =

6、x + 1X1Y1Y1第21頁/共145頁第二十二頁，共145頁。第22頁/共145頁第二十三頁，共145頁。使之落入一個小的特定區(qū)間。最小-最大、Z-Score、按小數(shù)定標(biāo)規(guī)范化。第23頁/共145頁第二十四頁，共145頁。 平滑，聚集 數(shù)據(jù)概化，規(guī)范化 屬性(shxng)構(gòu)造(特征構(gòu)造)有限(yuxin)區(qū)間的歸一化：無限區(qū)間的歸一化：模糊隸屬度：minmaxminvvvev11第24頁/共145頁第二十五頁，共145頁。仍接近保持原數(shù)據(jù)的完整性。對歸約后的數(shù)據(jù)集挖掘?qū)⒏行?，并產(chǎn)生相同（或幾乎相同）的結(jié)果。第25頁/共145頁第二十六頁，共145頁。第26頁/共145頁第二十七頁，共14

7、5頁。第27頁/共145頁第二十八頁，共145頁。第28頁/共145頁第二十九頁，共145頁。第29頁/共145頁第三十頁，共145頁。第30頁/共145頁第三十一頁，共145頁。第31頁/共145頁第三十二頁，共145頁。第32頁/共145頁第三十三頁，共145頁。第33頁/共145頁第三十四頁，共145頁。第34頁/共145頁第三十五頁，共145頁。第35頁/共145頁第三十六頁，共145頁。如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它對類標(biāo)號未知的數(shù)據(jù)元組或?qū)ο筮M行分類。第36頁/共145頁第三十七頁，共145頁。TrainingDataClassificationAlgorithmsIF

8、rank = professorOR years 6THEN tenured = yes Classifier(Model)NAMERANKYEARSTENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no第37頁/共145頁第三十八頁，共145頁。ClassifierTestingDataN A M ER A N KY E A R S TE N U R E DTomA ssistant P

9、 rof2noM erlisaA ssociate P rof7noG eorge P rofessor5yesJoseph A ssistant P rof7yesUnseen Data(Jeff, Professor, 4)Tenured?第38頁/共145頁第三十九頁，共145頁。涉及學(xué)習(xí)模型提供的理解和洞察的層次第39頁/共145頁第四十頁，共145頁。第40頁/共145頁第四十一頁，共145頁。第41頁/共145頁第四十二頁，共145頁。第42頁/共145頁第四十三頁，共145頁。第43頁/共145頁第四十四頁，共145頁。（a）類定義）類定義(dngy)（b）待分類）待分類(fn

10、li)樣例樣例 （c）分類結(jié)果）分類結(jié)果第44頁/共145頁第四十五頁，共145頁。Jaccard：還有信息熵、相關(guān)系數(shù)等其他(qt)的度量方法(|xiyi|pi1n)1/pInner(x,y) x,y xiyiicosqx1x2y1y2x12y12x22y22J(A,B)|AB|AB|第45頁/共145頁第四十六頁，共145頁。算法通過對每個元組和各個類的中心來比較算法通過對每個元組和各個類的中心來比較(bjio)，從而可以找出他的最近的類中心，得到確定的類，從而可以找出他的最近的類中心，得到確定的類別標(biāo)記。別標(biāo)記。第46頁/共145頁第四十七頁，共145頁。第47頁/共145頁第四十八頁，

11、共145頁。第48頁/共145頁第四十九頁，共145頁。（11）c=class to which the most uN. 第49頁/共145頁第五十頁，共145頁。q第50頁/共145頁第五十一頁，共145頁。第51頁/共145頁第五十二頁，共145頁。第52頁/共145頁第五十三頁，共145頁。例如，在貸款申請(shnqng)中，要對申請(shnqng)的風(fēng)險大小做出判斷。收入收入40000高負(fù)債高負(fù)債工作時間工作時間5年年是是否否是是否否“年收入大于￥40000”并且(bngqi)“高負(fù)債”的用戶被認(rèn)為是“高風(fēng)險”；“年收入小于￥40000”但“工作時間大于5年”的申請，是“低風(fēng)險”；N

12、YYNNY第53頁/共145頁第五十四頁，共145頁。buys_computer的決策樹示意的決策樹示意(shy) Age? Credit_rating? student? yes no yesyes no 40 3040yes no fairexcellent 第54頁/共145頁第五十五頁，共145頁。第55頁/共145頁第五十六頁，共145頁。第56頁/共145頁第五十七頁，共145頁。第57頁/共145頁第五十八頁，共145頁。用信息增益這種信息論的理論方法，用信息增益這種信息論的理論方法，使得對一個對象分類所需要的期望使得對一個對象分類所需要的期望測試數(shù)目達到最小，并確保找到一測試數(shù)

13、目達到最小，并確保找到一棵簡單的樹?？煤唵蔚臉?。第58頁/共145頁第五十九頁，共145頁。第59頁/共145頁第六十頁，共145頁。miiimppsssI1221log,其中其中pipi是任意是任意(rny)(rny)樣本屬于樣本屬于CiCi的概率，可用的概率，可用si/ssi/s來估計來估計第60頁/共145頁第六十一頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)

14、不買1 老中否優(yōu)買第61頁/共145頁第六十二頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買決策(juc)屬性“買計算機？”。該屬性分兩類：買/不買S1(買)=641 S2（不買）= 383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383) =-P1Log2P1-P2

15、Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537第第1步計算步計算(j sun)決策屬性的熵決策屬性的熵第62頁/共145頁第六十三頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2步計算條件步計算條件(tiojin)屬性的熵屬性的熵條件屬性共有4個。分別是年齡、收入、學(xué)生、信譽。分別計算不同(b tn)屬性的信息增益。第6

16、3頁/共145頁第六十四頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-1步計算步計算(j sun)年齡的熵年齡的熵年齡共分三個組： 青年(qngnin)、中年、老年青年(qngnin)買與不買比例為128/256S1(買)=128 S2（不買）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128

17、,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183第64頁/共145頁第六十五頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-2步計算步計算(j sun)年齡的熵年齡的熵年齡共分三個組： 青年、中年、老年(lonin)中年買與不買比例為256/0S1(買)=256 S2（不買）= 0S

18、=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0第65頁/共145頁第六十六頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-3步計算步計算(j sun)年齡的熵年齡的熵年齡共分三個組： 青年、中年、老年(lonin

19、)老年(lonin)買與不買比例為125/127S1(買)=125 S2（不買）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157第66頁/共145頁第六十七頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1

20、老中否優(yōu)買第第2-4步計算步計算(j sun)年齡的熵年齡的熵年齡共分三個組： 青年、中年、老年所占比例青年組 384/1025=0.375中年組 256/1024=0.25老年組 384/1024=0.375計算年齡的平均信息期望(qwng)E（年齡） 0.25*0+ =0.6877G（年齡信息增益） =0.9537-0.6877 =0.2660 （1）第67頁/共145頁第六十八頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老

21、中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第3步計算步計算(j sun)收入的熵收入的熵收入共分三個組： 高、中、低E（收入）=0.9361收入信息(xnx)增益=0.9537-0.9361 =0.0176 (2)第68頁/共145頁第六十九頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第4步計算步計算(j

22、sun)學(xué)生的熵學(xué)生的熵學(xué)生(xu sheng)共分二個組： 學(xué)生(xu sheng)、非學(xué)生(xu sheng)E（學(xué)生(xu sheng)）=0.7811年齡信息增益=0.9537-0.7811 =0.1726 （3）第69頁/共145頁第七十頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第5步計算步計算(j sun)信譽的熵信譽的熵信譽分二個

23、組： 良好，優(yōu)秀(yuxi)E（信譽）= 0.9048信譽信息增益=0.9537-0.9048 =0.0453 （4）第70頁/共145頁第七十一頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第6步計算步計算(j sun)選擇節(jié)點選擇節(jié)點 年齡信息(xnx)增益=0.9537-0.6877 =0.2660 （1）收入信息(xnx)增益=0.9537

24、-0.9361 =0.0176 （2）年齡信息(xnx)增益=0.9537-0.7811 =0.1726 （3）信譽信息(xnx)增益=0.9537-0.9048 =0.0453 （4）第71頁/共145頁第七十二頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買年齡年齡(ninlng)青年(qngnin)中年老年買/不買買買/不買葉子第72頁/共145頁第七十三頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青

25、中是優(yōu)買青年(qngnin)買與不買比例為128/256S1(買)=128 S2（不買）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183第73頁/共145頁第七十四頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買如果選擇收入(shur)作為節(jié)點分高、中、低平均信息期望(qwng)（加權(quán)總和）： E(收入）= 0.3333 * 0 + 0.

26、5 * 0.9183 + 0.1667 * 0 = 0.4592Gain(收入) = I(128, 256) - E(收入)=0.9183 0.4592 = 0.4591I(0,128)=0 比例: 128/384=0.3333I(64,128)=0.9183 比例: 192/384=0.5I(64,0)=0比例: 64/384=0.1667 注意第74頁/共145頁第七十五頁，共145頁。計數(shù)年齡收入學(xué)生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買

27、64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買年齡年齡(ninlng)青年(qngnin)中年老年學(xué)生買信譽葉子否否是是優(yōu)優(yōu)良良買不買買/不買買葉子葉子葉子第75頁/共145頁第七十六頁，共145頁。第76頁/共145頁第七十七頁，共145頁。第77頁/共145頁第七十八頁，共145頁。P(C|X)P(X|C)P(C)P(X)第78頁/共145頁第七十九頁，共145頁。第79頁/共145頁第八十頁，共145頁。)()()|()|(XPCPCXPXCPiii第80頁/共145頁第八十一頁，共145頁。)|()|(1inkkiCxPCXP概率(gil)P(x1|Ci)，P

28、(x2|Ci)，P(xn|Ci)由訓(xùn)練樣本估值。第81頁/共145頁第八十二頁，共145頁。，。即X被指派到其P(X|Ci)*P(Ci)最大的類。第82頁/共145頁第八十三頁，共145頁。希望希望(xwng)分類的未知分類的未知樣本為樣本為:X=（age=“=30”，income=“medium”，student=“yes”，credit_rating=“fair”）思路思路:計算每一個類的計算每一個類的P(Ci|X)=P(X|Ci)P(Ci)/P(X) , Ci代表代表(dibio)任意一個類任意一個類，X代表代表(dibio)需要判斷需要判斷的查詢條件的查詢條件第83頁/共145頁第八十

29、四頁，共145頁。，2。每個類的先驗概率P(Ci)可以根據(jù)(gnj)訓(xùn)練樣本計算：P(buys_computer=”yes”)=9/14=0.643，P(buys_computer=”no”)=5/14=0.357。第84頁/共145頁第八十五頁，共145頁。第85頁/共145頁第八十六頁，共145頁。X=（age=“ buys(x, “beers”) 0.5%, 60%nmajor(x, “CS”) takes(x, “DB”) = grade(x, “A”) 1%, 75%第119頁/共145頁第一百二十頁，共145頁。交易ID購買的商品2000A,B,C1000A,C4000A,D500

30、0B,E,F買尿布的客買尿布的客戶戶二者都買二者都買的客戶的客戶買啤酒的客戶買啤酒的客戶第120頁/共145頁第一百二十一頁，共145頁。尋找關(guān)聯(lián)規(guī)則。尋找關(guān)聯(lián)規(guī)則。n第第1 1個子問題是近年來關(guān)聯(lián)規(guī)則個子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的重點。挖掘算法研究的重點。第121頁/共145頁第一百二十二頁，共145頁。TIDItemset1001，3，42002，3，53001，2，3，54002，5 1994年，年，Agrawal 等人提出了著名等人提出了著名(zhmng)的的Apriori 算法。算法。第122頁/共145頁第一百二十三頁，共145頁。TID Items100 1 3 4200

31、 2 3 5300 1 2 3 5400 2 5Database DC1L1L2C2Scan DL3Scan DC3Scan DC4Scan DScan DL4L3是最大頻繁是最大頻繁(pnfn)項目集項目集第123頁/共145頁第一百二十四頁，共145頁。Rule-generate（L，minconf）（1） FOR each frequent itemset lk in L（2） genrules（ lk ， lk）;關(guān)聯(lián)規(guī)則的生成關(guān)聯(lián)規(guī)則的生成(shn chn)(shn chn)問題問題第124頁/共145頁第一百二十五頁，共145頁。序號序號lkxm-1ConfidenceSuppor

32、t規(guī)則（是否是強規(guī)則）規(guī)則（是否是強規(guī)則）1235267%50%235（否）（否）2235367%50%325（否）（否）3235567%50%523（否）（否）423523100%50%235（是）（是）52352567%50%253（否）（否）623535100%50%352（是）（是）包含包含2,35的事務(wù)的事務(wù)(shw)與包含與包含2的事務(wù)的事務(wù)(shw)的比值的比值,即即2:3同時同時(tngsh)滿足支持度和可信度滿足支持度和可信度TIDItemset1001，3，42002，3，53001，2，3，54002，5第125頁/共145頁第一百二十六頁，共145頁。第126頁/共14

33、5頁第一百二十七頁，共145頁。第127頁/共145頁第一百二十八頁，共145頁。TIDItemset1f,c,a,m,p2f,c,a,b,m3f,b4c,b,p5f,c,a,m,p樣本樣本(yngbn)數(shù)據(jù)庫數(shù)據(jù)庫下面下面(xi mian)看一個例子來說明看一個例子來說明FP-Tree的增長過程的增長過程,最小支持度閾值為最小支持度閾值為3。TIDItemset1f,a,c,d,g,i,m,p2a,b,c,f,l,m,o3b,f,h,j,o4b,c,k,s,p5a,f,c,e,l,m,p, nItemfrequencyf4c4a3b3m3p3L掃描數(shù)據(jù)庫一次生成掃描數(shù)據(jù)庫一次生成1-頻繁項目集（在數(shù)據(jù)庫中出現(xiàn)頻繁項目集（在數(shù)據(jù)庫中出現(xiàn)3次或次或3次以上的），并按頻度降序排序，放入次以上的），并按頻度降序排序，放入L列表