數據挖掘考試重點復習

1、1 ,了解商務智能的定義與大數據的四個基本特征；答：商務智能是企業(yè)利用數據倉庫（DW）、數據挖掘（DM）、在線分析處理（OLAP）、決策支持系統(tǒng)（DS0等現代信息技術對企業(yè)生產、經營過程中產生的大量結構化和非結構化數據進行收集、整理、分析，形成知識或情報，以輔助企業(yè)做出正確的決策、采取有效的商務行動、優(yōu)化商務流程、全面提升商務績效的工具、方法和技術的統(tǒng)稱。大數據特征：（4個V）大數據的特征特征體量VqIuee多樣性"ariety士匕看萌號的超大規(guī)模和增長總數揖用的80F0%比轉構化數據增代快10倍到50倍是傳統(tǒng)數據含庫的10倍到50倍大數據的異構和多樣性很多不同形式（文本、圖像，視理

2、、機益麴據）無模式或者模式不明顯不連貫的語法或句義價值密度Value大量的不相關信息對未來趨騁與模式的可預泅分析深度篁雜分析（機學習.人工智陡也傳統(tǒng)商信智就（咨詢、報告等）速度Velocity昇毒斤茄而非批量式分析數據瞬入，處再萬丟棄立竿見影而非事后見效2 .理解商務智能系統(tǒng)的5層結構商務智能系統(tǒng)結構大致分為五層數據源層：也可稱作操作型數據層，是整個數據倉庫的基礎,提供了整個系統(tǒng)最原始的數據精選文檔數據獲取層：也可稱作數據轉換層，主要是把數據源層的數據通過ETCL過程轉換到數據倉庫中數據存取層：該層是按主題進行分析和對相關的數據進行挖掘的數據源，包括每一個按主題進行分類的數據集市或專門用于數據

3、挖掘的數據倉庫數據分析服務層：該層是數據存儲和前端分析工具的橋梁前端展現層：用戶界面3 .理解操作型與分析型系統(tǒng)分離的必要性以及他們的特征數據處理模式對數據庫聯機的日常操作.通常是對一個或一組記錄的查詢和修改，主要是為企業(yè)的特定應用服務，人們關心的是響應時間、數據安全性和完整性保證業(yè)務正常運作對歷史數據進行分析和推理，找田有價值的模式為決策提供依據.一推就業(yè)務持續(xù)改進精選文檔推陳出新操作型數據庫/數據倉庫分離提高兩個系統(tǒng)的性能數據庫系統(tǒng)是為已知的任務和負載設計的.數據倉庫的查詢通常是復雜的,涉及大量匯總級的計算,在數據庫系統(tǒng)上處理分析,會大大降低操作任務的性能。兩系統(tǒng)對比操作型系統(tǒng)分析型系統(tǒng)系

4、統(tǒng)日的頗內支持日常操作辦事員-數據摩專家支持管理需求、獲取信息管理者.經理-分析專家數據內容當前俏歷史.推導的，匯總的俏適于事務處理適于分析處理訪問頻率IHI中、ft特別*詢.隨機，啟發(fā)式1兩倒幾分科甚至更多相對較少訪間類型讀取、更新、刪除使用方法可預知的.反復的響應時間1杪以F用戶大量精選文檔4 .理解維度爆炸給數據挖掘帶來的困難數據過高的維度會給計算帶來麻煩，在數據挖掘處理時，它會耗費很多的處理時間和內存容量。數據的高維度還使得數據間的關系也不容易察覺，增加了數據的無關屬性和噪音點。5 .掌握數據倉庫的定義并理解其四個方面的特征數據倉庫是決策支持系統(tǒng)和聯機分析應用數據源的結構化數據環(huán)境。數

5、據倉庫研究和解決從數據庫中獲取信息的問題。（數據倉庫是為支持管理決策建立的，面向主題的、集成的、隨時間變化的、相對穩(wěn)定的數據集合。）【滔注：我覺得寫括號里的會好一點】四方面特征： 面向主題：主題是指用戶使用數據倉庫進行決策時所關心的重點忙面。 集成性：在數據進入數據倉庫之前，要進過統(tǒng)一于綜合，將多個異源數據集成在一起。這一步是數據倉庫建設中最關鍵、最復雜的一步。 時變性：數據倉庫隨時間變化不斷增加新的數據。 相對穩(wěn)定性：數據倉庫反映的是歷史的內容，而不是聯機數據，主要供企業(yè)決策分析之用。精選文檔6,掌握數據挖掘的定義并描述其主要特征【數據挖掘定義】從大量的、不完全的、有噪聲的、模糊的、隨機的數

6、據中，提取隱含在其中的、人們事先不知道的、但又是潛在的有用的信息和知識的過程。數據挖掘是從大量數據中尋找其規(guī)律的技術?！局饕襟E】（1）數據準備：從各種數據源中選取和集成用于數據挖掘的數據；（2）規(guī)律尋找：用某種方法將數據中的規(guī)律找出來；（3）規(guī)律表示：用盡可能符合用戶習慣的方式將找出的規(guī)律表不出來。7,掌握Minkowski距離，并熟練計算11,12,l無窮norm1nr二dist（|Pkqkl）rk1Llnorm當r=1,城市街區(qū)（也稱曼哈頓、出租車、L1范數）距離；L2norm當r=2,歐幾里得距離；L°°norm當r=°0,上確界距離，這是對象屬性之間的最

7、大距離。精選文檔MinkowskiDistance閔可夫斯基距離例題pOlOtpl0pa0p3&15I.1Npit>ypl0446P-A0Ap3402P-*6-r0Lin<xwL2pl向P】02S263162P-2£280414:S2p33.1621.4X402，聽9j.162工olL2ncrrrLunomL«PlP2F3pl0j35向013淤310p45320DistanceMatrix距離矩陣8,理解Hunt's算法的基本過程通過將訓練記錄相繼劃分成較純的子集，以遞歸方式建立決策樹。設Dt是與節(jié)點t相關聯的訓練記錄集，而Y=y1,y2,c號類

8、標號,Hunt算法的遞歸定義如下：(1)如果Dt中所有記錄都屬于同一個類yt,則t是葉節(jié)點，用yt標記。(2)如果Dt中包含屬于多個類的記錄，則選擇一個屬性測試條件，將記錄劃分成較小的子集。對于測試條件的每個輸出創(chuàng)建一個子女節(jié)點，并根據測試結果將Dt中的記錄分布到子女節(jié)點中。然后，對于每個子女節(jié)點，遞歸地調用該算法。精選文檔Hunt'sAlgorithmKi:fund1ItuMcIncome露心,1s4hgta125KNo4N0MarrwdlOOKNo3ShgieFNd4YeaMamed120KNo5No口的95K9Mo“arrw，皿No7YmD時時£方2MKNoaNo啾Vf

9、t9NoMamedmNO10NO5-hgioWK¥*TKtHtlbndHviiUIT.kx«bl*SUtUitI方已"rt總Chwt9.掌握吉尼系數、嫡的定義，會計算其最大值與最小值，理解信息增益在構造決策樹時的意義【基尼系數、嫡是度量不純度的方法】GINI系數和嫡都是越小，代表所分的節(jié)點屬性越純，最小可取到0,表示這個節(jié)點中只有一個類。當一個節(jié)點中有n個父節(jié)點，而且能分出n個子節(jié)點，GINI系數取到最大值，為1-1/n.嫡也取到最大值10g2n（滔注：那個2是角標，不是1og2n!）【基尼值的性質】：越大越不純，越小越純，0最純，1-1/n最不純。精選文檔Mea

10、sureofImpurity:GINIGimIndexforagivennodet:(NOTE.p(j11)istherelativefrequencyofclassjatnodeti.Maximum(1-1/nc)whenrecordsareequallydistributedamongallclasses,implyingleastinterestinginformation-Minimum(0.0)whenallrecordsbelongtooneclass,implyingmostinterestinginformationExamplesforcomputingGINIf7/7(o=

11、1-£uiorGiM1-戶一印6戶口.打電P(C1)*06-0P1C2)*6蘋*1白坨|1_PC1|2-P1C2)3*1-o-1*0ClPfC力餐由6Pie藥=4圖Gink=1-例產T*呼=O+Mt*i11lcsnull.T.llupirer*Cl.3a3b.子節(jié)點基尼值C2SplittingBasedonGINIUsedinCART,SLIQ,SPRINT«Whenanodepissplitintokpartitions(children,thequalityofsplit(chhdren)iscomputedasi=lftwhere,n,=numberofrecords

12、atchildi.n=numberofrecordsatnodep.精選文檔BinaryAttributes:ComputingG1NIIndex Splitsintotwopartitions EffectolWeighingpartitionsLarger白ndPurerPartitionsaresoughtfdiB7J)rGini(NI)二1-|麗-(2ffp=o.4oaGi而N?)=1-11SF_(W5產=0.32Yrfi，NdX_ModeMlIiNodeN：ClC2GIM=0.500GlnHChildren)7/12r0.408+9/12*o.aa0.375c.最大值、最小值Meas

13、ureofImpurity:GINI*GlnlIndexfaragivennodet:(NOTE:/1門istherelativefrequencyofclassjatnodet).-Maximum(1-1/nc)whenrecordsareequallydistributedamongallclasses,implyingleastinterestinginformation-Minimum(0.0)whenallrecordsbelongtooneclass,implyingmostinterestinginformation（最小值表示最純，最大值表示最不純）【嫡】在信息領域嫡被用來衡量

14、一個隨機變量出現的期望值。嫡是對信息的不確定性的度量。嫡越低，意味著傳輸的信息越少?！镜盏男再|】：嫡是衡量節(jié)點一致性的函數。嫡大于等于0,當且僅當p1=p2=pn時,嫡最大，純的節(jié)點嫡是0.精選文檔SplittingCriteriabasedonEntropy«Entropyatagivennodet:Entropylf)="zQlogp(j/)(NOTE:isrelativefrequencyofclassjatnodet)-Measureshomogeneityofanode. Maximum0兇n.vhenrecordsareequallydistributedamo

15、ngallclassesimplyingleastinformation Minimum(0.0)whenallrecordsbelongtooneclass,implyingmostinformation EntropybasedcomputationsaresimilartotheGINIindexcomputationsExamplesforcomputingEntropyEnlropy(t)=Np(/1/)logpjF)【信息增益】當選擇嫡作為公式的不純性度量時，嫡的差就是所謂的信息增益。信息增益描述了當使用Q進行編碼時，再使用P進行編碼的差異。通常P代表樣本或觀察值的分布，也有可能是

16、精確計算的理論分布。Q代表一種理論，模型，描述或者對P的近似。當純度高達1時(即只有一種數據類型)：嫡最小，為0;當其中的各類數據均勻分布時，嫡最大，為-log2P(j|t)。精選文檔10.理解了解最鄰近分類的基本思想，鄰近分類的前提條件與分類過程【近鄰分類法】是基于類比學習，即通過將給定的檢驗元組與和它相似的訓練元組進行比較來學習。訓練元組用n個屬性描述。每個元祖代表n維空間的一個點。這樣，所有的訓練元組都存放在n維模式空間中。當給定一個未知元組時，近鄰分類法搜索模式空間，找出最接近未知元組的k個訓練元組。這k個訓練元組是未知元組的k個“最近鄰”。一句話概述：點x的k-最近鄰分類就是離點x的

17、歐式距離最近的k個點的集Nearest-NeighborClassifiersUnknownrecordRequiresthreethings-ThesetofstoredrecordsDistanceMetrictocomputedistancebetweenrecords-Thevalueofk,thenumberofnearestneighborstoBtrieveToclassifyanunknownrecord:ComputedistancetoothertrainingrecordsIdentityknearestneighbors-Useclasslabelsofnearestn

18、eighborstodeterminetheclasslabelofunknownrecord(eg,bytakingmajorityvote)三個前提條件：訓練集存在內存中；給定距離度量指標；給定K值分類過程：1計算未知點與其他訓練集的距離精選文檔2找到K個最鄰近的鄰近組3用鄰近組的分類標簽來決定未知點所在組的標簽。11. 了解分類中的過擬合及產生的原因【過度擬合數據】當決策樹變大時，測試誤差會越來越小，而訓練誤差會越來越大，測試集產生的決策樹與實際會不符。【產生的原因】(1)噪聲導致的過分擬合(2)決策樹的復雜程度超過了需要的程度，會產生過度擬合(3)訓練誤差的減小已經對結果沒有更多意義但

19、卻依然在計算，會產生過度擬合(4)沒有更多的屬性來減小樣本誤差，會產生過度擬合12. 理解關聯規(guī)則及支持與置信度的定義，并熟練計算支持度與置信度【關聯規(guī)則】關聯規(guī)則是形如X-Y的蘊涵式，其中，X和Y都是事務數據集。關聯規(guī)則的強度可以用它的支持度和置信度度量?！局С侄萐upport!事務數據庫中既包含X又包含Y某個項集的事務占事務總數的比例；【置信度Confidence在所有包含X的事務中包含Y的事務所占比例。精選文檔Example:Milk,Di叩ernBeertr(MiIkzDiaperBeer)_2_|T|",二一0U+nr。二仃(MilkQ加鈍B"r)二ofMilkD

20、iaper)支持度(Support)f事務敵據滓中包含國小項集的事多占事務總效的比例白77DItfMSEMilk.Di邛帝質=2=041即閑,Milk|I52Br»d.Diaper.E陽13Ulk,DIj卬”.除一匚dif-1Eke山MillDia|itiBtei5Biffld,Dupcr,f&ke例子iMilk,Diaper)->Beer(0.4.0,67),矍信度-Confidence(c)一4所布包畬x的事務中電含丫的事務所占比例b(Mi【k)_?EMilk,Diaper)4MiningAssociationRulesIF/U一ExampleofRulesMilk

21、hDiaperBeers=Q4,o=067)MEBeelDEF)(s=04hc=1.0)DiaperB&erMilk(s=04,c=0.6711Ikrid.5Iilk2BrucklMpmBrer.FfgE3Milk.口岫p*由卜/4Rrnd.Milk,IHapfr.H«r5llrnd.Milk.Dhpcr.CckrBeer1(Milk,Diaper*(s=04c=067)DiaperMilkhBeer)(5=0.4c=&5)Milk*DHper.EgF)$=0.4c=05)13. 理解Apriori性質及其意義Apriori如果一個項集是頻繁的，那么它的所有子集都是頻

22、繁的。相反，如果一個項集是非頻繁的，則它的所有超集也一定是非頻繁的?！疽饬x】利用該性質，通過減少搜索空間，來提高頻繁項集逐層產生的效率精選文檔14. 理解FP-Growth算法克服了Apriori算法的那些不足1 .減少了掃描數據庫的次數，只用掃描兩次2 .候選項變少，不會產生那么大的候選項集15. 給定一個交易數據庫與支持度閾值，能熟練運用Apriori算法與FP-Growth算法挖掘頻繁項集Min'rnumSupport=3Items(1Kcmsas)PairsgnifmK)(NntocandidalesinvolvingCokeorrroTriplets3itens&ts

23、)Apriori算法計算頻繁項集】1BrewlpAnik?Br»flipDid/叫Mr.E巴爐iMilkDiipff.BwCotoi-2dlimxXs5-Bread.103k.DiaperTCokf【步驟】1、第一次掃描，列出一項集，并計數2、去除低于閾值的項集，組合出二項集，掃描計數。3、重復步驟2,依次組合出N項集，直至項集計數小于閾值，結束【注意】Apriori定義：如果一個項集是非頻繁的，則它的所有超集也一定是非頻繁的。所以在組合項集時一定要注意，新組合出的項集不應包含已經被“淘汰”的項集。精選文檔FP-Growth算法計算頻繁項集】步驟一、掃描一次數據集，確定每個項的支持度

24、計數。丟棄非頻繁項，將頻繁項按照支持度的遞減排序，生成頻繁項集頭表。(注意事項：1、降序排列。2、MinSup的存在！)TITyTfrw.sbought100tfac,g,irrn,p200a,bfctfLmto>300也£hj.o)400byc,k.spBy-FrodjctofFirstScanofDatabase步驟二、第二次掃描投影，按照f,c,a,b,m,p的順序逐條對應寫出剔除非頻繁項后的頻繁集，(注意：f,c,a,b,m,p的順序確定后就不在變動，這在下面的步驟中起關鍵作用)f,cTaTb,m.p)TIPItems如ughtf0由-eg賽儂IO0dfgti,m,p)

25、200a.b,e,ft(mto300(Vh,i。400brcf500。/c良2P.nih.1的也ffi。arR5A£切瓦cMstrkJjr-ITJp朋IJJ.步驟三、并開始構建FP樹。按照事務ID號的順序，將處理好的頻繁項集映射$0。彳烏/G凡LP附h創(chuàng)建FP樹，并在對應節(jié)點計數恍£鼻FpNOTE:Lachtransactionccrie5pundstucrivpaliiintheFP-tree精選文檔FinalFP-tree(注意：不要步驟四、構建每個對象的條件模式基，建議從頻率低的節(jié)點開始。忘了f對應的()Conditionalpauernbases族刎mud.刀口仃電

26、界通口壁pJicam;2fcb:lbc;lafi:3c#3/1)步驟五、列出下表，對照MinSup剔除低于閾值的項。ItemConditionalpatternbaseConditionalFP-treeP(fcam：2)/cb:l)i(c：3)|pm(fca(fcab;l)(f:3fc:3,a3)|mbEmptya體;3)(f;3,c:3)|ac«f：3»fEmptyEmptyMinSup-3步驟六、針對每一項建立條件FP樹。下面用m項作例子，如下精選文檔Md叩=3HeaderTable步驟七、找出頻繁項集。1I儲c；3-a:3m-conditionalFP-treeAl

27、lfrequentpatternsconcerning川:combinationof£c:aandJm風fin,an.am,ca)nfcam16. 理解關聯規(guī)則產生時所采取的優(yōu)化策略(老師說直接距離就可以)比如，L=A,B,C,D):c(ABCD)>c(AB-CD)>c(ABCD)【為什么？分子不變，都是ABCD,分母越來越大】17. 理解K-means算法的內容并討論該算法之不足【K-meandK均值算法流程1、隨機選擇K個對象，每個對象代表一個簇的初始均值或中心2、對剩余的每個對象，根據它與簇均值的距離，將他指派到最相似的簇3、計算每個簇的新均值精選文檔4、回到步驟2

28、,循環(huán)，直到準則函數收斂*K-均值其法過程示例K=2隨機選打2個:象作為族的中心個指最的苗第卦像將時港相族掠的新唉他叱個均年的新技tfL一更個均【不足之處】1、只有當簇均值有定義的情況下，K-means方法才能夠使用2、用戶必須首先給定簇數目3、不適合發(fā)現非凸形狀的簇，或者大小差別很大的簇。4、對噪聲和離群點數據敏感。18. 理解凝聚聚類算法的基本過程，并分析算法時間與空間復雜度精選文檔AgglomerativeClusteringIPopularhierarchicalclusteringtechniquefBasicalgorithmisstraightforward1, Computet

29、heproximitymatrix2, Leteachdatapointbeaduster3, Repeat4, MergethetwogI。33stclusters5, Updatetheproximitymatrix6, Untilonlyasingleclusterremains/Keyoperationisthecomputationoftheproximityoftwoclusters-Differentapproachesdefiningthedistancebetweenclustersdistinguishthedifferentalgorithmsd步驟：1計算距離矩陣2讓每

30、個數據點成為一個群集3,循環(huán)開始4,合并兩個距離最近的群集5,更新距離矩陣6,直到只剩下一個群集精選文檔TimeandSpacerequirementsl0(N2)spacesincehierarchicalclusteringusestheproximitymatrix.-Nisthenumberofpoints,.O(N3：timeinmanycases一ThereareNstepsandateachstepthesize,N2,proximitymatrixmustbeupdatedandsearched-ComplexitycanbereducedtoO(N2log(N):timeforsomeapproaches時間復雜度：N2倍空間復雜度：N3倍19. 理解DBSCAN算法將待聚類的點分為哪幾類，分解解釋之精選文檔DensityBasedClustering:DBSCANIDBSCANisadensity-basedalgorithm.- Den