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

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

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

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

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

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