【正文】 類規(guī)則。 ? 商業(yè)算法通常以 10作為默認(rèn)值。 輸出： 輸出類別 c。給定一個(gè)樣本， k最臨近分類法搜索模式空間，找出最接近未知樣本的 k個(gè)訓(xùn)練樣本。每個(gè)樣本代表 n維空間的一個(gè)點(diǎn)。 K近鄰算法（ KNN） ? K Nearest neighbor(KNN) ?通過計(jì)算每個(gè)訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離 最近的 K個(gè)訓(xùn)練數(shù)據(jù) ， K個(gè)數(shù)據(jù)中哪個(gè)類別的訓(xùn)練數(shù)據(jù)占 多數(shù) ，則待分類元組就屬于哪個(gè)類別。 ? 輸出：輸出類別 c。 B || A 200。 = x i y ii229。) 1 / pI nne r ( x , y ) = 225。 ?相似性（距離）度量可以用來識別數(shù)據(jù)庫中不同成員之間的 “ 相似程度 ” 。 – 假負(fù) : 判定 ti不在 Cj中，實(shí)際上的確在其中。 – 假正 : 判定 ti在 Cj中，實(shí)際上不在其中。 ? 將已知的類標(biāo)號與該樣本的學(xué)習(xí)模型類預(yù)測比較 ? 準(zhǔn)確率 等于測試集的樣本中被模型正確分類的百分比 ? 測試集應(yīng)該與訓(xùn)練集的內(nèi)容相互獨(dú)立 ，否則會出現(xiàn)過分適應(yīng)的情況 ? 如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它對類標(biāo)號未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類。 ? 通過分析訓(xùn)練數(shù)據(jù)集來構(gòu)造 分類模型 ，可用分類規(guī)則、決策樹或數(shù)學(xué)公式等形式提供。 ? 為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集。 ?為了識別乘客是否是潛在的恐怖分子或罪犯，機(jī)場安全攝像站需要對乘客的臉部進(jìn)行掃描并辨識臉部的基本模式（例如雙眼間距、嘴的大小及形狀、頭的形狀）， ?然后將得到的模式與數(shù)據(jù)庫中的已知恐怖分子或罪犯的 模式 進(jìn)行逐個(gè)比較，看看是否與其中的某一模式相匹配。 ?分類算法通常通過觀察已知所屬類別的數(shù)據(jù)的特征來描述類別。 ?在分析測試數(shù)據(jù)之前，類別就已經(jīng)被確定了，所以分類統(tǒng)稱被稱作 有指導(dǎo)的學(xué)習(xí) 。 抽樣 ?用數(shù)據(jù)的小得多的隨機(jī)樣本（子集）不是大型數(shù)據(jù)集。 ?離散化的方法包括幾下幾種。 ?可以分為參數(shù)方法和非參數(shù)方法。 ?主成分分析（ PCA）：有損，能更好地處理稀疏數(shù)據(jù)。 ?主要方法： ?串壓縮：無損，但只允許有限的數(shù)據(jù)操作。 ?逐步向前選擇 ?逐步向后刪除 ?向前選擇和向后刪除的結(jié)合 ?決策樹歸納 維度規(guī)約 ?維度歸約使用數(shù)據(jù)編碼或變換，以便得到原數(shù)據(jù)的歸約或“壓縮”表示。通常采用壓縮搜索空間的啟發(fā)式算法。 ?其目標(biāo)是找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性得到的原分布。 ?如：立方體內(nèi)存儲季度銷售額，若對年銷售額感興趣，可對數(shù)據(jù)執(zhí)行聚集操作，例如 sum()等。 數(shù)據(jù)規(guī)約 數(shù)據(jù)歸約策略： （ 1）數(shù)據(jù)立方體聚集：對數(shù)據(jù)立方體做聚集操作 （ 2）屬性子集選擇：檢測并刪除不相關(guān)、弱相關(guān)或冗余的屬性和維。 ?數(shù)據(jù)歸約技術(shù)可以用來得到數(shù)據(jù)集的 歸約表示 ，它小得多，但仍接近保持原數(shù)據(jù)的完整性。vev ??? 1139。最小 最大、 ZScore、按小數(shù)定標(biāo)規(guī)范化。 ?數(shù)據(jù)泛化（概化）：使用概念分層，用高層概念替換低層或“原始”數(shù)據(jù)。技術(shù)包括分箱、回歸、聚類。 ?人工再審查這些孤立點(diǎn) Regression ?通過構(gòu)造函數(shù)來符合數(shù)據(jù)變化的趨勢，這樣可以用一個(gè)變量預(yù)測另一個(gè)變量。 ?人工填寫空缺值：工作量大，可行性低 ?使用一個(gè)全局變量填充空缺值：比如使用 unknown或 ∞ ?使用屬性的平均值填充空缺值 ?使用與給定元組屬同一類的所有樣本的平均值 ?使用最可能的值填充空缺值：使用像 Bayesian公式或判定樹這樣的基于推斷的方法 噪聲數(shù)據(jù) ?噪聲：一個(gè)測量變量中的隨機(jī)錯誤或偏差 ?引起不正確屬性值的原因 ?數(shù)據(jù)收集工具的問題 ?數(shù)據(jù)輸入錯誤 ?數(shù)據(jù)傳輸錯誤 ?技術(shù)限制 ?命名規(guī)則的不一致 ?其它需要數(shù)據(jù)清理的數(shù)據(jù)問題 ?重復(fù)記錄 ?不完整的數(shù)據(jù) ?不一致的數(shù)據(jù) 如何處理噪聲數(shù)據(jù) ?分箱 : ?first sort data and partition into (equidepth) 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 (., deal with possible outliers) ?回歸 ?smooth by fitting the data into regression functions 分箱 (Binning) ?等寬 Equalwidth (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. ?等深 Equaldepth (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 ?每個(gè)簇中的數(shù)據(jù)用其中心值代替 ?忽略孤立點(diǎn) ?先通過聚類等方法找出孤立點(diǎn)。 ? 分析客戶使用分銷渠道的情況和分銷渠道的容量 ；建立利潤評測模型；客戶關(guān)系優(yōu)化；風(fēng)險(xiǎn)控制等 ? 電子商務(wù) ? 網(wǎng)上商品推薦；個(gè)性化網(wǎng)頁；自適應(yīng)網(wǎng)站 … ? 生物制藥、基因研究 ? DNA序列查詢和匹配； 識別基因序列的共發(fā)生性 … ? 電信 ? 欺詐甄別；客戶流失 … ? 保險(xiǎn)、零售 數(shù)據(jù)挖掘應(yīng)用 Debt10% of Ine Debt=0% Good Credit Risks Bad Credit Risks Good Credit Risks Yes Yes Yes NO NO NO Ine$40K Q Q Q Q I I 1 2 3 4 5 6 factor 1 factor 2 factor n 神經(jīng)網(wǎng)絡(luò) Neural Networks 聚類分析 Clustering Open Ac’ t Add New Product Decrease Usage ??? Time 序列分析 Sequence Analysis 決策樹 Decision Trees ? 傾向性分析 ? 客戶保留 ? 客戶生命周期管理 ? 目標(biāo)市場 ? 價(jià)格彈性分析 ? 客戶細(xì)分 ? 市場細(xì)分 ? 傾向性分析 ? 客戶保留 ? 目標(biāo)市場 ? 欺詐檢測 關(guān)聯(lián)分析 Association ? 市場組合分析 ? 套裝產(chǎn)品分析 ? 目錄設(shè)計(jì) ? 交叉銷售 數(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ì)量評估（識別提供知識的真正有趣模式） ?知識表示（可視化和知識表示技術(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ù)，識別、刪除孤立點(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ù)，對數(shù)字型數(shù)據(jù)特別重要 數(shù)據(jù)清洗 ?臟數(shù)據(jù)：例如設(shè)備錯誤，人或者機(jī)器錯誤，傳輸錯誤等 ?不完整性：屬性值缺失或者只有聚集數(shù)據(jù) ?例如： phone=“”。大數(shù)據(jù)分析 和內(nèi)存計(jì)算 第 4講 數(shù)據(jù)挖掘技術(shù)概述 李國良 清華大學(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ù)挖掘的動機(jī) ?How? ?哪些數(shù)據(jù)可以用來挖掘？ ?數(shù)據(jù)挖掘的 主要內(nèi)容 數(shù)據(jù)挖掘定義 ?什么是數(shù)據(jù)挖掘（ Data Mining） ？ ? Extraction of interesting (nontrivial, 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, decisionsupport system, knowledge extraction, data archeology, data dredging and information harvesting etc. Da tap re p ro c e s s i ngDa tam i ni ngpos t p ro c e s s i ng know l e dgera w da t aF e a t u re s e l e c t i onD i m e ns i o n re duc t i onN o rm a l i z a t i onD a t a s ubs e t t i ngF i l t e ri n g p a t t e rn sV i s ua ra l i z a t i onP a t t e rn i nt e rp re t a t i onD ata M i n i n g P r oc e s s模式有效性度量 ?Simplicity ?., (association) rule length, (decision) tree size ?Certainty ?., confidence, P(A|B) = (A and B)/ (B), classification reliability or accuracy, rule strength, etc. ?Utility ?Potential usefulness, ., support (association), noise threshold (description) ?Novelty ?Not previously known, surprising (used to remove redundant rules)