這是大數(shù)據(jù)挖掘ppt，包括了數(shù)據(jù)挖掘概覽，數(shù)據(jù)預處理，分類（Classification），聚類（Cluster），關(guān)聯(lián)規(guī)則（Association Rule），回歸（Regression）等內(nèi)容，歡迎點擊下載。

大數(shù)據(jù)挖掘ppt是由紅軟PPT免費下載網(wǎng)推薦的一款課件PPT類型的PowerPoint.

李國良 清華大學計算機系 提綱 數(shù)據(jù)挖掘概覽 數(shù)據(jù)預處理 分類（Classification） 聚類（Cluster） 關(guān)聯(lián)規(guī)則（Association Rule） 回歸（Regression） 數(shù)據(jù)挖掘概覽 What? 數(shù)據(jù)挖掘的定義 Why? 數(shù)據(jù)挖掘的動機 How? 哪些數(shù)據(jù)可以用來挖掘？ 數(shù)據(jù)挖掘的主要內(nèi)容 數(shù)據(jù)挖掘定義 什么是數(shù)據(jù)挖掘（Data Mining）？ Extraction of interesting (non-trivial， implicit， previously unknown and potentially useful) patterns or knowledge from huge amount of data 其他稱謂： Knowledge discovery(mining) in database(KDD)， data/pattern analysis， business intelligence， decision-support system， knowledge extraction， data archeology， data dredging and information harvesting etc. 模式有效性度量 Simplicity E.g.， (association) rule length， (decision) tree size Certainty E.g.， confidence， P(A|B) = #(A and B)/ #(B)， classification reliability or accuracy， rule strength， etc. Utility Potential usefulness， e.g.， support (association)， noise threshold (description) Novelty Not previously known， surprising (used to remove redundant rules) 為何需要數(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ù)挖掘應用 銀行 美國銀行家協(xié)會(ABA)預測數(shù)據(jù)倉庫和數(shù)據(jù)挖掘技術(shù)在美國商業(yè)銀行的應用增長率是14.9％。 分析客戶使用分銷渠道的情況和分銷渠道的容量 ；建立利潤評測模型；客戶關(guān)系優(yōu)化；風險控制等 電子商務 網(wǎng)上商品推薦；個性化網(wǎng)頁；自適應網(wǎng)站… 生物制藥、基因研究 DNA序列查詢和匹配；識別基因序列的共發(fā)生性 … 電信 欺詐甄別；客戶流失… 保險、零售 數(shù)據(jù)挖掘應用 數(shù)據(jù)挖掘步驟 數(shù)據(jù)預處理 數(shù)據(jù)清理（消除噪音或不一致數(shù)據(jù)，補缺） 數(shù)據(jù)集成（多種數(shù)據(jù)源可以組合在一起） 數(shù)據(jù)變換（規(guī)范化） 數(shù)據(jù)規(guī)約（數(shù)據(jù)簡化） 數(shù)據(jù)挖掘算法（使用智能方法提取數(shù)據(jù)模式） 分類、聚類、關(guān)聯(lián)分析、回歸預測、文本挖掘 質(zhì)量評估（識別提供知識的真正有趣模式） 知識表示（可視化和知識表示技術(shù)） 數(shù)據(jù)質(zhì)量：為何需要數(shù)據(jù)預處理？ 數(shù)據(jù)質(zhì)量衡量： 準確度:correct or wrong， accurate or not 完整度:not recorded unavailable 一致性:some modified but some not， dangling 時效性:timely update? 可信度:how trustable the data are correct? 可解釋性:how easily the data can be understood? 數(shù)據(jù)挖掘預處理的主要任務 數(shù)據(jù)清理 填寫空缺的值，平滑噪聲數(shù)據(jù)，識別、刪除孤立點，解決不一致性 數(shù)據(jù)集成 集成多個數(shù)據(jù)庫、數(shù)據(jù)立方體或文件 數(shù)據(jù)變換 規(guī)范化和聚集 數(shù)據(jù)歸約 得到數(shù)據(jù)集的壓縮表示，它小得多，但可以得到相同或相近的結(jié)果 數(shù)據(jù)離散化 數(shù)據(jù)歸約的一部分，通過概念分層和數(shù)據(jù)的離散化來規(guī)約數(shù)據(jù)，對數(shù)字型數(shù)據(jù)特別重要 數(shù)據(jù)清洗 臟數(shù)據(jù)：例如設備錯誤，人或者機器錯誤，傳輸錯誤等 不完整性：屬性值缺失或者只有聚集數(shù)據(jù) 例如：phone=“”; 噪音：包含噪聲、錯誤或者異常值 例如：salary=-10 不一致性: 例如：age=42，birthday=03-07-2010 假值： 例如：使用某一值填補缺失屬性 缺失值（Incomplete/Missing Data) 數(shù)據(jù)并不總是完整的 例如：數(shù)據(jù)庫表中，很多條記錄的對應字段沒有相應值，比如銷售表中的顧客收入 引起空缺值的原因 設備異常 與其他已有數(shù)據(jù)不一致而被刪除 因為誤解而沒有被輸入的數(shù)據(jù) 在輸入時，有些數(shù)據(jù)因為得不到重視而沒有被輸入 對數(shù)據(jù)的改變沒有進行日志記載 空缺值要經(jīng)過推斷而補上 如何補充缺失值 忽略元組：當類標號缺少時通常這么做（假定挖掘任務設計分類或描述），當每個屬性缺少值的百分比變化很大時，它的效果非常差。 人工填寫空缺值：工作量大，可行性低 使用一個全局變量填充空缺值：比如使用unknown或-∞ 使用屬性的平均值填充空缺值 使用與給定元組屬同一類的所有樣本的平均值 使用最可能的值填充空缺值：使用像Bayesian公式或判定樹這樣的基于推斷的方法 噪聲數(shù)據(jù) 噪聲：一個測量變量中的隨機錯誤或偏差 引起不正確屬性值的原因 數(shù)據(jù)收集工具的問題 數(shù)據(jù)輸入錯誤 數(shù)據(jù)傳輸錯誤 技術(shù)限制 命名規(guī)則的不一致 其它需要數(shù)據(jù)清理的數(shù)據(jù)問題 重復記錄 不完整的數(shù)據(jù) 不一致的數(shù)據(jù) 如何處理噪聲數(shù)據(jù) 分箱: first sort data and partition into (equi-depth) bins then one can smooth by bin means， smooth by bin median， smooth by bin boundaries， etc. 聚類 detect and remove outliers 人機融合 detect suspicious values and check by human (e.g.， deal with possible outliers) 回歸 smooth by fitting the data into regression functions 分箱(Binning) 等寬Equal-width (distance) partitioning: Divides the range into N intervals of equal size: uniform grid if A and B are the lowest and highest values of the attribute， the width of intervals will be: W = (B –A)/N. The most straightforward， but outliers may dominate presentation Skewed data is not handled well. 等深Equal-depth (frequency) partitioning: Divides the range into N intervals， each containing approximately same number of samples Good data scaling Managing categorical attributes can be tricky. 數(shù)據(jù)平滑的分箱方法 price的排序后數(shù)據(jù)（單位：美元）：4，8，15，21，21，24，25，28，34 劃分為（等深的）箱： 箱1：4，8，15 箱2：21，21，24 箱3：25，28，34 用箱平均值平滑： 箱1：9，9，9 箱2：22，22，22 箱3：29，29，29 用箱邊界平滑： 箱1：4，4，15 箱2：21，21，24 箱3：25，25，34 聚類：Cluster Analysis Regression 數(shù)據(jù)集成 實體識別 元數(shù)據(jù)可幫助避免錯誤 知識圖譜 屬性冗余 相關(guān)分析 數(shù)據(jù)重復（元組冗余） 數(shù)據(jù)值沖突的檢測與處理 表示、比例或編碼不同 數(shù)據(jù)變換（規(guī)范化） 平滑：去掉數(shù)據(jù)中的噪聲。技術(shù)包括分箱、回歸、聚類。 聚集：對數(shù)據(jù)進行匯總或聚集。 數(shù)據(jù)泛化（概化）：使用概念分層，用高層概念替換低層或“原始”數(shù)據(jù)。 規(guī)范化：將屬性數(shù)據(jù)按比例縮放，使之落入一個小的特定區(qū)間。最小-最大、Z-Score、按小數(shù)定標規(guī)范化。 數(shù)據(jù)變換 數(shù)據(jù)規(guī)約 海量數(shù)據(jù)  代表性數(shù)據(jù) 對海量數(shù)據(jù)進行復雜的數(shù)據(jù)分析和挖掘?qū)⑿枰�很長時間，使得這種分析不現(xiàn)實或不可行。 數(shù)據(jù)歸約技術(shù)可以用來得到數(shù)據(jù)集的歸約表示，它小得多，但仍接近保持原數(shù)據(jù)的完整性。 對歸約后的數(shù)據(jù)集挖掘?qū)⒏�有效，并產(chǎn)生相同（或幾乎相同）的結(jié)果。 數(shù)據(jù)規(guī)約 數(shù)據(jù)歸約策略： （1）數(shù)據(jù)立方體聚集：對數(shù)據(jù)立方體做聚集操作 （2）屬性子集選擇：檢測并刪除不相關(guān)、弱相關(guān)或冗余的屬性和維。 （3）維度歸約：刪除不重要的屬性 （4）數(shù)值歸約： 用規(guī)模較小的數(shù)據(jù)表示、替換或估計原始數(shù)據(jù) （5）離散化和概念分層產(chǎn)生 屬性的原始數(shù)值用區(qū)間值或較高層的概念替換 數(shù)據(jù)立方體 據(jù)立方體存儲多維聚集信息，提供對預計算的匯總數(shù)據(jù)進行快速訪問。 如：立方體內(nèi)存儲季度銷售額，若對年銷售額感興趣，可對數(shù)據(jù)執(zhí)行聚集操作，例如sum()等。 屬性子集選擇 通過刪除不相關(guān)或冗余的屬性（或維）減小數(shù)據(jù)集。 其目標是找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性得到的原分布。 通過窮舉搜索找出有屬性的最佳子集是不現(xiàn)實的。通常采用壓縮搜索空間的啟發(fā)式算法。 如貪心算法：從局部最優(yōu)到全局最優(yōu)。 逐步向前選擇 逐步向后刪除 向前選擇和向后刪除的結(jié)合 決策樹歸納 維度規(guī)約 維度歸約使用數(shù)據(jù)編碼或變換，以便得到原數(shù)據(jù)的歸約或“壓縮”表示。 分為無損和有損兩種。 主要方法： 串壓縮：無損，但只允許有限的數(shù)據(jù)操作。 小波變換（DWT）：有損，適合高維數(shù)據(jù)。 主成分分析（PCA）：有損，能更好地處理稀疏數(shù)據(jù)。 數(shù)值規(guī)約 通過選擇替代的、“較小的”數(shù)據(jù)表示形式來減少數(shù)據(jù)量。 可以分為參數(shù)方法和非參數(shù)方法。 參數(shù)方法：回歸（regression ）和對數(shù)線性模型 非參數(shù)方法：直方圖、聚類、抽樣 離散化 離散化的用途： （1）適應某些僅接受離散值的算法； （2）減小數(shù)據(jù)的尺度。 離散化的方法包括幾下幾種。 （1）等距分割； （2）聚類分割； （3）直方圖分割； （4）基于熵的分割； （5）基于自然屬性的分割。 抽樣 用數(shù)據(jù)的小得多的隨機樣本（子集）不是大型數(shù)據(jù)集。 抽樣方法 s個樣本無放回簡單隨機抽樣 s個樣本有放回簡單隨機抽樣 聚類抽樣 分層抽樣 分類 分類 分類是指將數(shù)據(jù)映射到預先定義好的群組或類。 在分析測試數(shù)據(jù)之前，類別就已經(jīng)被確定了，所以分類統(tǒng)稱被稱作有指導的學習。 分類算法要求基于數(shù)據(jù)屬性來定義類別。 分類算法通常通過觀察已知所屬類別的數(shù)據(jù)的特征來描述類別。 分類應用 分類具有廣泛的應用，例如醫(yī)療診斷、信用卡系統(tǒng)的信用分級、圖像模式識別等。 為了識別乘客是否是潛在的恐怖分子或罪犯，機場安全攝像站需要對乘客的臉部進行掃描并辨識臉部的基本模式（例如雙眼間距、嘴的大小及形狀、頭的形狀）， 然后將得到的模式與數(shù)據(jù)庫中的已知恐怖分子或罪犯的模式進行逐個比較，看看是否與其中的某一模式相匹配。 分類步驟 1．建立一個模型，描述預定的數(shù)據(jù)類集或概念集 數(shù)據(jù)元組也稱作樣本、實例或?qū)ο蟆?為建立模型而被分析的數(shù)據(jù)元組形成訓練數(shù)據(jù)集。 訓練數(shù)據(jù)集中的單個元組稱作訓練樣本，假定每個元組屬于一個預定義的類，由一個稱作類標號。 通過分析訓練數(shù)據(jù)集來構(gòu)造分類模型，可用分類規(guī)則、決策樹或數(shù)學公式等形式提供。 2. 使用模型進行分類 首先評估模型（分類法）的預測準確率。 將已知的類標號與該樣本的學習模型類預測比較 準確率等于測試集的樣本中被模型正確分類的百分比 測試集應該與訓練集的內(nèi)容相互獨立，否則會出現(xiàn)過分適應的情況 如果認為模型的準確率可以接受，就可以用它對類標號未知的數(shù)據(jù)元組或?qū)ο筮M行分類。 （1）模型的構(gòu)建 （2）利用模型分類 分類方法評價 預測的準確率 這涉及模型正確地預測新的或先前未見過的數(shù)據(jù)的類標號的能力 速度 構(gòu)造模型的速度 利用模型進行分類的速度 強壯性 給定噪聲數(shù)據(jù)或具有空缺值的數(shù)據(jù)，模型正確預測的能力 可伸縮性 當給定大量數(shù)據(jù)時，有效地構(gòu)造模型的能力 可解釋性 涉及學習模型提供的理解和洞察的層次 分類器性能評價方式 準確率和召回率 - 混淆矩陣等 給定一個類Cj和一個數(shù)據(jù)庫元組ti，ti可能被分類器判定為屬于Cj或不屬于Cj，其實ti本身可能屬于Cj或不屬于Cj，這樣就會產(chǎn)生如下一些情況： 真正: 判定ti在Cj中，實際上的確在其中。 假正: 判定ti在Cj中，實際上不在其中。 真負: 判定ti不在Cj中，實際上不在其中。 假負: 判定ti不在Cj中，實際上的確在其中。 準確率:P=A/(A+B) 召回率:R=A/(A+C) 評估分類方法的準確性 保持方法 給定數(shù)據(jù)隨機劃分為兩個集合：訓練集(2/3)和測試集(1/3) 訓練集導出分類法，測試集對其準確性進行評估 k-折交叉驗證 初始數(shù)據(jù)被劃分為k個不相交的，大小大致相同的子集S1，S2…Sk 進行k次訓練和測試，第i次時，以Si做測試集，其他做訓練集 準確率為k次迭代正確分類數(shù)除以初始數(shù)據(jù)集樣本總數(shù) 分類方法 基于距離的分類方法 與一個類中的成員和另一個類中的成員之間的相似性相比，被映射到同一個類中的成員彼此之間被認為是更加相似的。 相似性（距離）度量可以用來識別數(shù)據(jù)庫中不同成員之間的“相似程度”。 基于距離的分類方法的直觀解釋 距離計算方法 閔可夫斯基距離: 當p=2時，為歐幾里得距離 當p=1時，為曼哈頓距離 當p->∞時，為切比雪夫距離 向量內(nèi)積： 夾角余弦： Jaccard： 還有信息熵、相關(guān)系數(shù)等其他的度量方法 基于距離的分類方法的一般性描述 算法 基于距離的分類算法 輸入：每個類的中心C1，…，Cm；待分類的元組t。 輸出：輸出類別c。 （1）dist=∞；//距離初始化 （2）FOR i:=1 to m DO （3） IF dis(ci，t)P(Cj|X)，j≠i。即最大化P(Ci|X) P(Ci|X)最大的類Ci稱為最大后驗假定。 樸素貝葉斯分類 (3) 由于P(X)對于所有類為常數(shù)，P(X|Ci)*P(Ci)最大即可。 如果Ci類的先驗概率未知，則通常假定這些類是等概率的，即P(C1)=P(C2)=…=P(Cm)，因此問題就轉(zhuǎn)換為對P(X|Ci)的最大化（P(X|Ci)常被稱為給定Ci時數(shù)據(jù)X的似然度，而使P(X|Ci)最大的假設Ci稱為最大似然假設）。否則，需要最大化P(X|Ci)*P(Ci)。 類的先驗概率可以用P(Ci)=si/s計算，其中si是類Ci中的訓練樣本數(shù)，而s是訓練樣本總數(shù)。 樸素貝葉斯分類 （4）給定具有許多屬性的數(shù)據(jù)集，計算P(X|Ci)的開銷可能非常大。為降低計算P(X|Ci)的開銷，可以做類條件獨立的樸素假定。給定樣本的類標號，假定屬性值相互條件獨立，即在屬性間，不存在依賴關(guān)系。這樣 如果Ak是離散屬性，則P(xk|Ci)=sik/si，其中sik是在屬性Ak上具有值xk的類Ci的訓練樣本數(shù)，si是Ci中的訓練樣本數(shù)。 如果Ak是連續(xù)值屬性，常用的處理方法有兩種：一是對其離散化，然后按照離散值處理；另一種假定這一屬性服從某一分布，通常假定該屬性服從高斯分布。 (5)對未知樣本X分類，也就是對每個類Ci，計算P(X|Ci)*P(Ci)。樣本X被指派到類Ci，當且僅當P(Ci|X)> P(Cj|X)，1≤j≤m，j≠i。 即X被指派到其P(X|Ci)*P(Ci)最大的類。 樸素貝葉斯分類舉例 樸素貝葉斯分類舉例 設 C1對應于類buys_computer=“yes”， C2對應于類buys_computer=“no”。 (1) 需要最大化P(X|Ci)*P(Ci)，i=1，2。每個類的先驗概率P(Ci)可以根據(jù)訓練樣本計算： P(buys_computer=”yes”)=9/14=0.643， P(buys_computer=”no”)=5/14=0.357。 樸素貝葉斯分類舉例 (2) 為計算P(X|Ci)，i=1，2，計算下面的條件概率： P(age<=30|buys_computer=“yes” )=2/9=0.222， P(age<=30”|buys_computer=“no” )=3/5=0.600， P(income=“medium”|buys_computer=“yes” )=4/9=0.444， P(income=“medium”|buys_computer=“no” )=2/5=0.400， P(student=“yes”|buys_computer=“yes” )=6/9=0.677， P(student=“yes”|buys_computer=“no” )=1/5=0.200， P(credit_rating=“fair”|buys_computer=“yes” )=6/9=0.667， P(credit_rating=“fair”|buys_computer=“no” )=2/5=0.400。 樸素貝葉斯分類舉例 (3) 假設條件獨立性，使用以上概率，得到： P(X|buys_computer=“yes” )=0.222*0.444*0.667*0.667=0.044， P(X|buys_computer=“no” )=0.600*0.400*0.200*0.400=0.019， P(X|buys_computer=“yes”)*P(buys_computer=“yes”)= 0.044*0.643=0.028， P(X|buys_computer=“no”)*P(buys_computer=“no”)= 0.019*0.357=0.007。 因此，對于樣本X，樸素貝葉斯分類預測buys_computer=“yes” 聚類 聚類：Cluster 聚類就是對大量未知標注的數(shù)據(jù)集，按數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)集劃分為多個類別 在同一個類中，對象之間具有相似性； 不同類的對象之間是相異的。 聚類分析 把一個給定的數(shù)據(jù)對象集合分成不同的簇； 聚類是一種無監(jiān)督分類法: 沒有預先指定的類別； 典型的應用 作為一個獨立的分析工具，用于了解數(shù)據(jù)的分布； 作為其它算法的一個數(shù)據(jù)預處理步驟； 聚類圖示 聚類與分類的區(qū)別 有類別標記和無類別標記; 有監(jiān)督與無監(jiān)督; （有訓練語料與無訓練語料） Train And Classification （分類）; No Train（聚類）; 聚類分析 為達到全局最優(yōu)，基于劃分的聚類會要求窮舉所有可能的劃分。聚類技術(shù)將數(shù)據(jù)元組視為對象。它將對象劃分為群或聚類，使得在一個聚類中的對象“類似”，但與其它聚類中的對象“不類似”。 絕大多數(shù)應用采用了以下兩個比較流行的基于劃分的方法，這些基于劃分的聚類方法對在中小規(guī)模的數(shù)據(jù)庫中發(fā)現(xiàn)球狀簇很適用。 （1）k-means算法，在該算法中，每個簇用該簇中對象的平均值來表示。 （2）k-medoids算法，在該算法中，每個簇用接近聚類中心的一個對象來表示。 K-means 初始參數(shù)-類別數(shù)&初始類別中心; 聚類有效性函數(shù)-最小誤差; 優(yōu)點： 聚類時間快; 缺點： 對初始參數(shù)敏感; 容易陷入局部最優(yōu); K-means步驟 1 設置初始類別中心和類別數(shù); 2 根據(jù)類別中心對數(shù)據(jù)進行類別劃分; 3 重新計算當前類別劃分下每類的中心; 4 在得到類別中心下繼續(xù)進行類別劃分; 5 如果連續(xù)兩次的類別劃分結(jié)果不變則停止算法;否則循環(huán)2～5 ; O（kndt） 初始值敏感 K-mediods步驟 1 任意選取K個對象作為medoids; 2 將余下的對象分到各個類中去（根據(jù)與medoid最相近的原則）; 3 對于每個類（Oi）中，順序選取一個Or，計算用Or代替Oi后的消耗—E（Or）。選擇E最小的那個Or來代替Oi。 4 重復2-3直到medoids不變; O（n2dt） 聚類方法性能評價 一個好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果——簇，這些簇要具備以下兩個特點： 高的簇內(nèi)相似性 低的簇間相似性 聚類結(jié)果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實現(xiàn)； 聚類方法的好壞還取決于該方法是能發(fā)現(xiàn)某些還是所有的隱含模式； 聚類方法性能評價 可伸縮性 能夠處理不同類型的屬性 能發(fā)現(xiàn)任意形狀的簇 在決定輸入?yún)��?shù)的時候，盡量不需要特定的領(lǐng)域知識； 能夠處理噪聲和異常 對輸入數(shù)據(jù)對象的順序不敏感 能處理高維數(shù)據(jù) 能產(chǎn)生一個好的、能滿足用戶指定約束的聚類結(jié)果 結(jié)果是可解釋的、可理解的和可用的 聚類評價 準備率：找到正確的結(jié)果數(shù)/找到結(jié)果數(shù) 召回率：找到正確的結(jié)果數(shù)/正確結(jié)果數(shù) 常用的相似性度量方法 相似性度量方法 聚類分析（續(xù)） 基于層次的方法：層次的方法對給定數(shù)據(jù)集合進行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以被分為凝聚或分裂方法。 （Chameleon ，CURE，BIRCH） 基于密度的方法：只要臨近區(qū)域的密度超過某個閾值，就繼續(xù)聚類。避免僅生成球狀聚類。（DBSCAN，OPTICS，DENCLUE） 基于網(wǎng)格的方法：基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，所有的聚類操作都在這個量化的空間上進行。這種方法的主要優(yōu)點是它的處理速度很快。（STING，CLIQUE，WaveCluster） 基于模型的方法：為每個簇假設一個模型，發(fā)現(xiàn)數(shù)據(jù)對模型的最好匹配。（COBWEB，CLASSIT，AutoClass） DBSCAN 基于密度的簇是密度相連的點的集合 主要思想 尋找被低密度區(qū)域分離的高密度區(qū)域 只要臨近區(qū)域的密度（單位大小上對象或數(shù)據(jù)點的數(shù)目）超過某個閾值，就繼續(xù)聚類 DBSCAN 兩個參數(shù)： Eps: 鄰域的最大半徑 MinPts: 一個核心對象以 Eps為半徑的鄰域內(nèi)的最小頂點數(shù) DBSCAN 密度 = 制定半徑 (Eps)內(nèi)點的個數(shù) 如果一個對象的 Eps 鄰域至少包含最小數(shù)目MinPts 個對象，則稱該對象為核心對象（Core point） 如果一個對象是非核心對象， 但它的鄰域中有核心對象，則稱該對象為邊界點（ Border point ） 除核心對象和邊界點之外的點是噪聲點（ Noise point ） DBSCAN DBSCAN 密度可達的（Density-reachable） 對于對象p和核心對象q(關(guān)于E和MinPts)，我們稱p是從q(關(guān)于E和MinPts)直接密度可達，若對象p在對象q的E鄰域內(nèi)。 如果存在一個對象鏈 p1， …， pn， p1 = q， pn = p ，pi+1 是從pi關(guān)于Eps和MinPts 直接密度可達的，則對象p是從對象q關(guān)于Eps和MinPts 密度可達的。 密度可達性是直接密度可達性的傳遞閉包，這種關(guān)系是非對稱的。 只有核心對象之間是相互可達的。 DBSCAN 密度相連的（Density-connected） 如果對象集合D中存在一個對象o，使得對象p和q是從o關(guān)于Eps 和 MinPts密度可達的，那么對象p和q是關(guān)于Eps 和 MinPts 密度相連的。 密度相連性是一個對稱的關(guān)系。 DBSCAN DBSCAN算法描述： 輸入：包含n個對象的數(shù)據(jù)庫，半徑ε，最少數(shù)目MinPts。 輸出：所有生成的簇，達到密度要求。 1. REPEAT 2. 從數(shù)據(jù)庫中抽取一個未處理過的點； 3. IF 抽出的點是核心點 THEN找出所有從該點密度可達的對象，形成一個簇 4. ELSE 抽出的點是邊緣點(非核心對象)，跳出本次循環(huán)，尋找下一點； 5. UNTIL 所有點都被處理； 基于密度方法的聚類- DBSCAN 下面給出一個樣本事務數(shù)據(jù)庫（見下表），對它實施DBSCAN算法。 根據(jù)所給的數(shù)據(jù)通過對其進行DBSCAN算法，以下為算法的步驟（設n=12，用戶輸入ε=1，MinPts=4） DBSCAN聚類過程 第1步，在數(shù)據(jù)庫中選擇一點1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點（小于4），因此它不是核心點，選擇下一個點。 第2步，在數(shù)據(jù)庫中選擇一點2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點，因此它不是核心點，選擇下一個點。 第3步，在數(shù)據(jù)庫中選擇一點3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點。 DBSCAN聚類過程 第4步，在數(shù)據(jù)庫中選擇一點4，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，尋找從它出發(fā)可達的點（直接可達4個，間接可達3個），聚出的新類{1，3，4，5，9，10，12}，選擇下一個點。 DBSCAN聚類過程 第5步，在數(shù)據(jù)庫中選擇一點5，已經(jīng)在簇1中，選擇下一個點。 第6步，在數(shù)據(jù)庫中選擇一點6，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點。 DBSCAN聚類過程 第7步，在數(shù)據(jù)庫中選擇一點7，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，尋找從它出發(fā)可達的點，聚出的新類{2，6，7，8，11}，選擇下一個點。 DBSCAN聚類過程 第8步，在數(shù)據(jù)庫中選擇一點8，已經(jīng)在簇2中，選擇下一個點。 第9步，在數(shù)據(jù)庫中選擇一點9，已經(jīng)在簇1中，選擇下一個點。 第10步，在數(shù)據(jù)庫中選擇一點10，已經(jīng)在簇1中，選擇下一個點。 第11步，在數(shù)據(jù)庫中選擇一點11，已經(jīng)在簇2中，選擇下一個點。 第12步，選擇12點，已經(jīng)在簇1中，由于這已經(jīng)是最后一點所有點都以處理，程序終止。 基于密度方法的聚類- DBSCAN DBSCAN 關(guān)聯(lián)規(guī)則 關(guān)聯(lián)規(guī)則：Association Rule 關(guān)聯(lián)規(guī)則挖掘： 在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或?qū)ο蠹�合之間的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。 應用： 購物籃分析、交叉銷售、產(chǎn)品目錄設計等。 舉例： 規(guī)則形式:“Body => Head [support， confidence]” buys(x， “diapers”) => buys(x， “beers”) [0.5%， 60%] major(x， “CS”) ^ takes(x， “DB”) => grade(x， “A”) [1%， 75%] 規(guī)則度量：支持度與可信度 查找所有的規(guī)則 X & Y => Z 具有最小支持度和可信度 支持度， s， 一次交易中包含{X 、 Y 、 Z}的可能性 可信度， c， 包含{X 、 Y}的交易中也包含Z的條件概率 關(guān)聯(lián)規(guī)則挖掘問題就是根據(jù)用戶指定的最小支持度和最小可信度來尋找強關(guān)聯(lián)規(guī)則。 關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個子問題： 1.發(fā)現(xiàn)頻繁項目集:通過用戶給定最小支持度，尋找所有頻繁項目集或者最大頻繁項目集。 2.生成關(guān)聯(lián)規(guī)則:通過用戶給定最小可信度，在頻繁項目集中，尋找關(guān)聯(lián)規(guī)則。 第1個子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的重點。 經(jīng)典的發(fā)現(xiàn)頻繁項目集算法 Apriori算法是通過項目集元素數(shù)目不斷增長來完成頻繁項目集發(fā)現(xiàn)的。首先產(chǎn)生1_頻繁項目集L1，然后產(chǎn)生2_頻繁項目集L2，直到不能再擴展頻繁項目集的元素數(shù)目為止。 Apriori算法例子 根據(jù)上面介紹的關(guān)聯(lián)規(guī)則挖掘的兩個步驟，在得到了所有頻繁項目集后，可以按照下面的步驟生成關(guān)聯(lián)規(guī)則： 對于每一個頻繁項目集 l ，生成其所有的非空子集； 對于l 的每一個非空子集x，計算Conference（x），如果Confidence（x）≥minconfidence，那么“ x(l-x) ”成立。 關(guān)聯(lián)規(guī)則生成算法: 從給定的頻繁項目集中生成強關(guān)聯(lián)規(guī)則 該算法的核心是genrules遞歸過程，它實現(xiàn)一個頻繁項目集中所有強關(guān)聯(lián)規(guī)則的生成。 Rule-generate算法例子 Minconfidence=80% 算法問題 Apriori作為經(jīng)典的頻繁項目集生成算法，在數(shù)據(jù)挖掘中具有里程碑的作用。 Apriori算法有兩個致命的性能瓶頸: 1．多次掃描事務數(shù)據(jù)庫，需要很大的I/O負載 對每次k循環(huán)，侯選集Ck中的每個元素都必須通過掃描數(shù)據(jù)庫一次來驗證其是否加入Lk。假如有一個頻繁大項目集包含10個項的話，那么就至少需要掃描事務數(shù)據(jù)庫10遍。 2．可能產(chǎn)生龐大的侯選集 由Lk-1產(chǎn)生k-侯選集Ck是指數(shù)增長的，例如104個1-頻繁項目集就有可能產(chǎn)生接近107個元素的2-侯選集。如此大的侯選集對時間和主存空間都是一種挑戰(zhàn)。 FP-tree算法的基本原理 2000年Han等提出了一個稱為FP-Tree（頻繁模式樹）的算法，該算法只進行 2 次數(shù)據(jù)庫掃描，不使用侯選集，直接壓縮數(shù)據(jù)庫成一個FP-Tree ，然后通過該樹生成關(guān)聯(lián)規(guī)則。構(gòu)造FP-Tree的過程如下 ： 按Apriori算法，掃描數(shù)據(jù)庫一次生成1-頻繁項目集，并按頻度降序排序，放入L列表中； 創(chuàng)建根結(jié)點，標志為null，掃描數(shù)據(jù)庫一次，當?shù)玫綌?shù)據(jù)庫的一個項目（元組）時，就把其中的元素按L表中的次序排列，然后通過遞歸實現(xiàn)FP-Tree的增長； FP-tree算法的基本原理 FP-tree算法的基本原理 FP-tree算法的基本原理 序列模式概念 序列模式的概念最早是由Agrawal和Srikant 提出的 序列模式定義： 給定一個由不同序列組成的集合，其中，每個序列由不同的元素按順序有序排列，每個元素由不同項目組成，同時給定一個用戶指定的最小支持度閾值 序列模式挖掘就是找出所有的頻繁子序列，即該子序列在序列集中的出現(xiàn)頻率不低于用戶指定的最小支持度閾值 序列模式表示 例子：設序列數(shù)據(jù)庫如下圖所示，并設用戶指定的最小支持度min-support = 2。 序列模式挖掘 問題描述：給定序列數(shù)據(jù)庫和最小支持度閾值，序列模式挖掘就是要找出序列數(shù)據(jù)庫中所有的序列模式 系統(tǒng)規(guī)定：由于同一個元素中的項目之間排列沒有順序，為了表達的唯一性，我們將同一個元素內(nèi)部的不同項目按照字典順序排列 序列模式挖掘算法 序列模式挖掘的主要算法 GSP(Generalized Sequential Patterns)算法：類似于Apriori算法 PrefixSpan(Prefix-project Sequential Pattern mining)算法：采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個更小的投影數(shù)據(jù)庫，然后在各個投影數(shù)據(jù)庫上進行序列模式挖掘 預測：Prediction 預測是構(gòu)造和使用模型評估無樣本類，或評估給定樣本可能具有的屬性或值空間。 預測和分類的異同 相同點 兩者都需要構(gòu)建模型 都用模型來估計未知值 預測當中主要的估計方法是回歸分析 線性回歸和多元回歸 非線性回歸 不同點 分類法主要是用來預測類標號（分類屬性值） 預測法主要是用來估計連續(xù)值（量化屬性值） 分類vs.預測 分類： 預測分類標號（或離散值） 根據(jù)訓練數(shù)據(jù)集和類標號屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù) 預測： 建立連續(xù)函數(shù)值模型，比如預測空缺值 典型應用 信譽證實 目標市場 醫(yī)療診斷 性能預測 回歸方法（Regression） 線性回歸：Y = α+ βX 其中a和b是回歸系數(shù)，可以根據(jù)給定的數(shù)據(jù)點，通過最小二乘法來求得 多元回歸：Y = α+ α1X1 + α2 X2 線性回歸的擴展，設計多個預測變量，可以用最小二乘法求得上式中的α，α1 和α2 非線性回歸：Y = α + α1X1 + α2 X22+ α3 X33 對不呈線性依賴的數(shù)據(jù)建模 使用多項式回歸建模方法，然后進行變量變換，將非線性模型轉(zhuǎn)換為線性模型，然后用最小二乘法求解 謝謝！ 大型數(shù)據(jù)庫中描述統(tǒng)計計量 對于數(shù)據(jù)挖掘任務，用戶經(jīng)常關(guān)心的數(shù)據(jù)特征包括數(shù)據(jù)的中心趨勢和離散特征 中心趨勢的度量包括：mean， median， mode 和 midrange 數(shù)據(jù)離散度量包括：quartiles， outliers， variance 和其他度量 關(guān)系數(shù)據(jù)庫中，系統(tǒng)提供了以下聚集函數(shù)：count()， sum()， avg()， max()， min() 在大型數(shù)據(jù)庫中挖掘用戶感興趣的描述統(tǒng)計計量涉及到如何利用關(guān)系數(shù)據(jù)庫現(xiàn)有的函數(shù)來計算上述兩類用戶感興趣的度量值 度量中心趨勢 算術(shù)平均值 加權(quán)算術(shù)平均: 中位值：使用一個近似的計算來度量 如果值的個數(shù)n是奇數(shù)，則中位數(shù)(median)是有序集合的中間值，否則它是中間兩個數(shù)的平均值 用插值法(interpolation)來近似計算 模(mode) 表示數(shù)據(jù)集中出現(xiàn)頻率最高的值 單模態(tài)、雙模態(tài)、三模態(tài)、多模態(tài)和沒有模的情況 單模態(tài)近似值計算的經(jīng)驗公式: 中列數(shù)：最大值和最小值的平均 度量數(shù)據(jù)的離散度 最常用度量：五數(shù)概括（基于四分位數(shù)）、中間四分位數(shù)區(qū)間和標準差 四分位數(shù)、孤立點和盒圖 百分位數(shù)(percentile)：第k個百分位數(shù)是具有如下性質(zhì)的值x：數(shù)據(jù)項的k%在x上或低于x 四分位數(shù)：Q1 (25th percentile)， Q3 (75th percentile) 中間四分位數(shù)區(qū)間(IQR)： IQR = Q3 – Q1 對傾斜分布的描述，除了IQR還常需兩個四分位數(shù)Q1和Q3，以及中位數(shù)M，一個識別孤立點的常用規(guī)則是：挑出落在至少高于第三個四分位數(shù)或低于第一個四分位數(shù) 1.5×IQR處的值 度量數(shù)據(jù)的離散度 五數(shù)概括: min， Q1， M， Q3， max 盒圖：數(shù)據(jù)分布的一種直觀表示。 方差和標準差 方差s2：n個觀測之x1，x2...xn的方差是 標準差s是方差s2的平方根 s是關(guān)于平均值的離散的度量，因此僅當選平均值做中心度量時使用 所有觀測值相同則 s＝0，否則 s>0 方差和標準差都是代數(shù)度量 盒圖-示例 在盒圖中： 端點在四分位數(shù)上，使得盒圖的長度是IQR 中位數(shù)M用盒內(nèi)的線標記 胡須延伸到最大最小觀測值 該盒圖為在給定時間段在AllElectronics的4個分店銷售的商品單價的盒圖 分店1 中位數(shù)$80 Q1: $60 Q3: $100 基本統(tǒng)計類描述的圖像顯示-直方圖 常用的顯示數(shù)據(jù)匯總和分布的方法： 直方圖、分位數(shù)圖、q-q圖、散布圖和局部回歸曲線 直方圖 一種單變量圖形方法 由一組矩形組成，這些矩形反映類在給定數(shù)據(jù)中出現(xiàn)的技術(shù)或頻率 vxV紅軟基地

大數(shù)據(jù)與精準醫(yī)療ppt：這是大數(shù)據(jù)與精準醫(yī)療ppt，包括了中國居民營養(yǎng)與慢性疾病狀況報告，醫(yī)療大數(shù)據(jù)提升醫(yī)療服務效率，大數(shù)據(jù)在治療中的優(yōu)點等內(nèi)容，歡迎點擊下載。

大數(shù)據(jù)數(shù)據(jù)挖掘ppt：這是大數(shù)據(jù)數(shù)據(jù)挖掘ppt，包括了大數(shù)據(jù)平臺生態(tài)系統(tǒng)，應用與研究，軟件著作權(quán)，大數(shù)據(jù)是什么？數(shù)據(jù)挖掘是什么，解決方案-比賽任務等內(nèi)容，歡迎點擊下載。

大數(shù)據(jù)開放日ppt：這是大數(shù)據(jù)開放日ppt，包括了你會認嗎？你會讀嗎？你會記嗎？你能有節(jié)奏地讀課文嗎？你能快樂地朗誦嗎等內(nèi)容，歡迎點擊下載。