數(shù)據(jù)挖掘總結(jié)

【p261.3】假設(shè)你是BigUniversity的軟件工程師，任務(wù)是設(shè)計一個數(shù)據(jù)挖掘系統(tǒng)，分析學(xué)校課程數(shù)據(jù)庫。該數(shù)據(jù)庫包括如下信息：每個學(xué)生的姓名、地址和狀態(tài)（例如本科生或研究生）所修課程以及他們的GPA（平均積分點(diǎn)）。描述你要選取的結(jié)構(gòu)。該結(jié)構(gòu)的每個成分的作用是什么。答：該數(shù)據(jù)挖掘結(jié)構(gòu)應(yīng)該包括以下幾個主要成分：（1）一個數(shù)據(jù)庫、數(shù)據(jù)倉庫或其它信息庫，它由一系列包含學(xué)生和課程信息的數(shù)據(jù)庫、數(shù)據(jù)倉庫、電子表格、或其它信息庫組成。（2）一個數(shù)據(jù)庫或數(shù)據(jù)倉庫服務(wù)器，它根據(jù)用戶的數(shù)據(jù)挖掘請求獲取相關(guān)的數(shù)據(jù)。（3）一個知識庫，它包含領(lǐng)域知識，用于指導(dǎo)搜索或評估結(jié)果模式的興趣度。例如，知識庫可能包含概念層次結(jié)構(gòu)和元數(shù)據(jù)（例如，描述來自多個異構(gòu)數(shù)據(jù)源的數(shù)據(jù)）。（4）一個數(shù)據(jù)挖掘引擎，它由一系列負(fù)責(zé)分類、關(guān)聯(lián)、聚類分析、演變和偏差分析的功能模塊組成。（5）一個模式評估模塊，它與數(shù)據(jù)挖掘模塊串聯(lián)工作，采用興趣度的方法，將搜索重心投注在興趣模式上。（6）一個圖形用戶界面，它為用戶提供對數(shù)據(jù)挖掘系統(tǒng)的交互式途徑。【p632.4】中列數(shù)是最大值和最小值的平均數(shù)。五數(shù)概括就是中位數(shù)、四分位數(shù)Q1和Q3、最小值和最大值箱線圖（盒圖）在p35分位數(shù)圖是一種觀察單變量數(shù)據(jù)分布的簡單有效方法，他顯示給定屬性的所有數(shù)據(jù)（允許用戶評估總的情況和不尋常的出現(xiàn)）。其次它繪出了分位數(shù)信息【p632.5】問：以計數(shù)、標(biāo)準(zhǔn)差和中位數(shù)為例說明分布的或代數(shù)的度量有利于有效的增量計算，而整體度量不行。答：計數(shù)：當(dāng)前的計數(shù)count可以作為一個值來保存，當(dāng)有x個新值加進(jìn)來時，可以很容易地更新count值為（count+x）。這就是分布式度量，可以很容易地進(jìn)行增量計算。標(biāo)準(zhǔn)差：如果我們之前存儲了已有數(shù)據(jù)平方的和sum和它們的計數(shù)count，就可以很容易地利用公式得到新的標(biāo)準(zhǔn)差，只需要計算新加入數(shù)據(jù)平方的和并將其加入sum中，同時更新count值，隨后將它們插入計算中就可獲得新的標(biāo)準(zhǔn)差。這些都不用重新掃描整個數(shù)據(jù)集而可以輕松得到。這就是代數(shù)度量，可以容易進(jìn)行增量計算。中位數(shù)：要準(zhǔn)確得到中位數(shù)必須掃描整個數(shù)據(jù)集。當(dāng)加入了新的數(shù)據(jù)后必須重新進(jìn)行排序，然后在新的排序后的數(shù)據(jù)集中查找中位數(shù)。這是比較困難的，這就是整體度量，沒辦法對增量進(jìn)行有效的計算。4.【p632.6】數(shù)據(jù)缺省值處理（1）忽略元組。當(dāng)缺少類標(biāo)號時通常這樣做（假定挖掘任務(wù)涉及分類）。除非元組有多個屬性缺少值，否則該方法不是很有效。當(dāng)每個屬性缺少值的百分比變化很大時，它的性能特別差。（2）人工填寫缺失值。一般該方法很費(fèi)時，并且當(dāng)數(shù)據(jù)集很大，缺少很多值時，該方法可能行不通。（3）使用一個全局常量填充缺失值。將缺失的屬性值用同一個常數(shù)（如“Unknown”替換如果缺失值都用“Unknown”替換，則挖掘程序可能誤以為它們形成了一個有趣的概念，因?yàn)樗鼈兌季哂邢嗤闹怠癠nknown”。因此，盡管該方法簡單，但是它并不是十分可靠。（4）使用屬性的均值填充缺失值。（5）使用與給定元組屬同一類的所有樣本的屬性均值。（6）使用最可能的值填充缺失值?？梢杂没貧w、使用貝葉斯形式化的基于推理的工具或決策樹歸納確定?！緋632.7】（1）問：使用分箱均值光滑對數(shù)據(jù)進(jìn)行光滑的步驟（深度為3）答：①對數(shù)據(jù)進(jìn)行排序；②將數(shù)據(jù)劃分到大小為3的等頻箱中；③計算每個箱的均值；④箱中的值都被箱的均值替換。（2）問：如何確定數(shù)據(jù)中的離群點(diǎn)答：可以通過聚類來檢測離群點(diǎn)，將類似的值組織成群或簇。直觀地，落在簇集合之外的值視為離群點(diǎn)。電腦和人的檢查可以結(jié)合來判斷，先由電腦根據(jù)已有的數(shù)據(jù)分布狀況得出可能的離散點(diǎn)，然后再由人來對這些可能的離散點(diǎn)進(jìn)行進(jìn)一步的分析來確定離散點(diǎn)，這樣大大地減少了人單獨(dú)工作的工作量。（3）問：對于數(shù)據(jù)光滑還有哪些方法答：類似的還有分箱中位數(shù)光滑，此時箱中的每一個值都被箱中位數(shù)替換。分箱邊界光滑，箱中的最大和最小值同樣被視為箱邊界，箱中的每個值都被最近的邊界值替換。一般來說，寬度越大光滑效果越大。箱可以是等寬的，每個箱值的區(qū)間范圍是個常量。此外可以用一個函數(shù)（如回歸函數(shù)）擬合數(shù)據(jù)來光滑數(shù)據(jù)。線性回歸涉及找出擬合兩個屬性的最佳線，使得一個屬性可以用來預(yù)測另一個。多元線性回歸是線性回歸的擴(kuò)展，其中涉及的屬性多于兩個，并且數(shù)據(jù)擬合到一個多維曲面。概念分層也可以用于數(shù)據(jù)光滑?！緋632.8】問：數(shù)據(jù)集成需要考慮的問題答：①實(shí)體識別問題。模式集成和對象匹配需要技巧，來自多個信息源的現(xiàn)實(shí)世界的等價實(shí)體必須能夠匹配。②數(shù)據(jù)冗余。一個屬性可能是冗余的，如果它能由另一個或另一組屬性“導(dǎo)出”屬性或命名的不一致也可能導(dǎo)致結(jié)果數(shù)據(jù)集中的冗余。③數(shù)據(jù)值沖突的檢測與處理。對于現(xiàn)實(shí)世界的同一實(shí)體，來自不同數(shù)據(jù)源的屬性值可能不同，這可能是因?yàn)楸硎?、比例或編碼不同?！緋632.9】（1）方差公式a2=^Zx]24（Zx]）2]2）散布圖：將每個值當(dāng)做坐標(biāo)對畫點(diǎn)qq圖：將數(shù)據(jù)都按遞增序排序，然后畫點(diǎn)3）z-score規(guī)范化（零均值規(guī)范化）屬性（數(shù)值減去均值除以標(biāo)準(zhǔn)差）2323272739414749SOz-agc-1.83-1.83-LSI-1.51-0.58-0420.040.200.28%fat7.817.831.427.427.231.2-2.U-0.25-2.33-1.220.29-0.32-0.15-0.1S0.275254S4575858GOG14ageCM30.59Q590.740.820.90O.SOLOGL13%fat34.G妞52&833J30.234.132.941.235.70^-651.530.00.510.160E90.4GL38077（4）答案是0.82，非常相關(guān)?？ǚ綑z驗(yàn)公式其中oij是實(shí)際計數(shù)，eij是期望頻度。count(A=count(A=ai)*count(B=bj)【p632.12】（1）最小最大規(guī)范化v—minAmaxA—minAv—minAmaxA—minA(new^A-newminA)+new_min^（2）小數(shù)定標(biāo)規(guī)范化，移動小數(shù)點(diǎn)位置進(jìn)行規(guī)范，移動位數(shù)取決于最大絕對值。（3）更愿用哪種規(guī)范方法？。小數(shù)定標(biāo)。???保持了數(shù)據(jù)的結(jié)構(gòu)并且是直觀表達(dá)并仍然可以在age的組內(nèi)進(jìn)行挖掘。最大最小有一個多余的功能就是禁止了任何未來值落在現(xiàn)在的最小最大值之外，沒有考慮到“越界錯誤”而未來的數(shù)據(jù)里可能出現(xiàn)。Z-score用標(biāo)準(zhǔn)差表示數(shù)據(jù)到平均值的距離，不像小數(shù)定標(biāo)那樣直觀?！緋973.2】（1）雪花型模式、事實(shí)星座形、星形網(wǎng)查詢模型雪花型模式和事實(shí)星座形都是星形模式的變種。雪花型模式的維表可能是規(guī)范化形式，以便減少冗余；事實(shí)星座形模式允許事實(shí)表共享維表。星形網(wǎng)查詢模型由中心點(diǎn)發(fā)出的射線組成，其中每條射線代表一個維的概念分層，而概念分層的每個抽象級稱為一個腳印，代表諸如上卷、下鉆等OLAP操作可用的粒度。（2）數(shù)據(jù)清理、數(shù)據(jù)變換、刷新數(shù)據(jù)清理：檢測數(shù)據(jù)中的錯誤，可能時訂正它們。數(shù)據(jù)變換：將數(shù)據(jù)由遺產(chǎn)或宿主格式轉(zhuǎn)換成數(shù)據(jù)倉庫格式。刷新：傳播由數(shù)據(jù)源到數(shù)據(jù)倉庫的更新。（3）企業(yè)數(shù)據(jù)倉庫、數(shù)據(jù)集市、虛擬倉庫企業(yè)數(shù)據(jù)倉庫收集了整個組織關(guān)于主題的所有信息，它提供企業(yè)范圍內(nèi)的數(shù)據(jù)集成，通常來自一個或多個操作數(shù)據(jù)庫系統(tǒng)或外部信息提供者，并且是跨功能的。通常，它包含細(xì)節(jié)數(shù)據(jù)和匯總數(shù)據(jù)，其大小有數(shù)千兆字節(jié)到數(shù)百千兆字節(jié)到更多。它可以在傳統(tǒng)的大型機(jī)、超級計算機(jī)服務(wù)器或并行結(jié)構(gòu)平臺上實(shí)現(xiàn)。它需要廣泛的商務(wù)建模，可能需要多年設(shè)計和建設(shè)。數(shù)據(jù)集市包含企業(yè)范圍數(shù)據(jù)的一個子集，對于特定的用戶群是有用的。其范圍限于選定的主題。包括在數(shù)據(jù)集市的數(shù)據(jù)通常是匯總的。它可以再低價格的部門服務(wù)器上實(shí)現(xiàn)，基于UNIX/LINUX或Windows。它的實(shí)現(xiàn)周期一般是一周計，而不是以月計或以年計。然而如果它的設(shè)計或規(guī)劃不是企業(yè)范圍的從長遠(yuǎn)講可能涉及很復(fù)雜的集成。獨(dú)立數(shù)據(jù)集市數(shù)據(jù)來自一個或多個操作系統(tǒng)或外部信息提供者，或者在特定的部門或地域局部產(chǎn)生的數(shù)據(jù)；依賴的數(shù)據(jù)集市的數(shù)據(jù)直接來自企業(yè)數(shù)據(jù)倉庫。虛擬倉庫是操作數(shù)據(jù)庫視圖的集合。為了有效地處理查詢，只有一些可能的匯總視圖可以物化。虛擬倉庫易于建立，但需要操作數(shù)據(jù)庫服務(wù)器具有剩余能力?！緋983.4】（1）雪花型模式圖

求每個學(xué)生CS課程的平均成績，OLAP操作①在course維表中由course_id上卷到department②在student維表中由student_id上卷到university③按如下選擇對中心立方體切塊：(department=求每個學(xué)生CS課程的平均成績，OLAP操作①在course維表中由course_id上卷到department②在student維表中由student_id上卷到university③按如下選擇對中心立方體切塊：(department=“CS”)and如果每維有5層，則立方體包含54=625個方體【p983.5】(1)觀看節(jié)目的星形模式圖university=“BigUniversity”)(latesalesfacttabkspectatordimensiontabledateiddateiddayspectatoridlllOlltll/gameidquarter/locationidvear//count/chaisediineusioutablegameidgamediineusioutablelocationdimensiontfiblephoneaddressstatusspectatoridgaiiieiiainepioducer1ccntici〕_idlocaTioiinairL亡phone*streetcityprovincecountryFigure3,3:Astarschemafordata,warehouseofExercise3.5.(2)列出2004年學(xué)生觀眾GM-Place的總付費(fèi)，需要采用哪些OLAP。在date上由date_id上卷至Uyear；在game上由game_id上卷至Uall；在location上由location_id上卷到location_name；在spectator上由spectator_id上卷到status；按以下選擇進(jìn)行切塊：(status=“student”)and(location=“GM_Place”)and(year=2004)(3)位圖索引結(jié)構(gòu)的優(yōu)點(diǎn)和問題。對于基數(shù)較小的域，位數(shù)索引非常有用，因?yàn)楸容^、連接和聚集操作都變成了位算術(shù)運(yùn)算，大大減少了處理時間。由于字符串可以用單個二進(jìn)位表示，位圖索引顯著降低了空間和I/O開銷。對于基數(shù)較高的域，需要使用壓縮技術(shù)才可以使用這個技術(shù)，就像例子中的date，這個位向量是非常長的，十年收集的數(shù)據(jù)就會得到3650條日期記錄，也就意味著date位向量有3650個二進(jìn)位?！緋983.6】簡略討論星形模式和雪花型模式的相似點(diǎn)和不同點(diǎn)，分析相對優(yōu)缺點(diǎn)。哪種模式更實(shí)用，給出觀點(diǎn)并陳述理由。答：相似點(diǎn)：他們都有一個事實(shí)表和多個維表。主要區(qū)別：雪花型模式有些維表是規(guī)范的，把數(shù)據(jù)進(jìn)一步分解到附加的表中。星形模式的優(yōu)點(diǎn)是非常簡易，使得操作有效率。但它需要更多的空間。雪花型模式易于維護(hù)并節(jié)省存儲空間。但是與巨大的事實(shí)表相比，這種空間的節(jié)省可以忽略，由于執(zhí)行查詢需要更多的連接操作，它可能降低瀏覽的性能。因此星形模式更實(shí)用，因?yàn)橹灰枵加玫目臻g不是特別大，效率是要比空間優(yōu)先考慮的。在一些工廠里，有時會將雪花型模式中的數(shù)據(jù)轉(zhuǎn)換成星形模式來加速處理過程?！緋973.9】（1）列出度量的三種類型度量可以根據(jù)所用的聚集函數(shù)類型分成三類，即分布的、代數(shù)的和整體的（2）方差屬于哪一類，如果數(shù)據(jù)分成了塊，描述怎么計算答：方差屬于代數(shù)的。如果立方體被分割成了一些塊，方差可以照以下步驟求得：首先挨個讀出每個塊中的數(shù)據(jù)，同時累加元組求得xi2的和xi的和。當(dāng)讀完所有塊的數(shù)據(jù)后，計算xi的均值，之后按提示中給出的公式進(jìn)行求解即可得到方差。（3）函數(shù)是最高的10個銷售額，如何有效地計算該度量。對于每個方體，用10個單位來存儲目前最高的10個銷售額。讀取每個方體中的數(shù)據(jù)，如果某個元組中的銷售額比存儲的最高的10個銷售額中的一個高，就將該銷售額加入到最高的10個銷售額列表中，同時剔除原列表中最小的那個數(shù)據(jù)。通過該操作的不斷循環(huán)執(zhí)行，最終可以得到最高的10個銷售額?！緋973.14】三種主要的數(shù)據(jù)倉庫應(yīng)用：信息處理、分析處理和數(shù)據(jù)挖掘的區(qū)別是什么。討論OLAP挖掘（OLAM）動機(jī)答：信息處理支持查詢、基本的統(tǒng)計分析，并使用交叉表、表、圖表或圖進(jìn)行報告。分析處理支持基本的OLAP操作，包括切片與切塊、下鉆、上卷和轉(zhuǎn)軸。一般對匯總和詳細(xì)歷史數(shù)據(jù)操作，支持?jǐn)?shù)據(jù)倉庫數(shù)據(jù)的多維數(shù)據(jù)分析。數(shù)據(jù)挖掘支持知識發(fā)現(xiàn)，包括找出隱藏的模式和關(guān)聯(lián)，構(gòu)造分析模型，進(jìn)行分類和預(yù)測，并使用可視化工具提供挖掘結(jié)果。OLAM的動機(jī)有以下幾點(diǎn)：①數(shù)據(jù)倉庫中數(shù)據(jù)的高質(zhì)量。經(jīng)過預(yù)處理而構(gòu)造的數(shù)據(jù)倉庫不僅用作OLAP，而且也用作數(shù)據(jù)挖掘的有價值的數(shù)據(jù)源。②環(huán)繞數(shù)據(jù)倉庫的信息處理基礎(chǔ)設(shè)施。全面的數(shù)據(jù)處理和數(shù)據(jù)分析基礎(chǔ)設(shè)施已經(jīng)或?qū)⒁獓@數(shù)據(jù)倉庫而系統(tǒng)地建立，謹(jǐn)慎的做法就是盡量利用可用的基礎(chǔ)設(shè)施，不是一切從頭做起。③基于OLAP的探測式數(shù)據(jù)分析。有效的數(shù)據(jù)挖掘需要探測式數(shù)據(jù)分析。用戶常常想遍歷數(shù)據(jù)庫，選擇相關(guān)數(shù)據(jù)，在不同粒度上分析它們，并以不同的形式提供知識/結(jié)果。④數(shù)據(jù)挖掘功能的聯(lián)機(jī)選擇。用戶常常不知道挖掘什么類型的知識，通過將OLAP與多種數(shù)據(jù)挖掘功能集成在一起，為用戶選擇所期望的數(shù)據(jù)挖掘功能，動態(tài)改變數(shù)據(jù)挖掘任務(wù)提供了靈活性?！緋1775.1】（1）項(xiàng)集s的任意非空子集亡的支持度至少和s的支持度一樣大

令D為相關(guān)事務(wù)數(shù)據(jù)，|D|為事務(wù)的數(shù)量。通過定義知support(s)=support_count(s)/|D|設(shè)s'為s的任意非空子集。通過定義得support(s')=support_count(s')/|D|因?yàn)閟upport_count(S)>=support_count(s),所以supports')>=support(s)。給定頻繁項(xiàng)集l和I的子集s,證明“s'=>(l-s')”的置信度不可能大于“s=>(l-s)”的置信度，其中s'是s的子集。答：令s是l的一個子集，則confidence(s=>(l-s))=support(l)/support(s)令s'是s的一個子集，則confidence(s=>(IY))=support(l)/support(s')因?yàn)閟upport(s)>=support(s)，所以confidence^'=>(l-s'))<=confidence(s=>(l-s))apriori的一種變形將事務(wù)數(shù)據(jù)庫D中的事務(wù)劃分成n個不重疊的部分，證明在D中頻繁的任何項(xiàng)集至少在D的一個部分中是頻繁的。答：假設(shè)頻繁項(xiàng)集在D的任何部分中都不頻繁。設(shè)F為D的任何頻繁項(xiàng)集。令D是相關(guān)事務(wù)數(shù)據(jù)集。令C是D中事務(wù)的總數(shù)量。令A(yù)是D中包含F(xiàn)的事務(wù)數(shù)量。令min_sup是最小支持度閾值。因?yàn)镕是頻繁項(xiàng)集，所以A=C*min_sup.令D分成n個不重疊的部分，d1,d2?dn。那么D=d1d2?dn.令c1c2?cn分別是各部分d1?dn的事務(wù)數(shù)量。則C=c1+c2+?+cn令a1a2?an分別是各部分d1?dn中包含F(xiàn)的事務(wù)數(shù)量，則A=a1+a2+?+anA=C*min_sup即a1+a2+?+an=(c1+c2+?+cn)*min_sup①由假設(shè)知F在各部分d1?dn中都不是頻繁的，所以ai<ci*min_sup(i=1,2,3,?,n)把式子加起來得a1+a2+?+an<(c1+c2+?+cn)*min_sup,②可得①②矛盾，所以原假設(shè)不成立。16?【p1775?3】Apriori:m3o3n2km3o3n2k5e4y3d1a1u1c21m3o3k5e4y3mo1ink3me2my2ok3oe3oy2ke4ky3ey2ink3ok3oe3ke4ky3oke3key2FP-growth:FP-growth:SeeFigure5,2fortheFP-tree*Figure5.2:FP-trccforExercise5.3.itemconditionalpatternbaseconditionaltreefrequentpatterny{{k尼{k.e.o:!},{k5m:l}}k:3{k,y：3}o{{k,e:2}k:3,e:3{k：o:3}：{??3}：{k.