數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第二章)

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)第二章數(shù)據(jù)1這是不是數(shù)據(jù)?2.3 1.2 1.7 5.0 2.3 2.21.3 2.2 3.7 2.1 3.3 2.23.3 1.3 2.1 2.2 3.1 5.21.2 2.2 3.5 2.9 5.1 3.12數(shù)據(jù)類型數(shù)據(jù)質(zhì)量數(shù)據(jù)預(yù)處理相似性和相異性度量3考慮你收到了某個(gè)醫(yī)學(xué)研究者發(fā)來的郵件，內(nèi)容如下：你好，我已附上先前郵件提及的數(shù)據(jù)文件。每行包含一個(gè)病人的信息，由5個(gè)字段組成。我們想使用前面4個(gè)字段預(yù)測(cè)最后一個(gè)字段。因?yàn)槲乙鋈滋欤詻]有時(shí)間為你提供關(guān)于這些數(shù)據(jù)的更多信息，但希望不會(huì)耽誤你太多時(shí)間。如果你不介意的話，我回來之后是否可以開會(huì)討論你的初步結(jié)果？我可能會(huì)邀請(qǐng)我們小組的其他成員參加。謝謝！幾天之后見！4盡管有些疑慮，你還是開始著手分析這些數(shù)據(jù)。字段1 字段2 字段3 字段4 字段5012 232 33.5 0 10.7020 121 16.9 2 210.1027 165 24.0 0 427.6…你好，我叫數(shù)據(jù)。這幾天就暫時(shí)拜托你了！5 看起來沒有什么不對(duì)。你開始分析，數(shù)據(jù)只有1000行，兩天后你認(rèn)為取得了一些進(jìn)展。去參加會(huì)議，并與一位負(fù)責(zé)參與該項(xiàng)目的統(tǒng)計(jì)人員交談。數(shù)據(jù)挖掘者統(tǒng)計(jì)人員哦，你得到了所有病人的數(shù)據(jù)？是的，我還沒有足夠的時(shí)間分析，但是我的確有了一些有趣的結(jié)果。真棒，病人數(shù)據(jù)集的數(shù)據(jù)問題太多，我沒什么進(jìn)展。。啊？我沒聽到任何問題哦，首先是字段5，這是我們要預(yù)測(cè)的變量。地球人都知道，如果使用這些值的日志，結(jié)果會(huì)更好，但是我們后來才發(fā)現(xiàn)這一點(diǎn)。他們告訴你了嗎？沒有。。。。。。。。那你一定聽說過字段4的問題了吧？他的測(cè)量范圍應(yīng)當(dāng)是1到10，而0表示有遺漏的值。但是，由于數(shù)據(jù)輸入錯(cuò)誤，所有的10都變成了0?？墒牵捎谟行┎∪诉@個(gè)字段的值有遺漏，所以不能確定該字段上的0實(shí)際是0還是10。不少記錄都存在這個(gè)問題。。。。有意思，還有其他問題嗎？是的。字段2和字段3也有不少問題。我猜想你可能已經(jīng)注意到了。是的。但是這些這些字段只是字段5的弱預(yù)測(cè)子。無論如何，盡管有這些問題，你還能夠完成一些分析。真厲害?。『吆?。我的結(jié)果那是相當(dāng)?shù)暮谩Ｗ侄?是字段5的很強(qiáng)的預(yù)測(cè)子。你們這些人竟然沒注意到。什么？字段1只是一個(gè)標(biāo)識(shí)號(hào)。無論如何，我的結(jié)果在那。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。??！不！我才想起來，按字段5排序之后，我們加上了一個(gè)ID號(hào)。他們之間存在很強(qiáng)的聯(lián)系，但是毫無意義，抱歉。。。61、數(shù)據(jù)類型7數(shù)據(jù)集的不同表現(xiàn)在很多方面用來描述數(shù)據(jù)對(duì)象的數(shù)據(jù)可以具有不同的類型-定量或定性的數(shù)據(jù)集可能具有特定的性質(zhì)，如數(shù)據(jù)集包含時(shí)間序列或彼此之間具有明顯聯(lián)系的對(duì)象數(shù)據(jù)的類型決定我們應(yīng)使用何種技術(shù)和工具來分析數(shù)據(jù)！81、數(shù)據(jù)集全稱是什么？數(shù)據(jù)對(duì)象的集合2、數(shù)據(jù)對(duì)象是什么？記錄、點(diǎn)、向量、模式、事件、案例、樣本、觀測(cè)、實(shí)體3、數(shù)據(jù)對(duì)象用什么來描述？屬性、變量、特性、字段、特征、維9 下表顯示包含學(xué)生信息的數(shù)據(jù)集

每行對(duì)應(yīng)于一個(gè)學(xué)生，而每列則是一個(gè)屬性，描述學(xué)生的某一方面，如平均成績(jī)（GPA）或標(biāo)示號(hào)(ID)學(xué)生ID年級(jí)平均GPA…1034262四年級(jí)3.24…1052663二年級(jí)3.51…1082246一年級(jí)3.62…這種數(shù)據(jù)集最常見，但還有其他類型的數(shù)據(jù)集101.1、屬性與度量11一、先來看看什么是屬性屬性是對(duì)象的性質(zhì)或特質(zhì)，因?qū)ο蠖?，或隨時(shí)間而變化例如：眼球的顏色因人而異，物體的溫度隨時(shí)間而變測(cè)量標(biāo)度是將數(shù)值或符號(hào)值與對(duì)象的屬性相關(guān)聯(lián)的規(guī)則或函數(shù)例如：踏上浴室的磅秤稱體重；將人分為男女；清點(diǎn)會(huì)議室的椅子數(shù)，確定是否能為與會(huì)者提供足夠的座位屬性本身并非數(shù)字或符號(hào)！12二、屬性類型 屬性的性質(zhì)不必與用來度量他的值的性質(zhì)相同

屬性類型告訴我們，屬性的哪些性質(zhì)反映在用于測(cè)量他的值中。例1：雇員年齡與ID號(hào)這兩個(gè)屬性都可以用整數(shù)表示雇員的平均年齡有意義，而平均ID卻無意義年齡有最大最小值，而整數(shù)卻無此限制但用整數(shù)來表示時(shí)，并未暗示有限制13例2：線段長(zhǎng)度每條后繼線段都是通過最上面的線段自我添加而形成的14二、屬性的不同類型屬性包括四種類型:標(biāo)稱(nomial)序數(shù)(ordinal)區(qū)間(interval)比率(ratio)相異性 =和≠序 <、≤、>、≥加法 +、-乘法 ×、÷15屬性的類型也可以用不改變屬性意義的變換來描述:例:

如果長(zhǎng)度分別用米和英尺度量，其屬性意義是否有變化。計(jì)算平均長(zhǎng)度時(shí)，有什么變化？例:溫度 我們說“溫度2度是1度的兩倍”,用下列哪種測(cè)量有意義?

絕對(duì)標(biāo)度?攝氏度?華氏度?16三、非對(duì)稱的屬性 對(duì)于非對(duì)稱的屬性，只有非零值才是重要的例1：對(duì)象是學(xué)生，屬性是學(xué)生是否選修某門大學(xué)課程。對(duì)某個(gè)學(xué)生，如果他選擇了對(duì)應(yīng)某屬性的課程，則該屬性取1，否則取0。課程1課程2課程3課程4課程5課程6課程7課程8課程9學(xué)生1000010001學(xué)生2100010000學(xué)生3010000010只有非0值才重要的二元屬性稱為非對(duì)稱二元屬性只有非0值才重要的離散屬性稱為非對(duì)稱二元屬性（學(xué)分）只有非0值才重要的連續(xù)屬性稱為非對(duì)稱二元屬性（成績(jī)）171.2、數(shù)據(jù)集的類型18維度：數(shù)據(jù)集中對(duì)象的屬性數(shù)目稀疏性：具有非對(duì)稱屬性的數(shù)據(jù)集分辨率：對(duì)數(shù)據(jù)描述的精細(xì)程度S1000010001S2100010000S3010000010S1110110111S2101110010S3110000010一、數(shù)據(jù)集的一般特性19許多數(shù)據(jù)挖掘任務(wù)都假定數(shù)據(jù)集是記錄的匯集記錄之間或字段(屬性)之間沒有明顯的聯(lián)系每個(gè)記錄具有相同的屬性集記錄數(shù)據(jù)通常存放在平展文件或關(guān)系數(shù)據(jù)庫(kù)中二、記錄數(shù)據(jù)標(biāo)準(zhǔn)記錄數(shù)據(jù)20特殊類型的記錄數(shù)據(jù)每個(gè)記錄中的項(xiàng)是購(gòu)物籃中的商品可以將它轉(zhuǎn)換為標(biāo)準(zhǔn)記錄數(shù)據(jù),記錄的字段是非對(duì)稱屬性屬性可以是離散或連續(xù)的,例如商品數(shù)量或費(fèi)用事務(wù)數(shù)據(jù)或購(gòu)物籃數(shù)據(jù)21數(shù)據(jù)集族中的所有數(shù)據(jù)對(duì)象都具有相同的數(shù)值屬性集數(shù)據(jù)對(duì)象可看作是多維空間中的向量可以使用標(biāo)準(zhǔn)的矩陣操作對(duì)數(shù)據(jù)進(jìn)行變換和處理數(shù)據(jù)矩陣22數(shù)據(jù)矩陣的特殊形式屬性類型相同非對(duì)稱稀疏數(shù)據(jù)矩陣23數(shù)據(jù)對(duì)象映射到圖中的結(jié)點(diǎn)對(duì)象之間的聯(lián)系用對(duì)象之間和鏈、方向、權(quán)值表示三、基于圖形的數(shù)據(jù)帶有對(duì)象之間聯(lián)系的數(shù)據(jù)24若對(duì)象具有結(jié)構(gòu)（包含具有聯(lián)系的子對(duì)象），則對(duì)象常用圖形表示具有圖形對(duì)象的數(shù)據(jù)25也稱為時(shí)間數(shù)據(jù),可看作記錄數(shù)據(jù)的擴(kuò)充每個(gè)記錄包含一個(gè)與之相關(guān)聯(lián)的時(shí)間用途舉例:萬圣節(jié)前糖果銷售達(dá)到高峰購(gòu)買dvd播放機(jī)的人趨向于在其后不久購(gòu)買DVD四、有序數(shù)據(jù)時(shí)序數(shù)據(jù)26是各個(gè)實(shí)體的序列,如詞或字母需要考慮項(xiàng)的位置序列數(shù)據(jù)27特殊的時(shí)序數(shù)據(jù),每個(gè)記錄都是一段時(shí)間以來的測(cè)量序列分析該類數(shù)據(jù)時(shí),需要考慮時(shí)間自相關(guān)時(shí)間自相關(guān)：如果兩個(gè)測(cè)量的時(shí)間很接近，則測(cè)量值通常非常相似時(shí)間序列數(shù)據(jù)28除具有其他類型的屬性外，還具有空間屬性，如位置或區(qū)域分析該類數(shù)據(jù)時(shí),需要考慮空間自相關(guān)空間自相關(guān)：物理上靠近的對(duì)象，趨向于在其他方面也相似例子:地球科學(xué)數(shù)據(jù)集記錄在各種分辨率下經(jīng)緯度球面網(wǎng)格點(diǎn)上測(cè)量的溫度和氣壓瓦斯氣流模擬中，可以針對(duì)模擬中的每個(gè)網(wǎng)格點(diǎn)記錄流速和方向空間數(shù)據(jù)29四、處理非記錄數(shù)據(jù)記錄數(shù)據(jù)非記錄數(shù)據(jù)子結(jié)構(gòu)1子結(jié)構(gòu)2子結(jié)構(gòu)3子結(jié)構(gòu)4化合物11001化合物21100化合物3…………30注意：盡管容易用記錄形式表示非記錄數(shù)據(jù)，但不能捕獲所有信息JanFebMarApr位點(diǎn)127.228.729.231.1位點(diǎn)230.133.535.937.3位點(diǎn)3…………此時(shí)，不要在進(jìn)行數(shù)據(jù)挖掘任務(wù)時(shí)假設(shè)屬性之間在統(tǒng)計(jì)上是相互獨(dú)立的！空間相關(guān)性時(shí)間相關(guān)性312、數(shù)據(jù)質(zhì)量32數(shù)據(jù)挖掘使用的數(shù)據(jù)通常是為其他用途收集的，或收集時(shí)無明確目的因此，數(shù)據(jù)質(zhì)量問題往往無法避免對(duì)數(shù)據(jù)挖掘任務(wù)來說，需要著眼于（1）數(shù)據(jù)質(zhì)量問題的檢測(cè)和糾正（2）使用容忍低質(zhì)量數(shù)據(jù)的算法332.1、測(cè)量和數(shù)據(jù)收集問題34一、測(cè)量誤差和數(shù)據(jù)收集錯(cuò)誤測(cè)量誤差：測(cè)量過程中導(dǎo)致的問題，在某種程度上，記錄的值與實(shí)際值不符例:一個(gè)人連續(xù)兩次測(cè)量體重，得到的值不一樣數(shù)據(jù)收集錯(cuò)誤：遺漏數(shù)據(jù)對(duì)象或?qū)傩灾?，或不?dāng)?shù)陌似渌麛?shù)據(jù)對(duì)象例:一類特定種類動(dòng)物研究可能包含了其他相關(guān)種類的動(dòng)物，他們只是表面上與要研究的種類相似。35二、噪聲和偽象噪聲：測(cè)量誤差的隨機(jī)部分例:在老舊電話上說話時(shí)的聲音的干擾電視屏幕上的雪花兩個(gè)正弦波正弦波+噪聲偽象：確定性現(xiàn)象造成的測(cè)量誤差例:一組照片在同一地方出現(xiàn)條紋36三、精度、偏倚、準(zhǔn)確率精度：（同一個(gè)量）重復(fù)測(cè)量值之間的接近程度偏倚：測(cè)量值與被測(cè)量值之間的系統(tǒng)變差例:某樣品的標(biāo)準(zhǔn)重量為1克，為了評(píng)估實(shí)驗(yàn)室新天平的精度和偏倚，我們稱重5次{1.015,0.990,1.013,1.001,0.986}偏倚=均值-標(biāo)準(zhǔn)重量=1.001-1.000=0.001精度=標(biāo)準(zhǔn)差=0.013準(zhǔn)確率：被測(cè)量的測(cè)量值與實(shí)際值之間的接近度準(zhǔn)確率依賴于精度和偏倚，他是一個(gè)一般化的概念37四、離群點(diǎn)某種意義上具有不同于數(shù)據(jù)集中其他大部分?jǐn)?shù)據(jù)對(duì)象的特征的數(shù)據(jù)對(duì)象離群點(diǎn)可以是合法的數(shù)據(jù)對(duì)象或值與噪聲不同，有時(shí)是人們感興趣的對(duì)象38五、遺漏值一個(gè)數(shù)據(jù)對(duì)象遺漏一個(gè)或多個(gè)屬性值信息收集不全屬性不能用于所有對(duì)象刪除數(shù)據(jù)對(duì)象或?qū)傩?，如遺漏數(shù)據(jù)對(duì)象很少估計(jì)遺漏值，如插值或最近鄰法在分析時(shí)忽略遺漏值，如忽略屬性計(jì)算相似度處理策略39六、不一致的值如地址字段包含城市和郵編，但是有的郵編區(qū)域不包含在城市中如人的身高出現(xiàn)了負(fù)值不一致的原因是次要的，重要的是檢測(cè)出來，并盡可能的更正七、重復(fù)數(shù)據(jù)通常，如兩個(gè)對(duì)象實(shí)際代表同一對(duì)象，則對(duì)應(yīng)的屬性值必然不同（為什么），必須解決不一致的值

需要避免將兩個(gè)相似但非重復(fù)的數(shù)據(jù)對(duì)象（如兩個(gè)人重名）合并若允許多個(gè)不同對(duì)象具有相同的屬性，則算法設(shè)計(jì)時(shí)需謹(jǐn)慎402.2、關(guān)于應(yīng)用的問題41從商業(yè)或科學(xué)的角度看只有當(dāng)數(shù)據(jù)適合預(yù)期應(yīng)用時(shí)，他才是高質(zhì)量的！

時(shí)效性：有些數(shù)據(jù)收集后就開始老化例如：顧客的購(gòu)買行為，WEB瀏覽模式

相關(guān)性：可用的數(shù)據(jù)必須包含應(yīng)用所需要的信息例如：預(yù)測(cè)交通事故發(fā)生率，忽略駕駛員的年齡和性別

例如：調(diào)查數(shù)據(jù)只反應(yīng)對(duì)調(diào)查做出響應(yīng)的人的意見（抽樣偏倚）

關(guān)于數(shù)據(jù)的知識(shí)：數(shù)據(jù)解釋文檔的好壞決定了他是否干擾分析例如：文檔說明屬性是強(qiáng)相關(guān)的，則說明屬性可能提供高度冗余的信息，我們可以只選擇一個(gè)屬性。若文檔沒有告訴我們某特定字段遺漏值用-9999表示，則數(shù)據(jù)分析就會(huì)出錯(cuò)。423、數(shù)據(jù)預(yù)處理43數(shù)據(jù)預(yù)處理的工作可以分為兩類（1）選擇分析所需要的數(shù)據(jù)對(duì)象和屬性（2）創(chuàng)建或改變屬性443.1、聚集45聚集：將兩個(gè)或多個(gè)對(duì)象或?qū)傩院喜閱我坏膶?duì)象或?qū)傩阅康模?）數(shù)據(jù)約減減少數(shù)據(jù)對(duì)象或?qū)傩缘臄?shù)目，從而可使用高復(fù)雜性算法（2）改變尺度

例如城市可以聚集為區(qū)域、省、以及國(guó)家（3）提高數(shù)據(jù)的穩(wěn)定性

對(duì)象或?qū)傩匀旱男袨橥ǔ１葐蝹€(gè)對(duì)象或?qū)傩缘男袨楦臃€(wěn)定

4647月降水量標(biāo)準(zhǔn)差直方圖年降水量標(biāo)準(zhǔn)差直方圖澳大利亞從1982到1993年月和年降水量的標(biāo)準(zhǔn)差直方圖483.2、抽樣49抽樣是一種選擇數(shù)據(jù)對(duì)象子集進(jìn)行分析的常用方法經(jīng)常被用于數(shù)據(jù)的事先調(diào)查和最終的數(shù)據(jù)分析

統(tǒng)計(jì)學(xué)中的意義

抽樣是因?yàn)榈玫礁信d趣的整個(gè)數(shù)據(jù)集的費(fèi)用太高、太費(fèi)時(shí)間

數(shù)據(jù)挖掘中的意義

抽樣是因?yàn)樘幚硭械臄?shù)據(jù)的費(fèi)用太高、太費(fèi)時(shí)間50

有效抽樣的定義如果樣本是有代表性的，則使用樣本與使用整個(gè)數(shù)據(jù)集的效果幾乎一樣樣本具有足夠的代表性的前提是它近似地具有與原數(shù)據(jù)集相同的感興趣的性質(zhì)

例子： 如果數(shù)據(jù)對(duì)象的均值是感興趣的性質(zhì)，則只要樣本具有近似于原數(shù)據(jù)集的均值，樣本就是有代表性的51簡(jiǎn)單隨機(jī)抽樣：選取任何特定項(xiàng)的概率相等

1、無放回隨機(jī)抽樣

每個(gè)選中項(xiàng)立即從構(gòu)成總體的所有對(duì)象集中刪除

2、有放回隨機(jī)抽樣

對(duì)象被選中時(shí)不從總體中刪除分層抽樣：將數(shù)據(jù)分為若干種類型，從各個(gè)類型中等概率抽取 數(shù)據(jù)對(duì)象各類中抽取相同個(gè)數(shù)的對(duì)象各類中抽取相同比例的對(duì)象一、抽樣方法有放回抽樣中，相同樣本可能被多次抽出，但是分析較為簡(jiǎn)單52抽樣與信息損失

2000Points500Points8000Points53如何確定樣本容量例：取數(shù)據(jù)點(diǎn)的一個(gè)小樣本，逐對(duì)計(jì)算點(diǎn)之間的相似性，然后形成高度相似的點(diǎn)組。然后從這些組每組取一個(gè)點(diǎn)，則可以得到具有代表性的點(diǎn)的集合。點(diǎn)的10個(gè)組樣本包含所有10個(gè)組中點(diǎn)的概率54 從小樣本開始，然后增加樣本容量直到得到足夠容量的樣本不需要在開始就確定正確的樣本容量需要評(píng)估樣本是否足夠大的方法例子：假定使用漸進(jìn)抽樣學(xué)習(xí)一個(gè)預(yù)測(cè)模型盡管預(yù)測(cè)模型的準(zhǔn)確率隨樣本容量增加，但是在某一點(diǎn)的準(zhǔn)確率的增加趨于穩(wěn)定通過掌握準(zhǔn)確率隨樣本逐漸增大的變化情況，并通過選取接近于當(dāng)前容量的其他樣本，估計(jì)于穩(wěn)定點(diǎn)的接近程度在穩(wěn)定點(diǎn)停止增加樣本容量二、漸進(jìn)抽樣553.3、維歸約56維災(zāi)難 隨著維度增加，數(shù)據(jù)在它所占據(jù)的空間中越來越稀疏對(duì)分類任務(wù)的影響沒有足夠的數(shù)據(jù)對(duì)象來創(chuàng)建模型對(duì)聚類任務(wù)的影響點(diǎn)之間的密度和距離的定義失去了意義隨機(jī)產(chǎn)生500個(gè)點(diǎn)計(jì)算點(diǎn)對(duì)之間的最大最小距離之間的差異57維歸約目的避免維災(zāi)難減少數(shù)據(jù)挖掘算法的時(shí)間與空間開銷便于模型的理解與數(shù)據(jù)的可視化刪除無關(guān)特征并降低噪聲技術(shù)主成分分析（PCA）奇異值分解（SVD）多維縮放（MDS）其他：有監(jiān)督方法或非線性方法58主成分分析目標(biāo)：找到捕獲數(shù)據(jù)最大變差的變換第一個(gè)維要盡可能多的捕獲數(shù)據(jù)的變異性第二個(gè)維要盡可能多的捕獲數(shù)據(jù)的剩余變異性，且與第一個(gè)維正交依次類推特性趨向于確定數(shù)據(jù)中最強(qiáng)的模式數(shù)據(jù)的大部分變異性通常都可以被整個(gè)維集合的一小部分新維所捕獲由于數(shù)據(jù)中的噪聲比模式弱，可以去掉許多噪聲59原數(shù)據(jù)點(diǎn)變換后的數(shù)據(jù)點(diǎn)60PCA步驟對(duì)原始數(shù)據(jù)預(yù)處理，使得每個(gè)屬性的均值都是0計(jì)算原始數(shù)據(jù)的屬性之間的協(xié)方差陣計(jì)算協(xié)方差陣的特征向量與特征值按特征值的大小對(duì)特征向量排序由前p個(gè)特征向量定義新的空間x2x1e1e261x2(0,0)(4,4)(3,1)(1,3)x1x2(-2,-2)(2,2)(1,-1)(-1,1)x1x2(-4,0)(4,0)(0,2)(0,-2)x162例:鳶尾花數(shù)據(jù)IRIS

每個(gè)主成分導(dǎo)致的方差所占的比例(斜坡圖)鳶尾話數(shù)據(jù)前兩個(gè)主成分上的散布圖6364MDS變種：ISOMAP根據(jù)原始數(shù)據(jù)，采用歐式距離構(gòu)建鄰域圖計(jì)算測(cè)地距，采用鄰域圖中的最短路徑來近似應(yīng)用經(jīng)典MDS65維歸約常見問題問題1:一種技術(shù)能夠產(chǎn)生相當(dāng)可靠的、數(shù)據(jù)的較低維的空間的表示嗎？這種表示能夠捕獲那些預(yù)期的應(yīng)用（如聚類）很重要的數(shù)據(jù)特征，而刪除不相關(guān)甚至有害的那些方面嗎（例如噪音）？答:這依賴于被維歸約方法分析的數(shù)據(jù)類型和數(shù)據(jù)分布66維歸約常見問題問題2:

維歸約算法的空間和時(shí)間復(fù)雜度如何?答:很不幸，大部分算法的時(shí)間和空間復(fù)雜度都很高。盡管抽樣有時(shí)是有效的，但這仍然限制了維歸約算法的可用性67維歸約常見問題問題3:

維歸約算法每次運(yùn)行的結(jié)果是否相同?答:PCA、SVD、LLE的結(jié)果是相同的因子分析和MDS可能會(huì)產(chǎn)生不一樣的結(jié)果很多其他技術(shù)也采用優(yōu)化搜索，因此可能陷入局部極小

68維歸約常見問題問題4:

如何確定維歸約的維數(shù)?答:可以采用斜坡圖等方法來測(cè)量維歸約的質(zhì)量有時(shí)這些曲線清楚的指示了固有的維度。有時(shí)需要在維數(shù)較少但是近似誤差較大和近似誤差較小但是維數(shù)更多之間權(quán)衡。693.4、特征子集的選擇70特征子集選擇是減少數(shù)據(jù)維度的另一種方式1、冗余特征重復(fù)了包含在一個(gè)或多個(gè)其他屬性中的許多或所有信息 例如： 一種產(chǎn)品的購(gòu)買價(jià)格和所支付的銷售稅額包含許多相同的信息2、不相關(guān)特征包含對(duì)手頭的數(shù)據(jù)挖掘任務(wù)幾乎無用的信息 例如： 學(xué)生的ID號(hào)碼對(duì)于預(yù)測(cè)學(xué)生的總平均成績(jī)是不相關(guān)的71特征子集選擇方法1、基于領(lǐng)域知識(shí)或常識(shí)的方法2、窮舉法（理想算法）

將所有可能的特征子集作為感興趣的數(shù)據(jù)挖掘算法的輸入，然后選取產(chǎn)生最好結(jié)果的子集3、其他（重點(diǎn)）嵌入法：特征子集選擇算法作為數(shù)據(jù)挖掘算法的一部分自然存在

例：決策樹算法過濾法：使用某種獨(dú)立于數(shù)據(jù)挖掘任務(wù)的方法，在數(shù)據(jù)挖掘算法運(yùn)行前進(jìn) 行特征選擇

例：選擇屬性對(duì)之間相關(guān)度低的屬性集合。包裝法：將目標(biāo)數(shù)據(jù)挖掘算法作為黑盒，使用類似理想算法的方法，但并 不枚舉所有可能72一、特征子集選擇體系結(jié)構(gòu)1、子集評(píng)估度量過濾法：不同于數(shù)據(jù)挖掘算法，預(yù)測(cè)實(shí)際數(shù)據(jù)挖掘算法的效果包裝法：直接使用目標(biāo)數(shù)據(jù)挖掘算法2、控制新的特征子集產(chǎn)生的搜索策略3、停止搜索判斷4、驗(yàn)證過程選擇的屬性停止判斷評(píng)估搜索策略屬性子集屬性集驗(yàn)證過程滿足不滿足73搜索策略計(jì)算花費(fèi)較低

vs

可找到最優(yōu)或近似最優(yōu)的特征子集停止搜索迭代次數(shù)子集評(píng)估度量值是否優(yōu)于閾值是否得到特定大小的子集大小和評(píng)估度量是否同時(shí)達(dá)到搜索得到的結(jié)果是否還有改進(jìn)驗(yàn)證過程全部特征集結(jié)果與選擇的特征子的結(jié)果進(jìn)行比較使用不同的特征選擇算法，比較數(shù)據(jù)挖掘算法在每個(gè)子集上的運(yùn)行結(jié)果74二、特征加權(quán)特征越重要，賦予的權(quán)值越大根據(jù)領(lǐng)域知識(shí)確定自動(dòng)確定 例：支持向量機(jī)，產(chǎn)生分類模型，對(duì)每個(gè)特征賦予權(quán)值計(jì)算余弦相似度時(shí)對(duì)數(shù)據(jù)對(duì)象進(jìn)行規(guī)范化753.5、特征創(chuàng)建76

特征創(chuàng)建由原來的屬性集創(chuàng)建新的屬性集，更有效的捕獲數(shù)據(jù)集的信息

特征創(chuàng)建包含三種相關(guān)方法特征提取領(lǐng)域相關(guān)知識(shí)映射數(shù)據(jù)到新的空間特征構(gòu)造組合特征

特征創(chuàng)建是增加特征！77一、特征提取由原始數(shù)據(jù)集創(chuàng)建新的特征集稱作特征提取最常用的特征提取技術(shù)都是高度針對(duì)具體領(lǐng)域的，如圖像處理。一旦數(shù)據(jù)挖掘用于一個(gè)全新的領(lǐng)域，一個(gè)關(guān)鍵任務(wù)就是開發(fā)新的特征和新的特征提取方法例：按照照片的集合中是否包含人臉進(jìn)行分類 圖像的原始數(shù)據(jù)是像素的集合，無法直接應(yīng)用分類算法。需提取高層次特征，如與人臉相關(guān)的的邊和區(qū)域78二、映射數(shù)據(jù)到新空間正弦波+噪聲如：傅立葉變換、小波變換

雙正弦波頻域圖79三、特征構(gòu)造

原始數(shù)據(jù)集的特征包含必要的信息，但形式不適合數(shù)據(jù)挖掘。由原特征構(gòu)造新特征可能會(huì)更有效例： 考慮一個(gè)包含人工制品信息的歷史數(shù)據(jù)集。該數(shù)據(jù)集包含每個(gè)人工制品的體積和質(zhì)量，以及其他信息。為簡(jiǎn)單起見，假定這些人工制品使用少量材料（木材，陶土，銅，黃金）制造，并且我們希望根據(jù)制造材料對(duì)它們分類。由質(zhì)量和體積體征構(gòu)造的密度特征（即密度=質(zhì)量/體積）可以很直接的產(chǎn)生準(zhǔn)確的分類。體積質(zhì)量制造材料2.331.2黃金32.1150陶土0.79.1銅110.290.7木材7.9102.7銅………體積質(zhì)量密度制造材料2.339.117黃金32.11504.67陶土0.79.113銅110.290.70.82木材7.9102.713銅………803.6、離散化和二元化81問題：某些算法，特別是分類算法，要求數(shù)據(jù)是分類屬性形式發(fā)現(xiàn)關(guān)聯(lián)模式的算法，要求數(shù)據(jù)是二元屬性形式若分類屬性具有大量不同類別，或某些類別出現(xiàn)不頻繁。則對(duì)某些數(shù)據(jù)挖掘任務(wù)，通過合并值減少類別數(shù)目可能是有益的離散化：將連續(xù)屬性變換為分類屬性二元化：將連續(xù)和離散屬性變換為一個(gè)或多個(gè)二元屬性目標(biāo)：對(duì)于用來分析數(shù)據(jù)的數(shù)據(jù)挖掘算法，產(chǎn)生最好結(jié)果82一、二元化如果有m個(gè)分類值，則將每個(gè)值唯一地賦予區(qū)間[0,m-1]中的一個(gè)整數(shù)即使屬性原本為整數(shù)，若不在區(qū)間[0,m-1]中，該過程必須執(zhí)行若屬性是有序的，則賦值必須保持序關(guān)系將m個(gè)整數(shù)的每一個(gè)都變換成一個(gè)二進(jìn)制數(shù)，二進(jìn)制位的總數(shù)為分類值整數(shù)值x1x2x3awful0000poor1001OK2010good3011great4100分類值整數(shù)值x1x2x3x4x5awful010000poor101000OK200100good300010great40000183二、離散化將連續(xù)屬性排序后，通過指定n-1個(gè)分割點(diǎn)把他們分成n個(gè)區(qū)間將一個(gè)區(qū)間中的所有值映射到所有的分類值非監(jiān)督離散化：在離散化時(shí)不考慮類信息監(jiān)督離散化：離散化時(shí)應(yīng)用類信息84原始數(shù)據(jù)等寬離散化等頻率離散化K均值離散化非監(jiān)督離散化85有監(jiān)督離散化一種概念上簡(jiǎn)單的方法是以極大化區(qū)間純度的方式確定分割點(diǎn)缺點(diǎn)：需人為確定區(qū)間的純度和最小區(qū)間的大小一種基于熵的離散化方法 設(shè)k是不同的類標(biāo)號(hào)數(shù)，mi是某劃分的第i個(gè)區(qū)間中的值的個(gè)數(shù)，而mij是 區(qū)間i中類j的值的個(gè)數(shù)。第i個(gè)區(qū)間的熵ei

其中pij=mij

/mi是第i個(gè)區(qū)間中類j的概率（比例）。該劃分的總熵是每個(gè) 區(qū)間的熵的加權(quán)平均，即 其中，m是值的個(gè)數(shù)，wi=mi/m是第i個(gè)區(qū)間的值的比例，n是區(qū)間個(gè)數(shù)86將初始值切分成兩部分，讓兩個(gè)結(jié)果區(qū)間產(chǎn)生最小的熵取具有最大熵的區(qū)間，重復(fù)分割過程指導(dǎo)區(qū)間的個(gè)數(shù)達(dá)到用戶制定的個(gè)數(shù)或滿足終止條件三個(gè)區(qū)間五個(gè)區(qū)間特點(diǎn)（1）各個(gè)維分別離散化通常只保證次最優(yōu)的結(jié)果（2）多區(qū)間的結(jié)果更好，但是區(qū)間增多的結(jié)果對(duì)離散化的改善不大873.7、屬性變換88 屬性變換將整個(gè)數(shù)據(jù)集中某一屬性的所有值都利用一個(gè)函數(shù)變換為新的值簡(jiǎn)單函數(shù)變換:xk,log(x),ex,|x|用途舉例：將不具有正態(tài)分布的數(shù)據(jù)變?yōu)榫哂姓龖B(tài)分布的數(shù)據(jù)在入侵檢測(cè)中，利用對(duì)數(shù)變換對(duì)數(shù)據(jù)進(jìn)行壓縮后比較（108與109比10和1000更相似）注意：因改變了數(shù)據(jù)特性，需結(jié)合應(yīng)用分析，必須對(duì)數(shù)據(jù)特性了解問題：需要保序嗎？變換作用于所有值嗎？對(duì)0和1之間的值有什么影響？標(biāo)準(zhǔn)化或規(guī)范化

問題舉例：使用年齡和收入兩個(gè)屬性來對(duì)人進(jìn)行比較對(duì)相似度的影響可用中位數(shù)取代均值可用絕對(duì)標(biāo)準(zhǔn)差取代標(biāo)準(zhǔn)差894、相似性和相異性度量909192問題:

你是如何來判斷他們是否相似的？934.1、定義與變換94相似度兩個(gè)對(duì)象相似程度的數(shù)值度量?jī)蓚€(gè)對(duì)象越相似，相似度就越高相似度非負(fù)，并在[0,1]區(qū)間內(nèi)取值相異度（距離）兩個(gè)對(duì)象差異程度的數(shù)值度量?jī)蓚€(gè)對(duì)象越相似，相異就越高相異度在區(qū)間[0,1]，或區(qū)間[0,∞]中取值鄰近度可以表示相似度或相異度95變換 變換通常用來把相似度轉(zhuǎn)換為相異度或者是相反,或者把鄰近度轉(zhuǎn)換到一個(gè)特定的區(qū)間,如[0,1]。一般為單調(diào)函數(shù)。例: 有相似度區(qū)間為[1,10]。但是我們準(zhǔn)備使用的數(shù)據(jù)挖掘算法或軟件包只能處理[0,1]區(qū)間的相似度。一般來說相似度區(qū)間[min,max]到[0,1]區(qū)間的變換由下式給出相似度←相似度/相異度←相異度 單調(diào)增函數(shù)相似度←相異度/相異度←相似度 單調(diào)減函數(shù)96 但是，鄰近度的區(qū)間變換有時(shí)可能非常復(fù)雜例1：相異度原來的區(qū)間在[0，∞]區(qū)間上，映射到[0，1]區(qū)間考慮采用下面這種變換好不好？00.5210100100000.330.670.900.990.999例2：相關(guān)性是一種相似度度量，在[-1,1]上取值，映射到[0,1]區(qū)間考慮采用下面這種變換好不好？97若需把相異度通過負(fù)變換映射到相似度01101000-1-10-10010.50.090.011.000.370.000.001.000.990.900.0098問題:

給定一個(gè)在區(qū)間[0,1]取值的相似性度量，描述將該相似度變換到區(qū)間[0,∞]的方法994.2、單個(gè)屬性對(duì)象之間的鄰近度100例1：學(xué)號(hào)ID為1001201和學(xué)號(hào)ID為1001211之間的相似度和相 異度是多少？例2：考慮在標(biāo)度{poor,fair,OK,good,wonderful}上測(cè)量糖 塊質(zhì)量的屬性。請(qǐng)問評(píng)定為wonderful的產(chǎn)品p1和評(píng)定為 fair的產(chǎn)品p2之間的相似度和相異度是多少？例3：考慮某人現(xiàn)在體重110公斤，一年前體重100公斤，其相似 度和相異度是多少？101p

和q

是兩個(gè)數(shù)據(jù)對(duì)象的屬性值.1024.3、數(shù)據(jù)對(duì)象之間的相異度103104歐式距離

n是維度，pk

與qk

分別是向量p和q的第k個(gè)分量若尺度不同，必須進(jìn)行標(biāo)準(zhǔn)化105106距離矩陣107閔可夫斯基距離歐式距離的推廣

r是參數(shù),n是維度，pk

與qk

分別是向量p和q的第k個(gè)分量108閔氏距離的例子r=1.城市街區(qū)距離（曼哈頓距離）一個(gè)常見的例子是漢明距離，他是具有二元屬性的對(duì)象之間的不同的二進(jìn)制位數(shù)r=2.歐氏距離r

.上確界距離(Lmax

范數(shù),L

范數(shù))

109閔可夫斯基距離矩陣110Mahalanobis距離紅色點(diǎn)的

歐式距離為14.7，而馬氏距離則為6

是輸入數(shù)據(jù)

X的協(xié)方差適用范圍：屬性相關(guān)、值域不同、正態(tài)分布缺陷：高時(shí)間復(fù)雜度111協(xié)方差矩陣:BACA:(0.5,0.5)B:(0,1)C:(1.5,1.5)Mahal(A,B)=5Mahal(A,C)=4112距離，尤其是歐式距離，具有下列性質(zhì)非負(fù)性，d(p,q)

0

，當(dāng)且僅當(dāng)p

=q時(shí)d(p,q)=0

對(duì)稱性，d(p,q)=d(q,p)

三角不等式：d(p,r)

d(p,q)+d(q,r)

同時(shí)滿足以上三個(gè)性質(zhì)的距離稱為度量定義時(shí)間之間的距離測(cè)度如下,請(qǐng)判斷是否為度量若不是度量，這個(gè)例子是否有意義？1134.4、數(shù)據(jù)對(duì)象之間的鄰近度114二值向量之間的相似度當(dāng)向量p和q只擁有二值屬性時(shí)，可采用下面的計(jì)量來測(cè)量相似度

M01

=p是0，q是1的屬性的數(shù)目

M10=p是1，q是0的屬性的數(shù)目

M00

=p是0，q是0的屬性的數(shù)目

M11

=p是1，q是1的屬性的數(shù)目簡(jiǎn)單匹配系數(shù)與Jaccard

系數(shù)SMC系數(shù)=

匹配數(shù)/屬性數(shù)

=(M11+M00)/(M01+M10+M11+M00)Jaccard系數(shù)

=11匹配數(shù)/非00匹配數(shù)=(M11)/(M01+M10+M11)115SMCvs

Jaccardp=1000000000

q=0000001001

M01=2(thenumberofattributeswherepwas0andqwas1)M10=1(thenumberofattributeswherepwas1andqwas0)M00=7(thenumberofattributeswherepwas0andqwas0)M11=0(thenumberofattributeswherepwas1andqwas1)

SMC=(M11+M00)/(M01+M10+M11+M00)=(0+7)/(2+1+0+7)=0.7

J=(M11)/(M01+M10+M11)=0/(2+1+0)=0116廣義Jaccard系數(shù)將Jaccard

系數(shù)推廣到連續(xù)或離散屬性當(dāng)該公式處理二元屬性時(shí)，退化為Jaccard系數(shù)117余弦相似度

若d1和d2

為兩個(gè)文本向量，則定義余弦相似度如下 例：

d1

=3205000200 d2=1000000102

d1

d2=3*1+2*0+0*0+5*0+0*0+0*0+0*0+2*1+0*0+0*2=5||d1||=(3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5=(42)0.5=6.481||d2||=(1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2)

0.5

=(6)0.5=2.245

cos(d1,d2)=0.315118相關(guān)性相關(guān)性是兩個(gè)對(duì)象之間的線性關(guān)系的度量

首先標(biāo)準(zhǔn)化數(shù)據(jù)對(duì)象p和q,然后計(jì)算它們的點(diǎn)積例: 下面的例子中，數(shù)據(jù)對(duì)象的屬性之間存在非線性關(guān)系yk=xk2

試計(jì)算其相關(guān)性

x=(-3,-2,-1,0,1,2,3) y=(9,4,1,0,1,4,9)119相關(guān)性可視化1204.5、異種對(duì)象之間的相似度121問題:

請(qǐng)問下面這兩個(gè)對(duì)象之間的相似度是多少