【正文】 為何需要數(shù)據(jù)挖掘？ 1. 數(shù)據(jù)量大 2. 缺乏理論知識 3. 數(shù)據(jù)挖掘可以幫助產(chǎn)生新的假說或者使數(shù)據(jù)變得有意義 為何需要數(shù)據(jù)挖掘？ ? We are drowning in data, but starving in knowledge ? Data explosion: Automated data collection tools and mature database technology lead to tremendous amounts of data accumulated and/or to be analyzed in databases, data warehouses, and other information repositories. 苦惱 : 淹沒在數(shù)據(jù)中 。 不能制定合適的決策 ! 數(shù)據(jù) 知識 決策 ? 模式 ? 趨勢 ? 事實 ? 關(guān)系 ? 模型 ? 關(guān)聯(lián)規(guī)則 ? 序列 ? 目標(biāo)市場 ? 資金分配 ? 貿(mào)易選擇 ? 在哪兒做廣告 ? 銷售的地理位置 ? 金融 ? 經(jīng)濟 ? 政府 ? 人口統(tǒng)計 ? 生命周期 數(shù)據(jù)挖掘的意義 數(shù)據(jù)挖掘 輔助社會管理 促進(jìn)民生改善 支持商業(yè)決策 推動科技進(jìn)步 股票趨勢分析 智能交通 數(shù)據(jù)挖掘應(yīng)用 ? 銀行 ? 美國銀行家協(xié)會 (ABA)預(yù)測數(shù)據(jù)倉庫和數(shù)據(jù)挖掘技術(shù)在美國商業(yè)銀行的應(yīng)用增長率是 ％。 ?噪音：包含噪聲、錯誤或者異常值 ?例如： salary=10 ?不一致性 : ?例如： age=42， birthday=03072023 ?假值： ?例如：使用某一值填補缺失屬性 缺失值（ Inplete/Missing Data) ?數(shù)據(jù)并不總是完整的 ?例如：數(shù)據(jù)庫表中，很多條記錄的對應(yīng)字段沒有相應(yīng)值，比如銷售表中的顧客收入 ?引起空缺值的原因 ?設(shè)備異常 ?與其他已有數(shù)據(jù)不一致而被刪除 ?因為誤解而沒有被輸入的數(shù)據(jù) ?在輸入時，有些數(shù)據(jù)因為得不到重視而沒有被輸入 ?對數(shù)據(jù)的改變沒有進(jìn)行日志記載 ?空缺值要經(jīng)過推斷而補上 如何補充缺失值 ?忽略元組：當(dāng)類標(biāo)號缺少時通常這么做（假定挖掘任務(wù)設(shè)計分類或描述），當(dāng)每個屬性缺少值的百分比變化很大時，它的效果非常差。這些孤立點可能包含有用的信息。 ?線性回歸 ?多線性回歸 ?非線性回歸 XY ?? ??2211 XXY ??? ???33221 XXXY ???? ????x y y = x + 1 X1 Y1 Y1’ 數(shù)據(jù)集成 ?實體識別 ?元數(shù)據(jù)可幫助避免錯誤 ?知識圖譜 ?屬性冗余 ?相關(guān)分析 ?數(shù)據(jù)重復(fù)（元組冗余） ?數(shù)據(jù)值沖突的檢測與處理 ?表示、比例或編碼不同 數(shù)據(jù)變換（規(guī)范化） ?平滑：去掉數(shù)據(jù)中的噪聲。 ?聚集：對數(shù)據(jù)進(jìn)行匯總或聚集。 ?規(guī)范化：將屬性數(shù)據(jù)按比例縮放，使之落入一個小的特定區(qū)間。 數(shù)據(jù)變換 ?平滑 ， 聚集 ?數(shù)據(jù)概化 ， 規(guī)范化 ?屬性構(gòu)造 (特征構(gòu)造 ) 有限區(qū)間的歸一化： 無限區(qū)間的歸一化： 模糊隸屬度： m i nm a xm i nvv???39。數(shù)據(jù)規(guī)約 ?海量數(shù)據(jù) ? 代表性數(shù)據(jù) ?對海量數(shù)據(jù)進(jìn)行復(fù)雜的數(shù)據(jù)分析和挖掘?qū)⑿枰荛L時間，使得這種 分析不現(xiàn)實或不可行 。 ?對歸約后的數(shù)據(jù)集 挖掘?qū)⒏行?，并產(chǎn)生相同（或幾乎相同）的結(jié)果。 （ 3）維度歸約：刪除不重要的屬性 （ 4）數(shù)值歸約： 用規(guī)模較小的數(shù)據(jù)表示、替換或估計原始數(shù)據(jù) （ 5）離散化和概念分層產(chǎn)生 屬性的原始數(shù)值用區(qū)間值或較高層的概念替換 數(shù)據(jù)立方體 ?據(jù)立方體存儲多維聚集信息，提供對預(yù)計算的匯總數(shù)據(jù)進(jìn)行快速訪問。 屬性子集選擇 ?通過刪除不相關(guān)或冗余的屬性（或維）減小數(shù)據(jù)集。 ?通過窮舉搜索找出有屬性的最佳子集是不現(xiàn)實的。 ?如貪心算法：從局部最優(yōu)到全局最優(yōu)。 ?分為無損和有損兩種。 ?小波變換（ DWT）：有損，適合高維數(shù)據(jù)。 數(shù)值規(guī)約 ?通過選擇替代的、“較小的”數(shù)據(jù)表示形式來減少數(shù)據(jù)量。 ?參數(shù)方法：回歸（ regression ）和對數(shù)線性模型 ?非參數(shù)方法：直方圖、聚類、抽樣 離散化 ?離散化的用途 ： （ 1）適應(yīng)某些僅接受離散值的算法； （ 2）減小數(shù)據(jù)的尺度。 （ 1）等距分割； （ 2）聚類分割； （ 3）直方圖分割； （ 4）基于熵的分割； （ 5）基于自然屬性的分割。 ?抽樣方法 ?s個樣本無放回簡單隨機抽樣 ?s個樣本有放回簡單隨機抽樣 ?聚類抽樣 ?分層抽樣 分類 分類 ?分類是指將數(shù)據(jù) 映射到預(yù)先定義好 的群組或 類。 ?分類算法要求基于數(shù)據(jù)屬性來定義類別。 分類應(yīng)用 ?分類具有廣泛的應(yīng)用，例如 醫(yī)療診斷、信用卡系統(tǒng)的信用分級、圖像模式識 別等。 分類步驟 1．建立一個模型，描述預(yù)定的數(shù)據(jù)類集或概念集 ? 數(shù)據(jù)元組也稱作 樣本、實例或?qū)ο?。 ? 訓(xùn)練數(shù)據(jù)集中的單個元組稱作 訓(xùn)練樣本 ，假定每個元組屬于一個預(yù)定義的類，由一個稱作 類標(biāo)號 。 2. 使用模型進(jìn)行分類 ? 首先評估模型（分類法）的預(yù)測準(zhǔn)確率。 （ 1）模型的構(gòu)建 Training Data Classification Algorithms IF rank = ‘ professor’ OR years 6 THEN tenured = ‘ yes’ Classifier (Model) NAME RANK YEARS TENURED Mike Assistant Prof 3 no Mary Assistant Prof 7 yes Bill Professor 2 yes Jim Associate Prof 7 yes Dave Assistant Prof 6 no Anne Associate Prof 3 no （ 2）利用模型分類 Classifier Testing Data N A M E RANK Y E A R S T E N U R E DT o m A s s i s t a n t P r o f 2 noM e r l i s a A s s o c i a t e P r o f 7 noG e o r g e P r o f e s s o r 5 y e sJ o s e p h A s s i s t a n t P r o f 7 y e sUnseen Data (Jeff, Professor, 4) Tenured? 分類方法評價 ? 預(yù)測的準(zhǔn)確率 ? 這涉及模型正確地預(yù)測新的或先前未見過的數(shù)據(jù)的類標(biāo)號的能力 ? 速度 ? 構(gòu)造模型的速度 ? 利用模型進(jìn)行分類的速度 ? 強壯性 ? 給定噪聲數(shù)據(jù)或具有空缺值的數(shù)據(jù)，模型正確預(yù)測的能力 ? 可伸縮性 ? 當(dāng)給定大量數(shù)據(jù)時，有效地構(gòu)造模型的能力 ? 可解釋性 ? 涉及學(xué)習(xí)模型提供的理解和洞察的層次 分類器性能評價方式 ? 準(zhǔn)確率和召回率 混淆矩陣 等 ? 給定一個類 Cj和一個數(shù)據(jù)庫元組 ti， ti可能被分類器判定為屬于 Cj或不屬于 Cj，其實 ti本身可能屬于 Cj或不屬于 Cj，這樣就會產(chǎn)生如下一些情況： – 真正 : 判定 ti在 Cj中，實際上的確在其中。 – 真負(fù) : 判定 ti不在 Cj中，實際上不在其中。 ?準(zhǔn)確率 :P=A/(A+B) ?召回率 :R=A/(A+C) 評估分類方法的準(zhǔn)確性 ?保持方法 ?給定數(shù)據(jù)隨機劃分為兩個集合：訓(xùn)練集 (2/3)和測試集 (1/3) ?訓(xùn)練集導(dǎo)出分類法，測試集對其準(zhǔn)確性進(jìn)行評估 ?k折交叉驗證 ?初始數(shù)據(jù)被劃分為 k個不相交的，大小大致相同的子集 S1,S2…S k ?進(jìn)行 k次訓(xùn)練和測試，第 i次時，以 Si做測試集，其他做訓(xùn)練集 ?準(zhǔn)確率為 k次迭代正確分類數(shù)除以初始數(shù)據(jù)集樣本總數(shù) 分類方法 基于距離的分類方法 ?與一個類中的成員和另一個類中的成員之間的相似性相比，被映射到同一個類中的成員彼此之間被認(rèn)為是更加相似的。 基于距離的分類方法的直觀解釋 （ a）類定義 （ b）待分類樣例 （ c）分類結(jié)果 距離計算方法 ?閔可夫斯基距離 : ?當(dāng) p=2時，為歐幾里得距離 ?當(dāng) p=1時，為曼哈頓距離 ?當(dāng) p∞ 時，為切比雪夫距離 ?向量內(nèi)積 ： ?夾角余弦： ?Jaccard： 還有信息熵、相關(guān)系數(shù)等其他的度量方法 ( | x i y i | pi = 1n229。 x , y 241。c os q =x 1 x 2 + y 1 y 2x 12 + y 12 x 22 + y 22J ( A , B ) = | A 199。 B |基于距離的分類方法的一般性描述 ? 算法 基于距離的分類算法 ? 輸入：每個類的中心 C1， … ， Cm；待分類的元組 t。 ?（ 1） dist=∞； //距離初始化 ?（ 2） FOR i:=1 to m DO ?（ 3） IF dis(ci， t)dist THEN BEGIN ?（ 4） c← Ci； ?（ 5） dist←dist (Ci， t)； ?（ 6） END. ? 算法通過對每個元組和各個類的中心來比較，從而可以找出他的最近的類中心，得到確定的類別標(biāo)記。 ? 訓(xùn)練樣本用 n維數(shù)值屬性描述。所有的訓(xùn)練樣本都放在 n維模式空間中。 K近鄰算法（ KNN） ? 要求的信息 ? 訓(xùn)練集 ? 距離計算值 ? 要獲取的最鄰近的鄰居的數(shù)目 k ? 一個未知的記錄進(jìn)行分類 ? 計算與其它訓(xùn)練記錄之間的距離 ? 識別出 k個最近的鄰居 ? 使用最近鄰居的類標(biāo)號來標(biāo)識未知元組的類（ by taking majority vote） K近鄰算法（ KNN） 算法 K近鄰分類算法 輸入： 訓(xùn)練數(shù)據(jù) T；近鄰數(shù)目 K；待分類的元組 t。 （ 1） N=?； （ 2） FOR each d ∈ T DO BEGIN （ 3） IF |N|≤K THEN （ 4） N=N∪ nhcuj7d3； （ 5） ELSE （ 6） IF u∈ N such that sim(t， u)sim(t， d) THEN BEGIN （ 7） N=N{u}； （ 8） N=N∪ nhcuj7d3； （ 9） END （ 10） END （ 11） c=class to which the most u∈ N. K近鄰算法（ KNN） ? K值的選取 ? 如果 k過于小，那么將會對數(shù)據(jù)中存在的噪聲過于敏感 ? 如果 k過大，鄰居中可能包含其他類的點 ? 一個經(jīng)驗的取值法則為 k≤ ， ? q為訓(xùn)練元組的數(shù)目 。 q決策樹 決策樹（ Decision Tree） ? 決策樹是以實例為基礎(chǔ) 的 歸納學(xué)習(xí)算法 。 ? 類似于流程圖的樹結(jié)構(gòu)，其中 每個內(nèi)部節(jié)點 表示在一個 屬性上的測試 ， 每個分支 代表一個測 試輸出 ， 而每個樹葉節(jié)點代表類或類分布 。 決策樹 例如，在貸款申請中，要對申請的風(fēng)險大小做出判斷。 ? 在 ID3算法的基礎(chǔ)上， 1993年 Quinlan又提出了 。 決策樹的步驟 ?使用決策樹進(jìn)行分類分為兩步： ?第 1步：利用訓(xùn)練集 建立 并精化一棵 決策樹 ， 建立決策樹模型 。 ?第 2步：利用生成完畢的決策樹對輸入數(shù)據(jù)進(jìn)行 分類 。 決策樹 ?算法遞歸執(zhí)行的終止條件（停止分支的條件） ? 對于給定的節(jié)點， 所有的例子都屬于同一個類 ? 雖然對于某一個節(jié)點當(dāng)前的例子不屬于同一個類，但是已經(jīng) 沒有屬性 可用來選擇繼續(xù)進(jìn)行分支處理 分裂屬性選擇 ?選擇屬性的方法 ? 選擇具有 最大信息增益 的屬性作為當(dāng)前節(jié)點的測試屬性 ? 該屬性使得對結(jié)果劃分中的樣本分類所需的 信息量最小 ，并反映劃分的最小隨機性。 分裂屬性選擇 ?怎樣計算信息增益（ information gain） ?信息增益被定義為 原始分割的熵 與劃分以后各分割的熵 累加得到的總熵之間的差。 ?選擇具有 最高信息增益 的屬性作為當(dāng)前節(jié)點的測試屬性。該屬性分 兩類：買 /不買