講授：吳雄華第一章數據挖掘概述電話mail：wuxionghua2003@163.com一、引例網站這種推薦并非漫無邊際，而是有一定技術依據的，這種技術就是數據挖掘技術（DM）。網站怎么知道讀者可能會對這些物品干興趣？這是因為網站采用了新的技術來了解顧客的潛在需求，比如：網站從顧客的購買清單中發現你買的書與張三買過的書有幾本是相同的，但是還有些書張三已經買了，而你卻還沒買，網站會據此認為你們的閱讀偏好相近，從而你會對那些書也干興趣。例1。如果你在當當的購書網站并購買過書籍或音像制品，以后再瀏覽該網站時經?？吹筋愃频奶崾荆骸皻g迎你，下面是我們給您推薦的新書和VCD?！比缓缶涂梢栽诰W頁的某個位置看到幾本新書或VCD的名字及其相關鏈接。從這個銷售數據中可以得出什么結論？某超市Post機上記錄如下的銷售數據：例2。啤酒與尿布的故事顧客購買商品1面包，黃油，尿布，啤酒2咖啡，糖，小甜餅，鮭魚，啤酒3面包，黃油，咖啡，尿布，啤酒，雞蛋4面包，黃油，鮭魚，雞5雞蛋，面包，黃油6鮭魚，尿布，啤酒7面包，茶，糖雞蛋8咖啡，糖，雞，雞蛋9面包，尿布，啤酒，鹽10茶，雞蛋，小甜餅，尿布，啤酒從數據挖掘的角度就是得到了如下的很強的關聯規則：簡單分析發現，有6個顧客買了啤酒，而其中5個人買了尿布，或說，5個買了尿布的顧客都買了啤酒。規則1：“買啤酒”“買尿布”。置信度為5/6規則2：“買尿布”“買啤酒”。置信度為5/5結論：“買尿布的顧客很可能會買啤酒”。原因？對決策者的啟示:商品的擺放設計和銷售策略。二、數據挖掘的定義三、數據挖掘技術產生的動力

數據挖掘的定義有多種不同的定義方式，現在為大家廣泛采用的是如下定義：數據挖掘是從大量的數據中挖掘出隱含的、未知的、用戶可能感興趣的和對決策有潛在價值的知識和規則。簡單的說，數據挖掘就是從大量的數據中發現有用的信息。1.數據爆炸問題。例3、美國未來學家阿爾溫~托夫勒在1980年的著作在《第三次浪潮》中認為，未來的信息量將以指數級的速度增長?，F在已成事實。例5.JohnRoth在聯合國世界電信論壇上又提出了一個關于網絡科技的一個觀點：互聯網寬帶每9個月會增加一倍的容量，但成本降低一半，比芯片的變革速度還快。----“光纖定律”。例4.1965年，Intel公司聯合創始人GordonMorore在準備一個演講時發現了一個具有歷史意義的現象:芯片的容量每18~24個月增加一倍。他據此推斷，按此趨勢發展下去，在較短時間內計算能力將呈指數增長。----“摩爾定律”。。還有很多案例都可以印證，現在的社會是一個信息爆炸的社會。是在信息的潮流中隨波逐流還是“到中流擊水，浪遏飛舟”？數據挖掘技術的另一個產生動力2.數據過量而知識貧乏現代人了解古代的主要方式主要是通過前人留下的記錄，但是這些記錄往往是零碎的、不完全的。例如？想象一下，如果后人希望了解現在人們的生活狀況，他們面臨的已不再是信息缺失，而是需要從浩如煙海的資料中有選擇性的收集他們認為有用的信息，若沒有一定技術支持，其難度恐怕可以用“浪里淘金”或“大海撈針”來形容。四、數據挖掘的支撐技術數據挖掘融合了統計、人工智能及數據庫等多種學科的理論、方法和技術如統計學：除了實驗設計與數據挖掘的關系不大，其他幾乎所有方法都可以用于數據挖掘，如估計、假設檢驗、回歸分析、主成分分析、時間序列分析、馬爾科夫鏈等。五、數據挖掘的主要任務1、預測：分類和回歸2、關聯分析：如研究顧客的行為模式3、聚類分析：例如對于新聞可以根據他們的主題分組。4、異常檢測：識別其特征顯著不同于其他數據的觀測值（異常點）。主要應用包括檢測欺詐、網絡攻擊、疾病的不尋常模式等。例6。信用卡欺詐檢測信用卡公司記錄每個持卡人所做的交易，同時也記錄信用限度、年齡、年薪和地址等個人信息。由于與合法交易相比，欺詐行為的數目相對較少，因此異常檢測技術可以用來構造合法交易的輪廓。當一個新的交易到達時就與之比較。如果該交易的特性與所構造的輪廓很不相同，就把交易標記為可能是欺詐。第二章數據一、理解數據例1。有人給你如下數據，每行包含一個病人的信息，用前4個字段預測后一個字段。01223233.5010.702012116.52210.7027165240427.6你做了相關的工作后再與數據提供者交流，字段1只是一個標號不代表任何實際意義，而字段4中0表示缺失值，在錄入數據時偏偏所有的10都變成了0.？!二、數據屬性及其類型屬性（Attitude）是對象的性質或特性。屬性類型描述例子分類的（定性的）標稱屬性值只是不同的名字，只提供足夠的信息區分對象（=，！=）郵編、ID號、顏色、性別序數屬性值只是確定對象的序（<或>)礦石硬度等級、成績（A、B、C）數值的（定量的）區間屬性值之間的差是有意義的（+或-）日期、溫度比率屬性值之間的差或比都有意義。絕對溫度、年齡、銷售量等三、數據集的類型1、記錄數據。如TidRufundMaritalStatusTaxableIncomeDefaultedBorrower1YesSingle125KNo2NoMarried100KNo3Yesdevorce189KYes三、數據集的類型2、事務數據（購物籃數據），如顧客購買商品1面包，黃油，尿布，啤酒2咖啡，糖，小甜餅，鮭魚，啤酒3面包，黃油，咖啡，尿布，啤酒，雞蛋4面包，黃油，鮭魚，雞5雞蛋，面包，黃油6鮭魚，尿布，啤酒7面包，茶，糖雞蛋8咖啡，糖，雞，雞蛋9面包，尿布，啤酒，鹽10茶，雞蛋，小甜餅，尿布，啤酒三、數據集的類型3、矩陣數據。如距離矩陣，協方差矩陣，相關系數矩陣等。4、文檔—詞數據。如teamcoachplayballscoregamewinlostfauldoc1305601804Doc2078930156doc30100010405、時間序列數據6、其他四、數據對象之間的相異度和相似度1、簡單屬性的相似度和相異度假設數據對象只有一個屬性，則通常其相似度和相異度可按如下定義。1.1標稱屬性的相異度和相似度d=0,如果x=y1,如果xy相異度相似度：s=1-d例如，如果只考慮顧客的性別屬性，如果都是“男”，則他們的相似度為1，相異度為0.1、簡單屬性的相似度和相異度1.2序數屬性的相異度和相似度d=|x-y|/(n-1)，相異度相似度：s=1-d例如，考慮學生的成績，共分為A、B、C、D四個等級，則n=4,相異度為2/3.其中n為屬性取值的總個數。1、簡單屬性的相似度和相異度1.3區間或比率屬性的相異度和相似度d=|x-y|相異度較常用的相似度有：s=1/(1+d),例如，考慮如下的身高數據S=1-(d-min_d)/(max_d-min_d)學生S1S2S3S4S5S6S7身高156178166170185168180可以計算學生身高的相異度矩陣如下：學生S1S2S3S4S5S6S7身高156178166170185168180S1S2S3S4S5S6S7S10221014291224S201287102S30419214S4015210S50175S6012S70二元屬性：屬性的值只接受兩個值：如真/假，男/女、是/否等，通常用0/1表示。則S2與S6之間的相異度為10，而相似度為1/11,有min_d=2,max_d=29,因此，也可以定義相似度為1-(10-2)/(29-2)=19/27。2.數據對象之間的相似度—相似性度量的例子2.1。二元數據的相似性度量兩個僅包含二元屬性的對象之間的相似性度量也稱為相似系數。設x和y是兩個對象，都由n個二元屬性組成。定義如下四個量f00=x取0且y取0的屬性個數f01=x取0且y取1的屬性個數f10=x取1且y取0的屬性個數f11=x取1且y取1的屬性個數2.1.1一種常用的相似系數是簡單匹配系數（SimpleMatchingCoeffient,SMC)，定義如下SMC=f00+f11f00+f11+f10+f01對于類似顧客是否購買某商品這樣的非對稱二元數據，這個相似系數則難以體現顧客相同的購買行為。Why?2.1.2Jaccard

相似系數。Jaccard（Jaccard

Coeffient,JC)相似系數定義如下J=f11f11+f10+f01例1.設二元數據對象x和y如下，計算其SMC和J。x=（1000101001）y=（1010110011）解：f00=3f01=3f10=1f11=3因此，SMC=6/10，J=3/7例2.設兩個顧客x和y購買的商品如下，計算它們的相似系數SMC和J。商品面包啤酒牛奶茶糖雞蛋鹽大米洋蔥大蒜派x10100010010y10100010010商品純凈水可樂水餃口香糖牙膏毛巾洗面奶洗發水面粉味精派瓜子x10010100000y010100000002.1.3余弦相似度通常類似于文檔—詞這樣的數據，度量其相似性不能依賴共享0的個數，如果統計0-0匹配，則大多數文檔都非常相似，因此同樣要忽略0-0匹配。這類數據最常用的相似度之一就是余弦相似度，定義如下Cos（x，y）=xy/(||x||||y||)2.1.4廣義Jaccard系數廣義Jaccard系數也可以用于文檔數據，并在二元屬性情況下歸約為Jaccard系數，其定義如下：例3.兩個文檔向量x和y如下，分別計算其余弦相似度cos(x，y）和EJx=（3205000200）EJ=xy/(||x||2+||y||2-xy)y=（1003106001）2.1.4相關性兩個具有二元變量或連續的數據之間對象之間的相關性是對象之間線性聯系的度量，一般可以用Pearson相關系數（Pearson，scorrelation）來描述。其定義如下：其中第三章數據挖掘中的統計方法一、數據探索1.1匯總統計1.1.1頻率與眾數給定一個在{v1,v2,....,vk}取值的分類屬性x和m個對象的集合，值vi的頻率定義為f（vi）=具有屬性值vi的對象數/m眾數：具有最高頻率的分類屬性例1.某所大學中各年級的學生人數如下表：則年級屬性的眾數為“一年級”。對于連續屬性，按照目前的定義，眾數通常沒有用（為什么？），但在某些情況下，眾數可能提供關于值的性質或關于出現遺漏值的重要信息。年級人數頻率一年級2000.33二年級1600.27三年級1300.22四年級1100.18例如，以毫米為單位，20個人的身高通常不會重復，但如果以分米為單位，則某些人很可能具有相同的身高。此外，如果使用一個唯一的值表示遺漏值，該值通常用眾數。1.1.2百分位數百分位數的定義：設有容量為n的樣本觀察值想x1，x2，x3，...，xn，樣本的p分位數（0<p<1）是指滿足如下性質的xp

:A：至少有np個觀察值小于或等于xp。B：至多有n（1-p）個觀察值大于或等于xp。樣本的p分位數xp可以按如下方法求得：將觀察值按自小到大的順序排列成：x(1)≤x(2)

≤...≤x(n);即：xp=1。：若np不是整數，則只有一個數據滿足定義的兩點要求，這一數據位于大于np的最小整數處，即[np]+1處；2。：若np是整數，則位于np和np+1位置的數據均符合要求，此時取這兩個數的平均值作為xp；x（[np]+1)當np不是整數（x（np）+x（np+1）)/2當np是整數與分位數有關常用術語一、極差：x(n)-

x(1);median(x)=二、中位數：p=0.5，此時xp稱為中位數，記為median(x)其計算如下:x（[n/2]+1)當n為奇數（x（n/2）+x（n/2+1）)/2當n整為偶數三、第一四分位數Q1：p=0.25；第三四分位數Q3：p=0.75；四分位數極差IQR=Q3-Q1；例1.下表是中國各?。ㄊ校﹪袉挝坏娜司鶊蟪?，單位：元/年。分別計算p=0.25,0.5,0.75時的分位數及樣本均值。地區上海浙江浙江北京西藏人均年收入5031147587475874582344813地區廣東天津江蘇青海福建人均年收入3605334509327382868127423地區山東山東寧夏重慶遼寧人均年收入2698626986261572506024281地區四川湖南湖南內蒙古廣西人均年收入2404522956229562271122614地區云南山西河南甘肅安徽人均年收入2227522107220442196821960地區貴州湖北吉林陜西新疆人均年收入2160821591215022134521213地區河北江西海南黑龍江

人均年收入20754192981872018392

解：n=34，n*0.75=8.5,Q3=32738(江蘇）,同理，median=22956（湖北或湖南），Q1=21608（貴州），Q3-Q1=11130，樣本均值為27501.59箱線圖如下：Q318392黑龍江Q1MinMax21608貴州32738江蘇50311上海M箱線圖的說明：若中位數位于箱子中間，則數據分布較為對稱；若Min離M的距離較Max離M的距離大，在表示數據分布向左傾斜；反之向右。二、估計2.1點估計2.1.1矩估計與極大似然估計另外一種常用的估計方法為折疊刀估計，它通過從一組觀測值中忽略一個值來實現對參數的估計。假設一個具有n個值的集合x={x1，x2，...，xn}，對均值的單次估計為：2.1.2折疊刀估計θ(i)=(x1+...+xi-1+xi+1+...xn)/(n-1)對這些單次估計求平均值θ=(θ(1)+...θ(n))/n作為總統的均值估計。例：設總體的分布率如下：現有樣本的10個觀察值：3,3,2,2,1,2,1,2,3,3，分別用矩估計發、極大似然估計法和折疊刀估計法估計θ。解：矩估計法X123Pkθ22θ(1-θ)(1-θ)2E（X）=3-2θ，又樣本均值為2.2，因此θ得矩估計值為0.4極大似然估計：L（θ）=。。。。，θ的極大似然估計值也是0.4數據：3,3,2,2,1,2,1,2,3,3折疊刀估計法計算θ(1)=(3+2+2+1+2+1+2+3+3)/9=θ(2)=θ(9)=θ(10)=19/9;因此對總體均值的估計為:（(19/9+20/9)*4+21/9*2）/10=19.8/9;θ(3)=(3+3+2+1+2+1+2+3+3)/9=θ(4)=θ(6)=θ(8)=20/9;θ(5)=(3+3+2+2+2+1+2+3+3)/9=θ(7)=θ(6)=21/9;又E（X）=3-2θ，令3-2θ=19.8/9;

解得θ=0.4估計的一個指導思想是奧卡姆剃刀原則（Ockham’sRazor):越簡單的模型能產生越好的結果。三、主成分分析3.1主成分分析概述在處理多元樣本數據時，經常遇到觀察數據多，維數很高的問題。如果有每個觀察對象有p個屬性，選取n個對象進行觀察，則達到n×p個數據。如何從這些數據中提取主要規律，從而分析樣本或總體的主要性質？例如，要分析若干個地區的經濟發展狀況，對每個地區都要統計很多指標，但如果只根據這些統計數據對不同地區進行評價、比較或排序，則因指標太多、主次不明顯很難做到公正客觀。另外，這些指標有點是主要的，有點是有的是次要的，甚至某些指標間還有一定的相關性。能否用較少的幾項指標來代替原來較多的指標，使得這較少的幾項指標仍能反映原來較多的指標反映的信息？主成分分析就是把一種原來多個指標變量轉化為少數幾個相互獨立指標變量的統計方法，它不是去分析比較各指標的重要性，將那些不重要的指標簡單去掉，而是通過全面分析各項指標所攜帶的信息，從中提取一下潛在的綜合性指標（稱為主成分）。三、主成分分析3.2主成分分析的數學模型及其求解步驟設每個數據對象的有p個屬性（指標）觀察了n次，得到觀察數據矩陣為用數據矩陣X的p個指標作線性組合（即綜合變量）為：系數aij的確定方法：對數據集X進行標準化，標準化后的數據仍記為X，然后求出X的樣本協方差陣S和相關系數陣R，進而求出R的特征值與及其對應的特征向量。特征值按從大到小順序排列對應的標準化特征向量為則第i個綜合變量的組合系數（a1i,a2i,…,api)即為第i個特征值對應的標準化特征向量。即第一個綜合變量為：第i個綜合變量為：可以Zi與Zj是正交的，因此主成分分析去除了指標之間的線性相關性。主成分分析的目的之一就是為了簡化數據結構，因而在實際應用中一般絕不用p個主成分，而選用m個主成分（m<p）。m取多大，這是一個和實際的問題，為此引入貢獻率的概念。定義3.1：稱為主成分Zi的貢獻率。m的確定：通常累積貢獻率達到70%以上時即可。為m個主成分Z1,Z2,…,Zm的累積貢獻率。主成分分析的幾何意義。Z1Z2三、主成分分析3.3主成分分析實例附表1是2008年中國內地各地區按登記注冊類型分城鎮單位就業人員平均勞動報酬（數據來源：中國統計年鑒2008），對其進行主成分分析。

地區國有單位x1城鎮集體單位x2股份合作單位x3聯營單位x4有限責任公司x5股份有限公司x6其他x7港、澳、臺商投資單位x8河北2075412304157433630919803181151182019160山西2210713987127101486023621189921268310591遼寧2428112117145921521821803289971210321866吉林2150211087106561193016774252061241214691北京4582348328202351621831124354806135732892上海5031127949238783900938783553185251829679江蘇3273818496173071680923372293721814821356浙江4758725242240533512922487305042643722717安徽2196015109150201415424566244151427015514江西1929812404145371517717610210411255411637山東2698615502168723375818306209111498118471河南2204415674175811337019728217711748820133湖北2159112869145321239316674158821076215296廣東3605316347205862810530694442132357320770主成分分析步驟：1.對數據進行標準化：設標準后的數據仍記為X。2.求觀察數據的相關系數矩陣。數據標準化后，樣本的相關系數矩陣即為：3.計算樣本相關陣的特征值和特征向量，并按特征值從小到大排列。4.計算累積貢獻率，確定綜合變量個數。標準化后的數據為如下，設為X。-0.2723-0.61285-0.32362-0.724231.430795-0.53864-0.89136-0.61372-0.075-0.44045-0.23018-0.44328-1.091290.23062-0.656020.059896-0.81125-0.55905-1.45232-0.48661-0.16252-0.63169-0.61494-0.48387-0.62119-0.225110.10271-0.595790.359937-0.3811-0.24901-0.73546-1.611171.465707-0.94108-1.01349-0.2436-0.57622-0.793310.0089940.5079743.0165980.813342-0.23476-0.52391.2361260.6949332.5245212.1321672.914370.6476620.9633991.7354111.8312151.6934832.4368122.5071381.9645571.6157351.3840980.1007050.0110030.072244-0.81171-0.46640.0208610.136967-0.212830.277963-0.079680.5628780.6906671.7797041.9680871.31599-0.117880.2403750.3122870.496719-0.28435-0.23476-0.33024-0.50661-0.59068-0.724710.208042-0.31586-0.45851-0.66103-0.51493-0.31761-0.60277-0.62886-0.46865-0.62518-0.88244-0.62407-0.56722-1.28419-1.07672-0.07833-0.29064-0.03786-0.815041.182603-0.77333-0.63595-0.41347-0.18575-0.45061-0.23215-0.273320.141596-0.79867-0.80098-0.5504-0.55739-0.254650.081388-0.43712-0.24624-0.55592-0.63013-0.46725-0.89604-1.02917-1.09535-0.68075-0.69607-0.297770.203884-0.205510.902182-0.100780.6326121.1687161.4926940.1308480.1837740.141896按公式求出相關系數矩陣R如下：10.79410.89770.57740.5440.77710.81060.8540.82710.71610.794110.6380.24530.17790.64280.52460.93690.82720.91180.89770.63810.38960.670.69310.72240.70940.75950.48940.57740.24530.389610.35990.35960.51120.37950.22910.26230.5440.17790.670.359910.3990.44580.30850.40370.12440.77710.64280.69310.35960.39910.90410.81540.70940.70740.81060.52460.72240.51120.44580.904110.74230.71420.62040.8540.93690.70940.37950.30850.81540.742310.87220.93340.82710.82720.75950.22910.40370.70940.71420.872210.83750.71610.91180.48940.26230.12440.70740.62040.93340.83751求R的特征值和特征向量，特征值從小到大排列，并計算相應的貢獻率，如下表：特征值貢獻率累積貢獻率5.19050.6488130.6488131.19220.1490250.7978380.76840.096050.8938880.43080.053850.9477380.22710.0283880.9761250.13430.0167880.9929130.03830.0047880.99770.01830.0022880.999988從上表可以看出，主成分的個數取2—3個較好。這里取3個。他們對于的單位特征向量為：0.3728-0.2601-0.30430.2175-0.44010.79280.236-0.6399-0.42040.39380.06570.04180.393-0.08210.15670.40790.25910.05370.39230.2063-0.24840.35810.45660.1056第一主成分為：Z1=0.3728*x1+0.2175*x2+0.236*x3+0.3938*x4+…+0.3581*x8同樣方法可以得到另外兩個主成分。根據實際情況，可以對相應的主成分命名。如上，原數據要考慮8個因素，通過提取主成分后只需要考慮3個因素，設原數據集（未標準化前）為X，三個最大特征值對應的特征向量構成的矩陣為：主成分分析的應用：1）降維做矩陣乘法X*V，即可把原8維數據降為3維數據。如本例，變換后的數據為地區綜合變量Z1綜合變量Z2綜合變量Z3河北55100-42471502山西45930-86292329遼寧54100-1782996吉林44640-2085716北京101310-1075711556上海114870-2568-2423江蘇62860-74391115浙江82530-14686-2119安徽51360-67062827江西43900-6874484山東58920-6980617河南51740-6182929湖北41890-7814449廣東79700-4616-1969當第一主成分的系數（最大特征值對應的特征向量）全部同號是，可按第一主成分對數據進行排序。如本例，所給省市的勞動報酬由高到低依次為主成分分析的應用：1）排序地區上海北京浙江廣東江蘇山東河北Z11148701013108253079700628605892055100遼寧河南安徽山西吉林江西湖北54100517405136045930446404390041890敬請各位同學提出寶貴意見非常