KDD 是一個以知識使用者為中心，人機交互的探索過程嘉熊，包括了在指定的數(shù)據(jù)庫中用數(shù)據(jù)挖掘算法提取模型，以及圍繞數(shù)據(jù)挖掘所進行的預處理和結(jié)果表達等一系列的步驟。

數(shù)據(jù)挖掘作為KDD的一個步驟垄开。盡管數(shù)據(jù)挖掘是整個過程的中心，但它通常只占KDD 過程15%~25%的工作量税肪。

KDD步驟：

ps：雖然數(shù)據(jù)挖掘作為KDD的一部分溉躲，但出國簽證時KDD職業(yè)通過率遠比數(shù)據(jù)挖掘職業(yè)的通過率高。

數(shù)據(jù)挖掘的特點：

第一益兄，數(shù)據(jù)挖掘的數(shù)據(jù)源必須是真實的锻梳。

數(shù)據(jù)挖掘所處理的數(shù)據(jù)通常是已經(jīng)存在的真實數(shù)據(jù)（如超市業(yè)務數(shù)據(jù)），而不是為了進行數(shù)據(jù)分析而專門收集的數(shù)據(jù)净捅。因此疑枯，數(shù)據(jù)收集本身不屬于數(shù)據(jù)挖掘所關(guān)注的焦點，這是數(shù)據(jù)挖掘區(qū)別于大多數(shù)統(tǒng)計任務的特征之一蛔六。

第二荆永，數(shù)據(jù)挖掘所處理的數(shù)據(jù)必須是海量的。

如果數(shù)據(jù)集很小的話国章，采用單純的統(tǒng)計分析方法就可以了具钥。但是，當數(shù)據(jù)集很大時液兽，會面臨許多新的問題骂删，諸如，數(shù)據(jù)的有效存儲抵碟、快速訪問桃漾、合理表示等。

第三拟逮，查詢一般是決策制定者（用戶）提出的隨機查詢撬统。

查詢要求靈活，往往不能形成精確的查詢要求敦迄，要靠數(shù)據(jù)挖掘技術(shù)來尋找可能的查詢結(jié)果恋追。

第四凭迹，挖掘出來的知識一般是不能預知的，數(shù)據(jù)挖掘發(fā)現(xiàn)的是潛在的苦囱、新穎的知識嗅绸。

這些知識在特定環(huán)境下是可以接受、可以理解撕彤、可以運用的鱼鸠，但不是放之四海皆準的。

數(shù)據(jù)挖掘基本概括為：Techniques（技術(shù)）?Applications（應用）Principles（原理）

數(shù)據(jù)挖掘的分類 ：

（1）根據(jù)挖掘的數(shù)據(jù)庫類型分類

數(shù)據(jù)庫系統(tǒng)本身可以根據(jù)不同的標準分類羹铅，例如,按照數(shù)據(jù)模型或處理的數(shù)據(jù)所涉及的應用類型分類蚀狰。每一類可能需要不同的數(shù)據(jù)挖掘技術(shù)。例如职员，根據(jù)數(shù)據(jù)模型分類麻蹋，可以有關(guān)系的、面向?qū)ο蟮暮盖小ο?關(guān)系的扮授、或數(shù)據(jù)倉庫的數(shù)據(jù)挖掘。

如果根據(jù)所處理的數(shù)據(jù)的特定類型分類专肪，有空間的刹勃、時間序列的、文本的牵祟、多媒體深夯、或Web數(shù)據(jù)等數(shù)據(jù)挖掘抖格。

（2）根據(jù)挖掘的知識類型分類

例如特征分析诺苹、關(guān)聯(lián)分析、分類分析雹拄、聚類分析收奔、異常點分析、趨勢和演化分析滓玖、偏差分析坪哄、類似性分析等。

此外势篡，數(shù)據(jù)挖掘也可以根據(jù)所挖掘的知識的粒度或抽象級別進行區(qū)分翩肌，包括泛化知識（在高抽象層），原始層知識（在原始數(shù)據(jù)層）禁悠，或多層知識（考慮若干抽象層）念祭。

（3）根據(jù)所用的技術(shù)分類

這些技術(shù)可以根據(jù)用戶交互程度（例如，自動系統(tǒng)碍侦、交互探查系統(tǒng)粱坤、查詢驅(qū)動系統(tǒng)）

或所用的數(shù)據(jù)分析方法（例如隶糕，面向數(shù)據(jù)庫或數(shù)據(jù)倉庫的技術(shù)、機器學習站玄、統(tǒng)計枚驻、可視化、模式識別株旷、神經(jīng)網(wǎng)絡等等）描述再登。

復雜的數(shù)據(jù)挖掘通常采用多種數(shù)據(jù)挖掘技術(shù)，或采用有效的晾剖、集成的技術(shù)霎冯，以綜合若干不同方法的優(yōu)點。

（4）根據(jù)數(shù)據(jù)挖掘的應用領域分類

例如钞瀑，可能有些數(shù)據(jù)挖掘方法特別適合財政沈撞、電訊，有些數(shù)據(jù)挖掘方法特別適合DNA雕什、股票市場等缠俺。

不同的應用有適合該應用不同的數(shù)據(jù)挖掘方法。而通用的贷岸、全面的數(shù)據(jù)挖掘可能并不適合特定領域的挖掘任務壹士。

數(shù)據(jù)挖掘的應用：生物信息學、Web搜索偿警、入侵檢測躏救、汽車自動駕駛、火星機器人螟蒸、決策助手盒使、古文獻修復等。

數(shù)據(jù)挖掘算法的組件化思想

聚類分析：聚類指事先并不知道任何樣本的類別標號七嫌，希望通過某種算法來把一組未知類別的樣本劃分成若干類別

基于劃分的算法（K-Means少办、K-Medoids、K-Modes诵原、K-Prototypes英妓、CLARA、CLARANS绍赛、focused CLARANS）基于層次蔓纠、密度、方格吗蚌、模型的算法

分類分析：根據(jù)一些給定的已知類別標號的樣本腿倚，訓練某種學習機器（即得到某種目標函數(shù)），使它能夠?qū)ξ粗悇e的樣本進行分類褪测。這屬于supervised learning（監(jiān)督學習）

決策樹算法（ID3猴誊、C4.5潦刃、EC4.5、PC4.5懈叹、CHAID乖杠、CART、Elisee澄成、SIPINA胧洒、QR-MDL等近20種）、貝葉斯算法墨状、支持向量機卫漫、人工神經(jīng)網(wǎng)絡

數(shù)據(jù)挖掘算法的組件化思想：許多著名的數(shù)據(jù)挖掘算法都是由五個“標準組件”構(gòu)成的，即：

（1）模型或模式結(jié)構(gòu)：通過數(shù)據(jù)挖掘過程所得到的知識通常被稱為模型（model）或模式(pattern)肾砂。例如:線性回歸模型列赎、層次聚類模型、頻繁序列模式镐确。

模型是對整個數(shù)據(jù)集的高層次包吝、全局性的描述或總結(jié)。例如源葫，模型可以將數(shù)據(jù)集中的每一個對象分配到某個聚類中诗越。模型是對現(xiàn)實世界的抽象描述，例如息堂，Y=aX+b就是一個簡單的模型嚷狞，其中X和Y是變量，a和c是模型的參數(shù)荣堰。

模式是局部的床未，它僅對一小部分數(shù)據(jù)做出描述。例如持隧，購買商品A和B的人也可能經(jīng)常購買C即硼，就是一個模式。模式有可能只支持幾個對象或?qū)ο蟮膸讉€屬性屡拨。

全局的模型和局部的模式是相互聯(lián)系的，就好比一個硬幣的兩個面褥实。例如呀狼，為了檢測出數(shù)據(jù)集內(nèi)的異常對象（局部模式），需要一種對數(shù)據(jù)集內(nèi)正常對象的描述（全局模型）损离。

模式（如果X>c哥艇，則Y>d的概率為p）的參數(shù)為c，d和p僻澎。

通常把參數(shù)不確定的模型叫做模型的結(jié)構(gòu)貌踏。把參數(shù)不確定的模式叫做模式的結(jié)構(gòu)十饥。（一般形式）

（2）數(shù)據(jù)挖掘任務

根據(jù)數(shù)據(jù)分析者的目標，可以將數(shù)據(jù)挖掘任務分為：1祖乳、模式挖掘：頻繁模式逗堵、異常模式…2、模型挖掘：預測建模(有監(jiān)督)：描述建模(無監(jiān)督)

模式挖掘：致力于從數(shù)據(jù)中尋找模式眷昆，比如尋找頻繁模式蜒秤，異常模式等。

頻繁模式指在某個數(shù)據(jù)集中頻繁出現(xiàn)的模式亚斋，這些模式可以是一個項集作媚、一個子序列或者一個子結(jié)構(gòu)(子圖)。例如帅刊，在交易數(shù)據(jù)集中纸泡，牛奶和面包經(jīng)常在一起出現(xiàn)，稱之為頻繁的項集赖瞒。人們經(jīng)常在購買了個人電腦之后弟灼，就會購買打印機，稱之為頻繁的子序列冒黑。在某些圖田绑、樹或格結(jié)構(gòu)中頻繁出現(xiàn)的一些子圖、子樹或子格則被稱為頻繁的子結(jié)構(gòu)

預測建模：根據(jù)現(xiàn)有數(shù)據(jù)先建立一個模型抡爹，然后應用這個模型來對未來的數(shù)據(jù)進行預測掩驱。

當被預測的變量是范疇型(category)時，稱之為分類冬竟。分類模型有時也稱作分類函數(shù)或分類器欧穴。分類的典型應用如，信用卡系統(tǒng)中的信用分級泵殴、市場調(diào)查涮帘、療效診斷、尋找店址等笑诅。因為分類的過程中调缨，用到了訓練集，進行了學習吆你，所以分類是一個有監(jiān)督的學習過程弦叶。

當被預測的變量是數(shù)量型(quantitative)時，稱之為預測（回歸）妇多∩瞬福回歸的典型應用如性能評測、概率估計等。

分類：構(gòu)造立莉、使用模型來對某個樣本的類別進行判別绢彤。主要用于對離散的數(shù)據(jù)進行預測。典型應用：信譽評估蜓耻、醫(yī)學診斷

回歸（預測）：構(gòu)造茫舶、使用模型來對某個樣本的值進行估計，例如預測某個不知道的值或者缺失值媒熊。主要用于對連續(xù)或有序的數(shù)據(jù)進行預測奇适。典型應用：性能預測

聚類：根據(jù)數(shù)據(jù)特征找出數(shù)據(jù)間的相似性，將相似的數(shù)據(jù)聚成一個類芦鳍。作為一個獨立的工具對數(shù)據(jù)分布進行分析嚷往，可以作為其他算法（如分類等）的預處理步驟，模式識別柠衅、空間數(shù)據(jù)分析皮仁、圖像處理、經(jīng)濟科學(尤其是市場研究)菲宴、WWW

描述建模：目標是描述數(shù)據(jù)的全局特征贷祈。描述建模的典型例子是聚類分析。

描述和預測的關(guān)鍵區(qū)別是：預測的目標是唯一的變量喝峦，如信用等級势誊、疾病種類等，而描述并不以單一的變量為中心谣蠢。

第一步粟耻，建立模型階段：用來構(gòu)造模型的數(shù)據(jù)集被稱為訓練集。模型一般表示為：分類規(guī)則, 決策樹或者數(shù)學公式

第二步眉踱，使用模型階段：首先測試模型的準確性挤忙，用測試集和由模型進行分類的結(jié)果進行比較，兩個結(jié)果相同所占的比率稱為準確率谈喳。測試集和訓練集必須不相關(guān)册烈。如果準確性可以接受的話, 使用模型對新數(shù)據(jù)進行分類

由于模型（模式）代表的是函數(shù)的一般形式，它的參數(shù)空間非常大婿禽，可選的參數(shù)值有很多赏僧。那么什么樣的參數(shù)值比較好呢，需要一個評價指標谈宛，這個評價指標就是評分函數(shù)次哈。

（3）評分函數(shù)

評分函數(shù)用來對數(shù)據(jù)集與模型（模式）的擬合程度進行評估。

如果沒有評分函數(shù)吆录，就無法說出一個特定的已擬合的模型是否比另一個要好∏砟粒或者說恢筝，就沒有辦法為模型（模式）選擇出一套好的參數(shù)值來哀卫。

常用的評分函數(shù)有：似然（likelihood）函數(shù)、誤差平方和撬槽、準確率等此改。

在為模型（模式）選擇一個評分函數(shù)時，既要能夠很好地擬合現(xiàn)有數(shù)據(jù)侄柔，又要避免過度擬合（對極端值過于敏感）共啃，同時還要使擬合后的模型（模式）盡量簡潔。

不存在絕對“正確”的模型（模式）暂题，所有模型（模式）都是對現(xiàn)有數(shù)據(jù)的一種近似移剪。從這個角度來講，如果模型（模式）沒有隨著現(xiàn)有數(shù)據(jù)的變化而劇烈變化薪者，這個模型（模式）就是能夠接受的了纵苛。換句話說，對數(shù)據(jù)的微小變化不太敏感的模型（模式）才是一個好的模型（模式）言津。

（4）搜索和優(yōu)化方法

評分函數(shù)衡量了提出的模型（模式）與現(xiàn)有數(shù)據(jù)集的擬合程度攻人，搜索和優(yōu)化的目標是確定模型（模式）的結(jié)構(gòu)及其參數(shù)值，以使評分函數(shù)達到最小值（或最大值）悬槽。如：平方差最小怀吻、準確率最高，等等初婆。

如果模型（模式）的結(jié)構(gòu)已經(jīng)確定蓬坡，則搜索將在參數(shù)空間內(nèi)進行，目的是針對這個固定的模型（模式）結(jié)構(gòu)烟逊，優(yōu)化評分函數(shù)渣窜。

如果模型（模式）的結(jié)構(gòu)還沒有確定的話（例如，存在一族不同的模型（模式）結(jié)構(gòu)）宪躯，那么搜索既要針對結(jié)構(gòu)空間又要針對和這些結(jié)構(gòu)相聯(lián)系的參數(shù)空間進行乔宿。

針對特定的模型，發(fā)現(xiàn)其最佳參數(shù)值的過程通常被稱為優(yōu)化問題访雪。

而從潛在的模型（模式）族中發(fā)現(xiàn)最佳模型（模式）結(jié)構(gòu)的過程通常被稱為搜索問題详瑞。

常用的優(yōu)化方法有：爬山（Hill-Climing）、最陡峭下降（Steepest-Descend）臣缀、期望最大化（Expectation-Maximization, EM）

常用的搜索方法有：貪婪搜索坝橡、分支界定、寬度（深度）優(yōu)先遍歷

（5）數(shù)據(jù)管理策略

傳統(tǒng)的統(tǒng)計和機器學習算法都假定數(shù)據(jù)是可以全部放入內(nèi)存的精置，所以不太關(guān)心數(shù)據(jù)管理技術(shù)计寇。

但是，對于數(shù)據(jù)挖掘工作者來說，GB甚至TB數(shù)量級的數(shù)據(jù)是常見的番宁。由于外存的訪問速度要慢的多元莫，直接將傳統(tǒng)的內(nèi)存算法應用于這些外存數(shù)據(jù)，性能將變得非常差蝶押。

因此踱蠢，針對海量數(shù)據(jù)，應該設計有效的數(shù)據(jù)組織和索引技術(shù)棋电，或者通過采樣茎截、近似等手段，來減少數(shù)據(jù)的掃描次數(shù)赶盔，從而提高數(shù)據(jù)挖掘算法的效率企锌。

組件總結(jié)：

在實踐中，數(shù)據(jù)挖掘算法的組件化思想是非常有用的招刨。它通過將算法分解成一些核心組件而闡明了算法的實現(xiàn)機制霎俩。更重要的是，該觀點強調(diào)了算法的本質(zhì)沉眶，而不僅僅是算法的羅列打却。

當面對一個新的應用時，數(shù)據(jù)挖掘人員應該從組件的角度谎倔，根據(jù)應用需求柳击，考慮應該選取哪些組件，來組成一個新的算法片习，而不是考慮選取哪個現(xiàn)成的算法捌肴。

確定模型（模式）結(jié)構(gòu)和評分函數(shù)的過程通常由人來完成

而優(yōu)化評分函數(shù)的過程通常需要計算機輔助來實現(xiàn)。實踐中藕咏，通常要根據(jù)前一次的計算結(jié)果來改進模型（模式）結(jié)構(gòu)和評分函數(shù)状知，所以整個過程要重復很多次。

有趣的是孽查，不同的研究團體將注意力放在不同的數(shù)據(jù)挖掘算法組件上饥悴。

統(tǒng)計學家強調(diào)推理過程，關(guān)注模型（模式）盲再、評分函數(shù)西设、參數(shù)估計等，很少突出計算效率問題答朋。

而從事數(shù)據(jù)挖掘的計算機科學家則更注重高效的空間搜索和數(shù)據(jù)管理贷揽，不太關(guān)心模型（模式）或評分函數(shù)是否合適。

實際上梦碗，一個數(shù)據(jù)挖掘算法的所有組件都是至關(guān)重要的禽绪。

對于小的數(shù)據(jù)集蓖救，模型（模式）的解釋和預測能力相對于計算效率來說可能要重要的多。

但是丐一，隨著數(shù)據(jù)集的增大藻糖，計算效率將變得越來越重要淹冰。對于海量數(shù)據(jù)库车，必須在模型（模式）的完備性和計算效率之間進行平衡，以期對現(xiàn)有數(shù)據(jù)達到某種程度的擬合樱拴。

1989 IJCAI Workshop on Knowledge Discovery in Databases (Piatetsky-Shapiro)

Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley,1991)

1991-1994 Workshops on Knowledge Discovery in Databases Advances in Knowledge Discovery and Data Mining (U. Fayyad,G. Piatetsky-Shapiro,P. Smyth, and R. Uthurusamy, 1996)

1995-1998 International Conferences on Knowledge Discovery in Databases and Data Mining (KDD’95-98)

Journal of Data Mining and Knowledge Discovery (1997)

1998 ACM SIGKDD, SIGKDD’1999-2001 conferences, and SIGKDD Explorations

More conferences on data mining

PAKDD (1997), PKDD (1997), SIAM-Data Mining (2001), (IEEE) ICDM (2001), etc.

--------------------------------------------------------------------------------

Reference

周志華柠衍，機器學習導論課程PPT

http://www.cs.uiuc.edu/homes/hanj/, Jiawei han’s lecture ppt.

http://www.comp.nus.edu.sg/~atung/, Anthony Tung’s lecture ppt.

T. Dasuand T. Johnson.? Exploratory Data Mining and Data Cleaning.John Wiley & Sons, 2003 U. M.Fayyad, G. Piatetsky-Shapiro,

P. Smyth, and R. Uthurusamy. Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996

U.Fayyad, G. Grinstein, and A. Wierse, Information Visualization in Data Mining and Knowledge Discovery, Morgan Kaufmann, 2001

J. Han and M. Kamber. Data Mining: Concepts and Techniques. 2nd ed.,Morgan Kaufmann, 2005

D. J.Hand, H. Mannila, and P. Smyth, Principles of Data Mining, MIT Press, 2001

T.Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer-Verlag, 2001?

T. M.Mitchell, Machine Learning, McGraw Hill, 1997

G. Piatetsky-Shapiro and W. J. Frawley. Knowledge Discovery in Databases. AAAI/MIT Press, 1991

S. M.Weiss and N. Indurkhya, Predictive Data Mining, Morgan Kaufmann, 1998

I. H.Witten and E. Frank,? Data Mining:Practical Machine Learning Tools and Techniques with Java Implementations, 2nd ed., Morgan Kaufmann, 2005