數(shù)據(jù)挖掘期末復(fù)習(xí)

目錄1什么是數(shù)據(jù)挖掘〔DataMining〕？請(qǐng)舉例。 22簡(jiǎn)述知識(shí)發(fā)現(xiàn)〔KDD〕過(guò)程。 23簡(jiǎn)述數(shù)據(jù)挖掘的功能。〔PPT引言1.4〕 24為什么要進(jìn)行數(shù)據(jù)預(yù)處理？〔PPT2,1〕 35怎樣平滑噪聲數(shù)據(jù)〔〕 36在數(shù)據(jù)清理中，對(duì)缺失值有哪些處理方法？ 47描述數(shù)據(jù)有哪幾種根本圖形形式？ 48簡(jiǎn)述盒圖的作用。 49標(biāo)準(zhǔn)化有哪些形式，舉例。 410按照分箱法對(duì)數(shù)據(jù)進(jìn)行離散化。 511什么是數(shù)據(jù)倉(cāng)庫(kù)？或數(shù)據(jù)倉(cāng)庫(kù)的4特性？ 612簡(jiǎn)述數(shù)據(jù)倉(cāng)庫(kù)建模的根本模式?！?種，可圖示〕PPT數(shù)據(jù)倉(cāng)庫(kù)P40~49 613頻繁模式與關(guān)聯(lián)規(guī)那么根本概念，最大頻繁項(xiàng)，閉合頻繁項(xiàng)。PPT8.1 814Apriori算法根本步驟。能夠根據(jù)所給數(shù)據(jù)寫出算法具體執(zhí)行過(guò)程。 915何為Apriori性質(zhì)、反單調(diào)性？ 9分析算法效率。PPT8P25~27 916簡(jiǎn)述FP-Growth算法根本步驟。 917比擬Apriori與FP-Growth算法?！矁?yōu)缺點(diǎn)、適用范圍？〕 1118闡述決策樹(shù)分類的主要步驟，有哪些算法？ 1119闡述神經(jīng)網(wǎng)絡(luò)分類的主要原理。〔三層結(jié)構(gòu)，后向傳播〕 1420簡(jiǎn)述最近鄰分類的原理。 1421什么是急迫學(xué)習(xí)法、惰性學(xué)習(xí)法？ 1422什么是聚類分析？ 1523什么是層次聚類？有哪幾種類型？ 1524簡(jiǎn)述K-均值方法根本步驟，優(yōu)缺點(diǎn)。 1525寫出幾種典型層次聚類算法的名稱、各自特點(diǎn)。 1626簡(jiǎn)述基于密度的聚類方法，例如DBSCAN。 16

1什么是數(shù)據(jù)挖掘〔DataMining〕？請(qǐng)舉例。數(shù)據(jù)挖掘:是從大量數(shù)據(jù)中提取或"挖掘"知識(shí),也就是從存放在數(shù)據(jù)庫(kù),數(shù)據(jù)倉(cāng)庫(kù)或其他信息庫(kù)中的數(shù)據(jù)挖掘有趣知識(shí)的過(guò)程.數(shù)據(jù)挖掘是可以從數(shù)據(jù)庫(kù)中提取有趣的知識(shí)規(guī)律或高層信息發(fā)現(xiàn)的知識(shí),可以用于決策,過(guò)程控制,信息管理,查詢處理.它不是一種從數(shù)據(jù)庫(kù),統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)開(kāi)展的技術(shù)的簡(jiǎn)單轉(zhuǎn)化,它涉及多學(xué)科技術(shù)的集成,包括數(shù)據(jù)庫(kù)技術(shù),統(tǒng)計(jì)學(xué),機(jī)器學(xué)習(xí),高性能計(jì)算模式識(shí)別,神經(jīng)網(wǎng)絡(luò),數(shù)據(jù)可視化,信息檢索,圖象與信號(hào)處理和空間數(shù)據(jù)分析.隨著數(shù)據(jù)庫(kù)技術(shù)開(kāi)展,數(shù)據(jù)的豐富帶來(lái)了對(duì)強(qiáng)有力的數(shù)據(jù)分析工具的需求,大量的數(shù)據(jù)被描述為"數(shù)據(jù)豐富,但信息貧乏",所以數(shù)據(jù)挖掘出來(lái)了.意義：需求：數(shù)據(jù)豐富，但知識(shí)貧乏。技術(shù)：數(shù)據(jù)庫(kù)技術(shù)的演化

隨著全球信息化的開(kāi)展，自動(dòng)數(shù)據(jù)采集工具和成熟的數(shù)據(jù)庫(kù)技術(shù)導(dǎo)致海洋數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)庫(kù)中，從海量數(shù)據(jù)中提取可信的、新穎的、有效的并能被人們理解的知識(shí)是非常重要的，所以數(shù)據(jù)挖掘引起了信息產(chǎn)業(yè)的極大關(guān)注。涉及領(lǐng)域廣〔企業(yè)管理、產(chǎn)品控制、市場(chǎng)分析、工程設(shè)計(jì)和科學(xué)研究等〕。Where.How.What.意義2簡(jiǎn)述知識(shí)發(fā)現(xiàn)〔KDD〕過(guò)程。當(dāng)把數(shù)據(jù)挖掘看作知識(shí)發(fā)現(xiàn)過(guò)程時(shí),它涉及的步驟為:數(shù)據(jù)清理：消除噪聲或不一致數(shù)據(jù)數(shù)據(jù)集成：多種數(shù)據(jù)源可以組合在一起數(shù)據(jù)選擇：從數(shù)據(jù)庫(kù)中檢索與分析任務(wù)相關(guān)的數(shù)據(jù)數(shù)據(jù)變換：數(shù)據(jù)變換或統(tǒng)一成適合挖掘的形式，如通過(guò)匯總或聚集操作數(shù)據(jù)挖掘：根本步驟，使用智能方法提取數(shù)據(jù)模式模式評(píng)估：根據(jù)某種興趣度度量，識(shí)別表示知識(shí)的真正有趣的模式知識(shí)表示：使用可視化和知識(shí)表示技術(shù)，向用戶提供挖掘的知識(shí)3簡(jiǎn)述數(shù)據(jù)挖掘的功能?！睵PT引言1.4〕〔網(wǎng)上〕數(shù)據(jù)挖掘功能用于指定數(shù)據(jù)挖掘任務(wù)中要找的模式類型。一般地，數(shù)據(jù)挖掘任務(wù)可以分兩類：描述和預(yù)測(cè)。描述性挖掘任務(wù)刻劃數(shù)據(jù)庫(kù)中數(shù)據(jù)的一般特性。預(yù)測(cè)性挖掘任務(wù)在當(dāng)前數(shù)據(jù)上進(jìn)行推斷，以進(jìn)行預(yù)測(cè)。數(shù)據(jù)挖掘通過(guò)預(yù)測(cè)未來(lái)趨勢(shì)及行為，做出前攝的、基于知識(shí)的決策。數(shù)據(jù)挖掘的目標(biāo)是從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)隱含的、有意義的知識(shí)，主要有以下五類功能。

5.1自動(dòng)預(yù)測(cè)趨勢(shì)和行為

數(shù)據(jù)挖掘自動(dòng)在大型數(shù)據(jù)庫(kù)中尋找預(yù)測(cè)性信息，以往需要進(jìn)行大量手工分析的問(wèn)題如今可以迅速直接由數(shù)據(jù)本身得出結(jié)論。一個(gè)典型的例子是市場(chǎng)預(yù)測(cè)問(wèn)題，數(shù)據(jù)挖掘使用過(guò)去有關(guān)促銷的數(shù)據(jù)來(lái)尋找未來(lái)投資中回報(bào)最大的用戶，其它可預(yù)測(cè)的問(wèn)題包括預(yù)報(bào)破產(chǎn)以及認(rèn)定對(duì)指定事件最可能作出反響的群體。

5.2關(guān)聯(lián)分析

數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫(kù)中存在的一類重要的可被發(fā)現(xiàn)的知識(shí)。假設(shè)兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性，就稱為關(guān)聯(lián)。關(guān)聯(lián)可分為簡(jiǎn)單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)、因果關(guān)聯(lián)。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫(kù)中隱藏的關(guān)聯(lián)網(wǎng)。有時(shí)并不知道數(shù)據(jù)庫(kù)中數(shù)據(jù)的關(guān)聯(lián)函數(shù)，即使知道也是不確定的，因此關(guān)聯(lián)分析生成的規(guī)那么帶有可信度。

5.3聚類

數(shù)據(jù)庫(kù)中的記錄可被化分為一系列有意義的子集，即聚類。聚類增強(qiáng)了人們對(duì)客觀現(xiàn)實(shí)的認(rèn)識(shí)，是概念描述和偏差分析的先決條件。聚類技術(shù)主要包括傳統(tǒng)的模式識(shí)別方法和數(shù)學(xué)分類學(xué)。80年代初，Mchalski提出了概念聚類技術(shù)牞其要點(diǎn)是，在劃分對(duì)象時(shí)不僅考慮對(duì)象之間的距離，還要求劃分出的類具有某種內(nèi)涵描述，從而防止了傳統(tǒng)技術(shù)的某些片面性。

5.4概念描述

概念描述就是對(duì)某類對(duì)象的內(nèi)涵進(jìn)行描述，并概括這類對(duì)象的有關(guān)特征。概念描述分為特征性描述和區(qū)別性描述，前者描述某類對(duì)象的共同特征，后者描述不同類對(duì)象之間的區(qū)別。生成一個(gè)類的特征性描述只涉及該類對(duì)象中所有對(duì)象的共性。生成區(qū)別性描述的方法很多，如決策樹(shù)方法、遺傳算法等。

5.5偏差檢測(cè)

數(shù)據(jù)庫(kù)中的數(shù)據(jù)常有一些異常記錄，從數(shù)據(jù)庫(kù)中檢測(cè)這些偏差很有意義。偏差包括很多潛在的知識(shí)，如分類中的反常實(shí)例、不滿足規(guī)那么的特例、觀測(cè)結(jié)果與模型預(yù)測(cè)值的偏差、量值隨時(shí)間的變化等。偏差檢測(cè)的根本方法是，尋找觀測(cè)結(jié)果與參照值之間有意義的差異。4為什么要進(jìn)行數(shù)據(jù)預(yù)處理？〔PPT2,1〕1〕不完整的缺少屬性值或某些感興趣的屬性，或僅包含聚集數(shù)據(jù)。

2〕含噪聲的包含錯(cuò)誤或存在偏離期望的離群值。

3〕不一致的采用的編碼或表示不同，如屬性名稱不同

4〕冗余的如屬性之間可以相互導(dǎo)出

5〕數(shù)據(jù)錯(cuò)誤的不可防止性與危害

6〕數(shù)據(jù)預(yù)處理的形式〔1〕數(shù)據(jù)清理補(bǔ)充缺失數(shù)據(jù)、平滑噪聲數(shù)據(jù)、識(shí)別或刪除離群點(diǎn)，解決不一致〔2〕數(shù)據(jù)集成集成多個(gè)數(shù)據(jù)庫(kù)、數(shù)據(jù)立方或文件〔3〕數(shù)據(jù)變換標(biāo)準(zhǔn)化和聚集〔4〕數(shù)據(jù)歸約簡(jiǎn)化數(shù)據(jù)、但產(chǎn)生同樣或相似的結(jié)果5怎樣平滑噪聲數(shù)據(jù)〔〕分箱：

通過(guò)考察數(shù)據(jù)的“近鄰”〔周圍的值〕來(lái)光滑有序數(shù)據(jù)的值。局部光滑。

劃分：等頻、等寬

光滑：用箱均值、用箱中位數(shù)、用箱邊界〔去替換箱中的每個(gè)數(shù)據(jù)〕回歸：

用一個(gè)函數(shù)〔回歸函數(shù)〕擬合數(shù)據(jù)來(lái)光滑數(shù)據(jù)?？煞譃椋壕€性回歸、多元線性回歸聚類：將類似的值聚集為簇。檢測(cè)離群點(diǎn)其他：如數(shù)據(jù)歸約、離散化和概念分層。6在數(shù)據(jù)清理中，對(duì)缺失值有哪些處理方法？〔1〕忽略元組：當(dāng)缺少類標(biāo)號(hào)時(shí)通常這樣做〔假定挖掘任務(wù)涉及分類〕。除非元組有多個(gè)屬性缺少值，否那么該方法不是很有效。當(dāng)每個(gè)屬性缺少值的百分比變化很大時(shí)，它的性能特別差?！?〕人工填寫缺失值：一般，該方法很費(fèi)時(shí)，并且當(dāng)數(shù)據(jù)集很大，缺少很多值時(shí)，該方法可能行不通?！?〕使用一個(gè)全局常量填充缺失值：將缺失的屬性值用同一個(gè)常數(shù)〔如“Unknown”或-∞〕替換。如果缺失值都用“Unknown”替換，那么挖掘程序可能誤以為它們形成了一個(gè)有趣的概念，因?yàn)樗鼈兌季哂邢嗤闹怠癠nknown”。因此，盡管該方法簡(jiǎn)單，但是它并不十分可靠。

〔4〕使用屬性的均值填充缺失值：例如，假定AllElectronics顧客的平均收入為56000美元，那么使用該值替換income中的缺失值。

〔5〕使用與給定元組屬同一類的所有樣本的屬性均值：例如，將顧客按credit_risk分類，那么用具有相同信用度給定元組的顧客的平均收入替換income中的缺失值。

〔6〕使用最可能的值填充缺失值：可以用回歸、使用貝葉斯形式化的基于推理的工具或決策樹(shù)歸納確定。例如，利用數(shù)據(jù)集中其他顧客的屬性，可以構(gòu)造一棵決策樹(shù)來(lái)預(yù)測(cè)income的缺失值。7描述數(shù)據(jù)有哪幾種根本圖形形式？直方圖〔概括給定屬性分布的圖形方法、每個(gè)矩形等寬〕分位數(shù)圖、分位數(shù)-分位數(shù)圖〔q-q圖〕觀察單變量數(shù)據(jù)分布的簡(jiǎn)單有效方法散布圖、散布圖矩陣〔直接觀察是否存在簇(cluster)，離群點(diǎn)等、每個(gè)點(diǎn)對(duì)應(yīng)一個(gè)坐標(biāo)對(duì)〕局部回歸〔Loess〕曲線〔添加一條光滑曲線到散布圖〕8簡(jiǎn)述盒圖的作用。直觀明了地識(shí)別數(shù)據(jù)集中的離群點(diǎn)判斷數(shù)據(jù)集的偏態(tài)和尾重比擬幾批數(shù)據(jù)的形狀9標(biāo)準(zhǔn)化有哪些形式，舉例。1〕最小-最大標(biāo)準(zhǔn)化：將原始數(shù)據(jù)v經(jīng)線性變換，映射到區(qū)間[new_minA,new_maxA]例如:income的最大，最小值分別為9000，2000，那么將它的值映射到[0，1]時(shí)，假設(shè)income的值6800標(biāo)準(zhǔn)后為：〔6800-2000〕/〔9000-2000〕*〔1-0〕+0=0.686缺點(diǎn)：1假設(shè)存在離群點(diǎn)，可能影響標(biāo)準(zhǔn)化。2在標(biāo)準(zhǔn)化后添加新的數(shù)據(jù)，當(dāng)新數(shù)據(jù)落在原數(shù)據(jù)的區(qū)間[minA,maxA]之外，將導(dǎo)致“越界”錯(cuò)誤。2〕z-score標(biāo)準(zhǔn)化〔零均值標(biāo)準(zhǔn)化〕：屬性A的值基于A的平均值和標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化。缺點(diǎn)：對(duì)離群點(diǎn)不敏感10按照分箱法對(duì)數(shù)據(jù)進(jìn)行離散化。price的排序后數(shù)據(jù)(美元):4,8,9,15,21,21,24,25,26,28,29,34劃分為〔等深的〕箱:-箱1:4,8,9,15-箱2:21,21,24,25-箱3:26,28,29,34用箱平均值平滑:-箱1:9,9,9,9-箱2:23,23,23,23-箱3:29,29,29,29用箱邊界值平滑:-箱1:4,4,4,15-箱2:21,21,25,25-箱3:26,26,26,34〔以下內(nèi)容來(lái)的百度〕用邊界值平滑時(shí)，先確定兩個(gè)邊界，然后依次計(jì)算除邊界值外的其它值與兩個(gè)邊界的距離，與之距離最小的邊界確定為平滑邊界值。具體如下計(jì)算：-箱1：｜8-4｜＝4；｜15-8｜＝7；應(yīng)選4做為平滑邊界值。｜9-4｜＝5；｜15-9｜＝6；應(yīng)選4做為平滑邊界值。-箱2：｜21-21｜＝0；｜25-21｜＝4；應(yīng)選21做為平滑邊界值。｜24-21｜＝3；｜25-24｜＝1；應(yīng)選25做為平滑邊界值。-箱3：｜28-26｜＝2；｜34-28｜＝6；應(yīng)選26做為平滑邊界值。｜29-26｜＝3；｜34-29｜＝5；應(yīng)選26做為平滑邊界值。11什么是數(shù)據(jù)倉(cāng)庫(kù)？或數(shù)據(jù)倉(cāng)庫(kù)的4特性？“數(shù)據(jù)倉(cāng)庫(kù)是一個(gè)面向主題的、集成的、時(shí)變的、非易失的數(shù)據(jù)集合，支持管理部門的決策過(guò)程”數(shù)據(jù)倉(cāng)庫(kù)的4特性：面向主題的、集成的、時(shí)變的、非易失的〔具體PPT數(shù)據(jù)倉(cāng)庫(kù)2.1.1P16~20〕12簡(jiǎn)述數(shù)據(jù)倉(cāng)庫(kù)建模的根本模式?！?種，可圖示〕PPT數(shù)據(jù)倉(cāng)庫(kù)P40~49星型模型:模式圖很像星星爆發(fā)，維表圍繞事實(shí)表顯示在射線上

雪花模型:雪花模式是星型模式的變種，其中某些維表是標(biāo)準(zhǔn)化的，把數(shù)據(jù)進(jìn)一步分解到附加的表中，形成類似于雪花的形狀

星網(wǎng)模型:多個(gè)事實(shí)表共享維表，這種模式可以看作星型模式集，因此也可以稱為星系模式，或者事實(shí)星座

13頻繁模式與關(guān)聯(lián)規(guī)那么根本概念，最大頻繁項(xiàng)，閉合頻繁項(xiàng)。PPT8.1閉〔頻繁〕項(xiàng)集：假設(shè)不存在真超項(xiàng)集Y〔Y?X〕，使得Y與X在數(shù)據(jù)集S中有相同的支持度計(jì)數(shù)，那么稱項(xiàng)集X在S中是閉的。極大〔頻繁〕項(xiàng)集：如果X是頻繁的，并且不存在頻繁的超項(xiàng)集Y使得Y?X，稱X是極大項(xiàng)集。14Apriori算法根本步驟。能夠根據(jù)所給數(shù)據(jù)寫出算法具體執(zhí)行過(guò)程。掃描數(shù)據(jù)庫(kù)，累積每個(gè)項(xiàng)的支持度計(jì)數(shù)，生成頻繁1項(xiàng)集集合L1；掃描數(shù)據(jù)庫(kù)，由L1構(gòu)造、搜索頻繁2項(xiàng)集L2；同理，生成L3，…，直到不能生成頻繁k項(xiàng)集。15何為Apriori性質(zhì)、反單調(diào)性？分析算法效率。PPT8P25~27Apriori性質(zhì):頻繁項(xiàng)集的所有非空子集也必須是頻繁的。i.e.,如果{AB}是頻繁項(xiàng)集,{A}和{B}都應(yīng)該是頻繁項(xiàng)集反單調(diào)性：如果一個(gè)集合不能通過(guò)測(cè)試，那么它的所有超集也都不能通過(guò)相同的測(cè)試。16簡(jiǎn)述FP-Growth算法根本步驟。掃描數(shù)據(jù)庫(kù)一次，找到頻繁1項(xiàng)集對(duì)頻繁項(xiàng)集降序排序再次掃描數(shù)據(jù)庫(kù)，構(gòu)造FP-樹(shù)(這個(gè)網(wǎng)上找的？？)步驟〔一〕：

挖掘頻繁模式前首先要構(gòu)造FP-Tree，算法為碼如下：

輸入:一個(gè)交易數(shù)據(jù)庫(kù)DB和一個(gè)最小支持度threshold.

輸出:它的FP-tree.

步驟:

1.掃描數(shù)據(jù)庫(kù)DB一遍.得到頻繁項(xiàng)的集合F和每個(gè)頻繁項(xiàng)的支持度.把F按支持度遞降排序,結(jié)果記為L(zhǎng).2.創(chuàng)立FP-tree的根節(jié)點(diǎn),記為T,并且標(biāo)記為’null’.然后對(duì)DB中的每個(gè)事務(wù)Trans做如下的步驟.

根據(jù)L中的順序,選出并排序Trans中的事務(wù)項(xiàng).把Trans中排好序的事務(wù)項(xiàng)列表記為[p|P],其中p是第一個(gè)元素,P是列表的剩余局部.調(diào)用insert_tree([p|P],T).

函數(shù)insert_tree([p|P],T)的運(yùn)行如下.

如果T有一個(gè)子結(jié)點(diǎn)N,其中N.item-name=p.item-name,那么將N的count域值增加1;否那么,創(chuàng)立一個(gè)新節(jié)點(diǎn)N,使它的count為1,使它的父節(jié)點(diǎn)為T,并且使它的node_link和那些具有相同item_name域串起來(lái).如果P非空,那么遞歸調(diào)用insert_tree(P,N).注：構(gòu)造FP-Tree的算法理解上相對(duì)簡(jiǎn)單，所以不過(guò)多描述

步驟〔二〕：

對(duì)FP-Tree進(jìn)行挖掘，算法如下：

輸入:一棵用算法一建立的樹(shù)Tree

輸出:所有的頻繁集

步驟:

調(diào)用FP-growth(Tree,null).

procedureFP-Growth(Tree,x)

{

(1)if(Tree只包含單路徑P)then

(2)

對(duì)路徑P中節(jié)點(diǎn)的每個(gè)組合〔記為B〕

(3)

生成模式B并x，支持?jǐn)?shù)＝B中所有節(jié)點(diǎn)的最小支持度

(4)else對(duì)Tree頭上的每個(gè)ai，do

{

(5)

生成模式B=ai并x，支持度＝ai.support；

(6)

構(gòu)造B的條件模式庫(kù)和B的條件FP樹(shù)TreeB；

(7)

ifTreeB!=空集

(8)

thencallFP-Growth(TreeB,B)17比擬Apriori與FP-Growth算法。〔優(yōu)缺點(diǎn)、適用范圍？〕FP優(yōu)點(diǎn)：完全:1不會(huì)破壞任何事務(wù)的長(zhǎng)模式；2為頻繁模式挖掘保持完整的信息簡(jiǎn)潔，緊密：1減少不相關(guān)的信息，去掉非頻繁項(xiàng)；2頻繁項(xiàng)的降序排序：越頻繁越可能被共享；3永遠(yuǎn)不會(huì)比初始數(shù)據(jù)庫(kù)大性能說(shuō)明：FP-Growth比Apriori算法快一個(gè)數(shù)量級(jí)，也比樹(shù)-投影算法快原因：1沒(méi)有候選集產(chǎn)生，沒(méi)有候選測(cè)試；2使用壓縮的數(shù)據(jù)結(jié)構(gòu)；3沒(méi)有過(guò)多的數(shù)據(jù)庫(kù)的掃描；4根本操作是計(jì)算和FP-tree的構(gòu)造Apriori算法時(shí)間消耗的主要癥結(jié)反映在兩個(gè)方面，一是由于對(duì)海量數(shù)據(jù)庫(kù)的多趟電子掃描，另外一個(gè)是用JOIN孕育發(fā)生潛在頻仍項(xiàng)集?？赡墚a(chǎn)生大量的候選集,以及可能需要重復(fù)掃描數(shù)據(jù)庫(kù)，是Apriori算法的兩大缺點(diǎn)

FP-Tree布局在完整性方面，它不會(huì)打破生意業(yè)務(wù)中的任何標(biāo)準(zhǔn)樣式，而且包羅了開(kāi)采序列標(biāo)準(zhǔn)樣式所需的全部信息；在精密性方面，它不剔掉不相關(guān)信息，不包羅非頻仍項(xiàng)，按支撐度降序排列，支撐度高的項(xiàng)在FP-Tree中同享的時(shí)機(jī)也高。

機(jī)能研究顯示FP-growth比Apriori快一個(gè)數(shù)目級(jí)，這是由于FP-growth不生成候選集，不用候選集實(shí)驗(yàn)，而且施用收縮的數(shù)據(jù)布局，防止反復(fù)數(shù)據(jù)庫(kù)電子掃描FP-growth算法的應(yīng)用范圍最廣,它把事務(wù)數(shù)據(jù)庫(kù)壓縮.到一個(gè)FP-樹(shù)進(jìn)行處理,相對(duì)Apriori算法來(lái)說(shuō),最大的優(yōu)點(diǎn)是不需要產(chǎn)生候選頻繁項(xiàng)集且只需要兩次掃描數(shù)據(jù)庫(kù)。但是它仍然存在一些問(wèn)題,比方需要產(chǎn)生大量的條件FP-樹(shù)、不能有效的挖掘大型數(shù)據(jù)庫(kù)等。18闡述決策樹(shù)分類的主要步驟，有哪些算法？決策樹(shù)分類的步驟：以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)開(kāi)始建樹(shù)〔創(chuàng)立N節(jié)點(diǎn)〕。如果樣本都在同一個(gè)類，那么該節(jié)點(diǎn)成為樹(shù)葉，并用該類標(biāo)記。否那么，算法使用稱為信息增益的基于熵的度量為啟發(fā)信息，選擇能夠最好的將樣本分類的屬性，該屬性成為該節(jié)點(diǎn)的測(cè)試或判定屬性。〔注意：在這類算法中，所有的屬性都是分類的，即取離散值的。連續(xù)值的屬性必須離散化?！硨?duì)測(cè)試屬性的每個(gè)的值，創(chuàng)立一個(gè)分支，并據(jù)此劃分樣本。算法使用同樣的過(guò)程，遞歸地形成每個(gè)劃分上的樣本決策樹(shù)。一旦一個(gè)屬性出現(xiàn)在一個(gè)節(jié)點(diǎn)上，就不必考慮該節(jié)點(diǎn)的任何后代。遞歸劃分步驟，當(dāng)以下條件之一成立時(shí)停止：給定節(jié)點(diǎn)的所有樣本屬于同一類。沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分樣本。在此情況下，采用多數(shù)表決。這涉及將給定的節(jié)點(diǎn)轉(zhuǎn)換成樹(shù)葉，并用樣本中的多數(shù)所在的類別標(biāo)記它。分支〔測(cè)試屬性的分枝〕沒(méi)有樣本。在這種情況下，以樣本中的多數(shù)創(chuàng)立一個(gè)樹(shù)葉。決策樹(shù)是以實(shí)例為根底的歸納學(xué)習(xí)算法。它從一組無(wú)次序、無(wú)規(guī)那么的元組中推理出決策樹(shù)表示形式的分類規(guī)那么。它采用自頂向下的遞歸方式，在決策樹(shù)的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比擬，并根據(jù)不同的屬性值從該結(jié)點(diǎn)向下分支，葉結(jié)點(diǎn)是要學(xué)習(xí)劃分的類。從根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條合取規(guī)那么，整個(gè)決策樹(shù)就對(duì)應(yīng)著一組析取表達(dá)式規(guī)那么。1986年Quinlan提出了著名的ID3算法。在ID3算法的根底上，1993年Quinlan又提出了C4.5算法。為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需要，后來(lái)又提出了假設(shè)干改良的算法，其中SLIQ(super-visedlearninginquest)和SPRINT(scalableparallelizableinductionofdecisiontrees)是比擬有代表性的兩個(gè)算法。

(1)ID3算法ID3算法的核心是：在決策樹(shù)各級(jí)結(jié)點(diǎn)上選擇屬性時(shí)，用信息增益〔informationgain〕作為屬性的選擇標(biāo)準(zhǔn)，以使得在每一個(gè)非葉結(jié)點(diǎn)進(jìn)行測(cè)試時(shí)，能獲得關(guān)于被測(cè)試記錄最大的類別信息。其具體方法是：檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹(shù)結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用該方法建立決策樹(shù)結(jié)點(diǎn)的分支，直到所有子集僅包含同一類別的數(shù)據(jù)為止。最后得到一棵決策樹(shù)，它可以用來(lái)對(duì)新的樣本進(jìn)行分類。某屬性的信息增益按以下方法計(jì)算。通過(guò)計(jì)算每個(gè)屬性的信息增益，并比擬它們的大小，就不難獲得具有最大信息增益的屬性。設(shè)S是s個(gè)數(shù)據(jù)樣本的集合。假定類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類Ci(i=1,…,m)。設(shè)si是類Ci中的樣本數(shù)。對(duì)一個(gè)給定的樣本分類所需的期望信息由下式給出：其中pi=si/s是任意樣本屬于Ci的概率。注意，對(duì)數(shù)函數(shù)以2為底，其原因是信息用二進(jìn)制編碼。

設(shè)屬性A具有v個(gè)不同值{a1,a2,……,av}。可以用屬性A將S劃分為v個(gè)子集{S1,S2,……,Sv}，其中Sj中的樣本在屬性A上具有相同的值aj〔j=1,2,……,v〕。設(shè)sij是子集Sj中類Ci的樣本數(shù)。由A劃分成子集的熵或信息期望由下式給出：

熵值越小，子集劃分的純度越高。對(duì)于給定的子集Sj，其信息期望為其中pij=sij/sj是Sj中樣本屬于Ci的概率。在屬性A上分枝將獲得的信息增益是Gain(A)=I(s1,s2,…,sm)-E(A)ID3算法的優(yōu)點(diǎn)是：算法的理論清晰，方法簡(jiǎn)單，學(xué)習(xí)能力較強(qiáng)。其缺點(diǎn)是：只比照擬小的數(shù)據(jù)集有效，且對(duì)噪聲比擬敏感，當(dāng)訓(xùn)練數(shù)據(jù)集加大時(shí)，決策樹(shù)可能會(huì)隨之改變。(2)C4.5算法C4.5算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾方面對(duì)ID3算法進(jìn)行了改良：1)用信息增益率來(lái)選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的缺乏；2)在樹(shù)構(gòu)造過(guò)程中進(jìn)行剪枝；3)能夠完成對(duì)連續(xù)屬性的離散化處理；4)能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。C4.5算法與其它分類算法如統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)等比擬起來(lái)有如下優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)那么易于理解，準(zhǔn)確率較高。其缺點(diǎn)是：在構(gòu)造樹(shù)的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行屢次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。(3)SLIQ算法SLIQ算法對(duì)C4.5決策樹(shù)分類算法的實(shí)現(xiàn)方法進(jìn)行了改良，在決策樹(shù)的構(gòu)造過(guò)程中采用了“預(yù)排序”和“廣度優(yōu)先策略”兩種技術(shù)。1)預(yù)排序。對(duì)于連續(xù)屬性在每個(gè)內(nèi)部結(jié)點(diǎn)尋找其最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，都需要對(duì)訓(xùn)練集按照該屬性的取值進(jìn)行排序，而排序是很浪費(fèi)時(shí)間的操作。為此，SLIQ算法采用了預(yù)排序技術(shù)。所謂預(yù)排序，就是針對(duì)每個(gè)屬性的取值，把所有的記錄按照從小到大的順序進(jìn)行排序，以消除在決策樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行的排序。具體實(shí)現(xiàn)時(shí)，需要為訓(xùn)練數(shù)據(jù)集的每個(gè)屬性創(chuàng)立一個(gè)屬性列表，為類別屬性創(chuàng)立一個(gè)類別列表。2)廣度優(yōu)先策略。在C4.5算法中，樹(shù)的構(gòu)造是按照深度優(yōu)先策略完成的，需要對(duì)每個(gè)屬性列表在每個(gè)結(jié)點(diǎn)處都進(jìn)行一遍掃描，費(fèi)時(shí)很多，為此，SLIQ采用廣度優(yōu)先策略構(gòu)造決策樹(shù)，即在決策樹(shù)的每一層只需對(duì)每個(gè)屬性列表掃描一次，就可以為當(dāng)前決策樹(shù)中每個(gè)葉子結(jié)點(diǎn)找到最優(yōu)分裂標(biāo)準(zhǔn)。SLIQ算法由于采用了上述兩種技術(shù)，使得該算法能夠處理比C4.5大得多的訓(xùn)練集，在一定范圍內(nèi)具有良好的隨記錄個(gè)數(shù)和屬性個(gè)數(shù)增長(zhǎng)的可伸縮性。然而它仍然存在如下缺點(diǎn)：1)由于需要將類別列表存放于內(nèi)存,而類別列表的元組數(shù)與訓(xùn)練集的元組數(shù)是相同的,這就一定程度上限制了可以處理的數(shù)據(jù)集的大小。2)由于采用了預(yù)排序技術(shù)，而排序算法的復(fù)雜度本身并不是與記錄個(gè)數(shù)成線性關(guān)系，因此，使得SLIQ算法不可能到達(dá)隨記錄數(shù)目增長(zhǎng)的線性可伸縮性。(4)SPRINT算法為了減少駐留于內(nèi)存的數(shù)據(jù)量，SPRINT算法進(jìn)一步改良了決策樹(shù)算法的數(shù)據(jù)結(jié)構(gòu)，去掉了在SLIQ中需要駐留于內(nèi)存的類別列表，將它的類別列合并到每個(gè)屬性列表中。這樣，在遍歷每個(gè)屬性列表尋找當(dāng)前結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，不必參照其他信息，將對(duì)結(jié)點(diǎn)的分裂表現(xiàn)在對(duì)屬性列表的分裂，即將每個(gè)屬性列表分成兩個(gè)，分別存放屬于各個(gè)結(jié)點(diǎn)的記錄。SPRINT算法的優(yōu)點(diǎn)是在尋找每個(gè)結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)變得更簡(jiǎn)單。其缺點(diǎn)是對(duì)非分裂屬性的屬性列表進(jìn)行分裂變得很困難。解決的方法是對(duì)分裂屬性進(jìn)行分裂時(shí)用哈希表記錄下每個(gè)記錄屬于哪個(gè)孩子結(jié)點(diǎn)，假設(shè)內(nèi)存能夠容納下整個(gè)哈希表，其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓(xùn)練集的大小成正比，當(dāng)訓(xùn)練集很大時(shí)，哈希表可能無(wú)法在內(nèi)存容納，此時(shí)分裂只能分批執(zhí)行，這使得SPRINT算法的可伸縮性仍然不是很好。根本算法(貪心算法)1〕如何劃分訓(xùn)練集自頂向下遞歸的分治法構(gòu)造決策樹(shù)開(kāi)始，所有的訓(xùn)練樣本在根部屬性分類(假設(shè)是連續(xù)值,屬性首先離散化)基于選定的屬性遞歸的形成每個(gè)劃分選擇屬性基于啟發(fā)式或統(tǒng)計(jì)式策略(比方,信息增益)2〕如何停止〔停止條件〕給定節(jié)點(diǎn)的所有樣本屬于同一類沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分樣本–使用majorityvoting沒(méi)有樣本剩余算法：ID3,C4.5〔書p144-150〕19闡述神經(jīng)網(wǎng)絡(luò)分類的主要原理。〔三層結(jié)構(gòu)，后向傳播〕神經(jīng)元是神經(jīng)網(wǎng)絡(luò)中根本的信息處理單元，他由以下局部組成:1一組突觸和聯(lián)結(jié)，聯(lián)結(jié)具有權(quán)值W1,W2,…,Wm通過(guò)加法器功能，將計(jì)算輸入的權(quán)值之和3鼓勵(lì)函數(shù)限制神經(jīng)元輸出的幅度BP網(wǎng)絡(luò)模型處理信息的根本原理是：輸入信號(hào)Xi通過(guò)中間節(jié)點(diǎn)〔隱層點(diǎn)〕作用于輸出節(jié)點(diǎn)，經(jīng)過(guò)非線形變換，產(chǎn)生輸出信號(hào)Yk，網(wǎng)絡(luò)訓(xùn)練的每個(gè)樣本包括輸入向量X和期望輸出量t，網(wǎng)絡(luò)輸出值Y與期望輸出值t之間的偏差，通過(guò)調(diào)整輸入節(jié)點(diǎn)與隱層節(jié)點(diǎn)的聯(lián)接強(qiáng)度取值Wij和隱層節(jié)點(diǎn)與輸出節(jié)點(diǎn)之間的聯(lián)接強(qiáng)度Tjk以及閾值，使誤差沿梯度方向下降，經(jīng)過(guò)反復(fù)學(xué)習(xí)訓(xùn)練，確定與最小誤差相對(duì)應(yīng)的網(wǎng)絡(luò)參數(shù)〔權(quán)值和閾值〕，訓(xùn)練即告停止。此時(shí)經(jīng)過(guò)訓(xùn)練的神經(jīng)網(wǎng)絡(luò)即能對(duì)類似樣本的輸入信息，自行處理輸出誤差最小的經(jīng)過(guò)非線形轉(zhuǎn)換的信息。〔此題不確定〕20簡(jiǎn)述最近鄰分類的原理。〔百度百科〕如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，那么該樣本也屬于這個(gè)類別。21什么是急迫學(xué)習(xí)法、惰性學(xué)習(xí)法？急性子〔急迫學(xué)習(xí)法〕決策樹(shù)、貝葉斯、神經(jīng)網(wǎng)絡(luò)給定訓(xùn)練元組，立刻建立模型，學(xué)習(xí)分類慢性子〔惰性學(xué)習(xí)法〕給定訓(xùn)練元組，知道看到檢驗(yàn)元組時(shí)才分類，比方k-最近鄰分類，基于案例的推理22什么是聚類分析？聚類分析：將數(shù)據(jù)對(duì)象的集合分成由相似對(duì)象組成的多個(gè)類聚類分析中要?jiǎng)澐值念愂俏粗牡湫偷膽?yīng)用：1作為獨(dú)立的工具來(lái)獲得數(shù)據(jù)分布的情況；2也可以作為其他算法的預(yù)處理步驟聚類分析指將物理或抽象對(duì)象的集合分組成為由類似的對(duì)象組成的多個(gè)類的分析過(guò)程。它是一種重要的人類行為。聚類分析的目標(biāo)就是在相似的根底上收集數(shù)據(jù)來(lái)分類。聚類源于很多領(lǐng)域，包括數(shù)學(xué)，計(jì)算機(jī)科學(xué)，統(tǒng)計(jì)學(xué)，生物學(xué)和經(jīng)濟(jì)學(xué)。在不同的應(yīng)用領(lǐng)域，很多聚類技術(shù)都得到了開(kāi)展，這些技術(shù)方法被用作描述數(shù)據(jù)，衡量不同數(shù)據(jù)源間的相似性，以及把數(shù)據(jù)源分類到不同的簇中。23什么是層次聚類？有哪幾種類型？層次聚類:按某種標(biāo)準(zhǔn)將給定數(shù)據(jù)對(duì)象集合進(jìn)行層次的分解。將嵌套定義的簇集組成一棵層次形式的樹(shù)按照分裂方式可分為：凝聚的把每個(gè)點(diǎn)都作為一個(gè)簇，開(kāi)始聚類每一步合并兩個(gè)最近的簇，直到只剩下一個(gè)簇分裂的所有的點(diǎn)看做一個(gè)簇每一步，分裂一個(gè)簇，直到每個(gè)點(diǎn)都是一個(gè)簇24簡(jiǎn)述K-均值方法根本步驟，優(yōu)缺點(diǎn)。步驟給定k:任意選擇k個(gè)點(diǎn)作為初始的質(zhì)心repeat將每個(gè)點(diǎn)指派到最近〔相似〕的簇集重新計(jì)算每個(gè)簇的均值，即更新質(zhì)心until不再發(fā)生變化.優(yōu)點(diǎn)：簡(jiǎn)單、有效可用于各種數(shù)據(jù)類型〔但并非適合所有數(shù)據(jù)類型〕缺點(diǎn)：不能處理：1不同尺寸的簇；2不同密度的簇；3非球形的簇對(duì)含離群點(diǎn)的數(shù)據(jù)聚類時(shí)也有問(wèn)題25寫出幾種典型層次聚類算法的名稱、各自特點(diǎn)。AGNES(凝聚的層次聚類)

KaufmannandRousseeuw(1990)

將具有最少相異性的點(diǎn)合并

將這些簇合并成越來(lái)越