數據挖掘基本知識與算法介紹數據應用部

黃金寶2014-5-162023/2/515:291數據挖掘的基本概念數據挖掘流程數據挖掘的基本算法數據挖掘應用及演示案例目錄2023/2/515:292什么是數據挖掘？存在太多數據挖掘的定義，但基本上有這樣一種描述結構Tofind/discover/extract/dredge/harvest、、、Interesting/novel/useful/implicit/actable/meaningful、、、Information/knowledge/patterns/trends/rules/anomalies、、、Inmassivedata/largedataset/largedatabase/datawarehouse、、、DataInformationKnowledgeWisdomData+contextInformation+rulesKnowledge+experience2023/2/515:293要點一數據挖掘是指從數據庫的大量數據中揭示出隱含的、先前未知的并有潛在價值的信息的非平凡過程。要點二數據挖掘是一種決策支持過程，它主要基于人工智能、機器學習、模式識別、統計學、數據庫、可視化技術等，高度自動化地分析企業的數據，做出歸納性的推理，從中挖掘出潛在的模式，幫助決策者調整市場策略，減少風險，做出正確的決策。數據挖掘的理解2023/2/515:294統計學與數據挖掘的區別數據樣本數量不同（在統計學中樣本數量大于30，則成為大樣本）數據來源和質量不同數據挖掘既可以處理結構化數據，也可以處理非結構化和異型數據方法有些數據挖掘的分析方法是統計學中沒有的，如強調實時分析（協同過濾）統計分析方法在對大規模數據處理時不能像數據挖掘那樣采用神經網絡、遺傳算法等機器學習的方法模型（模式）模型（統計學）VS模式（數據挖掘）統計建模強調模型的普適性，數據挖掘強調從數據中發現模式算法統計學強調模型，運算量居于次要地位數據挖掘的精華在于結果的未知性，強調探索性分析，與之對應的是算法而不是模型方法論統計學：以數學為基礎，每種方法有嚴格的證明體系（主成分分析，回歸分析）數據挖掘：采用合理的算法，這些算法不全都有堅實的數學基礎作支撐。2023/2/515:295怎么做數據挖掘？定義問題數據理解數據預處理建立模型實際挖掘工作評價和解釋應用數據挖掘一般流程各步驟之間互相影響、反復調整，形成一種螺旋式上升的過程2023/2/515:296數據導入數據預處理模型挖掘評價應用2023/2/515:297數據挖掘過程中的數據預處理數據集成多個數據庫、數據方或文件的集成數據清洗填充缺失值,修均噪聲數據,識別或刪除孤立點,并解決數據不一致問題主要分析方法：分箱（Binning）、聚類、回歸數據變換規范化與匯總數據簡化（降維）減少數據量的同時,還可以得到相同或相近的分析結果主要分析方法：抽樣、主成分分析2023/2/515:298幾類基本的挖掘算法分類與預測發現能夠區分或預測目標變量（唯一的）的規則或者函數分類的目標變量一般是范疇型的，而預測則是數量型的，并不必然帶有任何時間延續型的暗示例如：股票市值的預測，病人病情的判斷聚類對數據分組以形成新類，類標記是未知的例如：市場細分關聯規則發現數據集中的頻繁模式例如：buy(x,”diapers”)buy(x,”beers”)[0.5%,60%]孤立點探測（OutlierDetection）分析異?；蛟肼晹祿男袨槟Ｊ嚼纾浩墼p檢測2023/2/515:299分類（有監督的學習過程，根據訓練數據集和類標號屬性，構建模型來分類現有數據，并用來分類新數據）第一步，建立一個模型，描述預定數據類集和概念集第二步，使用模型，對將來的或未知的對象進行分類訓練數據集分類算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分類規則測試集分類規則未知數據Tenured2023/2/515:2910常用的分類方法——決策樹歸納決策樹樣本的屬性作為結點分支代表屬性的值葉節點代表分類標簽或分布用信息論原理對大量樣本屬性進行分析和歸納（主要有信息增益和信息增益率，其中后者克服了前者偏向選擇取值多的屬性的缺點）決策樹的生成包括兩個階段樹的創建首先,從所有訓練樣本中選擇包含信息量最大的屬性作為根節點其次，中間結點是該根節點出發的的所有子集中包含信息量最大的屬性樹的修剪識別并刪除那些反映噪聲或孤立點的分支決策樹的停止條件決策樹的構建過程是一個遞歸的過程，所以需要確定停止條件，否則過程將不會結束。一種最直觀的方式是當每個子節點只有一種類型的記錄時停止，但是這樣往往會使得樹的節點過多，導致過擬合問題（Overfitting）。另一種可行的方法是當前節點中的記錄數低于一個閥值，那么就停止分割，將記錄中出現比例最大對應的分類作為當前葉節點的分類。應用決策樹:對未知樣本進行分類在決策樹上對新樣本從根結點開始，按照樣本屬性的取值，逐漸沿著決策樹向下，直到葉節點，該葉節點代表的類就是新樣本的類別2023/2/515:2911優點決策樹簡單易理解，容易生成便于解釋的規則既能處理數值型屬性，也能處理非數值型的屬性能在相對較短時間內對大量數據源作出可行且效果良好的結果（高效）缺點對那些樣本屬性包含的類別數量不一致的數據，在決策樹當中,信息增益的結果易偏向于那些具有更多類別的屬性決策樹對缺失值難處理過度擬合問題的出現2023/2/515:2912決策樹示意age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40示例：是否購買計算機？2023/2/515:2913常用的分類方法——貝葉斯分類貝葉斯分類利用統計學中的貝葉斯定理，來預測類成員的概率，即給定一個樣本，計算該樣本屬于一個特定的類的概率。（假設每個屬性之間都是相互獨立的，并且每個屬性對分類問題產生的影響都是一樣的）算法過程;1.待分類項X=(a1、a2、….an)，其中a為X的一個特征的屬性2.類別集合Y=(c1、c2、…cn),現在計算P(c1/X)、P(c2/X)..

P(cn/X)3根據貝葉斯定理P(ci/X)=

P(X/ci)*

P(ci)/

P(X)=

P(aj/ci)*P(ci)/P(X)4.計算P(ck/X)=max(P(ci/X))=max(P(aj/ci)*P(ci)/P(X))5.對所有的類別P(X)是常數，故P(aj/ci)*P(ci）最大項對應的類別就是X所屬類別2023/2/515:2914優點算法簡單，易理解有堅實的數學理論支撐，同時有穩定的分類效率缺點模型假設的各屬性之間相互獨立，這個在實際應用中很難實現2023/2/515:2915常用的分類方法——神經網絡神經網絡是一組連接的輸入/輸出單元，每個連接都與一個權相連。在學習階段，通過調整神經網絡的權，使得能夠預測輸入樣本的正確標號來學習。1.MP模型每個神經元的狀態只取0或1，分別代表抑制與興奮，每個神經元的狀態由MP方程決定：2023/2/515:2916（其中Wi是權值，T是閥值，f(x)是作用函數）1.[0,1]階梯函數2.(0,1)S型函數（常用的作用函數）2023/2/515:2917特性1：多輸入單輸出圖(a)表明，正如生物神經元有許多激勵輸入一祥，人工神經元也應該有許多的輸入信號，圖中每個輸入的大小用確定數值xi表示，它們同時輸入神經元j，神經元的單輸出用oj表示特性2：輸入類型：興奮性和抑制性生物神經元具有不同的突觸性質和突觸強度，其對輸入的影響是使有些輸入在神經元產生脈沖輸出過程中所起的作用比另外一些輸入更為重要。圖(b)中對神經元的每一個輸入都有一個加權系數wij，稱為權重值，其正負模擬了生物神經元中突觸的興奮和抑制，其大小則代表了突觸的不同連接強度。特性3：空間整合特性和閾值特性作為ANN的基本處理單元，必須對全部輸入信號進行整合，以確定各類輸入的作用總效果，圖(c)表示組合輸人信號的“總和值”，相應于生物神經元的膜電位。神經元激活與否取決于某一閾值電平，即只有當其輸入總和超過閾值時,神經元才被激活而發放脈沖,否則神經元不會產生輸出信號。2023/2/515:29182.感知機神經元i的輸入（神經元J輸出）為Xj為神經元j的輸入，wij是連接權值，神經元i的輸出為設神經元i的期望輸出為D,通過樣本學習，修正權值，使得計算輸出和期望輸出之差盡可能小感知機原理：3.BP神經網絡（1）多層網絡結構（不僅有輸入、輸出結點還有一層或多層隱結點，每一層連接都對應一個連接權值和結點閥值）（2）作用函數為(0，1)S型函數（3）誤差公式為

作用函數為[0,1]型階梯函數優點預測精度總的來說較高健壯性好，訓練樣本中包含錯誤時也可正常工作輸出可能是離散值、連續值對目標進行分類較快缺點訓練（學習）時間長蘊涵在學習的權中的符號含義很難理解很難跟專業領域知識整合2023/2/515:2919其他的分類方法

Logistic回歸支持向量機（SVM）k-最臨近分類(K-NN)遺傳算法粗糙集方法2023/2/515:2920提高分類法的準確性Bagging技術和boosting技術都通過將T個學習得到的分類法C1,C2…CT組合起來，從而創造一個改進的分類法C*Bagging技術對訓練集S進行T次迭代，每次通過放回取樣選取樣本集St，通過學習St得到分類法Ct對于未知樣本X，每個分類法返回其類預測，作為一票C*統計得票，并將得票最高的預測賦予XBoosting技術每個分類Ct賦予一個權值Ct的權值取決于分類準確率2023/2/515:29212023/2/515:2922Bagging技術演示boost技術演示

預測

注：預測是構造和使用模型評估給定樣本可能具有的屬性或值空間.

常用的預測方法回歸分析神經網絡2023/2/515:2923回歸分析線性回歸：Y=+X其中和是回歸系數，可以根據給定的數據點，通過最小二乘法來求得多元回歸：Y=+1X1+2X2線性回歸的擴展，設計多個預測變量，可以用最小二乘法求得上式中的，1和2非線性回歸：Y=+1X1+2X22+3X33對不呈線性依賴的數據建模使用多項式回歸建模方法，然后進行變量變換，將非線性模型轉換為線性模型，然后用最小二乘法求解2023/2/515:2924分類VS

預測相同點兩者都需要構建模型來估計未知值不同點分類法主要是用來預測類標號（分類屬性值）預測法主要是用來估計連續值（量化屬性值2023/2/515:2925聚類

(無監督學習過程，把一個給定的數據對象集合分成不同的簇)聚類的原則：類內相似度高，類間相似度低相似度一般為某種距離函數D(i,j)聚類既可以作為獨立分析工具考察數據分布結構，也可以作為其他分析方法的預處理步驟很不幸，對聚類結果的評價一般都是主觀的客戶分群示例分群是根據客戶的關鍵屬性將客戶分成不同的組別，要求做到組間差異化最大組內相似性最大2023/2/515:2926聚類分析方法劃分方法（PartitioningMethods）層次方法基于密度的方法基于網格的方法基于模型（Model-Based）的聚類方法2023/2/515:29271.劃分法(partitioningmethods)：給定一個有N個元組或者紀錄的數據集，將構造K個分組，每一個分組就代表一個聚類，K<N。而且這K個分組滿足下列條件：（1）每一個分組至少包含一個數據紀錄；（2）每一個數據紀錄屬于且僅屬于一個分組；對于給定的K，算法首先給出一個初始的分組方法，以后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次好，而所謂好的標準就是：同一分組中的記錄越近越好，而不同分組中的紀錄越遠越好。使用這個基本思想的算法有：K-MEANS算法、K-MEDOIDS算法；2023/2/515:2928K-means算法是劃分法的一種，用來對一組輸入字段的值基于相似度分類。其基本思路是試圖發現k個聚類，各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。（K值的選擇具有主觀性）聚類示意圖2023/2/515:29291.從N個點中選擇K個點作為初始質心

2.計算剩余點到K個點的距離，將每個點指派到最近的質心，形成K個類

3.重新計算每個類的質心

4.重復2、3的操作

直到各類的質心變化低于閥值或達到最大迭代次數距離計算方法：歐式距和余弦相似度算法過程

兩種劃分區別：K-MEANS和K-MEDOIDS區別主要是前者以各點的平均值作為中心，而后者以類別中的一個點為中心，該點滿足到類中各點的距離之和最小優點算法簡單，運算速度快缺點初始K值難易確定，需要多次迭代或者主觀判斷確定。只有在中心平均值確定情況下才能使用，所以數據對象必須是數值型的字段對極端值或奇異值敏感2023/2/515:29302.層次法(hierarchicalmethods)：這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。例如在“自底向上”方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。代表算法有：TwoStep

算法、CURE算法、CHAMELEON算法等；TwoStep

算法(能夠為訓練數據自動估計最佳聚類數)第一步完成簡單數據處理，以便將原始輸入數據壓縮為可管理的子聚類集合。第二步使用層級聚類方法將子聚類一步一步合并為更大的聚類。2023/2/515:29313.基于密度的方法(density-basedmethods)：基于密度的方法與其它方法的一個根本區別是：它不是基于各種各樣的距離的，而是基于密度的。這樣就能克服基于距離的算法只能發現“類圓形”的聚類的缺點。這個方法的指導思想就是，只要一個區域中的點的密度大過某個閥值，就把它加到與之相近的聚類中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；4.基于網格的方法(grid-basedmethods)：這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構，所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標數據庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；5.基于模型的方法(model-basedmethods)：基于模型的方法給每一個聚類假定一個模型，然后去尋找一個很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分布所決定的。通常有兩種嘗試方向：統計的方案和神經網絡的方案2023/2/515:2932關聯規則基本定義給定事務數據集，試圖發現其中的頻繁模式或關聯關系所謂頻繁模式或者關聯規則就是一個具有“AB”形式的邏輯式頻繁模式并不必然蘊涵著因果關系或相關關系！算法實現基本上基于APRIORI法則：頻繁項集的所有非空子集一定也是頻繁（Frequent）的類型布爾關聯規則vs定量關聯規則buy(x,”diapers”)buy(x,”beers”)Age(x,”30..39”)^income(x,”42k..48k”)buy(x,”PC”)單維關聯規則vs多維關聯規則單層關聯規則vs多層關聯規則Age(x,”30..39”)^income(x,”42k..48k”)buy(x,”IBMPC”)序列模式（SequencePattern）數據項是一個包含時間標簽的序偶[item(i),t]2023/2/515:2933支持度：Support(A=>B)=#AB/#N，表示A和B同時出現的概率。期望可信度：Support(B)=#A/#N，表示B出現的概率。置信度：Confidence(A=>B)=Support(A=>B)/Support(A)改善度：Lift(A=>B)=Confidence(A=>B)/Support(B)名稱描述公式支持度X、Y同時出現的頻率P(X∩Y)期望可信度Y出現的頻率P(Y)置信度X出現的前提下，Y出現的頻率P(Y|X)改善度置信度對期望可信度的比值P(Y|X)/P(Y)關聯規則的度量2023/2/515:2934發現具有最小置信度和支持度的全部規則X^YZ支持度(support),s,事務中包含{X&Y&Z}的概率置信度(confidence),c,

事務中包含{X&Y}的條件下,包含Z的條件概率令最小支持度為50%,最小置信度為50%,則有AC(50%,66.6%)CA(50%,100%)顧客購買尿布顧客購買兩者顧客購買啤酒2023/2/515:2935關聯規則的應用市場購物籃分析（MarketBasketAnalysis）例如一個事務是客戶的一個購物清單，同一客戶的兩份清單被認為是兩個不同的事務數據項是所有可能陳列貨物的全集目標是發現同時出現的貨品組合間的關聯模式應用：商品貨價設計、倉儲規劃、網頁布局、產品目錄設計等等交叉銷售（CrossSelling）客戶依次購買不同產品的序列目標是發現在購買某一產品組合之后客戶可能購買的另一產品或服務應用：網絡故障分析、網站門戶設計等2023/2/515:2936關聯規則的算法Apriori算法通過迭代，檢索出事務數據庫中的所有頻繁項集，即支持度不低于用戶設定的閾值的項集；利用頻繁項集構造出滿足用戶最小置信度的規則。FP-growth算法JiaweiHan等人在2000年提出了一種基于FP-樹的關聯規則挖掘算法FP_growth，它采取“分而治之”的策略，將提供頻繁項目集的數據庫壓縮成一棵頻繁模式樹（FP-樹）。僅兩次掃描數據庫，理論和實驗表明該算法優于Apriori算法2023/2/515:2937數據挖掘的工具有哪些？2023/2/515:2938數據挖掘應用Debt<10%ofIncomeDebt=0%GoodCreditRisksBadCreditRisksGoodCreditRisksYesYesYesNONONOIncome>$40KQQQQII123456factor1factor2factorn神經網絡NeuralNetworks聚類分析Clustering決策樹DecisionTrees

傾向性分析

客戶細分市場細分

傾向性分析客戶保留目標市場欺詐檢測關聯分析Association

市場組合分析套裝產品分析目錄設計交叉銷售2023/2/515:2939數據挖掘在通信行業的應用實例1結論：ARPU<=120元,租期已滿23個月以上，平均撥打電話少于270秒，六個月內賬單遲繳4次以上，撥打號碼平均少于10個的客戶退租可能性很大ARPU租期已滿23個月以上六個月內賬單遲繳4次以上撥打號碼平均少于10個《120〉120是非平均撥打電話少于270秒是非70.0%不退租（1000）是77.0%退租（1200）是非非Etc.Etc.Etc.Etc.2023/2/515:2940數據挖掘在通信行業的應用實例2我們定義LIFT值大于1的規則為強關聯規則。發現這樣的關聯規則是有價值，有意義的。關聯規則是基于統計方法發現的數據當中的內在規律，而這種規律在現實中是否有意義還需要市場業務人員作進一步的驗證。業務一業務二LSUPPORTRSUPPORTSUPPORTCONFIDENCELIFTZSCORE彩鈴業務手機郵箱0.07340.040320.03220.4386910.88021266.19541夢網短信手機郵箱0.670380.040320.040320.060141.4915740.52694國內自動漫游手機郵箱0.382530.040320.020370.053251.3206819.84956本地普通通話(比例)手機郵箱0.690050.040320.030590.044331.099458.320422023/2/515:2941移動數據挖掘應用

客戶流失(分類模型、Logistic回歸算法等)彩鈴WAP購買傾向預測(分類模型、Logistic回歸算法等)彩信增量銷售預測(分類模型、Logistic回歸算法等)彩鈴用戶流失預測(分類模型、Logistic回歸算法等)客戶價值增長預測(分類模型、Logistic回歸算法等)競爭對手流失預測(分類模型、Logistic回歸算法等)集團客戶分群(聚類模型、K-Means算法)集團客戶級別打分(分類模型、Logistic回歸算法)產品關聯分析(關聯規則)個人客戶分群分析(聚類模型、K-Means算法)

集團客戶流失預警模型(Logistic回歸算法，神經網絡)2023/2/515:29422023/2/515:2943西塔數據挖掘應用實例1——客戶細分模型字段1.用戶基礎信息品牌地市網齡年齡ARPU流量金卡、銀卡、鉆卡客戶VIP客戶手機終端品牌手機終端型號終端操作系統TD終端客戶終端合約客戶終端合約客戶類型2.套餐訂購信息動感地帶客戶神州行客戶全球通客戶短信包客戶彩信包客戶5元彩信包訂購標識用戶3元彩信包訂購標識用戶彩信連連發半年優惠套餐訂購標識用戶TD流量包客戶GPRS套餐客戶GPRS5元套餐客戶GPRS10元套餐客戶GPRS20元套餐客戶GPRS30元套餐客戶GPRS50元套餐客戶GPRS100元套餐客戶動感10元半年包訂購標識用戶動感10元年包訂購標識用戶動感10元半年包即將到期用戶動感10元年包即將到期用戶2023/2/515:29443.無線音樂業務偏好無線音樂特級會員客戶咪咕會員訂購客戶振鈴開通客戶振鈴下載客戶振鈴活躍客戶振鈴沉默客戶振鈴連續三月訂購客戶振鈴連續三月使用客戶振鈴連續三月沉默客戶彩鈴開通客戶彩鈴下載客戶彩鈴活躍客戶彩鈴沉默客戶彩鈴連續三月訂購客戶彩鈴連續三月使用客戶彩鈴連續三月沉默客戶歌曲下載客戶歌曲下載沉默客戶歌曲下載活躍客戶歌曲下載訂購客戶歌曲下載5元半年包訂購標識用戶歌曲下載10元半年包訂購標識用戶歌曲下載5元半年包即將到期用戶歌曲下載10元半年包即將到期用戶歌曲下載連續三月使用客戶歌曲下載連續三月沉默客戶歌曲下載連續三月訂購客戶未使用自有無線音樂用戶使用競品音樂1使用競品音樂22023/2/515:2945將無線音樂業務偏好變量作為細分變量，在SPSS中使用kmeans模型將客戶群進行細分細分結果描述通過用戶基礎信息及用戶套餐訂購信息這些描述變量定位人群，進一步分析人群特征。2023/2/515:2946細分結果應用2023/2/515:2947西塔數據挖掘應用實例2——客戶上網行為分類模型字段2023/2/515:2948在SPSS中使用決策樹（C5.0）模型，實現用戶上網業務類型分類具體操作步驟如下：1.使用特征選取節點（featureselection）選取重要度較高的字段作為分類變量2.使用C5.0模型，完成分類3.歸納出用戶使用各種業務的規則。如（女性&動感地帶用戶&年齡‘30-40’傾向于支付類型的業務）模型應用：1.預測其他未知客戶的上網行為