數(shù)據(jù)挖掘技術(shù)方法P151課件

數(shù)據(jù)挖掘技術(shù)1分類和預(yù)測2分類對離散數(shù)據(jù)的分類稱為分類，對數(shù)值數(shù)據(jù)的分類稱為預(yù)測。分類要解決的問題是為一個事件或?qū)ο髿w類，即確定一個特定的對象屬于哪一類。分類函數(shù)或分類模型(分類器)分類模型是通過那些已知歷史數(shù)據(jù)訓(xùn)練出來的。這里用于建立模型的數(shù)據(jù)稱為訓(xùn)練集，通常是已經(jīng)掌握的歷史數(shù)據(jù)。在訓(xùn)練集中每個對象都賦予一個類別的標(biāo)記，不同的類別具有不同的標(biāo)記。分類就是通過分析訓(xùn)練集中的數(shù)據(jù)，為每個類別做出準確的描述或建立分析模型或挖掘出分類規(guī)則，然后用這個分類規(guī)則對其它數(shù)據(jù)對象進行分類。3分類數(shù)據(jù)ThedatausedtobuildaclassificationmodelconsistsofAsetofrecords.Eachrecordhasthesamenumberoffields.Onefieldintheserecordcontainsindicatorsofclasseswhichrecordsbelongto.Thisfieldiscalledtargetfield.Otherfieldsarecalledindependentfieldswhichdescribetheindividualobjectsrepresentedbytherecords.5決策表實例6決策樹arewidelyusedindatamining.weredevelopedinmachinelearningandstatistics.areusedtobuildclassificationandpredictionmodels.arewidelyavailable.判定樹分類算法output訓(xùn)練集決策樹input新數(shù)據(jù)分類7決策樹算法基本算法（貪心算法）自上而下分而治之的方法開始時所有的實例都在根節(jié)點屬性都是分類型(如果是連續(xù)的，將其離散化)所有記錄用所選屬性遞歸的進行分割屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量(如信息增益)停止分割的條件一個節(jié)點上的實例都屬于同一個類別；沒有屬性可以再用于對數(shù)據(jù)進行分割9屬性選擇的統(tǒng)計度量信息增益—Informationgain(ID3/C4.5)所有屬性假設(shè)都是分類型字段經(jīng)過修改之后可以適用于數(shù)值型字段基尼指數(shù)—Giniindex(IBMIntelligentMiner)能夠適用于分類和數(shù)值字段其他10信息增益度度量(ID3/C4.5)任意樣本分類的期望信息：I(s1,s2,……,sm)=－∑Pilog2(pi)(i=1..m)其中，數(shù)據(jù)集為S，m為S的分類數(shù)目，PiCi為某分類標(biāo)號，Pi為任意樣本屬于Ci的概率，si為分類Ci上的樣本數(shù)由A劃分為子集的熵：E(A)=∑j(|s1j|+……+|smj|)/|s|*I(s1j，……，smj)A為屬性，具有V個不同的取值信息增益：Gain(A)=I(s1,s2,……,sm)－E(A)11使用信息增益進行屬性選擇ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarly0.69413分枝14決策樹age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..401517基尼指數(shù)（GiniIndex）集合T包含n個類別的記錄，那么其Gini指數(shù)就是

pj

類別j出現(xiàn)的頻率如果集合T分成兩部分N1andN2。那么這個分割的Gini就是提供最小Ginisplit

就被選擇作為分割的標(biāo)準.18PruningTree目的：消除決策樹的過擬合(OverFitting)問題實質(zhì)：消除訓(xùn)練集中的異常和噪聲兩種方法：先剪枝法(Public算法)后剪枝法(Sprint算法)19誤分類率

C1 C2 C3C1 0 r12

r13

C2

r21 0 r23C3

r31

r32 0實際類別分類類別Cost(orloss)matrix21常用的決策樹算法

ID3,C4.5,C5.0(RossQuinlan1986,1993)CART(LeoBriemen,etal1984)CHAID(J.A.Hartigan,1975)22銀行信用卡市場分析員的市場促銷（1）確定促銷最理想的顧客群體?？蛡兪欠袷倾y行的受益顧客？這里的常客指每月至少使用一次信用卡的顧客，受益顧客指為銀行帶來回報的顧客。顧客分類記錄人數(shù)常顧客76028給企業(yè)帶來最大收益的顧客7205176028720515124常顧客和給企業(yè)帶來最大收益的顧客2類顧客數(shù)量比較報告23銀行信用卡市場分析員的市場促銷（3）401709個記錄帳戶平衡的：24378960.7%延遲超過60天的8586921.4%延遲超過30天的7205117.9%婚姻狀況=寡居36519個記錄帳戶平衡的：789621.6%延遲超過60天的1677945.9%延遲超過30天的1184432.4%婚姻狀況=獨身65142個記錄帳戶平衡的：1974030.3%延遲超過60天的987015.2%延遲超過30天的3553254.5%婚姻狀況=已婚300048個記錄帳戶平衡的：21615372.0%延遲超過60天的5922019.7%延遲超過30天的246758.2%居住情況=租房42441個記錄帳戶平衡的：9872.3%延遲超過60天的592214.0%延遲超過30天的3553283.7%居住情況=自有住房22701個記錄帳戶平衡的：1875382.6%延遲超過60天的394817.4%月可支配收入938美元6909個記錄帳戶平衡的98714.3%延遲超過60天的592285.7%月可支配收入>938美元35532個記錄延遲超過30天的35532100%Customerprofiling25預(yù)測預(yù)測是構(gòu)造和使用模型評估給定的樣本數(shù)據(jù)可能具有的屬性值或值區(qū)間：離散數(shù)據(jù)的預(yù)測：可以使用分類分析的方法，例如預(yù)測一個移動用戶是否流失。連續(xù)數(shù)據(jù)的預(yù)測：可以使用回歸分析的方法。26神經(jīng)元神經(jīng)元：每個細胞處于兩種狀態(tài)，突觸聯(lián)接有強度。多輸入單輸出，實質(zhì)上傳播的是脈沖信號，信號的強弱與脈沖頻率成正比。UseneuralmodelstoapproximatemultiplevariatefunctionslikeY=f(X1,X2,…,Xn,W1,W2,…,Wk)Here,theformoff(...)isunknown.Xiareinputvariables,Wiarecoefficients

.29神經(jīng)網(wǎng)絡(luò)用途分類

回歸

預(yù)測

聚類30神經(jīng)網(wǎng)絡(luò)適合數(shù)值型數(shù)據(jù)以數(shù)值型數(shù)據(jù)為輸入

輸出為可分類屬性31神經(jīng)網(wǎng)絡(luò)模型*Multi-layerPerceptrons(ANN)RadialBasisFunctionNetworks(RBFN)ProbabilisticNeuralNetworks(PNN)32前饋型神經(jīng)網(wǎng)絡(luò)最初稱之為感知器。應(yīng)用最廣泛的一種人工神經(jīng)網(wǎng)絡(luò)模型，采用BP學(xué)習(xí)算法。前饋網(wǎng)絡(luò)結(jié)構(gòu)是分層的，信息只能從下一層單元傳遞到相應(yīng)的上一層單元。上層單元與下層所有單元相聯(lián)結(jié)。激活函數(shù)可以是線性的。33感知器的不足1957年FrankRosenblatt定義了一個神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)感知器（perception）。第一次把神經(jīng)網(wǎng)絡(luò)研究從純理論的探討推向工程實現(xiàn)，在IBM704計算機上進行了模擬，證明了該模型有能力通過調(diào)整權(quán)的學(xué)習(xí)達到正確分類的結(jié)果。1969年Minsky和Papert發(fā)表了《Perceptions》的論著，指出感知器僅能線性劃分，對于非線性或其他分類會遇到很大困難。34BP網(wǎng)的產(chǎn)生1986年美國的一個并行計算研究小組提出了前向反饋神經(jīng)網(wǎng)絡(luò)的BackPropagation（BP）算法，成為目前最廣泛使用的方法之一，克服了感知器非線性不可分類問題。35BP神經(jīng)網(wǎng)絡(luò)輸出隱層x1x2x3x4x5x6x7y1y2y3y4yw11w12w74w1w2w3w4給定訓(xùn)練樣本集

設(shè)計網(wǎng)絡(luò)結(jié)構(gòu)

訓(xùn)練網(wǎng)絡(luò)36網(wǎng)絡(luò)基本參數(shù)網(wǎng)絡(luò)結(jié)構(gòu)包括隱層數(shù)和隱層節(jié)點數(shù)學(xué)習(xí)率： w(t+1)=w(t)+(d-y)xi停止條件：

訓(xùn)練次數(shù)、精度或時間37神經(jīng)網(wǎng)絡(luò)的應(yīng)用(1)在財務(wù)方面，神經(jīng)網(wǎng)絡(luò)可用來協(xié)助投資公司預(yù)測普通股的表現(xiàn)、公司的債券等級或公司破產(chǎn)的可能性。VISA國際公司用神經(jīng)網(wǎng)絡(luò)來幫助偵測信用卡欺詐，它監(jiān)控所有VISA交易并且注意持卡人消費形態(tài)的改變。收入負債年齡付款記錄信譽良好風(fēng)險值信譽不良風(fēng)險值38神經(jīng)網(wǎng)絡(luò)的應(yīng)用(2)股票拐點趨勢預(yù)測:利用歷史價格數(shù)據(jù)預(yù)測中短期（從2到10或15天）的價格走勢。

39貝葉斯分類器

40貝葉斯定理

假設(shè)X和Y在分類中可以分別表示樣本的屬性集和類別。P(X,Y)表示它們的聯(lián)合概率，p(X|Y)和p(Y|X)表示條件概率，其中是后驗概率，而稱為Y的先驗概率。X和Y的聯(lián)合概率和條件概率滿足下列關(guān)系：變換后得到41樸素貝葉斯分類器

對于屬性集，如果之間相互獨立，即，有樸素貝葉斯分類器：

其中是常數(shù)，先驗概率可以通過訓(xùn)練集中每類樣本所占的比例估計。給定，如果要估計測試樣本X的分類，由樸素貝葉斯分類器得到y(tǒng)類的后驗概率：

只要找出使最大的類別y即可。

42貝葉斯分類器在供電電容生產(chǎn)中的應(yīng)用（1）

假設(shè)某段時期內(nèi)某電腦主板制造商所用的供電電容是由三家電容生產(chǎn)廠提供的。對制造商在這段時期內(nèi)的業(yè)務(wù)數(shù)據(jù)進行抽樣，得到下表。因為三家電容工廠的供電電容在電腦主板生產(chǎn)商的倉庫中是均勻混合的，并無明顯的區(qū)別標(biāo)志?，F(xiàn)在電腦主板生產(chǎn)商想通過對數(shù)據(jù)進行分析，解決下面兩個問題：（1）隨機地從倉庫中取一只供電電容是次品的概率。（2）從倉庫中隨機地取一只供電電容，若已知取到的是一只次品，想分析此次品來自哪家工廠的可能性最大。43貝葉斯分類器在供電電容生產(chǎn)中的應(yīng)用（2）

44貝葉斯分類器在垃圾郵件處理中的應(yīng)用

貝葉斯分類器是對郵件的內(nèi)容進行分析，不僅考慮關(guān)鍵詞在垃圾郵件中出現(xiàn)的概率，也考慮關(guān)鍵詞在正常郵件中的概率。當(dāng)一封新的郵件到達時，這封郵件的內(nèi)容將被分解成字串。依據(jù)數(shù)據(jù)庫中這些詞的概率通過公式進行計算，用貝葉斯定理計算出的垃圾郵件可能性高于某個閾值時就判定這封郵件是垃圾郵件。貝葉斯過濾防范有一定的智能性，通過一定的學(xué)習(xí)方法可以對數(shù)據(jù)庫詞的概率進行更新，可以適應(yīng)垃圾郵件的變化情況。

45K-最近鄰分類遺傳算法粗糙集理論模糊理論…

其他分類方法46聚類

Clustering47聚類Definitionofclustering Clusteringisaprocessofpartitioningasetofobjectssuchascustomersintogroupsinwhichtheobjectsinthesamegrouparesimilartoeachotherandtheobjectsindifferentgroupsaredissimilar,accordingtosomesimilaritymeasure.

聚類就是把整個數(shù)據(jù)分成不同的組，并使組與組之間的差距盡可能大，組內(nèi)數(shù)據(jù)的差異盡可能小。ClusteringisoftencalledunsupervisedclassificationClusteringisusedforcustomersegmentation48聚類分析簇（Cluster）:一個數(shù)據(jù)對象的集合聚類分析把一個給定的數(shù)據(jù)對象集合分成不同的簇；聚類是一種無監(jiān)督分類法:沒有預(yù)先指定的類別；典型的應(yīng)用作為一個獨立的分析工具，用于了解數(shù)據(jù)的分布；作為其它算法的一個數(shù)據(jù)預(yù)處理步驟；CustomerSegmentationCustomersegmentationisaprocesstodividecustomersintogroupsorsegments.Customersinthesamesegmenthavesimilarneedsorbehaviorssothatsimilarmarketingstrategiesorservicepoliciescanbeappliedtothem.SegmentationaccordingtosomevariablesE.g.,usecustomertypevariabletodividecustomersintocorporatecustomersandindividualcustomersSegmentationusingadataminingtechniquesE.g.,aclusteringalgorithmordecisiontreealgorithm50與分類的區(qū)別與分類不同，在開始聚集之前用戶并不知道要把數(shù)據(jù)分成幾組，也不知分組的具體標(biāo)準，聚類分析時數(shù)據(jù)集合的特征是未知的。聚類根據(jù)一定的聚類規(guī)則，將具有某種相同特征的數(shù)據(jù)聚在一起也稱為無監(jiān)督學(xué)習(xí)。分類用戶則知道數(shù)據(jù)可分為幾類，將要處理的數(shù)據(jù)按照分類分入不同的類別，也稱為有監(jiān)督學(xué)習(xí)。51聚類問題的數(shù)學(xué)描述給定數(shù)據(jù)集合V，根據(jù)數(shù)據(jù)對象間的相似程度將數(shù)據(jù)集合分成組，并滿足：則該過程稱為聚類。Ci稱為簇。52基本概念

ClustercenterClustersizeClusterdensityClusterdescriptions一個好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果—簇，這些簇要具備以下兩個特點：高的簇內(nèi)相似性低的簇間相似性53聚類的典型應(yīng)用

模式識別空間數(shù)據(jù)分析在GIS中，通過聚類發(fā)現(xiàn)特征空間來建立主題索引；在空間數(shù)據(jù)挖掘中，檢測并解釋空間中的簇；圖象處理經(jīng)濟學(xué)(尤其是市場研究方面)WWW文檔分類；分析WEB日志數(shù)據(jù)來發(fā)現(xiàn)相似的訪問模式ClusteranalysisofdataCustomersegmentationFrauddetectionMissingvalueprediction54聚類需求

可伸縮性能夠處理不同類型的屬性能發(fā)現(xiàn)任意形狀的簇在決定輸入?yún)?shù)的時候，盡量不需要特定的領(lǐng)域知識；能夠處理噪聲和異常對輸入數(shù)據(jù)對象的順序不敏感能處理高維數(shù)據(jù)能產(chǎn)生一個好的、能滿足用戶指定約束的聚類結(jié)果結(jié)果是可解釋的、可理解的和可用的55計算對象之間的相異度通常使用距離來衡量兩個對象之間的相異度。常用的距離度量方法有:

明考斯基距離（Minkowskidistance）:其中i=(xi1,xi2,…,xip)和

j=(xj1,xj2,…,xjp)是兩個p維的數(shù)據(jù)對象,q是一個正整數(shù)。當(dāng)q=1時,d

稱為曼哈坦距離（Manhattandistance）56SimilarityandDissimilarityBetweenObjects(Cont.)當(dāng)q=2時,

d就成為歐幾里德距離:距離函數(shù)有如下特性：d(i,j)

0d(i,i)

=0d(i,j)

=d(j,i)d(i,j)

d(i,k)

+d(k,j)可以根據(jù)每個變量的重要性賦予一個權(quán)重57二元變量二元變量的可能性表 其中每個對象有p個變量，且 p=a+b+c+dObjectiObjectj58二元變量對稱的

如果一個二元變量的兩個狀態(tài)是同等價值的，具有相同的權(quán)重。即可以任取其中一種狀態(tài)編碼為1或者0。對于對稱的二元變量，采用簡單匹配系數(shù)來評價兩個對象之間的相異度

59二元變量非對稱的 如果變量的兩個狀態(tài)不是同樣重要的，則稱該變量是不對稱的。將比較重要通常也是出現(xiàn)概率比較小的狀態(tài)編碼為1，將另一種狀態(tài)編碼為0。對于非對稱的二元變量，采用Jaccard系數(shù)來評價兩個對象之間的相異度60二元變量的相異度計算gender是一個對稱的二元變量其它的都是非對稱的二元變量將值Y和P編碼為1,值N編碼為0，根據(jù)Jaccard系數(shù)計算得：61標(biāo)稱變量（NominalVariables）標(biāo)稱變量是二元變量的推廣，它可以具有多于兩個的狀態(tài)，比如變量map_color可以有red,yellow,blue,green四種狀態(tài)。有兩種計算相異度的方法：方法1:簡單匹配方法m是匹配的數(shù)目,

p是全部變量的數(shù)目方法2:使用二元變量為每一個狀態(tài)創(chuàng)建一個新的二元變量，可以用非對稱的二元變量來編碼標(biāo)稱變量。62序數(shù)型變量一個序數(shù)型變量可以是離散的也可以是連續(xù)的離散的序數(shù)型變量類似于標(biāo)稱變量，除了它的M個狀態(tài)是以有意義的序列排序的，比如職稱。連續(xù)的序數(shù)型變量類似于區(qū)間標(biāo)度變量，但是它沒有單位，值的相對順序是必要的，而其實際大小并不重要。63聚類算法

K-meanstypealgorithmsKohonenneuralnetwork(self-organizingmap)Hierarchicalclusteringmethods其他64K-均值算法（1）InputAsetofnumericrecordsAnintegerk>1(numberofclusterstobefound).OutputApartitionofrecordsintokclusters.Eachrecordisidentifiedasoneofthekclusters.x11,x12x21,x22…xn1,xn2x11,x12 1x21,x22 2…xn1,xn2 165K-均值算法過程661.Selectkdistinctrecordsasinitialmeans,eachrepresentingacluster.2.Foreachrecordindata,calculatethesquaredEuclideandistancesbetweenitandthemeans.Assigntherecordtotheclusterwhosemeanisthenearesttotherecord.3.Afterallrecordsareassignedacluster,calculatethenewmeanforeachclusterastheaverageofallrecordsinthecluster.4.Ifthenewmeansequaltothepreviousmeans,stop,otherwise,gotoStep2.K-均值算法（2）671x11,x122x21,x223x31,x324x41,x425x51,x526x61,x62C1C21x11,x1212x12,x1213x13,x1224x14,x1215x15,x1226x16,x122C1C21x11,x1212x12,x1223x13,x1224x14,x1215x15,x1216x16,x121C1C268K-均值算法性質(zhì)

EfficientinclusteringlargedataSolutiondependsoninitialmeansSensitivetooutliersSphericalclustersNumericdata69K-均值算法局限非球形的簇70發(fā)現(xiàn)客戶的特征客戶分割（segmentation）是一種發(fā)現(xiàn)用戶特性的方法。數(shù)據(jù)驅(qū)動的分割將一個基于數(shù)據(jù)的客戶信息的自然客戶分組：從而給你一個客戶信息的概況，這可以直接轉(zhuǎn)化為增加客戶的經(jīng)營策略。71聚類可視化TotalPopulationThisClass性別FM050001000015000200002500030000350004000045000500000102030percentTotalPopulationThisClass收入72聚類結(jié)果

–信用卡用戶聚類73聚類結(jié)果

–高花費用戶74偏離（異常）檢測75偏離檢測在數(shù)據(jù)庫中尋找含有你不希望出現(xiàn)的值的記錄或記錄系列。應(yīng)用實例：用它來識別欺詐行為模式或控制生產(chǎn)過程的質(zhì)量。76異常探測異常探測是數(shù)據(jù)挖掘中一個重要方面，用來發(fā)現(xiàn)“小的模式”(相對于聚類)，即數(shù)據(jù)集中顯著不同于其它數(shù)據(jù)的對象。異常探測應(yīng)用電信和信用卡欺騙貸款審批藥物研究氣象預(yù)報金融領(lǐng)域客戶分類網(wǎng)絡(luò)入侵檢測等

77什么是異常（outlier）？Hawkins(1980)給出了異常的本質(zhì)性的定義：異常是在數(shù)據(jù)集中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非隨機偏差，而是產(chǎn)生于完全不同的機制。聚類算法對異常的定義：異常是聚類嵌于其中的背景噪聲。異常探測算法對異常的定義：異常是既不屬于聚類也不屬于背景噪聲的點。他們的行為與正常的行為有很大不同。78關(guān)聯(lián)分析associationanalysis79關(guān)聯(lián)若兩個或多個變量的取值之間存在某種規(guī)律性，就稱為關(guān)聯(lián)。關(guān)聯(lián)規(guī)則是尋找在同一個事件中出現(xiàn)的不同項的相關(guān)性，比如在一次購買活動中所買不同商品的相關(guān)性。關(guān)聯(lián)分析即利用關(guān)聯(lián)規(guī)則進行數(shù)據(jù)挖掘。關(guān)聯(lián)規(guī)則是形式如下的一種規(guī)則，“在購買計算機的顧客中，有30％的人也同時購買了打印機”。從大量的商務(wù)事務(wù)記錄中發(fā)現(xiàn)潛在的關(guān)聯(lián)關(guān)系，可以幫助人們作出正確的商務(wù)決策。80啤酒和尿布問題反映一個事件和其他事件之間依賴或關(guān)聯(lián)的知識。如果兩項或多項屬性之間存在關(guān)聯(lián)，那么其中一項的屬性值就可以依據(jù)其他屬性值進行預(yù)測。在美國，一些年輕的父親下班后經(jīng)常要到超市去買嬰兒尿布，超市也因此發(fā)現(xiàn)了一個規(guī)律，在購買嬰兒尿布的年輕父親們中，有30%～40%的人同時要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。81購物籃分析此類關(guān)聯(lián)分析在零售業(yè)，如超市等得到廣泛應(yīng)用，企業(yè)可以獲得注入產(chǎn)品間的關(guān)聯(lián)，或者產(chǎn)品類別和購買這些類別的產(chǎn)品的顧客的統(tǒng)計信息之間的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)分析又稱購物籃分析，在銷售配貨、商店商品的陳列設(shè)計、超市購物路線設(shè)計、產(chǎn)品定價和促銷等方面得到廣泛應(yīng)用。82AssociationRuleThefirstassociationdiscoveryalgorithmwasdesignedforbasketanalysisinretail.Trytoanswer“HowmanycustomerswhoboughtitemXalsoboughtItemY?”Suchalgorithmhasbeenfoundusefulinotherapplications,e.g.,associationsofdrugs.Associationrule:

Frozenmeal<=Cannedveg&Beer(167:16.7%,0.87)Support:Numberorpercentageoftransactionswhichcontainboth CannedvegandBeerinthedatabase.Confidence:

NumberoftransactionscontainingFrozenmeal&Cannedveg&Beer

numberoftransactionscontainingCannedveg&Beer83什么是關(guān)聯(lián)挖掘?關(guān)聯(lián)規(guī)則挖掘：在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)結(jié)構(gòu)。應(yīng)用：購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計、聚集和分類等。舉例：

規(guī)則形式：“Body—>Head[support,confidence]”.buys(x,“diapers”)—>buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)—>grade(x,“A”)[1%,75%]84關(guān)聯(lián)規(guī)則問題的形式化描述項目定義1：集合I={i1，i2，…,im}為標(biāo)識符的集合，其中m為正整數(shù)，ik（k=1，2，…,m)稱為項目。項目是一個從具體問題中抽象出的一個概念。在超市的關(guān)聯(lián)規(guī)則挖掘問題中，項目表示各種商品，如旅游鞋等。由于在超市的關(guān)聯(lián)規(guī)則挖掘中并不關(guān)心顧客購買的商品數(shù)量和價格等，因此顧客的一次購物可以用該顧客所購買的所有商品的名稱來表示，稱為事務(wù)，所有事務(wù)的集合構(gòu)成關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)集，稱為事務(wù)數(shù)據(jù)庫。85事務(wù)定義2：關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)庫記為D，事務(wù)數(shù)據(jù)庫D中的每個元組稱為事務(wù)。一條事務(wù)T是I中項目的集合。一條事務(wù)僅包含其涉及到的項目，而不包含項目的具體信息。在超級市場的關(guān)聯(lián)規(guī)則挖掘問題中事務(wù)是顧客一次購物所購買的商品，但事務(wù)中并不包含這些商品的具體信息，如商品的數(shù)量、價格等。86項目集定義3：項目集是由I中項目構(gòu)成的集合。若項目集包含的項目數(shù)為k，則稱此項目集為k-項目集。定義4：任意的項目集X和事務(wù)T若滿足：TX，則稱事務(wù)T包含項目集X。在超市的關(guān)聯(lián)規(guī)則挖掘問題中項目集可以看成一個或多個商品的集合。若某顧客一次購買所對應(yīng)的事務(wù)T包含項目集X，就說該顧客在這次購物中購買了項目集X中的所有商品。87頻繁項目集定義5：對任意的項目集X，若事務(wù)數(shù)據(jù)庫D中?%的事務(wù)包含項目集X，則項目集的支持率為?，記為support（X）=?，其中包含項目集X的事務(wù)數(shù)稱為項目集X的頻度，記為count（X）。若項目集X的支持率大于或等于用戶指定的最小支持率（minsupport），則項目集X稱為頻繁項目集（或大項目集），否則項目集X為非頻繁項目集（或小項目集）。如果數(shù)據(jù)庫D中的事務(wù)數(shù)記為|D|，頻繁項目集是至少被?%x|D|條事務(wù)包含的項目集.88支持度和置信度定義6:關(guān)聯(lián)規(guī)則是形如X->Y的規(guī)則，其中X，Y為項目集且XY=。定義7：在數(shù)據(jù)庫D中，若s%的事務(wù)包含XY，則關(guān)聯(lián)規(guī)則X->Y的支持度為s%；在數(shù)據(jù)庫D中，若c%的包含項目集X的事務(wù)也包含項目集Y，則關(guān)聯(lián)規(guī)則X->Y的置信度為c%:p（Y│X）＝p（XY）/p(X)。置信度反應(yīng)了關(guān)聯(lián)規(guī)則的可信度—購買了項目集X中的商品的顧客同時也購買了Y中商品的可能性有多大。89強關(guān)聯(lián)規(guī)則定義8：若關(guān)聯(lián)規(guī)則X->Y的支持度和置信度分別大于或等于用戶指定的最小支持率minsupport和最小置信度minconfidence，則稱關(guān)聯(lián)規(guī)則X->Y為強關(guān)聯(lián)規(guī)則，否則稱關(guān)聯(lián)規(guī)則X->Y為弱關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘的核心就是要找出事務(wù)數(shù)據(jù)庫D中的所有強相關(guān)規(guī)則。90關(guān)聯(lián)規(guī)則挖掘問題的分解給定數(shù)據(jù)庫D，關(guān)聯(lián)規(guī)則的挖掘就是找出所有存在于數(shù)據(jù)庫D中的強關(guān)聯(lián)規(guī)則。因此整個關(guān)聯(lián)規(guī)則挖掘過程可以分解為以下兩個子問題：找出所有的頻繁項目集；根據(jù)找到的頻繁項目集導(dǎo)出所有的強關(guān)聯(lián)規(guī)則。91強關(guān)聯(lián)規(guī)則的產(chǎn)生第一個子問題的求解，需要多次掃描數(shù)據(jù)庫D，這意味著關(guān)聯(lián)規(guī)則挖掘算法的效率將主要取決于數(shù)據(jù)庫掃描、I/O操作和頻繁項目集的計算上。因此如何迅速、高效地找出所有的頻繁項目集是關(guān)聯(lián)規(guī)則挖掘的中心問題第二個子問題的求解比較容易，R.Agrawal等人已提出了有效的解決辦法，具體過程如下：對每個頻繁項目集I，產(chǎn)生所有的非空真子集：對I的任意非空真真子集m，若support（I）/Support（m）minconfidence，則產(chǎn)生強關(guān)聯(lián)規(guī)則m->(l-m)。92規(guī)則度量：支持度與可信度查找所有的規(guī)則X&YZ具有最小支持度和可信度支持度,

s,交易中包含{X、Y、Z}的可能性可信度,

c,

包含{X、Y}的交易中也包含Z的條件概率設(shè)最小支持度為50%,最小可信度為50%,則可得到AC(50%,66.6%)CA(50%,100%)買尿布的客戶二者都買的客戶買啤酒的客戶93關(guān)聯(lián)規(guī)則挖掘：路線圖布爾vs.定量關(guān)聯(lián)

(基于處理數(shù)據(jù)的類型)buys(x,“SQLServer”)^buys(x,“DMBook”)?buys(x,“DBMiner”)[0.2%,60%]age(x,“30..39”)^income(x,“42..48K”)?buys(x,“PC”)[1%,75%]單維vs.多關(guān)聯(lián)(例子同上)單層vs.多層分析哪個品牌的啤酒與那個牌子的尿布有關(guān)系?各種擴展相關(guān)性、因果分析關(guān)聯(lián)并不一定意味著相關(guān)或因果添加約束如哪些“小東西”的銷售促發(fā)了“大家伙”的買賣？94關(guān)聯(lián)規(guī)則挖掘例子對于A

C：support=support({A、C})=50%confidence=support({A、C})/support({A})=66.6%Apriori的基本思想:頻繁項集的任何子集也一定是頻繁的最小支持度50%最小置信度50%95Apriori算法連接:用Lk-1自連接得到Ck修剪:一個k-項集，如果它的一個k-1項集（它的子集）不是頻繁的，那它本身也不可能是頻繁的。偽代碼:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for

(k=1;Lk!=;k++)dobegin

Ck+1=candidatesgeneratedfromLk;

foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedint

Lk+1=candidatesinCk+1withmin_support

endreturn

k

Lk;96如何生成候選集假定Lk-1

中的項按順序排列第一步:自連接Lk-1

insertinto

Ckselect

p.item1,p.item2,…,p.itemk-1,q.itemk-1from

Lk-1p,Lk-1qwhere

p.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1第二步:修剪forallitemsetscinCk

doforall

(k-1)-subsetssofcdoif(sisnotinLk-1)then

delete

c

from

Ck97生成候選集的例子L3={abc,abd,acd,ace,bcd}自連接:L3*L3abc

和abd得到abcdacd和

ace得到acde修剪:ade不在L3中，刪除acdeC4={abcd}98Apriori算法例子數(shù)據(jù)庫D掃描DC1L1L2C2掃描DC3L3掃描D{2,3}->{5}99Apriori夠快了嗎?—性能瓶頸Apriori算法的核心:用頻繁的(k–1)-項集生成候選的頻繁k-項集用數(shù)據(jù)庫掃描和模式匹配計算候選集的支持度Apriori的瓶頸:候選集生成巨大的候選集:多次掃描數(shù)據(jù)庫：

如果最長的模式是n的話，則需要

n+1次數(shù)據(jù)庫掃描100多層關(guān)聯(lián)規(guī)則項通常具有層次。底層的項通常支持度也低。某些特定層的規(guī)則可能更有意義。交易數(shù)據(jù)庫可以按照維或?qū)泳幋a?？梢赃M行共享的多維挖掘。食品面包牛奶脫脂奶光明統(tǒng)一酸奶白黃101挖掘多層關(guān)聯(lián)規(guī)則自上而下，深度優(yōu)先的方法：先找高層的“強”規(guī)則：牛奶?面包[20%,60%].再找他們底層的“弱”規(guī)則：酸奶?黃面包[6%,50%].多層關(guān)聯(lián)規(guī)則的變種層次交叉的關(guān)聯(lián)規(guī)則：酸奶?復(fù)旦面包房黃面包不同種分層方法間的關(guān)聯(lián)規(guī)則：酸奶?復(fù)旦面包房面包102多層關(guān)聯(lián)：冗余過濾由于“祖先”關(guān)系的原因，有些規(guī)則可能是多余的。例子牛奶白面包[support=8%,confidence=70%]酸奶白面包[support=2%,confidence=72%]第一個規(guī)則是第二個規(guī)則的祖先參考規(guī)則的祖先，如果它的支持度與“預(yù)期”的支持度近似的話，則這條規(guī)則是冗余的。103多層挖掘：深度優(yōu)先自頂向下，深度優(yōu)先的方法：先挖掘高層頻繁項：

牛奶(15%),面包(10%)再挖掘它們底層的相對較弱的頻繁項：酸奶(5%),白面包(4%)跨層時對支持度的不同處理方法，對應(yīng)了不同的算法:層之間支持度不變：如果t的祖先是非頻繁的，則不用考慮t支持度隨層遞減：則只考慮那些其祖先是頻繁的/不可忽略的項104多維關(guān)聯(lián)規(guī)則概念單維規(guī)則：buys(X,“milk”)buys(X,“bread”)多維規(guī)則：2個以上維/謂詞維間關(guān)聯(lián)規(guī)則(謂詞不重復(fù))age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)混合維關(guān)聯(lián)規(guī)則(謂詞重復(fù))age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)類別屬性有限個值,值之間無順序關(guān)系數(shù)量屬性數(shù)字的，值之間隱含了順序關(guān)系105序列模式發(fā)現(xiàn)

SequentialPatternsDiscovery106序列模式分析（趨勢分析）序列模式的發(fā)現(xiàn)是由R．Agrawal于1995年首先提出的。序列模式尋找的是事件之間在順序上的相關(guān)性。例如，“凡是買了噴墨打印機的顧客中，80%的人在三個月之后又買了墨盒”，就是一個序列關(guān)聯(lián)規(guī)則。序列模式挖掘在交易數(shù)據(jù)庫分析、Web訪問日志分析以及通信網(wǎng)絡(luò)分析等領(lǐng)域具有廣泛的應(yīng)用前景。107序列模式Identifiestime-dependentsequencesamongtransactionsetswhereeachtransactionincludesasetofitems.ExampleGivenasetoforderedcustomer"transactions“.Each"transaction"containsasetof"items“.Findsequences:ifacustomerbuysitemA thenthecustomerwillbuyitemXafterwards108實例（1）TransactionTimeCustomerItemsBoughtJune20,199410:13amJ.BrownJuice,CokeJune20,199411:02amF.ZappaBrandyJune20,199411:47amJ.BrownBeerJune20,19942:32pmB.MooreBeerJune21,19949:22amJ.BrownWine,Water,CiderJune21,19943:19pmJ.MitchellBeer,Gin,CiderJune21,19945:27pmB.AdamsBeer(Diapers?)June21,19946:17pmB.MooreWine,CiderJune22,199410:34amB.AdamsBrandyJune22,19945:03pmB.MooreBrandy109實例（2）DatabaseSortedbyCustomerandDateCustomerTransactionTimeItemsBoughtB.AdamsJune21,19945:27pmBeerB.AdamsJune22,199410:34amBrandyJ.BrownJune20,199410:13amJuice,CokeJ.BrownJune20,199411:47amBeerJ.BrownJune21,19949:22amWine,Water,CiderJ.MitchellJune21,19943:19pmBeer,Gin,CiderB.MooreJune20,19942:32pmBeerB.MooreJune21,19946:17pmWine,CiderB.MooreJune22,19945:03pmBrandyF.ZappaJune20,199411:02amBrandy110實例（3）CustomerSequenceDatabaseCustomerCustomerSequenceB.Adams(Beer)(Brandy)J.Brown(Juice,Coke)(Beer)(Wine,Water,Cider)J.Mitchell(Beer,Gin,Cider)B.Moore(Beer)(Wine,Cider)(Brandy)F.Zappa(Brandy)SequentialPatternsintheDatabaseSequentialPatternswithSupport>40%CustomersSupportingit(Beer)(Brandy)B.Adams,B.Moore(Beer)(Wine,Cider)J.Brown,B.MooreSequentialRulewithSupport>40%CustomersSupportingtheRuleBodyConfidenceValue(Beer)=>(Brandy)B.Adams,B.Moore50%(Beer)=>(Wine,Cider)J.Brown,B.Moore50%DerivedSequentialRules111序列模式序列模式的概念最早是由Agrawal和Srikant提出的。序列模式定義：給定一個由不同序列組成的集合，其中每個序列由不同的元素按順序有序排列，每個元素由不同項目組成，同時給定一個用戶指定的最小支持度閾值，序列模式挖掘就是找出所有的頻繁子序列，即該子序列在序列集中的出現(xiàn)頻率不低于用戶指定的最小支持度閾值。112序列模式應(yīng)用例子例子1：在兩年前購買了Ford牌轎車的顧客，很有可能在今年采取貼舊換新的購車行動。例子2：在購買了自行車和購物籃的所有客戶中，有70%的客戶會在兩個月后購買打氣筒。113序列模式應(yīng)用領(lǐng)域客戶購買行為模式預(yù)測Web訪問模式預(yù)測疾病診斷自然災(zāi)害預(yù)測DNA序列分析114序列模式符號化表示：項目集(Itemset)是各種項目組成的集合。序列(Sequence)是不同項目集(ItemSet)的有序排列，序列s可以表示為s=<s1s2…sl>，sj(1<=j<=l)為項目集(Itemset)，也稱為序列s的元素。序列的元素(Element)可表示為(x1，x2，…，xm)，xk(1<=k<=m)為不同的項目，如果一個序列只有一個項目，則括號可以省略。一個序列包含的所有項目的個數(shù)稱為序列的長度。長度為l的序列記為l-序列。115序列模式符號化表示：設(shè)=<a1a2…an>，=<b1b2…bm>，如果存在整數(shù)1<=j1<j2<…<jn

<=m，使得a1bj1，a2bj2，…，an

bjn，則稱序列為序列的子序列，又稱序列包含序列，記為。序列在序列數(shù)據(jù)庫S中的支持數(shù)為序列數(shù)據(jù)庫S中包含序列的序列個數(shù)，記為Support()。給定支持度閾值，如果序列在序列數(shù)據(jù)庫中的支持數(shù)不低于，則稱序列為序列模式。長度為l的序列模式記為l-模式。116序列模式例子：設(shè)序列數(shù)據(jù)庫如下表所示，并設(shè)用戶指定的最小支持度min-support=2。Sequence_idSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>序列<a(bc)df>是序列<a(abc)(ac)d(cf)>的子序列序列<(ab)c>是長度為3的序列模式117序列模式問題描述：給定序列數(shù)據(jù)庫和最小支持度閾值，序列模式挖掘就是要找出序列數(shù)據(jù)庫中所有的序列模式。系統(tǒng)規(guī)定：由于同一個元素中的項目之間排列沒有順序，為了表達的唯一性，將同一個元素內(nèi)部的不同項目按照字典順序排列。118序列模式挖掘的主要算法GSP(GeneralizedSequentialPatterns)算法：類似于Apriori算法。PrefixSpan(Prefix-projectSequentialPatternmining)算法：采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個更小的投影數(shù)據(jù)庫，然后在各個投影數(shù)據(jù)庫上進行序列模式挖掘。119GSP算法的主要問題缺少時間限制：用戶可能需要指定序列模式的相鄰元素之間的時間間隔。例如，一個序列模式可能會發(fā)現(xiàn)客戶在購買了物品A后的第三年購買物品B。需要的卻是給定時間間隔內(nèi)用戶的購買意向。事務(wù)的定義過于嚴格：一個事務(wù)中包含在客戶的一次購買行為中所購買的所有物品?？赡苄枰付ㄒ粋€滑動時間窗口，客戶在滑動時間窗口的時間段內(nèi)的所有的購買行為均作為一個事務(wù)。缺少分類層次：只能在項目的原始級別上進行挖掘。120GSP算法掃描序列數(shù)據(jù)庫，得到長度為1的序列模式L1，作為初始的種子集。根據(jù)長度為i的種子集Li通過連接操作和剪切操作生成長度為i+1的候選序列模式Ci+1；然后掃描序列數(shù)據(jù)庫，計算每個候選序列模式的支持數(shù)，產(chǎn)生長度為i+1的序列模式Li+1，并將Li+1作為新的種子集。重復(fù)第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止L1C2L2C3L3C4L4……121候選序列模式步驟連接階段：如果去掉序列模式s1的第一個項目與去掉序列模式s2的最后一個項目所得到的序列相同，則可以將s1與s2進行連接，即將s2的最后一個項目添加到s1中。剪切階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除。L1C2L2C3L3C4L4……122實例下表演示了如何從長度為3的序列模式產(chǎn)生長度為4的候選序列模式。SequentialpatternsWithlength3Candidate4-SequencesAfterJoinAfterPruning<(1,2)3><(1,2)(3,4)><(1,2)(3,4)><(1,2)4><(1,2)35><1(3,4)><(1,3)5><2(3,4)><235>123對于給定的候選序列模式集合C，掃描序列數(shù)據(jù)庫，對于其中的每一條序列d,找出集合C中被d所包含的所有候選序列模式，并增加其支持度計數(shù)。L1C2L2C3L3……候選序列模式的支持度124時間序列挖掘

TimeSeriesMining125時間序列時間序列的數(shù)據(jù)庫內(nèi)某個字段的值是隨著時間而不斷變化的。時間序列數(shù)據(jù)是包含時間屬性的序列數(shù)據(jù)的一種特殊形式，序列數(shù)據(jù)庫中既可以包含時間屬性，也可以不包含時間屬性。有關(guān)時序和序列數(shù)據(jù)挖掘的研究內(nèi)容包括趨勢分析，在時序分析中的相似度搜索以及與時間相關(guān)數(shù)據(jù)中序列模式和周期模式的挖掘等。126時間序列應(yīng)用領(lǐng)域FinanceHedgingwithassetmismatch.Forexample,hedginganexposuretoanilliquidassetRetailLookingatdaily/weeklysalesofproducts/productgroupsSeewhichgroupshadsimilarsalesoveragivenperiodSeeifanygroupleads/lagsanotherFraudIdentifyhigh-riskpatternsinusageElectricityClassificationofelectricityloadprofiles127相似時間序列FindsimilaritiesbetweentwosetsoftimedependentdataSequence2TimeValueSequence1TimeValuecomparecurvesandfindsimilarsub-sequences128時間序列參數(shù)Windowsizelengthofatomicsubsequenceformatching(nooutliers).Epsilontolerancerangeofdeviationoftwoatomicsubsequences.Gapnumberofconsecutivetimeunitsforwhichoutliersareignored.MatchingLengthminimallengthofsubsequencestobeconsidered.129相似時間序列分析（1）o.k.!atomicsubsequencesEpsiloncomparesubsequencesbindtogethersimilar,neighboredsubsequencesinviewofgaps(=subsequentoutliers)gapo.k.ifgap=3atomicpartatomicpart130相似時間序列分析（2）SequenceTimeValue

SlidingWindowScalingOffsettranslationLengthofSequence=ndatavaluesw131回歸分析

Regression132統(tǒng)計與數(shù)據(jù)挖掘（1）Statisticsisconcernedwiththepresentationandinterpretationofchanceoutcomes.Statisticalanalysismethodsanddataminingalgorithmsarecombinedtoformthemostpowerfulbusinessdataanalysistools.Forexample,wehaveobservedthatanumberofourcustomershaveleftus.Wewanttofindoutwhywithhelpofstatisticsanddatamining.133統(tǒng)計與數(shù)據(jù)挖掘（2）StatisticsisusefulindataminingToexploretheinputdata,Topreprocesstheinputdata,Tobuilddataminingmodels,Toassessdataminingmodels,Toanalyzedataminingresults.134統(tǒng)計與數(shù)據(jù)挖掘（3）TwosubareasofstatisticsDescriptiveStatisticsisconcernedwithsummarizinganddescribingagivensetofdatasoastoyieldmeaningfulinformation.AnalyticalStatisticsconsistsofmethodsconcernedwiththeanalysisofasubsetofdataleadingtopredictionsorinferencesabouttheentiresetofdata(StatisticalInference).135回歸分析在數(shù)據(jù)挖掘中，統(tǒng)計學(xué)可應(yīng)用于預(yù)測、聚類規(guī)則挖掘和時序數(shù)據(jù)的趨勢分析等。預(yù)測是數(shù)據(jù)分析的一種重要形式，通過建立連續(xù)值函數(shù)模型，可以預(yù)測數(shù)據(jù)的未來變化趨勢。連續(xù)值的預(yù)測可以使用統(tǒng)計學(xué)中的回歸（Regression）統(tǒng)計技術(shù)建模，如線性回歸、多元回歸、非線性回歸、廣義線性回歸（對數(shù)回歸、泊松回歸等）。許多問題可以用線性回歸方法解決，而更多的問題則可以對變量進行變換，使得非線性的問題轉(zhuǎn)換為線性的問題加以處理。136回歸分析應(yīng)用Findpatternsinadatabasethatallowpredictionofnumericfieldsgiventheotherindependentfields.Given:alargeamountofdatarecordswithindividualproperties(fieldvalues)onepropertytobepredictedfromtheothers.trainingdataforwhichthatpropertyisknown.Lookfor:functionaldependencyofthepredictedfieldfromtheotherrecordproperties.apredictionmodel.137回歸模型線性回歸模型:Notappropriatefordichotomousresponsevariable,i.e.Yiseither1or0.Logistic回歸模型:138線性回歸Findthelinewhose