《資料挖掘概念與技術》學習筆記

1.Chapter1 引論：

(1) OLTP 和 OLAP 概念:

OLTP(on-line transaction processing) 聯機事物處理，就是我們經常說的關系資料庫的主要應用，主要是基本的、日常的事務處理，例如銀行交易。例如：mysql

OLAP(on-line analytical processing) 聯機分析處理，是資料倉庫系統的主要應用，支援複雜的分析操作，側重決策支援，并且提供直覺易懂的查詢結果。例如：hive+hdfs。 

(2) 資料倉庫概念：

資料倉庫是一個面向主題的(subject-oriented)、內建的(integrated)、時變的(time-variant)、非易失的(nonvolatile)資料集合，支援管理者的決策過程。

ps：上面是比較官網的定義，更白話一點就是：資料倉庫是一種多個異構資料源在單個站點以統一的模式組織的存儲,以支援管理決策。

(3) 資料挖掘的步驟（KDD）：

資料清理（清除噪聲和删除不一緻資料）。

資料內建（多種資料源可以組合在一起）。

資料選擇（從資料庫中提取和分析任務相關的資料）。

資料變換（通過彙總或聚集操作，把資料變換和統一成适合資料挖掘的形式。

資料挖掘（基本步驟，使用智能方法提取資料模式）。

資料評估（根據某種興趣度度量，識别代表知識的真正有趣的模式）。

知識表示（使用可視化和知識表示技術，向使用者提供挖掘的知識）。

ps:資料挖掘是從大量資料中挖掘有趣模式和知識的過程，資料源包括資料庫、資料倉庫、Web、其他資訊存儲庫或動态地流入系統的資料。

(4) 離群點分析：

資料集中可能包含一些資料對象，他們與資料的一般行為或模型不一緻。這些資料對象是離群點（outlier）。大部分資料挖掘方法都将離群點視為噪聲或異常而丢棄。

(5) 多元資料挖掘（又稱探索式資料挖掘）把資料挖掘的核心技術和OLAP的多元分析結合在一起。他在不同的抽象層的多元（屬性）組合中搜尋有趣的模式，進而探索多元資料空間。

2.Chapter2 認識資料：

(1)各種數的定義：

衆數：衆數是資料集中心的一種中心度量趨勢，資料集的衆數是集合中出現最頻繁的的值。

中列數：中列數也可以用來評估數值資料的中心趨勢。中列數是資料集中的最大和最小值的平均值。

中位數：對于傾斜（非對稱）資料，資料中心的最好度量是中位數。中位數是有序數值的中間值。它把資料較高的一半和較低的一半分開的值。

分位數：分位數根據其資料列等分的形式不同可以分為中位數、四分位數、十分位數、百分位數等等。四分位數作為分位數的一種形式，在統計中有十分重要的意義和作用。人們經常會将資料劃分為4個部分，每個部分大約包含1/4和25%的資料項。這種劃分的臨界點即為四分位數。他們定義如下：

Q1=第一個四分位數，即第25百分位數。

Q2=第二個四分位數，即第50百分位數。

Q3=第三個四分位數，即第75百分位數。

(2)距離:

歐式距離：歐式距離（Euclidean distance)也稱歐幾裡得距離，他是一個通常采用的距離定義，他是在m維空間中兩個點之間的真實距離。

定義公式如下：d=sqrt( ∑(xi1-xi2)^2 ) 這裡i=1,2..n

曼哈頓距離(計算兩個街區之間的距離)：

距離公式為：|x1-y1|+|x2-y2|+|x3-y3|+|x4-y4|+……+|xn-yn|（兩點的坐标分别為（x1,x2,……,xn）、（y1,y2,……,yn））

闵可夫斯基距離：其是歐幾裡得距離和曼哈頓距離的推廣。 公式定義為： 

3.chapter3 資料預處理:

(1) 恒量資料品質的幾個要素：準确性、完整性、一緻性、時效性、可信性、可解釋性。

(2) 資料預處理分為如下幾個步驟：資料清理、資料內建、資料規約、資料交換。

資料清理：資料清理是通過填寫缺失的值，光滑噪聲資料，識别和删除離群點并解決不一緻性來“清理”資料。

資料內建：整合多個資料庫、資料立方體或檔案，即資料內建。

資料規約(data reduction):得到資料集的簡化表示，它小的多，但能夠産生同樣（或幾乎同樣的）分析結果。資料規約政策包括維規約和數值規約。在維規約中，使用資料編碼方案，以便得到資料的簡化或“壓縮”表示。例如資料資料壓縮技術（小波變化或主成分分析）。在數值規約中，使用參數模型（例如，回歸和對數線性模型）或非參數模型（例如，直方圖、聚類、抽樣或資料聚集），用較小的表示取代資料。

(3)缺失值處理政策：

忽略缺失值、人工填寫缺失值、使用一個全局常量填充缺失值、使用屬性的中心度量（如均值或中位數）、使用與給定元祖屬同一類的所有樣本的屬性均值或中位數、使用最可能的值填充缺失值。

(4)資料變換政策：

光滑（smoothing）：去掉資料中的噪聲。這類技術包括分箱、回歸、和聚類。

屬性構造：可以由給定的屬性構造新的屬性并添加到屬性集中，以幫助挖掘過程。

聚集：對資料進行彙總或聚集。例如：可以聚集日銷售資料，計算月銷售或年銷售資料，通常，這一步用來為多個抽象層的資料分析構造資料立方體。

規範化：把屬性資料按比例縮放，使之落入一個特定的小區間，例如 -1 ~ 1。

離散化：數值屬性（例如：年齡）的原始值，可以用數值區間替換使其離散化。

由标稱資料産生概念分層：屬性，如street，可以泛化到較高的概念層，例如city或country。

4.chapter4 資料倉庫和聯機分析處理（OLAP):

(1) OLTP和OLAP的主要差別如下：

=>使用者和系統的面向性：OLTP是面向顧客的，用于辦事員、客戶和資訊技術專業人員的事物和查詢處理。OLAP是面向市場的，用于知識勞工（包括經理、主管和分析人員）的資料分析。

=>資料内容：OLTP系統管理目前資料。通常，這種資料台瑣碎，很難用于決策。OLAP系統管理大量曆史資料，提供彙總和聚集機制，并在不同的粒度層上存儲和管理資訊。這些特點使得資料更容易用于有根據的決策。

=>資料庫設計：通常，OLTP系統采用實體-聯系（ER）資料模型和面向應用的資料庫設計。而OLAP系統通常采用星形或雪花模型和面向主題的資料庫設計。

=>視圖：OLTP系統主要關注一個企業或部門内部的目前資料，而不涉及曆史資料或不同機關的資料。OLAP系統常常跨越資料庫模式的多個版本。OLAP系統還處理來自不同機關的資訊，以及由多個資料庫內建的資訊。 =>通路模式：OLTP系統的通路主要由短的原子事物組成。這種系統需要并發控制和恢複機制。然而，對OLAP系統的通路大部分是隻讀操作（由于大部分資料倉庫存放曆史資料,而不是最新資料）。

(2)資料倉庫的分層結構：

底層是倉庫資料庫伺服器 =》 中間層是OLAP伺服器 =》 頂層是前端客戶層。

(3)資料倉庫模型： 企業倉庫、資料集市、虛拟倉庫。

=》企業倉庫：企業倉庫搜集了關于主題的所有資訊，跨越整個企業。它提供企業範圍内的資料內建，通常來自一個或多個作業系統資料庫系統或外部資訊提供者，并且是多功能的。

=>資料集市:資料集市包含企業範圍資料的一個子集，對于特定的使用者群是有用的。其範圍限定于標明的主題。

=>虛拟倉庫：虛拟倉庫是操作資料庫上視圖的集合。為了有效的處理查詢，隻有一些可能的彙總視圖被物化。虛拟倉庫易于建立，但需要操作資料庫伺服器還有餘力。

OLAP操作：

(4)上卷（roll-up）操作：上卷操作通過沿一個維的概念分層向上攀升或者通過維規約在資料立方體上進行聚集。

(5)下鑽（drill-down）：下鑽是上卷的逆操作，它由不太詳細的資料得到更詳細的資料。下鑽可以通過沿維的概念分層向下或引入附加的維來實作。

5.chapter5資料立方體技術：

(1)資料立方體由方體的格組成。每個方體都對應給定多元資料的不同程度的彙總。完全物化是指計算資料立方體格中的所有方體。部分物化是指選擇性的計算格中方體單元的子集。冰山立方體是一種資料方體，它僅存儲其聚集值（如count）大于某最小支援度門檻值的立方體單元。

(2)4種有效的立方體計算方法：1）多路資料聚集Multiway，基于稀疏數組的、自底向上的、共享計算的物化整個資料立方體；2）BUC，通過探查有效的自頂向下的計算次序和排序計算冰山立方體；3）Star-Cubing，使用星樹結構，內建自頂向下和自底向上計算，計算冰山立方體。4）外殼片段立方體，通過僅計算劃分的立方體外殼片段，支援高維OLAP。

6.chapter6 資料頻繁模式、關聯和相關性:

(1) 關聯規則挖掘首先找出頻繁項集（項的集合，如A和B，滿足最小支援度閥值，或任務相關元祖的百分比），然後，由他們産生形如A=》B的強關聯規則。這些規則還滿足最小置信度閥值。可以進一步分析關聯，發現項集A和B之間具有統計相關性的相關規則。

(2) 對于頻繁項集挖掘，已經開發了許多有效的、可伸縮的算法，由他們可以導出關聯和相關規則。這些算法可以分為3類: 1)類Apriori算法； 2）基于頻繁模式增長的算法，如：FP-growth； 3）使用垂直資料格式的算法。

(3) Apriori算法是為布爾關聯規則挖掘頻繁項集的原創性算法。它逐層進行發掘，利用先驗性質：頻繁項集的所有非空子集也都是頻繁的。

(4) 頻繁模式增長（FP-growth）是一種不産生候選的挖掘頻繁項集方法。它構造一個高壓縮的資料結構（FP樹），壓縮原來的資料庫。與類Apriori方法使用産生-測試政策不同，它聚焦于頻繁模式增長，避免了高代價的候選産生，可獲得更高的效率。

7.Chapter 7

(1)稀有模式很少出現但特别有趣。負模式是其成員呈現負相關行為的模式。應該小心定義負模式，考慮零不變性性質。稀有模式和負模式可能凸顯資料的異常行為，這肯能很有趣。

(2)基于限制的挖掘政策可以用來引導挖掘過程，挖掘和使用者直覺一緻或滿足某些限制的模式，許多使用者包括單調性，反單調性，資料反單調性和簡潔性。具有這些性質的限制可以正确的內建到資料挖掘過程中。

(3)為了減少挖掘傳回的模式數量，我們可以代之以挖掘壓縮模式或近似模式。壓縮模式可以通過基于聚類概念定義代表模式來挖掘，而近似模式可以通過提取感覺備援的top-k模式（即k個代表模式的小集合，他們不僅具有高顯著性，而且互相之間低備援)來挖掘。

8.Chapter 8

(1) 分類是一種資料分析形式，它提取描述資料類的模型。分類器或分類模型預測類标号（類）。資料預測建立連續函數模型。分類和數值預測是兩類主要的預測問題。

(2) 決策樹歸納是一種自頂向下的樹歸納算法，它使用一種屬性選擇度量為樹的每個非樹葉結點選擇屬性測試。ID3、C4.5和CART都是這種算法的例子，他們使用不同的屬性選擇度量。樹剪枝算法試圖通過減去反映資料中噪聲的分枝、提高準确率。早期的決策樹算法通常假定資料是駐留記憶體的。已經為可伸縮的樹歸納提出了一些可伸縮的算法，如RainForest。

(3) 樸素貝葉斯分類基于後驗機率的貝葉斯定理。它假定類條件獨立，一個屬性對給定分類的影響獨立于其他屬性的值。

(4) 分類器的構造與評估需要把标記的資料劃分成訓練集和測試集。保持、随機抽樣、交叉驗證和自助法都是用于這種劃分的典型方法。

(5) 顯著性校驗和ROC曲線對于模型選擇是有用的。顯著性校驗可以用來評估兩個分類器準确率的差别是否處于偶然。ROC曲線繪制一個或多個分類器的真正例率（或靈敏性)與假正例率。

9.chapter9

(1) 不像樸素貝葉斯分類（它假定類條件獨立），貝葉斯信念網絡允許在變量子集之間定義類獨立性。它提供了一種因果關系的圖形模型，在其上進行學習。訓練後的貝葉斯信念網絡可以用來分類。

(2) 支援向量機（SVM）是一種用于線性和非線性資料的分類方法。它把資料源資料變換到較高維空間，使用稱作支援向量的基本元組，從中發現分離資料的超平面。

(3) 主動學習是一種監督學習，它适合資料豐富、但類标号稀缺或難以獲得的情況。學習算法可以主動的向使用者學習詢問類标号。為了保持低價，主動學習的目标是使用盡可能少的有标号的執行個體來獲得高準确率。

10.chapter 10

(1) 簇是資料對象的集合，同一個簇中的對象彼此相似，而不同簇中的對象彼此相異。将實體或抽象對象的集合劃分為相似的類的過程成為聚類。

(2) 聚類分析具有廣泛的應用，包括商務智能，圖像模式識别，Web搜尋，生物學和安全。聚類分析可以作為獨立的資料挖掘工具來獲得資料分布的了解，也可以作為檢測簇上運作的其他資料挖掘算法的預處理步驟。

(3) 劃分方法：首先建立K個分區的初始集合，其中參數k是建構的分區數。然後，它采用疊代重定位技術，試圖通過吧對象從一個簇移到另一個簇來改進劃分的品質。典型的劃分方法包括k-均值、k-中心點、CLARANS。