數據挖掘學習筆記一：引論

1. 數據清理（消除噪聲和刪除不一致數據）
2. 數據集成（多種數據源可以組合在一起）
3. 數據選擇（從數據庫中提取與分析人物相關的數據）
4. 數據變換（通過匯總和聚集操作，把數據變換和統一成適合挖掘的形式）
5. 數據挖掘（基本步驟，使用智能方法提取數據模式）
6. 模式評估（根據某種 興趣度度量 ，識別代表知識的真正有趣的模式）
7. 知識表示（使用可視化和知識表示技術，向用戶提供挖掘的知識）

1.3 可以挖掘什么類型的數據

數據庫數據，數據倉庫數據，事務數據，其他類型的數據

1.3.1 數據庫數據

customer (cust_ID,name,address,age,occupation,annual_income,credit_information,category,...)
item        (item_ID,brand,category,type,price,place_made,supplier,cost,...)
employee    (empl_ID,name,category,group,group,salary,commission,...)
branch      (branch_ID,name,address,...)
purchases   (trans_ID,cust_ID,empl_ID,date,time,method_paid,amount)
item_sold   (trans_ID,item_ID,gty)
works_at    (empl_ID,branch_ID)

當數據挖掘用于關系數據庫時，你可以進一步 搜索趨勢 或 數據模式 。例如，數據挖掘系統可以分析顧客數據，根據顧客的收入、年齡和以前的信用信息預測新顧客的信用風險。數據挖掘系統也可以檢測偏差：例如，與以前的年份相比，哪些商品的銷售出人預料。可以進一步考察這種偏差：例如，數據挖掘可能發現這些商品的包裝的變化，或價格的大幅度提高。

關系數據庫是數據挖掘的最常見、最豐富的信息源，因此它是我們數據挖掘研究的一種主要數據新式。

1.3.2 數據倉庫

假設AllElectronics是一個成功的跨國公司，分部遍布全世界。每個分部都有一組自己的數據庫。AllElectronics的總裁要你提供公司第三季度每種類型的商品及每個分部的銷售分析。這是一項困難的任務，特別是當相關數據散布在多個數據庫，物理地駐留在許多站點時尤其如此。

數據倉庫是一個從多個數據源收集的信息存儲庫，存放在一致的模式下，并且通常駐留在單個站點上。數據倉庫通過數據清理、數據變換、數據集成、數據裝入和定期數據刷新來構造。

為便于決策，數據倉庫中的數據圍繞 主題 （如顧客、商品、供應商和活動）組織。數據存儲從 歷史的角度 （如過去的6~12個月）提供信息，并且通常是匯總的。例如，數據倉庫不是存放每個銷售事物的細節，而是存放每個商店、每類商品的銷售事務的匯總，或匯總到較高層次，即每個銷售地區、每類商品的銷售事務的匯總。

通常，數據倉庫用稱作 數據立方體（data cube） 的多維數據結構建模。其中，每個維對應于模式中的一個或一組屬性，而每個單元存放某種聚集度量值，如count或sum(sales_amount)。數據立方體提供數據的多維視圖，并允許預計算和快速訪問匯總數據。

例1.3 AllElectronics的數據立方體。AllElectronics的匯總銷售數據的數據立方體有三個維：address（城市值 芝加哥、紐約、多倫多、溫哥華 ），time（季度值 Q1、Q2、Q3、Q4 ），item（商品類型值 家庭娛樂、計算機、電話、安全 ）。存放在立方體的每個單元的聚集值是sales_amount（單位：千美元）。例如，在第一季度Q1，與安全系統相關的商品在溫哥華的總銷售為400，存放在單元 <溫哥華,Q1,安全> 中。其他立方體可以用于存放每個維上的聚集和，對應于使用不同的SQL分組的道德聚集值（例如，每個城市和季度的，或每個季度和商品的，或每一微的總銷售量）。

通過提供多維數據視圖和匯總數據的與計算，數據倉庫非常適合 聯機分析處理。OLAP 操作的例子包括下鉆（drill-down）和上卷（roll-up），它們允許用戶在不同的匯總級別觀察數據。

例如，可以對按季度匯總的銷售數據下鉆，觀察按月匯總的數據。類似的，可以按城市匯總的銷售數據上卷，觀察按國家匯總的數據。

多維數據挖掘（又稱 探索式多維數據挖掘 ）以OLAP風格在多維空間進行數據挖掘。也就是說，在數據挖掘中，允許在各種粒度進行多維組合探查，因此更有可能發現代表知識的有趣模式。

1.3.3 事務數據 一般地說，事務數據庫的每個記錄代表一個事務，如顧客的一次購物、一個航班訂票，或一個用戶的網頁點擊。通常，一個事務包含一個唯一的事務標識符（trans_ID），以及一個組成事物的項（如，交易中購買的商品）的列表。事務數據庫可能有一些與之相關聯的附加表，包含關于事物的其他信息，如商品描述、關于銷售人員或部門等的信息。

1.3.4 其他類型的數據 除 關系數據庫數據 、 數據倉庫數據 、 事務數據 外，還有許多其他類型的數據：

• 事件相關或序列數據（如：歷史記錄、股票交易數據、時間序列和生物學序列數據）
• 數據流（如：視頻監控和傳感器數據，他們連續播送）
• 空間數據（如：地圖）
• 工程設計數據（如：建筑數據、系統部件或集成電路）
• 超文本和多媒體數據（包括文版、圖像、視頻和音頻數據）
• 圖和網狀數據（如社會和信息網絡）
• 萬維網（由Internet提供的巨星、廣泛分布的信息存儲庫）

這些應用帶來了新的挑戰，例如，如何處理具有空間結構的數據（如序列、樹、圖和網絡）和特殊語義（如次序、圖像、音頻和視頻的內容、連接性），以及如何挖掘具有豐富結構和語義的模式。

例如，就時間數據而言，可以挖掘銀行數據的變化趨勢，這可以幫助銀行根據顧客流量安排出納員。

可以挖掘股票交易數據，發現趨勢，幫助你規劃投資策略（例如，購買AllElectronics的股票的最佳時機）。

可以挖掘計算機網絡數據，根據消息流的異常進行入侵檢測。這種異常可以通過聚類、流模型的動態創建，或把當前的頻繁模式與先前的比較發現。

使用空間數據，我們可以得到根據城市離主要公路的距離描述都市貧困率的變化趨勢的模式。

可以考察空間對象集之間的聯系，發現那些對象子集是空間自相關或關聯的。

通過挖掘文本數據，如挖掘過去10年“數據挖掘”方面的文獻，可以了解該領域熱點課題的演變。

通過挖掘顧客對產品發表的評論（通常，以短文本信息提交），我們可以評估顧客的意見，了解產品被市場接受的程度。

由多媒體數據，我們可以挖掘圖像，識別對象，并通過指派語義標號或標簽對它們分類。

通過挖掘曲棍球運動的視頻數據，可以檢測對應于進球的視頻序列。

Web挖掘 可以幫助我們了解萬維網信息的一般分布，刻畫網頁的特征，對網頁進行分類，并發現Web的動態，以及不同網頁、用戶、社區和基于Web的活動之間的關聯和聯系。

1.4 可以挖掘什么類型的模式

數據挖掘功能：特征化與區分,頻繁模式、關聯和相關性區分,分類與回歸,聚類分析,離群點分析

數據挖掘功能用于指定數據挖掘任務發現的模式。可分為兩類： 描述性 （descriptive）和預測性（predictive）。

• 描述性挖掘任務刻畫目標數據中數據的一般性質。
• 預測性挖掘任務在當前數據上進行歸納，以便做出預測。

1.4.1 類/概念描述：特征化與區分

數據可以與類或概念相關聯。 例如，在AllElectronics商店，銷售的商品類包括計算機和打印機，顧客概念包括bigSpenders和budgetSpenders。 用匯總的、間接地、精確地表達方式描述每個類和概念是有用的。這種類或概念的描述成為類/概念描述。這種描述可以通過下述方法得到：

1. 數據特征化，一般地匯總所研究類（通常稱為 目標類 ）的數據；
2. 數據區分，將目標類與一個或多個可比較類（通常稱為 對比類 ）進行比較；
3. 數據特征化和區分。

數據特征化（data characterization）是目標類數據的一般特征或特征的匯總。通常，通過查詢來收集對應于用戶指定類的數據。例如，為研究上一年銷售增加10%的軟件產品的特征，可以通過在銷售數據庫上執行一個SQL查詢來手機關于這些產品的數據。

數據特征化的輸出可以用多種形式提供，例如 餅圖 、 條圖 、 曲線 、 多維數據立方體 和包括交叉表在內的 多維表 。結果描述也可以用 廣義關系 或規則（稱作 特征規則 ）形式提供。

例1.5 數據特征化。 AllElectronics的客戶關系經理可能提出如下數據挖掘任務：“匯總一年之內在AllElectronics花費5000美元以上的顧客特征。”結果可能是顧客的概況，如年齡在40~50歲、有工作、有很好的信等級。數據挖掘系統應當允許用戶在任意維下鉆，如在occupation維下鉆，以便根據這些顧客的職業類型來觀察他們。

數據區分(data discrimination)是將目標類數據對象的一般特征與一個或多個對比類對象的一般特性進行比較。目標類和對比類可以由用戶指定，而對應的數據對象可以通過數據庫查詢檢索。例如，用戶可能希望將上一年銷售增加10%的軟件產品與同一時期銷售至少下降30%的軟件產品進行比較。用于數據區分的方法與用于數據特征化的方法類似。

區分描述 應當包括比較度量，以便幫助區別目標類和對比類。用規則表示的區分描述稱為 區分規則 （discriminant rule）。

例1.6 數據區分。AllElectronics的客戶關系經理可能想比較兩組顧客——定期（例如，每月多于兩次）購買計算機產品的顧客和不經常（例如，每年少于3次）購買這種產品的客戶。結果描述提供這些顧客比較的情況，例如頻繁購買計算機產品的顧客80%在20~40歲之間，受過大學教育；而不經常購買這種產品的顧客60%或者年齡太大或者太年輕，沒有大學學位。沿著維下鉆，如沿occupation維下鉆，或添加新的維，如income_level維，可以幫助發現兩類之間的更多區分特征。

1.4.2 挖掘頻繁模式、關聯和相關性

頻繁模式（frequent pattern）是在數據中頻繁出現的模式。

存在多種類型的頻繁模式，包括 頻繁項集 、 頻繁子序列（又稱序列模式） 和 頻繁子結構 。

頻繁項集 指頻繁地在事務數據集中出現的商品的集合，如小賣部中被許多顧客頻繁地一起購買的牛奶和面包。

頻繁子序列 ，如顧客傾向于先購買便攜機，再購買數碼相機，然后再購買內存卡這樣的模式就是一個 頻繁序列模式 。

頻繁子結構

可能涉及不同的結構形式（例如，圖、樹或格），可以與項集或子序列結合在一起。如果一個子結構頻繁地出現，則稱它為（頻繁）結構模式。挖掘頻繁模式導致返現數據中有趣的關聯和相關性。

通常，如果一個關聯規則不能同時滿足 最小支持度閾值 和 最小置信度閾值 ，則該關聯規則被認為是無趣的而被丟棄。

還可以做進一步分析，發現相關聯的屬性-值對之間的有趣的統計 相關性 (correlation)。

1.4.3 用于預測分析的分類與回歸

分類：找出描述和區分數據類或概念的模型（或函數），以便能夠使用模型預測類標號未知的對象的類標號。導出模型是基于 訓練數據集 （即，類標號已知的數據對象）的分析。該模型用來預測類標號未知的對象的類標號。

“如何提供導出的模型？”：分類規則（即IF-THEN規則）、決策樹、數學公式或神經網絡。

決策樹是一種類似于流程圖的樹結構，其中每個節點代表在一個屬性值上的測試，每個分支代表測試的一個結果，而輸液代表類或者類分布。容易把決策樹轉換成分類規則。

當用于分類時， 神經網絡 是一組類似于神經元的處理單元，單元之間加權連接。

還有很多構造分類模型的其他方法：樸素貝葉斯分類（我竟然打成了樸樹被噎死）、支持向量機和k最近鄰分類。

分類預測類別（離散的、無序的）標號，而 回歸 建立連續值函數模型。

也就是說：回歸用來預測缺失的或難以獲得的數值數據值，而不是（離散的）類標號。

回歸分析（regression analysis）是一種最長是用的數值預測的統計學方法。

回歸也包含基于可用數據的分布 趨勢 識別。

相關分析（relevance analysis）可能需要在分類和回歸之前進行，它視圖識別與分類和回歸過程顯著相關的屬性。我們將選取這些屬性用于分類和回歸過程，其他屬性是不相關的，可以不必考慮。

1.4.4 聚類分析

聚類（clustering）與[分類與回歸標記類的（訓練）數據集]不同，聚類分析數據對象，而不考慮類標號。在許多情況下，開始并不存在標記類的數據。可以使用聚類產生數據群組的類標號。對象根據 最大化類內相似性、最小化類間相似性 的原則進行聚類或分組。也就是說，對象的簇（cluster）這樣形成，使得相比之下在同一個簇中的對象具有很高的相似性，而與其他簇中的對象很不相似。所形成的每個簇都可看做一個對象類，由它可以導出規則。聚類也便于 分類法形成 (taxonomy formation)，即將觀測組織成類分層結構，把類似的時間組織在一起。

例1.9 聚類分析。可以在AllElectronics的顧客數據上進行聚類分析，識別顧客的同類子群。這些簇可以表示每個購物目標群。

1.4.5 離群點分析

數據集中可能包含一些數據對象，他們與數據的一般行為或模型不一致。這些數據對象是離群點（outlier）。大部分數據挖掘方法都將離群點視為噪聲或異常而丟棄。然而，在一些應用中（例如，欺詐檢測），罕見的事件可能比正常出現的事件更令人感興趣。離群點數據分析稱作 離群點檢測 或 異常挖掘 。

可以假定一個數據分布概率模型，使用統計檢驗來檢測離群點；

或者使用距離度量，將遠離任何簇的對象視為離群點； 或者不使用統計或距離度量，基于密度的方法皆可以識別局部區域中的離群點。

例1.10 離群點分析。通過檢測一個給定賬號與正常的付費相比付款數額特別大，離群點分析可以發現信用卡欺騙性使用。離群點還可以通過購物地點和類型或購物頻率來檢測。

1.4.6 所有模式都是有趣的嗎

“什么樣的模式是有趣的？”

一個模式是有趣的（interesting），如果它：

1. 易于被人理解；
2. 在某種 確信度 上，對于新的或檢驗數據使 有效的 ；
3. 是潛在有用的；
4. 是 新穎 的。

如果一個模式證實了用戶尋求正式的某種假設，則它也是有趣的。

有趣的模式代表 知識 。

模式興趣度的

客觀度量

：

• 支持度（support）：support(X ==> Y) = P(X ∪ Y)
• 置信度（confidence）：confidence(X ==> Y) = P(Y|X)

其他數據度量包括分類（IF-THEN）規則的 準確率 與 覆蓋率 。

一般而言，準確率告訴我們被一個規則正確分類的數據所占的百分比。

覆蓋率類似于“支持度”，告訴我們規則可以作用的數據所占的百分比。

主觀興趣度度量 基于用戶對數據的信念。這種度量發現模式是有趣的，如果他們是 出乎意料的 （與用戶的信念相矛盾），或者提供用戶可以采取行動的至關重要的信息。在后一種情況下，這樣的模式成為 可行動的 （actionable）。意料之內的模式也可能是有趣的，如果他們證實了用戶希望正式的假設，或與用戶的預料相似。

“數據挖掘系統能夠產生所有有趣的模式嗎？”

“數據挖掘系統能夠產生所有有趣的模式嗎？” —— 涉及數據挖掘算法的完全性。

“數據挖掘系統能夠僅產生有趣的模式嗎？”

“數據挖掘系統能夠僅產生有趣的模式嗎？” —— 是數據挖掘的優化問題。

使用什么技術

統計學 、機器學習、模式識別、數據庫和數據倉庫、信息檢索、可視化、高性能計算……

1.5.1 統計學

統計學研究數據的手機、分析、解釋和表示。數據挖掘與統計學具有天然聯系。

統計模型是一組數學函數，它們用隨機變量及概率分布刻畫目標類對象的行為。

1.5.2 機器學習

機器學習考察計算機如何基于數據學習（或提高他們的性能）。其主要研究領域之一是，計算機程序基于數據 自動地 學習復雜的模式，并作出智能的決斷。例如，一個典型的機器學習問題是為計算機編制程序，使之自動地識別郵件上的手寫體郵政編碼。

一些與數據挖掘高度相關的、經典的機器學習問題：

• 監督學習（supervised learning） 基本上是分類的同義詞。學習中的監督來自訓練數據集中標記的實例。例如，在郵政編碼識別問題中，一組手寫郵政編碼圖像與其對應的機器可讀的轉換物用作訓練實例，監督分類模型的學習。
• 無監督學習（unsupervised learning） 本質上是聚類的同義詞。學習過程是無監督的，因為輸入實例沒有類標記。典型地，我們可以使用聚類發現數據中的類。例如，一個無監督學習方法可以取一個手寫數字圖像集合作為輸入。假設它找出了10個數據簇，這些簇可以分別對應于0~9這10個不同的數字。然而，由于訓練數據并無標記，因此學習到的模型并不能告訴我們所發現的簇的語義。
• 半監督學習（semi-supervised learning） ：在學習模型時，它使用標記的和未標記的實例。在一種方法中，標記的實例用來學習類模型，而未標記的實例用來進一步改進類邊界。對于兩類問題，我們可以把屬于一個類的實例看做 正實例 ，而屬于另一個類的實例為 負實例 。
• 主動學習（active learning） ：然用戶在學習過程中扮演主動角色。主動學習方法可能要求用戶（例如領域專家）對一個可能來自未標記的實例集或由學習程序合成的實例進行標記。給定可以要求標記的勢力數量的約束，目的是主動通過從用戶獲取知識來提高模型質量。

1.5.3 數據庫系統與數據倉庫

……

1.5.4 信息檢索

信息檢索（IR）是搜索文檔或文檔中信息的科學。

信息檢索的典型方法是采用概率模型。

一個文本文檔集的主題可以用詞匯表上的概率分布建模，稱作 主題模型 。

數據挖掘的主要問題：挖掘方法、用戶交互、有效性與可伸縮性、數據類型的多樣性、數據挖掘與社會。

1.8 小結

需要是發明之母。

數據挖掘是從海量數據中發現有趣模式的過程。作為 知識發現過程 ，它通常包括數據清理、數據集成、數據選擇、數據變換、模式發現、模式評估和知識表示。

一個模式是 有趣的 ，如果它在某種確信度上對于檢驗數據是有效的、新穎的、潛在有用的（例如，可以據之行動，或者驗證了用戶關注的某種預感），并且易于被人理解。有趣的模式代表知識。 模式興趣度 度量，無論是客觀的還是主觀的，都可以用來知道發現過程。

數據挖掘的 多維視圖 。主要的維是數據、知識、計數和應用。

只要數據對于目標應用是有意義的，數據挖掘可以在任何類型的數據上進行，如數據庫管理、數據倉庫數據、事務數據和高級數據類型等。高級數據類型包括時間相關的序列數據、數據流、空間和時空數據、文本和多媒體數據、圖和網絡數據、Web數據。

數據倉庫是一種用于長期存儲數據的倉庫，這些數據來自多個數據源，是經過組織的，以便支持管理決策。這些數據在一中統一的模式下存放，并且通常是匯總的。數據倉庫提供一些數據分析能力，稱作 聯機分析處理 。

多維數據挖掘（又稱 探索式多維數據挖掘 ）把數據挖掘的核心技術與基于OLAP的多維分析結合在一起，搜索有趣的模式，探索多維空間。

數據挖掘功能用來指定數據挖掘任務發現的模式或 知識 類型，包括特征化和區分，頻繁模式、關聯和相關性挖掘，分類和回歸，聚類分析和離群點檢測。

作為一個應用驅動的領域，數據挖掘融匯萊西其它一些領域的技術。這些領域包括統計學、機器學習、數據庫和數據倉庫系統，以及信息檢索。

數據挖掘有許多成功的應用，如商務智能、Web搜索、生物信息學、衛生保健信息學、金融、數字圖書館和數字政府。

數據挖掘研究存在許多 挑戰性問題 。領域包括挖掘方法、用戶交互、有效性和可伸縮性，以及處理多種多樣的數據類型。