數(shù)據(jù)挖掘簡單概括

1、第1章 引言 第2章 數(shù)據(jù)預(yù)處理 第3章 數(shù)據(jù)倉庫與OLAP技術(shù)概述 第4章 數(shù)據(jù)立方體計(jì)算與數(shù)據(jù)泛化 第5章 挖掘頻繁模式、關(guān)聯(lián)和相關(guān) 第6章 分類和預(yù)測 第7章 聚類分析 第8章 挖掘流、時間序列和序列數(shù)據(jù) 第9章 圖挖掘、社會網(wǎng)絡(luò)分析和多關(guān)系數(shù)據(jù)挖掘 第10章 挖掘?qū)ο蟆⒖臻g、多媒體、文本和Web數(shù)據(jù) 第11章 數(shù)據(jù)挖掘的應(yīng)用和發(fā)展趨勢,體系結(jié)構(gòu):典型數(shù)據(jù)挖掘系統(tǒng),數(shù)據(jù)庫或數(shù)據(jù)倉庫服務(wù)器,數(shù)據(jù)挖掘引擎,模式評估,圖形用戶界面,知識庫,數(shù)據(jù)清洗、集成和選擇,數(shù)據(jù)庫,數(shù)據(jù)倉庫,萬維網(wǎng),其他信息庫,在何種數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘(數(shù)據(jù)源),關(guān)系數(shù)據(jù)庫 數(shù)據(jù)倉庫 事務(wù)數(shù)據(jù)庫 高級數(shù)據(jù)庫系統(tǒng)和信息庫 空

2、間數(shù)據(jù)庫 時間數(shù)據(jù)庫和時間序列數(shù)據(jù)庫 流數(shù)據(jù) 多媒體數(shù)據(jù)庫 面向?qū)ο髷?shù)據(jù)庫和對象-關(guān)系數(shù)據(jù)庫 異種數(shù)據(jù)庫和遺產(chǎn)(legacy)數(shù)據(jù)庫 文本數(shù)據(jù)庫和萬維網(wǎng)(WWW),數(shù)據(jù)倉庫,數(shù)據(jù)倉庫是一個從多個數(shù)據(jù)源收集的信息存儲，存放在一個一致的模式下，并通常駐留在單個站點(diǎn)。數(shù)據(jù)倉庫通過數(shù)據(jù)清理、數(shù)據(jù)變換、數(shù)據(jù)集成、數(shù)據(jù)裝入和定期數(shù)據(jù)刷新構(gòu)造。,數(shù)據(jù)挖掘的應(yīng)用,數(shù)據(jù)分析和決策支持 市場分析和管理 目標(biāo)市場, 客戶關(guān)系管理 (CRM), 市場占有量分析, 交叉銷售, 市場分割 風(fēng)險(xiǎn)分析和管理 風(fēng)險(xiǎn)預(yù)測, 客戶保持, 保險(xiǎn)業(yè)的改良, 質(zhì)量控制, 競爭分析 欺騙檢測和異常模式的監(jiān)測 (孤立點(diǎn)) 其他的應(yīng)用 文本挖

3、掘 (新聞組,電子郵件, 文檔) 和WEB挖掘 流數(shù)據(jù)挖掘 DNA 和生物數(shù)據(jù)分析,數(shù)據(jù)挖掘應(yīng)用市場分析和管理(1),數(shù)據(jù)從那里來? 信用卡交易, 會員卡, 商家的優(yōu)惠卷, 消費(fèi)者投訴電話, 公眾生活方式研究 目標(biāo)市場 構(gòu)建一系列的“客戶群模型”，這些顧客具有相同特征: 興趣愛好, 收入水平, 消費(fèi)習(xí)慣,等等 確定顧客的購買模式 交叉市場分析 貨物銷售之間的相互聯(lián)系和相關(guān)性，以及基于這種聯(lián)系上的預(yù)測,數(shù)據(jù)挖掘應(yīng)用市場分析和管理(2),顧客分析 哪類顧客購買那種商品 (聚類分析或分類預(yù)測) 客戶需求分析 確定適合不同顧客的最佳商品 預(yù)測何種因素能夠吸引新顧客 提供概要信息 多維度的綜合報(bào)告 統(tǒng)計(jì)

4、概要信息 (數(shù)據(jù)的集中趨勢和變化),數(shù)據(jù)挖掘應(yīng)用公司分析和風(fēng)險(xiǎn)管理,財(cái)務(wù)計(jì)劃 現(xiàn)金流轉(zhuǎn)分析和預(yù)測 交叉區(qū)域分析和時間序列分析（財(cái)務(wù)資金比率，趨勢分析等等） 資源計(jì)劃 總結(jié)和比較資源和花費(fèi) 競爭 對競爭者和市場趨勢的監(jiān)控 將顧客按等級分組和基于等級的定價(jià)過程 將定價(jià)策略應(yīng)用于競爭更激烈的市場中,數(shù)據(jù)挖掘應(yīng)用欺詐行為檢測和異常模式的發(fā)現(xiàn),方法: 對欺騙行為進(jìn)行聚類和建模，并進(jìn)行孤立點(diǎn)分析 應(yīng)用: 衛(wèi)生保健、零售業(yè)、信用卡服務(wù)、電信等 汽車保險(xiǎn): 相撞事件的分析 洗錢: 發(fā)現(xiàn)可疑的貨幣交易行為 醫(yī)療保險(xiǎn) 職業(yè)病人, 醫(yī)生以及相關(guān)數(shù)據(jù)分析 不必要的或相關(guān)的測試 電信: 電話呼叫欺騙行為 電話呼叫模型:

5、 呼叫目的地，持續(xù)時間，日或周呼叫次數(shù). 分析該模型發(fā)現(xiàn)與期待標(biāo)準(zhǔn)的偏差 零售產(chǎn)業(yè) 分析師估計(jì)有38的零售額下降是由于雇員的不誠實(shí)行為造成的 反恐怖主義,其他應(yīng)用,體育競賽 美國NBA的29個球隊(duì)中，有25個球隊(duì)使用了IBM 分析機(jī)構(gòu)的數(shù)據(jù)挖掘工具，通過分析每個對手的數(shù)據(jù)（蓋帽、助攻、犯規(guī)等數(shù)據(jù)）來獲得比賽時的對抗優(yōu)勢。 天文學(xué) JPL實(shí)驗(yàn)室和Palomar天文臺就曾經(jīng)在數(shù)據(jù)挖掘工具的幫助下發(fā)現(xiàn)了22顆新的恒星 網(wǎng)上沖浪 通過將數(shù)據(jù)挖掘算法應(yīng)用于網(wǎng)絡(luò)訪問日志，從與市場相關(guān)的網(wǎng)頁中發(fā)現(xiàn)消費(fèi)者的偏愛和行為, 分析網(wǎng)絡(luò)行銷的有效性，改善網(wǎng)絡(luò)站點(diǎn)組織。這就是新興的WEB挖掘研究,數(shù)據(jù)挖掘技術(shù)分類,數(shù)據(jù)

6、挖掘,驗(yàn)證驅(qū)動挖掘,發(fā)現(xiàn)驅(qū)動挖掘,SQL,SQL生成器,查詢工具,OLAP,描述,預(yù)測,可視化,聚類,關(guān)聯(lián)規(guī)則,順序關(guān)聯(lián),匯總描述,分類,統(tǒng)計(jì)回歸,時間序列,決策樹,神經(jīng)網(wǎng)路,數(shù)據(jù)挖掘的主要方法,關(guān)聯(lián)分析 發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則，這些規(guī)則展示屬性值頻繁的在給定的數(shù)據(jù)中所一起出現(xiàn)的條件。 廣泛的用于購物籃或事務(wù)數(shù)據(jù)分析。 關(guān)聯(lián)規(guī)則是形如X Y，即”A1.Am B1.Bn”的規(guī)則；其中,Ai(i1,.,m),Bj(j1,.,n)是屬性-值對。關(guān)聯(lián)規(guī)則解釋為“滿足X中條件的數(shù)據(jù)庫元組多半也滿足Y中條件”。 例1.6給定AllElectronics關(guān)系數(shù)據(jù)庫，一個數(shù)據(jù)挖掘系統(tǒng)可能發(fā)現(xiàn)如下形式的規(guī)則 a

7、ge(X, “2029”) income(X, “2029K”) buys(X, “CD_player”) support = 2%, confidence = 60% 其中，X是變量，代表顧客。該規(guī)則是說，所研究的AllElectronics顧客2%（支持度）在20-29歲，年收入20-29K，并且在AllElectronics購買CD機(jī)。這個年齡和收入組的顧客購買CD機(jī)的可能性有60%（置信度或可信性）。 關(guān)聯(lián)規(guī)則挖掘在第6章詳細(xì)討論。,數(shù)據(jù)挖掘的主要方法,分類和預(yù)測 通過構(gòu)造模型 (或函數(shù))用來描述和區(qū)別類或概念，用來預(yù)測類型標(biāo)志未知的對象類。 比如：按氣候?qū)曳诸?，按汽油消耗定額將汽

8、車分類 導(dǎo)出模型的表示: 決策樹、IFTHEN規(guī)則、神經(jīng)網(wǎng)絡(luò) 預(yù)測（prediction）用來預(yù)測空缺的或不知道的數(shù)值數(shù)據(jù)值，而不是類標(biāo)號，在本書中，預(yù)測主要是指數(shù)值預(yù)測。 可以用來預(yù)報(bào)某些未知的或丟失的數(shù)字值 第6章將詳細(xì)討論分類和預(yù)測,數(shù)據(jù)挖掘的主要方法,聚類分析 與分類和預(yù)測不同，聚類分析數(shù)據(jù)對象，而不考慮已知的類標(biāo)號。一般地，訓(xùn)練數(shù)據(jù)中不提供類標(biāo)號，因?yàn)椴恢缽暮伍_始。聚類可以產(chǎn)生這種標(biāo)號。對象根據(jù)最大化類內(nèi)的相似性、最小化類間的相似性的原則進(jìn)行聚類或分組。即，對象的聚類這樣形成，使得在一個聚類中的對象具有很高的相似性，而與其它聚類中的對象很不相似。,關(guān)于一個城市內(nèi)顧客的2-D圖，顯示

9、了3個聚類，每個聚類的“中心”用“+”標(biāo)記,2.1 為什么要預(yù)處理數(shù)據(jù)?,現(xiàn)實(shí)世界中的數(shù)據(jù)是臟的 不完全: 缺少屬性值, 缺少某些有趣的屬性, 或僅包含聚集數(shù)據(jù) 例, occupation=“” 噪音: 包含錯誤或孤立點(diǎn) 例, Salary=“-10” 不一致: 編碼或名字存在差異 例, Age=“42” Birthday=“03/07/1997” 例, 以前的等級 “1,2,3”, 現(xiàn)在的等級 “A, B, C” 例, 重復(fù)記錄間的差異,數(shù)據(jù)為什么臟?,不完全數(shù)據(jù)源于 數(shù)據(jù)收集時未包含 數(shù)據(jù)收集和數(shù)據(jù)分析時的不同考慮. 人/硬件/軟件問題 噪音數(shù)據(jù)源于 收集 錄入 變換 不一致數(shù)據(jù)源于 不同

10、的數(shù)據(jù)源 違反函數(shù)依賴,為什么數(shù)據(jù)預(yù)處理是重要的?,沒有高質(zhì)量的數(shù)據(jù), 就沒有高質(zhì)量的數(shù)據(jù)挖掘結(jié)果! 高質(zhì)量的決策必然依賴高質(zhì)量的數(shù)據(jù) 例如, 重復(fù)或遺漏的數(shù)據(jù)可能導(dǎo)致不正確或誤導(dǎo)的統(tǒng)計(jì). 數(shù)據(jù)倉庫需要高質(zhì)量數(shù)據(jù)的一致集成 數(shù)據(jù)提取, 清理, 和變換是建立數(shù)據(jù)倉庫的最主要的工作,第3章: 數(shù)據(jù)倉庫與OLAP技術(shù),3.1什么是數(shù)據(jù)倉庫? 3.2多維數(shù)據(jù)模型 3.3數(shù)據(jù)倉庫結(jié)構(gòu) 3.4數(shù)據(jù)倉庫實(shí)現(xiàn) 3.5從數(shù)據(jù)倉庫到數(shù)據(jù)挖掘,多維數(shù)據(jù)模型,數(shù)據(jù)倉庫基于 多維數(shù)據(jù)模型 , 多維數(shù)據(jù)模型將數(shù)據(jù)視為數(shù)據(jù)方(data cube)形式 多維數(shù)據(jù)模型圍繞中心主題組織，該主題用事實(shí)表表示。事實(shí)是數(shù)值度量的。 數(shù)

11、據(jù)方, 可以將數(shù)據(jù)建模, 并允許由多個維進(jìn)行觀察,由維和事實(shí)定義 維是關(guān)于一個組織想要記錄的視角或觀點(diǎn)。每個維都有一個表與之相關(guān)聯(lián)，稱為維表。 事實(shí)表包括事實(shí)的名稱或度量以及每個相關(guān)維表的關(guān)鍵字,多維數(shù)據(jù)模型,不同視角的數(shù)據(jù)立方分析,數(shù)據(jù)倉庫、數(shù)據(jù)集市和數(shù)據(jù)立方之間的關(guān)系,數(shù)據(jù)倉庫由于是企業(yè)范圍的，能對多個相關(guān)的主題建模，所以在設(shè)計(jì)其數(shù)據(jù)構(gòu)成時一般采用星系模式。而數(shù)據(jù)集市是部門級的，具有選定的主題，可以采用星形或雪花模式。,數(shù)據(jù)倉庫的后端工具和實(shí)用程序,數(shù)據(jù)提取: 由多個異種, 外部數(shù)據(jù)源收集數(shù)據(jù) 數(shù)據(jù)清理: 檢測數(shù)據(jù)中的錯誤, 可能時訂正它們 數(shù)據(jù)變換: 將數(shù)據(jù)由遺產(chǎn)或宿主格式轉(zhuǎn)換成數(shù)據(jù)倉庫

12、格式 裝載: 排序, 綜合, 加固, 計(jì)算視圖, 檢查整體性, 并建立索引和劃分 刷新 傳播由數(shù)據(jù)源到數(shù)據(jù)倉庫的更新,參考：數(shù)據(jù)倉庫與OLAP實(shí)踐教程 工具：Microsoft Analysis Services,2、使用Crystal Analysis,上表下圖式（Horizontal Worksheet and Chart）,顯示的維度,隱藏的維度,顯示的度量值,圖形化顯示,（電子教案）,OLAP:Excel數(shù)據(jù)透視表和數(shù)據(jù)透視圖,1、創(chuàng)建Excel數(shù)據(jù)透視表 2、使用Excel透視表瀏覽數(shù)據(jù) 3、使用Excel透視圖分析數(shù)據(jù),第5章：挖掘頻繁模式、關(guān)聯(lián)和相關(guān),本章主要講解關(guān)聯(lián)規(guī)則挖掘 關(guān)

13、聯(lián)規(guī)則挖掘是當(dāng)前數(shù)據(jù)挖掘研究的主要方法之一，側(cè)重于確定數(shù)據(jù)中不同領(lǐng)域之間的聯(lián)系，找出滿足給定支持度和可信度閾值的多個域之間的依賴關(guān)系 。 例：在銷售手機(jī)的商店中，70%的包含手機(jī)的交易中包含充電器,在所有交易中，有56%同時包含這兩種物品。 于是規(guī)則表示為手機(jī) 充電器 （可信度70%，支持度56%）,購物籃分析,購物籃分析：通過發(fā)現(xiàn)顧客放入“購物籃”中的不同商品之間的關(guān)聯(lián)，分析顧客的購物習(xí)慣。這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商了解哪些商品頻繁地被顧客同時購買，從而幫助他們開發(fā)更好的營銷策略。,購物籃分析還可以應(yīng)用在下列問題上：（1）針對信用卡購物，能夠預(yù)測未來顧客可能購買什么。（2）對于電信與金融服

14、務(wù)業(yè)而言，經(jīng)由購物籃分析能夠設(shè)計(jì)不同的服務(wù)組合以擴(kuò)大利潤。（3）保險(xiǎn)業(yè)能藉由購物籃分析偵測出可能不尋常的投保組合并作預(yù)防。（4）對病人而言，在療程的組合上，購物籃分析能作為是否這些療程組合會導(dǎo)致并發(fā)癥的判斷依據(jù)。等等,為什么頻繁模式挖掘是數(shù)據(jù)挖掘的基本任務(wù)?,許多基本的數(shù)據(jù)挖掘任務(wù)的基礎(chǔ) 關(guān)聯(lián), 相關(guān), 因果關(guān)系 序列模式, 時間或周期關(guān)聯(lián), 局部周期性, 空間和多媒體關(guān)聯(lián) 關(guān)聯(lián)分類, 聚類分析, 冰山方, fascicles (語義數(shù)據(jù)壓縮) 廣泛的應(yīng)用 購物籃數(shù)據(jù)分析, 交叉銷售, 分類設(shè)計(jì), 銷售活動分析 Web 日志 (點(diǎn)擊流) 分析, DNA 序列分析, 等.,Apriori -關(guān)聯(lián)

15、規(guī)則的一個算法 CARMA,CARMA算法簡介,CARMA是一種比較新的關(guān)聯(lián)規(guī)則算法，它是1999年由Berkeley大學(xué)的Christian Hidber教授提出來的。,1,2,3,4,能夠處理在線連續(xù)交易流數(shù)據(jù),僅需一次，最多兩次對數(shù)據(jù)的掃描就可以構(gòu)造出結(jié)果集,允許在算法執(zhí)行過程中按需要重新設(shè)置支持度,占用內(nèi)存少,CARMA,supermarket,關(guān)聯(lián)規(guī)則：哪些商品會在一起被購買？在超市的促銷中就應(yīng)搭配在一起或擺放在相同的貨架。此時關(guān)注的是商品而不是顧客個人信息。,分類與預(yù)測,6.1分類與預(yù)測概述,分類分析 所謂分類，就是把給定的數(shù)據(jù)劃分到一定的類別中。分類分析就是通過分析訓(xùn)練集中的數(shù)據(jù)

16、，為每個類別建立分類分析模型；然后用這個分類分析模型對數(shù)據(jù)庫中的其他記錄進(jìn)行分類。 分類分析的輸入集是一組記錄集合和幾種類別的標(biāo)記。這個輸入集又稱示例數(shù)據(jù)庫或訓(xùn)練集。 訓(xùn)練集中的記錄稱為樣本。在這個訓(xùn)練集中，每個記錄都被賦予一個類別的標(biāo)記。,6.1分類與預(yù)測概述,分類分析 分類分析方法的一個典型例子是信用卡核準(zhǔn)過程。信用卡公司根據(jù)信譽(yù)程度，將一組持卡人記錄分為良好、一般和較差三類，且把類別標(biāo)記賦給每個記錄。分類分析就是分析該組記錄數(shù)據(jù)，對每個信譽(yù)等級建立分類分析模型。如“信譽(yù)良好的客戶是那些收入在5萬元以上，年齡在4050歲之間的人士”。得出這個分類分析模型之后，就可根據(jù)這個分類分析模型對新的

17、記錄進(jìn)行分類，從而判斷一個新的持卡人的信譽(yù)等級是什么。,6.1分類與預(yù)測概述,分類與預(yù)測 分類： 預(yù)測分類標(biāo)號（或離散值） 根據(jù)訓(xùn)練數(shù)據(jù)集和類標(biāo)號屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù) 預(yù)測： (prediction)是構(gòu)造和使用模型評估無標(biāo)號樣本類，或評估給定樣本可能具有的屬性值或值區(qū)間。 相同點(diǎn) 兩者都需要構(gòu)建模型 都用模型來估計(jì)未知值 預(yù)測當(dāng)中主要的估計(jì)方法是回歸分析 線性回歸和多元回歸 非線性回歸 不同點(diǎn) 分類法主要是用來預(yù)測類標(biāo)號（分類屬性值） 預(yù)測法主要是用來估計(jì)連續(xù)值（量化屬性值）,6.1分類與預(yù)測概述,分類步驟 第一步，學(xué)習(xí)過程，建立一個模型，描述預(yù)定數(shù)據(jù)類集和概念集

18、假定每個元組屬于一個預(yù)定義的類，由一個類標(biāo)號屬性確定 基本概念 訓(xùn)練數(shù)據(jù)集：由為建立模型而被分析的數(shù)據(jù)元組組成 訓(xùn)練樣本：訓(xùn)練數(shù)據(jù)集中的單個樣本（元組） 學(xué)習(xí)模型可以用分類規(guī)則、決策樹或數(shù)學(xué)公式的形式提供,6.1分類與預(yù)測概述,第一步建立模型,6.1分類與預(yù)測概述,分類步驟 第二步，分類過程，使用模型，對將來的或未知的對象進(jìn)行分類 首先評估模型的預(yù)測準(zhǔn)確率 對每個測試樣本，將已知的類標(biāo)號和該樣本的學(xué)習(xí)模型類預(yù)測比較 模型在給定測試集上的準(zhǔn)確率是正確被模型分類的測試樣本的百分比 測試集要獨(dú)立于訓(xùn)練樣本集，否則會出現(xiàn)“過分適應(yīng)數(shù)據(jù)”的情況,6.1分類與預(yù)測概述,第二步用模型進(jìn)行分類,6.1分類與預(yù)

19、測概述,有指導(dǎo)的學(xué)習(xí) VS.無指導(dǎo)的學(xué)習(xí) 有指導(dǎo)的學(xué)習(xí)（用于分類） 模型的學(xué)習(xí)在被告知每個訓(xùn)練樣本屬于哪個類的“指導(dǎo)”下進(jìn)行 數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類 無指導(dǎo)的學(xué)習(xí)（用于聚類） 每個訓(xùn)練樣本的類編號是未知的，要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的 通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號或進(jìn)行聚類,6.1分類與預(yù)測概述,分類的主要算法 （1）決策樹算法 （2）貝葉斯分類算法 （3）神經(jīng)網(wǎng)絡(luò)分類算法 （4）遺傳算法 （5）粗糙集分類算法 其他,6.2 決策樹分類算法,什么是決策樹（判定樹，Decision Tree）？ 決策樹是采用樹狀分岔的架構(gòu)來產(chǎn)生規(guī)則，適用于所有分類的問題。

20、 類似于流程圖的樹結(jié)構(gòu) 每個內(nèi)部節(jié)點(diǎn)表示在一個屬性上的測試 每個分枝代表一個測試輸出 每個樹葉節(jié)點(diǎn)代表類或類分布 用途：提取分類規(guī)則，進(jìn)行分類預(yù)測,6.2 決策樹分類算法,決策樹的概念 如果每個內(nèi)節(jié)點(diǎn)都恰好有兩個分枝，則稱為二叉樹。如果內(nèi)節(jié)點(diǎn)有多于兩個的分枝，則稱為多叉樹。從根節(jié)點(diǎn)到每個葉節(jié)點(diǎn)的路徑稱為“決策規(guī)則”。 決策樹可用于對新樣本的分類，即通過決策樹對新樣本屬性值進(jìn)行測試，從樹的根節(jié)點(diǎn)開始，按照樣本屬性的取值，逐漸沿著決策樹向下，直到樹的葉節(jié)點(diǎn)，該葉節(jié)點(diǎn)表示的類別就是新樣本的類別，也能有效地識別新樣本的類別。,6.2 決策樹分類算法,決策樹生成算法分成兩個步驟 樹的生成 開始，數(shù)據(jù)都在

21、根節(jié)點(diǎn) 遞歸的通過選定的屬性，來劃分樣本（必須是離散值） 樹的修剪 去掉一些可能是噪音或者異常的數(shù)據(jù) 決策樹使用: 對未知數(shù)據(jù)進(jìn)行分割 按照決策樹上采用的分割屬性逐層往下，直到一個葉子節(jié)點(diǎn),6.2 決策樹分類算法,決策樹算法 基本算法（貪婪算法） 自上而下分而治之的方法 開始時，所有的數(shù)據(jù)都在根節(jié)點(diǎn) 屬性都是種類字段 (如果是連續(xù)的，將其離散化) 所有記錄用所選屬性遞歸的進(jìn)行分割 屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計(jì)的度量 (如, information gain) 停止分割的條件 一個節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個類別 沒有屬性可以再用于對數(shù)據(jù)進(jìn)行分割,6.2 決策樹分類算法,常用的決策樹

22、演算法 ID3, C4, C4.5, C5, CART, CHAID, QUEST 決策樹分類算法ID3算法 決策樹方法中影響最大的是1986年提出的ID3方法。它是建立在推理系統(tǒng)和概念學(xué)習(xí)系統(tǒng)的基礎(chǔ)上的算法。 ID3算法的基本思想是貪心算法，采用自上而下的分而治之的方法構(gòu)造決策樹。 首先檢測訓(xùn)練數(shù)據(jù)集的所有特征，選擇信息增益最大的特征A建立決策樹根節(jié)點(diǎn)，由該特征的不同取值建立分枝，對各分枝的實(shí)例子集遞歸，用該方法建立樹的節(jié)點(diǎn)和分枝，直到某一子集中的數(shù)據(jù)都屬于同一類別，或者沒有特征可以在用于對數(shù)據(jù)進(jìn)行分割。,6.2 決策樹分類算法,決策樹的建立-決策樹建立的關(guān)鍵,建立一個好的決策樹的關(guān)鍵是決定

23、樹根和子樹根的屬性,樹根？,6.2 決策樹分類算法,決策樹的建立-決策樹建立的關(guān)鍵,年齡,青,中,老,6.2 決策樹分類算法,決策樹的建立-對測試樣例的信息期望,讓我們稱所需要研究的屬性為“分類屬性”。假設(shè)該屬性共分m類，而它們每一類在數(shù)據(jù)表中計(jì)數(shù)的總和分別為s1, s2 , sm。 令s = s1+ s2 + +sm 則對于任一樣例，決定它所屬類別的信息期望可以用下面的公式來計(jì)算： I(s1, s2 , sm) = -pilog2(pi) 其中pi = si /s,6.2決策樹分類算法,決策樹的建立-對測試樣例的信息期望,例：左表 分類屬性：買計(jì)算機(jī)？ 該屬性共分兩類(m=2): 買/不買

24、s1 = 641, s2 = 383 s = s1+ s2 = 1024 p1 = s1 /s = 641/1024 = 0.6260 p2 = s2 /s = 383/1024 = 0.3740 I(s1, s2) = I(641, 383) = -(p1*log2(p1) + p2*log2(p2) = 0.9537,-(p1*log2(p1) + p2*log2(p2)在Excel中寫為： -(0.626*LOG(0.626,2)+0.374*LOG(0.374,2),6.2 決策樹分類算法,決策樹的建立-對測試樣例的信息期望,平均信息期望，E，是節(jié)點(diǎn)各直系 分支的信息期望值的加權(quán)總和

25、1. 假定選擇年齡作樹根節(jié)點(diǎn)，則： 青年組: I(128,256)=0.9183 中年組: I(256,0)=0 老年組: I(257,127)=0.9157 青年組比例: (128+256)/1024=0.375 中年組比例: 256/1024=0.25 老年組比例: (257+127)/1024=0.375 平均信息期望（加權(quán)總和）： E(年齡）= 0.375*0.9183 +0.25*0+0.375*0.9157 = 0.6877 信息增益: Gain(年齡) = I(641, 383)-E(年齡) =0.9537 0.6877 = 0.2660,6.2 決策樹分類算法,決策樹的建立-對

26、測試樣例的信息期望,2. 假定選擇收入作樹根節(jié)點(diǎn)，則： 高收入組: I(160,128)=0.9911 中收入組: I(289,191)=0.9697 低收入組: I(192,64)=0.8133 高收入組比例: 288/1024=0.2813 中收入組比例: 480/1024=0.4687 低收入組比例: 256/1024=0.25 平均信息期望（加權(quán)總和）： E(收入）= 0.2813 * 0.9911 + 0.4687 * 0.9697 + 0.25 * 0.8133 = 0.9361 Gain(收入) = I(641, 383)-E(收入) =0.9537 0.9361= 0.0176

27、,6.2 決策樹分類算法,決策樹的建立-對測試樣例的信息期望,3. 假定選擇學(xué)生作樹根節(jié)點(diǎn)，則： 學(xué)生組: I(420,64)=0.5635 非學(xué)生組: I(221,319)=0.9761 學(xué)生組比例: 484/1024=0.4727 非學(xué)生組比例:540/1024=0.5273 平均信息期望（加權(quán)總和）： E(學(xué)生）= 0.4727 * 0.5635 + 0.5273 * 0.9761 = 0.7811 Gain(學(xué)生) = I(641, 383)-E(學(xué)生) =0.9537 0.7811= 0.1726,6.2 決策樹分類算法,決策樹的建立-對測試樣例的信息期望,4. 假定選擇信譽(yù)作樹根節(jié)

28、點(diǎn)，則： 良好組: I(480,192)=0.8631 優(yōu)秀組: I(161,191)=0.9948 良好組比例: 672/1024=0.6563 優(yōu)秀組比例: 352/1024=0.3437 平均信息期望（加權(quán)總和）： E(信譽(yù)）= 0.6563 * 0.8631 + 0.3437 * 0.9948 = 0.9048 Gain(信譽(yù)) = I(641, 383)-E(信譽(yù)) =0.9537 0.9048 = 0.0453,6.2 決策樹分類算法,決策樹的建立-對測試樣例的信息期望 決定樹根節(jié)點(diǎn) E(年齡）= 0.6877， Gain(年齡) = 0.2660（此值最大，作為根節(jié)點(diǎn)） E(收入

29、）= 0.9361，Gain(收入) = 0.0176 E(學(xué)生）= 0.7811，Gain(學(xué)生) = 0.1726 E(信譽(yù)）= 0.9048，Gain(信譽(yù)) = 0.0453,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例）,年齡,青,中,老,樹葉,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例）,年齡,青,中,老,買,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例） 青年組數(shù)據(jù)表分析： 1. 假定選擇收入作節(jié)點(diǎn) I(128,256) = 0.9183,I(0,128)=0 比例: 128/384=0.3333,I(64,128)=0.9183 比例: 1

30、92/384=0.5,I(64,0)=0 比例: 64/384=0.1667,平均信息期望（加權(quán)總和）： E(收入）= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592 Gain(收入) = I(128, 256) - E(收入)=0.9183 0.4592 = 0.4591,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例） 青年組數(shù)據(jù)表分析： 2. 假定選擇學(xué)生作節(jié)點(diǎn) I(128,256) = 0.9183,I(128,0)=0 比例: 128/384=0.3333,I(0,256)=0 比例: 256/384=0.6667,平均信息期

31、望（加權(quán)總和）： E(學(xué)生）= 0.3333 * 0 + 0.6667 * 0 = 0 Gain(學(xué)生) = I(128, 256) - E(學(xué)生)=0.9183 0 = 0.9183 結(jié)論: 不需要考慮屬性信譽(yù)，決定選擇屬性學(xué)生,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例）,年齡,青,中,老,買,學(xué)生,是,否,樹葉,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例）,年齡,青,中,老,買,學(xué)生,是,否,買,不買,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例） 老年組數(shù)據(jù)表分析： 1. 假定選擇收入作節(jié)點(diǎn) I(257,127) = 0.9157,I(64,64

32、)=1 比例: 128/384=0.3333,I(193,63)=0.8050 比例: 256/384=0.6667,平均信息期望（加權(quán)總和）： E(收入）= 0.3333 * 1 + 0.6667 * 0.8050 = 0.8700 Gain(收入) = I(257, 127) - E(收入)=0.9157 0.8700 = 0.0457,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例） 老年組數(shù)據(jù)表分析： 2. 假定選擇學(xué)生作節(jié)點(diǎn) I(257,127) = 0.9157,I(196,64)=0.8051 比例: 260/384=0.6771,I(61,63)=0.9998 比例:

33、 124/384=0.3229,平均信息期望（加權(quán)總和）： E(學(xué)生）= 0.6771 * 0.8051 + 0.3229 * 0.9998 = 0.8680 Gain(學(xué)生) = I(257, 127) - E(學(xué)生)=0.9157 0.8680= 0.0477,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例） 老年組數(shù)據(jù)表分析： 3. 假定選擇信譽(yù)作節(jié)點(diǎn) I(257,127) = 0.9157,I(256,0)=0 比例: 256/384=0.6667,I(1,127)=0.0659 比例: 128/384=0.3333,平均信息期望（加權(quán)總和）： E(信譽(yù)）= 0.6667 *

34、 0 + 0.3333 * 0.0659 = 0.0220 Gain(信譽(yù)) = I(257, 127) - E(信譽(yù))=0.9157 0.0220 = 0.8937 結(jié)論: 決定選擇屬性信譽(yù),6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例）,年齡,青,中,老,買,學(xué)生,是,否,買,不買,信譽(yù),良,優(yōu),樹葉,6.2 決策樹分類算法,決策樹的建立-決策樹建立步驟（例）,年齡,青,中,老,買,學(xué)生,是,否,買,不買,信譽(yù),良,優(yōu),買,依據(jù)收入、學(xué)生再進(jìn)一步分類,6.2 決策樹分類算法,由決策樹提取分類規(guī)則 可提取決策樹表示的知識，并以IF-THEN形式的分類規(guī)則表示 對從根到樹葉的每條路

35、徑創(chuàng)建一個規(guī)則 沿著給定路徑上的每個屬性-值對形成規(guī)則前件（IF部分）的一個合取項(xiàng) 葉節(jié)點(diǎn)包含類預(yù)測，形成規(guī)則后件（THEN部分） IF-THEN規(guī)則易于理解，尤其樹很大時 示例： IF age = “40” AND credit_rating = “excellent” THEN buys_computer = “yes” IF age = “40” AND credit_rating = “fair” THEN buys_computer= “no”,6.2 決策樹分類算法,決策樹分類作業(yè) 寫出下表決策樹分類步驟及圖，并以IF-THEN形式的分類規(guī)則表示 6個變量依次為：編號、天氣晴、陰、

36、雨、溫度熱、冷、適中、濕度高、正常、風(fēng)力強(qiáng)、弱以及最后是否去玩的決策是、否。,CHAID模塊簡介,CHAID：又叫卡方自動交叉檢驗(yàn)(CHi-squared Automatic Interaction Detector) 在1980年,由Kass等人提出，它在建立決策樹過程中主要是利用卡方統(tǒng)計(jì)量來尋找最優(yōu)的分支節(jié)點(diǎn)。 CHAID可產(chǎn)生多分枝的決策樹 CHAID是建立在因果關(guān)系的探討中的，依據(jù)目標(biāo)變量實(shí)現(xiàn)對輸入變量眾多水平的劃分 CHAID是市場研究和社會調(diào)查研究中應(yīng)用比較廣泛的方法 例如：市場細(xì)分研究；信件回復(fù)率研究；滿意度研究,CHAID模塊應(yīng)用及簡單示例,現(xiàn)有數(shù)據(jù)Newschan.sav 導(dǎo)

37、入數(shù)據(jù) 查看數(shù)據(jù)形式 本數(shù)據(jù)是一個市場研究 案例，目的通過已知的7個變量 age, sex, education, income category, hours spent watching television each day, number of Children，number of organization 來預(yù)測哪一類人更傾向通過網(wǎng) 絡(luò)購買一交互式新聞服務(wù),CHAID模塊應(yīng)用及簡單示例,模型執(zhí)行結(jié)果 首先用年齡變量進(jìn)行分類，分成4類 在對年齡大于23小于37的用性別進(jìn)行分支，分為兩支 若模型的錯判概率在我們可以接受的范圍之內(nèi)，則我們可以應(yīng)用決策樹模型進(jìn)行預(yù)測，如若已知一名潛在顧客的年

38、齡為20歲，則我們應(yīng)用此決策樹可以判斷他購買這項(xiàng)服務(wù)的概率僅為18.605%。另外，廠家還可以利用決策樹判斷哪些人更具有購買傾向，從而在進(jìn)行廣告宣傳時，更具有針對性。比如對于本例，年齡在2337之間的男性及年齡在60歲以上的人更具有購買傾向，因此廠家可以對這部分人群進(jìn)行更多的廣告宣傳，從而具有更大的命中性。,貝葉斯分類,樸素貝葉斯分類與貝葉斯網(wǎng),舉例說明,目標(biāo)概念PlayTennis的訓(xùn)練樣例,supermarket,分類：假設(shè)超市要進(jìn)行紅葡萄酒的促銷，當(dāng)一個顧客進(jìn)入超市時有針對性的對其進(jìn)行重點(diǎn)介紹，這就要事先知道是哪些人(哪類人？什么特征？)最有可能會購買紅葡萄酒，此時關(guān)注的是商品（紅葡萄酒

39、）與顧客個人信息（如性別、收入、年齡等）之間的關(guān)系。在進(jìn)行挖掘時就要對原始表進(jìn)行加工處理，只保留需要的信息，并對部分信息進(jìn)行轉(zhuǎn)換。要怎么處理？,（電子教案）,第七章聚類分析,一、什么是聚類分析,二、k-均值聚類,三、分層聚類或系統(tǒng)聚類,1.1聚類的理解,聚類問題不屬于預(yù)測性的問題，它主要解決的是把一群對象劃分成若干個組的問題。劃分的依據(jù)是聚類問題的核心。所謂“物以類聚，人以群分”，故得名聚類。 聚類問題容易與分類問題混淆，主要是語言表達(dá)的原因，因?yàn)槲覀兂Ｕf這樣的話：“根據(jù)客戶的消費(fèi)行為，我們把客戶分成三個類，第一個類的主要特征是”，實(shí)際上這是一個聚類問題，但是在表達(dá)上容易讓我們誤解為這是個分類

40、問題。 分類問題與聚類問題是有本質(zhì)區(qū)別的：分類問題是預(yù)測一個未知類別的用戶屬于哪個類別（相當(dāng)于做單選題），而聚類問題是根據(jù)選定的指標(biāo)，對一群用戶進(jìn)行劃分（相當(dāng)于做開放式的論述題），它不屬于預(yù)測問題。,1.1聚類的理解,什么是聚類 聚類（Clustering）就是將數(shù)據(jù)分組成為多個類（Cluster）。在同一個類內(nèi)對象之間具有較高的相似度，不同類之間的對象差別較大。 首先，基于數(shù)據(jù)的相似性把數(shù)據(jù)集合劃分成組，然后給這些組指定標(biāo)號。 聚類的方法可以適應(yīng)變化，能夠挑選出區(qū)分不同組的有用特征。 比如，要想把中國的縣分成若干類，就有很多種分類法： 可以按照自然條件來分，比如考慮降水、土地、日照、濕度等各

41、方面； 也可以考慮收入、教育水準(zhǔn)、醫(yī)療條件、基礎(chǔ)設(shè)施等指標(biāo)； 既可以用某一項(xiàng)來分類，也可以同時考慮多項(xiàng)指標(biāo)來分類。,1.2聚類的應(yīng)用,聚類分析無處不在 早在孩提時代，人就通過不斷改進(jìn)下意識中的聚類模式來學(xué)會如何區(qū)分貓和狗，動物和植物 經(jīng)濟(jì)領(lǐng)域： 幫助市場分析人員從客戶數(shù)據(jù)庫中發(fā)現(xiàn)不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。 誰喜歡打國際長途，在什么時間，打到那里？ 對住宅區(qū)進(jìn)行聚類，確定自動提款機(jī)ATM的安放位置 股票市場板塊分析，找出最具活力的板塊龍頭股 企業(yè)信用等級分類 生物學(xué)領(lǐng)域 推導(dǎo)植物和動物的分類； 對基因分類，獲得對種群的認(rèn)識,1.2聚類的應(yīng)用,誰經(jīng)常光顧商店，誰買什么東西，買多少？ 按忠誠卡記錄的光臨次數(shù)、光臨時間、性別、年齡、職業(yè)、購物種類、金額等變量分類 這樣商店可以. 識別顧客購買模式（如喜歡一大早來買酸奶和鮮肉