數(shù)據(jù)挖掘與數(shù)據(jù)倉(cāng)庫(kù)知識(shí)點(diǎn)總結(jié).doc

1、數(shù)據(jù)倉(cāng)庫(kù)定義：數(shù)據(jù)倉(cāng)庫(kù)是一種新的數(shù)據(jù)處理體系結(jié)構(gòu)，它與組織機(jī)構(gòu)的操作數(shù)據(jù)庫(kù)分別維護(hù)，允許將各種應(yīng)用系統(tǒng)一起，為統(tǒng)一的歷史數(shù)據(jù)分析提供堅(jiān)實(shí)的平臺(tái)，對(duì)信息處理提供支持。數(shù)據(jù)倉(cāng)庫(kù)是面向主題的、集成的、相對(duì)穩(wěn)定的、反映歷史變化的數(shù)據(jù)集合，為企業(yè)決策支持系統(tǒng)提供所需的集成信息。設(shè)計(jì)和構(gòu)造步驟：1）選取待建模的商務(wù)處理；2）選取商務(wù)處理的粒變；3）選取用于每個(gè)事實(shí)表記錄的維；4）選取事實(shí)表中每條記錄的變量系統(tǒng)結(jié)構(gòu)：（1）底層是倉(cāng)庫(kù)數(shù)據(jù)服務(wù)器，總是關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)。（2）中間層是OLAP服務(wù)器，有ROLAP和MOLAP，它將對(duì)多維數(shù)據(jù)的操作映射為標(biāo)準(zhǔn)的關(guān)系操作（3）頂層是前端客戶端，它包括查詢和報(bào)表工具、分析工具和數(shù)據(jù)挖掘工具2、數(shù)據(jù)倉(cāng)庫(kù)的多維數(shù)據(jù)模型：（1）星形模式：在此模型下，數(shù)據(jù)倉(cāng)庫(kù)包括一個(gè)大的包含大批數(shù)據(jù)并且不含冗余的中心表，一組小的附屬表，維表圍繞中心事實(shí)表顯示的射線上。特征：星型模型四周的實(shí)體是維度實(shí)體，其作用是限制和過(guò)濾用戶的查詢結(jié)果，縮小訪問(wèn)范圍。每個(gè)維表都有自己的屬性，維表和事實(shí)表通過(guò)關(guān)鍵字相關(guān)聯(lián)。【例子：sales數(shù)據(jù)倉(cāng)庫(kù)的星形模式，此模式包含一個(gè)中心事實(shí)表sales，它包含四個(gè)維time, item, branch和location。（2）雪花型模式：它是星形模式的變種，其中某些維表是規(guī)范化的，因而把數(shù)據(jù)進(jìn)一步分解到附加的表中。特征：雪花模型通過(guò)最大限度地減少數(shù)據(jù)存儲(chǔ)量和聯(lián)合較小的維表來(lái)改善查詢性能，增加了用戶必須處理的表數(shù)量和某些查詢的復(fù)雜性，但同時(shí)提高了處理的靈活性，可以回答更多的商業(yè)問(wèn)題，特別適合系統(tǒng)的逐步建設(shè)要求?！纠油希徊贿^(guò)把其中的某些維給擴(kuò)展了。（3）事實(shí)星座形：復(fù)雜的應(yīng)用可能需要多個(gè)事實(shí)表共享維表，這種模式可看作星形模式的匯集。特征：事實(shí)星座模型能對(duì)多個(gè)相關(guān)的主題建模。例子：有兩個(gè)事實(shí)表sales和shipping，它們可以共享維表time, item和location。3、OLAP：即聯(lián)機(jī)分析處理，是在OLTP基礎(chǔ)上發(fā)展起來(lái)的、以數(shù)據(jù)倉(cāng)庫(kù)基礎(chǔ)上的、面向高層管理人員和專業(yè)分析人員、為企業(yè)決策支持服務(wù)。特點(diǎn)：1.實(shí)時(shí)性要求不是很高。2.數(shù)據(jù)量大。3.因?yàn)橹攸c(diǎn)在于決策支持，所以查詢一般是動(dòng)態(tài)的，也就是說(shuō)允許用戶隨機(jī)提出查詢要求。OLAP操作：上卷：通過(guò)沿一個(gè)維的概念分層向上攀登，或者通過(guò)維歸約，對(duì)數(shù)據(jù)立方體進(jìn)行類聚。下鉆：是上卷的逆操作，它由不太詳細(xì)的數(shù)據(jù)得到更詳細(xì)的數(shù)據(jù)，下鉆可以通過(guò)沿維的概念分層向下或引入附加的維來(lái)實(shí)現(xiàn)。切片：對(duì)給定方體的一個(gè)維進(jìn)行進(jìn)行選擇，導(dǎo)致一個(gè)子立方體。切塊：通過(guò)對(duì)兩個(gè)或多個(gè)維執(zhí)行選擇，定義子立方體。轉(zhuǎn)軸：是一種可視化操作，它轉(zhuǎn)動(dòng)數(shù)據(jù)的視角，提供數(shù)據(jù)的替代表示。OLTP：即聯(lián)機(jī)事務(wù)處理，是以傳統(tǒng)數(shù)據(jù)庫(kù)為基礎(chǔ)、面向操作人員和低層管理人員、對(duì)基本數(shù)據(jù)進(jìn)行查詢和增、刪、改等的日常事務(wù)處理。OLTP的特點(diǎn)有：a.實(shí)時(shí)性要求高；b.數(shù)據(jù)量不是很大。C.交易一般是確定的，是對(duì)確定性數(shù)據(jù)進(jìn)行存取。d.并發(fā)性要求高且嚴(yán)格的要求事務(wù)的完整性，安全性。OLTP和OLAP的區(qū)別：1）用戶和系統(tǒng)的面向性:OLTP面向顧客，而OLAP面向市場(chǎng)；2）數(shù)據(jù)內(nèi)容：OLTP系統(tǒng)管理當(dāng)前數(shù)據(jù)，而OLAP管理歷史的數(shù)據(jù)；3）數(shù)據(jù)庫(kù)設(shè)計(jì)：OLTP系統(tǒng)采用實(shí)體-聯(lián)系（ER)模型和面向應(yīng)用的數(shù)據(jù)庫(kù)設(shè)計(jì)，而OLAP系統(tǒng)通常采用星形和雪花模型；4）視圖：OLTP系統(tǒng)主要關(guān)注一個(gè)企業(yè)或部門內(nèi)部的當(dāng)前數(shù)據(jù)，而OLAP 系統(tǒng)主要關(guān)注匯總的統(tǒng)一的數(shù)據(jù)；5）訪問(wèn)模式：OLTP訪問(wèn)主要有短的原子事務(wù)組成，而OLAP系統(tǒng)的訪問(wèn)大部分是只讀操作，盡管許多可能是復(fù)雜的查詢。7、PageRank算法 原理：1）在初始階段：構(gòu)建Web圖，每個(gè)頁(yè)面初始設(shè)置相同的PageRank值，通過(guò)迭代計(jì)算，會(huì)得到每個(gè)頁(yè)面所獲得的最終PageRank值。2）在一輪中更新頁(yè)面PageRank得分的計(jì)算方法：每個(gè)頁(yè)面將其當(dāng)前的PageRank值平均分配到本頁(yè)面包含的出鏈上。每個(gè)頁(yè)面將所有指向本頁(yè)面的入鏈所傳入的權(quán)值求和，即可得到新的PageRank得分。優(yōu)點(diǎn)：是一個(gè)與查詢無(wú)關(guān)的靜態(tài)算法，所有網(wǎng)頁(yè)的PageRank值通過(guò)離線計(jì)算獲得；有效減少在線查詢時(shí)的計(jì)算量，極大降低了查詢響應(yīng)時(shí)間。 缺點(diǎn)：1）人們的查詢具有主題特征，PageRank忽略了主題相關(guān)性，導(dǎo)致結(jié)果的相關(guān)性和主題性降低。2）舊的頁(yè)面等級(jí)會(huì)比新頁(yè)面高。因?yàn)榧词故欠浅：玫男马?yè)面也不會(huì)有很多上游鏈接，除非它是某個(gè)站點(diǎn)的子站點(diǎn)。5、分類：指把數(shù)據(jù)樣本映射到一個(gè)事先定義的類中的學(xué)習(xí)過(guò)程，即給定一組輸入的屬性向量及其對(duì)應(yīng)的類。過(guò)程：在已知訓(xùn)練數(shù)據(jù)集上，根據(jù)屬性特征，為每一種類別找到一個(gè)合理的描述或模型，即分類規(guī)則；然后根據(jù)規(guī)則對(duì)新數(shù)據(jù)進(jìn)行分類。分類的方法有哪些，給出你所了解的評(píng)估分類器的方法和特點(diǎn)？分類方法：用基于歸納的學(xué)習(xí)算法，k-最近鄰分類，人工神經(jīng)網(wǎng)絡(luò)法、粗糙集法和遺傳算法。用判定樹(shù)歸納分類；貝葉斯分類；后向傳播分類；基于規(guī)則的分類；關(guān)聯(lián)分類，SVM支持向量機(jī)等。分類和預(yù)測(cè)的評(píng)估方法：預(yù)測(cè)的準(zhǔn)確率、速度、強(qiáng)壯性、可規(guī)模性、可解釋性。評(píng)估方法：（1）保持方法，給定數(shù)據(jù)隨機(jī)地劃分成兩個(gè)獨(dú)立的集合：訓(xùn)練集和測(cè)試集。通常，三分之二的數(shù)據(jù)分配到訓(xùn)練集，其余三分之一分配到測(cè)試集。使用訓(xùn)練集導(dǎo)出分類法，其準(zhǔn)確率用測(cè)試集評(píng)估。評(píng)估是保守的，因?yàn)橹挥幸徊糠殖跏紨?shù)據(jù)用于導(dǎo)出的分類法。（2）交叉確認(rèn)：在k-折交叉確認(rèn)中，初試數(shù)據(jù)被劃分成 k 個(gè)互不相交的子集或“折”S 1,S 2,.,S k，每個(gè)折的大小大致相等。訓(xùn)練和測(cè)試進(jìn)行 k次。在第 i次迭代，S i用作測(cè)試集，其余的子集都用于訓(xùn)練分類法。其它方法包括解靴帶（bootstrapping）和留一。前者使用一致的、帶放回的選樣，選取給定的訓(xùn)練實(shí)例；后者是 k-折交叉確認(rèn)，這里 k 為初始樣本數(shù) s。一般地，建議使用調(diào)整的 10-折交叉確認(rèn)，因?yàn)樗哂邢鄬?duì)低的偏置和方差。（3）袋裝：給定 s 個(gè)樣本的集合 S，對(duì)于迭代 t ( t = 1,2,.,T )，訓(xùn)練集 S t采用放回選樣，由原始樣本集 S 選取。由于使用放回選樣，S 的某些樣本可能不在 St中，而其它的可能出現(xiàn)多次。由每個(gè)訓(xùn)練集 S t學(xué)習(xí)，得到一個(gè)分類法 C t。為對(duì)一個(gè)未知的樣本 X 分類，每個(gè)分類法 C t返回它的類預(yù)測(cè)，算作一票。裝袋的分類法 C*統(tǒng)計(jì)得票，并將得票最高的類賦予 X。通過(guò)取得票的平均值，而不是多數(shù)，裝袋也可以用于連續(xù)值的預(yù)測(cè)。（4）推進(jìn)：每個(gè)訓(xùn)練樣本賦予一個(gè)權(quán)。學(xué)習(xí)得到一系列分類法。學(xué)習(xí)得到分類法 Ct后，更新權(quán)，使得隨后的分類法 C t+1 “更關(guān)注” C t的分類錯(cuò)誤。最終的推進(jìn)分類法 C*組合每個(gè)分類法的表決，這里每個(gè)分類法的表決是其準(zhǔn)確率的函數(shù)。推進(jìn)算法也可以擴(kuò)充到連續(xù)值預(yù)測(cè)。應(yīng)用領(lǐng)域：是數(shù)據(jù)挖掘領(lǐng)域中研究和應(yīng)用最為廣泛的技術(shù)之一，許多分類算法被包含在統(tǒng)計(jì)分析工具的軟件包中，作為專門的分類工具來(lái)使用。分類問(wèn)題在商業(yè)、銀行業(yè)、生物學(xué)、文本挖掘、因特網(wǎng)篩選等領(lǐng)域都有廣泛應(yīng)用。例如在因特網(wǎng)篩選中，分類方法可以協(xié)助網(wǎng)絡(luò)工作人員將正常郵件和垃圾郵件進(jìn)行分類，從而制定有效的垃圾郵件過(guò)濾機(jī)制，防止垃圾郵件干擾人們的正常生活。8、決策樹(shù)歸納算法及其優(yōu)缺點(diǎn)決策樹(shù)定義：是用樣本的屬性作為結(jié)點(diǎn)，用屬性的取值作為分支的樹(shù)結(jié)構(gòu)。它是利用信息論原理對(duì)大量樣本的屬性進(jìn)行分析和歸納而產(chǎn)生的。決策樹(shù)的根結(jié)點(diǎn)是所有樣本中信息量最大的屬性。樹(shù)的中間結(jié)點(diǎn)是以該結(jié)點(diǎn)為根的子樹(shù)所包含的樣本子集中信息量最大的屬性。決策樹(shù)的葉結(jié)點(diǎn)是樣本的類別值。歸納算法過(guò)程：創(chuàng)建節(jié)點(diǎn)N，若劃分D中所有元組屬于同一個(gè)類C，返回N，并用C標(biāo)記若屬性表為空，返回N并以D中多數(shù)類標(biāo)記 從屬性表中找到最優(yōu)屬性a，標(biāo)記節(jié)點(diǎn)N 如果a是離散的且允許多路劃分，則從屬性表中刪除a 對(duì)屬性a在D上的每個(gè)劃分Dj，若Dj為空，則加一個(gè)樹(shù)葉到N并標(biāo)記D中的多數(shù)類，否則遞歸調(diào)用本算法處理Dj，返回的節(jié)點(diǎn)加到N 返回N優(yōu)點(diǎn)：更高的準(zhǔn)確性可以生成可理解的規(guī)則計(jì)算量不是很大可以處理連續(xù)和種類字段可以清晰顯示哪些字段比較重要容易轉(zhuǎn)化成分類規(guī)則：只要沿著樹(shù)根向下一直走到葉子，沿途的分裂條件就能夠唯一的決定一條分類的謂詞缺點(diǎn)：缺乏伸縮性，由于進(jìn)行深度優(yōu)先搜索，所以算法受內(nèi)存大小限制，難于處理大訓(xùn)練集為了處理大數(shù)據(jù)集的種種算法（離散化、取樣）不僅增加了分類算法的額外開(kāi)銷，而且降低了分類的準(zhǔn)確性。6.聚類分析的功能，主要的聚類方法及其特點(diǎn)。聚類：【不知道數(shù)據(jù)的分類，甚至連分成幾類也不知道】將物理或抽象對(duì)象的集合分成由類似的對(duì)象組成的多個(gè)類的過(guò)程被稱為聚類。由聚類所生成的簇是一組數(shù)據(jù)對(duì)象的集合，這些對(duì)象與同一個(gè)簇中的對(duì)象彼此相似，與其他簇中的對(duì)象相異。是無(wú)指導(dǎo)的學(xué)習(xí)。聚類與分類的主要區(qū)別：和分類學(xué)習(xí)相比，聚類的樣本沒(méi)有標(biāo)記，需要由聚類學(xué)習(xí)算法來(lái)自動(dòng)確定。聚類分析是研究如何在沒(méi)有訓(xùn)練集的條件下把樣本劃分為若干類。在分類中，對(duì)于目標(biāo)數(shù)據(jù)庫(kù)中存在哪些類是知道的，要做的就是將每一條記錄分別屬于哪一類標(biāo)記出來(lái)。主要的聚類方法：1）劃分方法：給定n個(gè)對(duì)象或數(shù)據(jù)元組的數(shù)據(jù)庫(kù)，劃分方法構(gòu)建數(shù)據(jù)的K個(gè)劃分，每個(gè)劃分表示一個(gè)簇，k<=n. 構(gòu)建不同劃分。如K均值、K中心點(diǎn)算法等。缺點(diǎn)是需要窮舉所有可能劃分，適用于中小規(guī)模數(shù)據(jù)庫(kù)2） 層次方法：對(duì)給定數(shù)據(jù)庫(kù)對(duì)象進(jìn)行層次分解，如Diana，Agnes、BIRCH、ROCK、CAMELEON等，缺點(diǎn)在于一旦一個(gè)步驟（合并或分裂）完成，就不能撤銷3） 基于密度的方法?；谶B接和密度函數(shù)，如DBSCAN和OPTICS4） 基于網(wǎng)格的方法，基于多層粒度函數(shù)，如STING、WaveCluster、CLIQUE等，把對(duì)象空間量化為有限個(gè)單元，形成網(wǎng)格結(jié)構(gòu)，聚類都在網(wǎng)格上進(jìn)行。處理速度快，處理時(shí)間依賴于量化空間每一維的單元數(shù)目5） 基于模型的方法，為每個(gè)簇假定一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合，如EM、SOM、COBWEB算法等6） 基于頻繁模式的聚類：從頻繁出現(xiàn)的維數(shù)自己中提取不同的頻繁模式。7） 基于約束的聚類：結(jié)合用戶指定或面向應(yīng)用的約束進(jìn)行聚類。應(yīng)用領(lǐng)域：是數(shù)據(jù)挖掘應(yīng)用的主要技術(shù)之一，它可以作為一個(gè)獨(dú)立的工具來(lái)使用，將未知類標(biāo)號(hào)的數(shù)據(jù)集劃分為多個(gè)類別之后，觀察每個(gè)類別中數(shù)據(jù)樣本的特點(diǎn)，并且對(duì)某些特定的類別作進(jìn)一步的分析。此外，聚類分析還可以作為其他數(shù)據(jù)挖掘技術(shù)（例如分類學(xué)習(xí)、關(guān)聯(lián)規(guī)則挖掘等）的預(yù)處理工作。4、人工神經(jīng)網(wǎng)絡(luò)：是一個(gè)函數(shù)，主要在于這個(gè)函數(shù)的自學(xué)習(xí)過(guò)程，在學(xué)習(xí)過(guò)程中，它根據(jù)正確結(jié)果不停的校正自己的網(wǎng)絡(luò)結(jié)構(gòu)。分類方法：1.依學(xué)習(xí)策略分類主要有：監(jiān)督式學(xué)習(xí)網(wǎng)絡(luò)為主、無(wú)監(jiān)督式學(xué)習(xí)網(wǎng)絡(luò)、混合式學(xué)習(xí)網(wǎng)絡(luò)、聯(lián)想式學(xué)習(xí)網(wǎng)絡(luò)、最適化學(xué)習(xí)網(wǎng)絡(luò)2.依網(wǎng)絡(luò)架構(gòu)分類主要有:前向式架構(gòu)、回饋式架構(gòu)、強(qiáng)化式架構(gòu)優(yōu)點(diǎn)：預(yù)測(cè)準(zhǔn)確性高、對(duì)噪聲數(shù)據(jù)的高承受力（訓(xùn)練樣本差錯(cuò)時(shí)仍可工作）、輸出離散值、快速評(píng)估目標(biāo) 缺點(diǎn)：1、需要很長(zhǎng)的訓(xùn)練時(shí)間 2、難以與域知識(shí)合作3、可解釋性差BP網(wǎng)絡(luò)：是一種按誤差逆?zhèn)鞑ニ惴ㄓ?xùn)練的多層前饋網(wǎng)絡(luò)。BP網(wǎng)絡(luò)能學(xué)習(xí)和存貯大量的輸入-輸出模式映射關(guān)系，而無(wú)需事前揭示描述這種映射關(guān)系的數(shù)學(xué)方程。BP算法由數(shù)據(jù)流的前向計(jì)算（正向傳播）和誤差信號(hào)的反向傳播兩個(gè)過(guò)程構(gòu)成。 BP神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過(guò)程：神經(jīng)網(wǎng)絡(luò)在外界輸入樣本的刺激下不斷改變網(wǎng)絡(luò)連接的權(quán)值，閾值。以使網(wǎng)絡(luò)的輸出不斷地接近期望的輸出。學(xué)習(xí)的本質(zhì)：對(duì)各連接權(quán)值、閾值的動(dòng)態(tài)調(diào)整。學(xué)習(xí)規(guī)則：權(quán)值、閾值調(diào)整規(guī)則，即在學(xué)習(xí)過(guò)程中網(wǎng)絡(luò)中各神經(jīng)元的連接權(quán)變化所依據(jù)的一定的調(diào)整規(guī)則 BP學(xué)習(xí)算法的步驟: 選定學(xué)習(xí)的數(shù)據(jù),p=1,P, 隨機(jī)確定初始權(quán)矩陣W（0）; 用學(xué)習(xí)數(shù)據(jù)計(jì)算網(wǎng)絡(luò)輸出;反向修正,直到用完所有學(xué)習(xí)數(shù)據(jù)。BP神經(jīng)網(wǎng)絡(luò)算法步驟：1初始化，依據(jù)實(shí)際問(wèn)題給出網(wǎng)絡(luò)連接結(jié)構(gòu)，隨機(jī)設(shè)置所有連接權(quán)值。2提供訓(xùn)練樣本，如果輸入變量為n個(gè)，輸出變量為m個(gè)，則每個(gè)訓(xùn)練樣本形式為（x1,x2,xn;t1,t2,tm）。這里t1,t2,tm是輸入為x1,x2,xn的期望輸出。3計(jì)算實(shí)際輸出，利用非純屬函數(shù)逐級(jí)計(jì)算各層節(jié)點(diǎn)的輸入值。4權(quán)值調(diào)整，用遞歸方法從輸出節(jié)點(diǎn)開(kāi)始返回到隱層節(jié)點(diǎn)。5返回第二步，重復(fù)執(zhí)行，直到達(dá)到滿意誤差。BP網(wǎng)絡(luò)的缺點(diǎn):易陷入局部最小點(diǎn)；收斂速度慢；學(xué)習(xí)過(guò)程容易出現(xiàn)震蕩；9、提升Adaboost：在提升方法中，權(quán)重賦予每個(gè)訓(xùn)練元組。迭代地學(xué)習(xí)k個(gè)分類器序列。學(xué)習(xí)得到分類器Mi之后，更新權(quán)重，使得其后的分類器Mi+1“更關(guān)注”Mi誤分類的訓(xùn)練元組。最終提升的分類器M*組合每個(gè)個(gè)體分類器，其中每個(gè)分類器投票的權(quán)重是其準(zhǔn)確率的函數(shù)。過(guò)程：給定數(shù)據(jù)集D，包含d個(gè)類標(biāo)記的元組(X1，y1)，(X2，y2),，(Xd，yd)，其中，yi是元組Xi的類標(biāo)號(hào)。Adaboost對(duì)每個(gè)訓(xùn)練元組賦予相等的權(quán)重1/d。在第i輪中：從D中元組抽樣，形成大小為d的訓(xùn)練集Di。每個(gè)元組被選中的機(jī)會(huì)由它的權(quán)重決定。從訓(xùn)練元組Di導(dǎo)出分類模型Mi。使用Di作為檢驗(yàn)集計(jì)算Mi的誤差。調(diào)整訓(xùn)練元組D的權(quán)重：如果元組不正確地分類，則它的權(quán)重增加。如果元組正確分類，則它的權(quán)重減少。元組的權(quán)重反應(yīng)對(duì)它們分類的困難程度權(quán)重越高，越可能錯(cuò)誤地分類。分類器使用這些權(quán)重產(chǎn)生下一輪的訓(xùn)練樣本。如果分類器Mi的性能太差，誤差率超過(guò)0.5，則丟棄它。AdaBoost算法的優(yōu)點(diǎn)：一是訓(xùn)練的錯(cuò)誤率上界，隨著迭代次數(shù)的增加，會(huì)逐漸下降；二是adaboost算法即使訓(xùn)練次數(shù)很多，也不會(huì)出現(xiàn)過(guò)擬合的問(wèn)題。10、DBSCAN算法的特點(diǎn)和算法描述DBSCAN 原理：(具有噪聲的基于密度的聚類應(yīng)用)，這類方法將簇卸任是數(shù)據(jù)空間中被低密度區(qū)域分割開(kāi)的稠密數(shù)據(jù)對(duì)象區(qū)域。它將簇定義為密度相連的點(diǎn)的最大集合?？稍诰哂性肼暤目臻g數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意開(kāi)關(guān)的聚類。基于密度的簇是基于密度可達(dá)性的密度相連的點(diǎn)的最大集合。算法描述：(1)任選一未處理過(guò)的點(diǎn)p為種子點(diǎn)；(2)如果p為核心對(duì)象，則查找點(diǎn)p直接密度可達(dá)的點(diǎn)，將其中未標(biāo)記的點(diǎn)標(biāo)記簇標(biāo)號(hào)，并且將未處理的其它核心點(diǎn)加入種子列表；否則，轉(zhuǎn)到(1)；(3) 將種子列表的點(diǎn)依次執(zhí)行操作(2)直到列表為空，一個(gè)簇形成；(4) 重復(fù)(1)-(3)，直到?jīng)]有點(diǎn)可以加到任何一個(gè)簇中，聚類完成，剩余的點(diǎn)為噪聲點(diǎn)。 優(yōu)點(diǎn)：1如果用戶定義的參數(shù)設(shè)置的恰當(dāng)，該算法可以有效地找出任意形狀的簇。同時(shí)，DBSCAN能夠識(shí)別出噪聲點(diǎn)。2DBSCAN對(duì)于數(shù)據(jù)庫(kù)中的樣本的順序不敏感。但是，對(duì)于處于簇類之間邊界樣本，可能會(huì)根據(jù)哪個(gè)簇類優(yōu)先被探測(cè)到而其歸屬有所擺動(dòng)。缺點(diǎn)：1聚類質(zhì)量對(duì)參數(shù)非常敏感;2需要較大的內(nèi)存和輸入輸出支持。3使用全局密度參數(shù)，不能處理多密度數(shù)據(jù)集。4、支持向量機(jī)（SVM）思想：使用一種非線性映射，將原訓(xùn)練集映射到較高的維，在新的維上，它搜索最佳分離超平面，使用一個(gè)適合的對(duì)足夠高維的非線性映射，兩類數(shù)據(jù)總可以被超平面分開(kāi)。優(yōu)點(diǎn)：（1）對(duì)復(fù)雜的非線性決策邊界的建模能力是高度準(zhǔn)確的（2）不太容易過(guò)分?jǐn)M合（3）提供了學(xué)習(xí)模型的緊湊表示。（4）可以用來(lái)預(yù)測(cè)和分類。缺點(diǎn)：訓(xùn)練時(shí)間長(zhǎng)。特點(diǎn) ：SVM是一種有堅(jiān)實(shí)理論基礎(chǔ)的小樣本學(xué)習(xí)方法 ; SVM最終決策函數(shù)只由少數(shù)的支持向量所確定，計(jì)算復(fù)雜度和支持向量的數(shù)目有關(guān)。算法具有較好的“魯棒”性。SVM可以有效處理非線性分類和回歸問(wèn)題; SVM可以確定所建模型的推廣能力的上界 ;核函數(shù)的選取和參數(shù)優(yōu)化仍需要解決5、EM：（定義）EM(期望最大化)算法是一種流行的迭代求精算法，可以用來(lái)求得參數(shù)的估計(jì)值，它可看作是k均值算法的一種擴(kuò)展，基于簇的均值把對(duì)象指派到最相似的簇中。EM不是把每個(gè)對(duì)象指派到特定的簇，而是根據(jù)一個(gè)代表隸屬概率的權(quán)重將每個(gè)對(duì)象指派到簇。（步驟）（1）期望步：對(duì)每簇計(jì)算對(duì)象x的簇隸屬概率（2）最大化步：利用前面得到的概率估計(jì)重新估計(jì)模型參數(shù)（優(yōu)點(diǎn)）簡(jiǎn)單和穩(wěn)定，收斂快（缺點(diǎn)）達(dá)不到局部最優(yōu)4、關(guān)聯(lián)規(guī)則：定義：最初由R.Agrawal 等人提出，用來(lái)發(fā)現(xiàn)超級(jí)市場(chǎng)中用戶購(gòu)買的商品之間的隱含關(guān)聯(lián)關(guān)系，并用規(guī)則的形式表示出來(lái)，稱為關(guān)聯(lián)規(guī)則。應(yīng)用：關(guān)聯(lián)規(guī)則除了可以發(fā)現(xiàn)超市購(gòu)物中隱含的關(guān)聯(lián)關(guān)系之外，還可以應(yīng)用于其他很多領(lǐng)域。關(guān)聯(lián)規(guī)則的應(yīng)用還包括文本挖掘、商品廣告郵寄分析、網(wǎng)絡(luò)故障分析等。分類：（1）基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)，關(guān)聯(lián)規(guī)則可以分為單維的和多維的。（2）基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。（3）基于規(guī)則中處理的變量的類型不同，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。挖掘步驟：1）找出交易數(shù)據(jù)庫(kù)中所有大于或等于用戶指定的最小支持度的頻繁項(xiàng)集；（2）利用頻繁項(xiàng)集生成所需要的關(guān)聯(lián)規(guī)則，根據(jù)用戶設(shè)定的最小可信度進(jìn)行取舍，產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)。3、樸素貝葉斯分類：定義：貝葉斯分類法是統(tǒng)計(jì)學(xué)分類方法，可以預(yù)測(cè)類成員關(guān)系的可能性。樸素貝葉斯分類法假定一個(gè)屬性值對(duì)給定類的影響?yīng)毩⒂谄渌麑傩灾?。它表示屬性子集間的依賴主要思想：設(shè)為一個(gè)類別未知的數(shù)據(jù)樣本，H為某個(gè)假設(shè)，若數(shù)據(jù)樣本X屬于一個(gè)特定的類別C，分類問(wèn)題就是決定P（H|X），即在獲得數(shù)據(jù)樣本X時(shí)假設(shè)成立的概率。優(yōu)點(diǎn)：（1）理論上，貝葉斯分類具有最小的錯(cuò)誤率（2）可以用來(lái)為不直接使用貝葉斯定理的其他分類法提供理論判定（3）有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率（4）模型所需估計(jì)的參數(shù)很少，對(duì)缺失數(shù)據(jù)不太敏感，算法也比較簡(jiǎn)單（5）網(wǎng)格結(jié)構(gòu)一旦確定下來(lái)后，添加新變量容易（5）適合處理不完整的數(shù)據(jù)（6）對(duì)過(guò)分?jǐn)M合問(wèn)題魯棒。缺點(diǎn)：（1）實(shí)際上，由于對(duì)其使用的假定的不正確性，以及缺乏可用的概率，此分類法并不具有最小的錯(cuò)誤率（2）有可能遇到零概率值，需要修正（3）構(gòu)造網(wǎng)格費(fèi)時(shí)、費(fèi)力為什么樸素：樸素貝葉斯分類假定一個(gè)屬性值對(duì)給定類的影響?yīng)毩⒂谄渌鼘傩缘闹?。該假定稱作類條件獨(dú)立。做此假定是為了簡(jiǎn)化所需計(jì)算，并在此意義下稱為“樸素的”2、簡(jiǎn)述數(shù)值數(shù)據(jù)根據(jù)直觀劃分離散化的3-4-5規(guī)則（1）如果一個(gè)區(qū)間在最高有效位包括3， 6，7或 9 個(gè)不同的值，則將該區(qū)間劃分為3個(gè)區(qū)間（對(duì)于3，6和9 ，劃分為3個(gè)等寬的區(qū)間；對(duì)于7，按2-3-2劃分為3個(gè)區(qū)間）。（2）如果最高位包含2，4，8個(gè)不同值，則將區(qū)間劃分為4個(gè)等寬區(qū)間。（3）如果最高位包含1 ，5或10個(gè)不同的值，則將區(qū)間劃分為5個(gè)等寬的區(qū)間。最高分層一般在第5個(gè)百分位到第95個(gè)百分位上進(jìn)行。2、急切學(xué)習(xí)法是在接收待分類的新元組(如檢驗(yàn)元組)之前，利用訓(xùn)練集，構(gòu)造泛化模型，即分類器。學(xué)習(xí)后的模型已經(jīng)就緒，并急于對(duì)先前未見(jiàn)過(guò)的元組進(jìn)行分類。常見(jiàn)的急切學(xué)習(xí)法主要有支持向量機(jī)，決策樹(shù)歸納，貝葉斯分類，基于規(guī)則的分類等。3、惰性學(xué)習(xí)法是當(dāng)給定一組訓(xùn)練元組時(shí)，簡(jiǎn)單地存儲(chǔ)它，僅當(dāng)給出檢驗(yàn)元組時(shí)，才利用存儲(chǔ)的訓(xùn)練元組的相似性對(duì)該元組進(jìn)行分類，不像急切學(xué)習(xí)法，惰性學(xué)習(xí)法在提供訓(xùn)練元組時(shí)只做少量工作，而在進(jìn)行分類或預(yù)測(cè)時(shí)才做更多的工作。常見(jiàn)的惰性學(xué)習(xí)法有K最近鄰和基于案例的推理分類法。急切學(xué)習(xí)法和惰性學(xué)習(xí)法的優(yōu)缺點(diǎn)：急切學(xué)習(xí)法訓(xùn)練分類器時(shí)需耗費(fèi)大量時(shí)間，但對(duì)檢驗(yàn)元組進(jìn)行分類或預(yù)測(cè)時(shí)速度較快，且占用空間少； 惰性學(xué)習(xí)法不需要建立模型，但是在對(duì)檢驗(yàn)元組進(jìn)行分類或預(yù)測(cè)時(shí)，需要將所有訓(xùn)練元組與檢驗(yàn)元組進(jìn)行運(yùn)算，計(jì)算開(kāi)銷可能相當(dāng)大，耗費(fèi)大量時(shí)間。1、后向傳播是一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法；神經(jīng)網(wǎng)絡(luò)是一組連接的輸入/輸出單元，每個(gè)連接都與一個(gè)權(quán)相連。在學(xué)習(xí)階段，通過(guò)調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)，使得能夠預(yù)測(cè)輸入樣本的正確標(biāo)號(hào)來(lái)學(xué)習(xí)。優(yōu)點(diǎn)：預(yù)測(cè)精度總的來(lái)說(shuō)較高、健壯性好，訓(xùn)練樣本中包含錯(cuò)誤時(shí)也可正常工作、輸出可能是離散值、連續(xù)值或者是離散或量化屬性的向量值、對(duì)目標(biāo)進(jìn)行分類較快缺點(diǎn)：訓(xùn)練（學(xué)習(xí)）時(shí)間長(zhǎng)、蘊(yùn)涵在學(xué)習(xí)的權(quán)中的符號(hào)含義很難理解、很難根專業(yè)領(lǐng)域知識(shí)相整合34、KNN定義：即K最近鄰分類法，它是基于類比學(xué)習(xí)，即通過(guò)給定的檢驗(yàn)元組與和他相似的訓(xùn)練元組進(jìn)行比較來(lái)學(xué)習(xí)。優(yōu)點(diǎn)1）算法簡(jiǎn)單直觀，易于實(shí)現(xiàn)；（2）不需要產(chǎn)生額外的數(shù)據(jù)來(lái)描述規(guī)則，并且可以存在噪音；（3）可以較好地避免樣本數(shù)量的不平衡問(wèn)題；（4）減少了類別特征選擇不當(dāng)對(duì)分類結(jié)果造成的不利影響，可以最大程度地減少分類過(guò)程中的誤差項(xiàng)（5）適合增量學(xué)習(xí)缺點(diǎn)：1）分類速度慢（2）樣本庫(kù)容量依賴性較強(qiáng)（3）必須指定K值，K值選擇不當(dāng)則分類精度不能保證。k值的設(shè)定，k太小，分類結(jié)果易受噪聲點(diǎn)影響，k值太大，近鄰中又可能包含太多的其它類別的點(diǎn)（4）計(jì)算開(kāi)銷大（5）需要有效的存儲(chǔ)技術(shù)和并行硬件的支撐。1、數(shù)據(jù)預(yù)處理過(guò)程：數(shù)據(jù)清理：旨在消除或減少數(shù)據(jù)噪音和處理遺漏值的數(shù)據(jù)預(yù)處理。相關(guān)性分析：數(shù)據(jù)中許多屬性可能與分類和預(yù)測(cè)任務(wù)不相關(guān)。數(shù)據(jù)變換：數(shù)據(jù)可以泛化到較高層概念。3.數(shù)據(jù)倉(cāng)庫(kù)的特點(diǎn)和操作數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)的區(qū)別：數(shù)據(jù)倉(cāng)庫(kù)的特點(diǎn)：（1）面向主題的：數(shù)據(jù)倉(cāng)庫(kù)圍繞一些主題，如顧客、供應(yīng)商、產(chǎn)品和銷售組織。數(shù)據(jù)倉(cāng)庫(kù)關(guān)注決策者的數(shù)據(jù)建模與分析，而不是構(gòu)造組織機(jī)構(gòu)的日常操作和事務(wù)處理。因此，數(shù)據(jù)倉(cāng)庫(kù)排除對(duì)于決策無(wú)用的數(shù)據(jù)，提供特定主題的簡(jiǎn)明視圖。（2）集成的：通常，構(gòu)造數(shù)據(jù)倉(cāng)庫(kù)是將多個(gè)異種數(shù)據(jù)源，如關(guān)系數(shù)據(jù)庫(kù)、一般文件和聯(lián)機(jī)事務(wù)處理記錄，集成在一起。使用數(shù)據(jù)清理和數(shù)據(jù)集成技術(shù)，確保命名約定、編碼結(jié)構(gòu)、屬性度量的一致性。 （3）時(shí)變的：數(shù)據(jù)存儲(chǔ)從歷史的角度（例如，過(guò)去 5-10 年）提供信息。數(shù)據(jù)倉(cāng)庫(kù)中的關(guān)鍵結(jié)構(gòu)，隱式或顯式地包含時(shí)間元素。 （4）非易失的：數(shù)據(jù)倉(cāng)庫(kù)總是物理地分離存放數(shù)據(jù)；這些數(shù)據(jù)源于操作環(huán)境下的應(yīng)用數(shù)據(jù)。由于這種分離，數(shù)據(jù)倉(cāng)庫(kù)不需要事務(wù)處理、恢復(fù)和并行控制機(jī)制。通常，它只需要兩種數(shù)據(jù)訪問(wèn)：數(shù)據(jù)的初始化裝入和數(shù)據(jù)訪問(wèn)。操作數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)的區(qū)別： （1）用戶和系統(tǒng)的面向性：OLTP 是面向顧客的，用于辦事員、客戶、和信息技術(shù)專業(yè)人員的事務(wù)和查詢處理。OLAP 是面向市場(chǎng)的，用于知識(shí)工人（包括經(jīng)理、主管、和分析人員）的數(shù)據(jù)分析。（2）數(shù)據(jù)內(nèi)容：OLTP 系統(tǒng)管理當(dāng)前數(shù)據(jù)。通常，這種數(shù)據(jù)太瑣碎，難以方便地用于決策。OLAP 系統(tǒng)管理大量歷史數(shù)據(jù)，提供匯總和聚集機(jī)制，并在不同的粒度級(jí)別上存儲(chǔ)和管理信息。這些特點(diǎn)使得數(shù)據(jù)容易用于見(jiàn)多識(shí)廣的決策。（3）數(shù)據(jù)庫(kù)設(shè)計(jì)：通常，OLTP 系統(tǒng)采用實(shí)體-聯(lián)系（ER）模型和面向應(yīng)用的數(shù)據(jù)庫(kù)設(shè)計(jì)。而 OLAP 系統(tǒng)通常采用星形或雪花模型(2.2.2小節(jié)討論）和面向主題的數(shù)據(jù)庫(kù)設(shè)計(jì)。（4）視圖：OLTP系統(tǒng)主要關(guān)注一個(gè)企業(yè)或部門內(nèi)部的當(dāng)前數(shù)據(jù)，而不涉及歷史數(shù)據(jù)或不同組織的數(shù)據(jù)。相比之下，由于組織的變化，OLAP 系統(tǒng)常?？缭綌?shù)據(jù)庫(kù)模式的多個(gè)版本。OLAP 系統(tǒng)也處理來(lái)自不同組織的信息，由多個(gè)數(shù)據(jù)存儲(chǔ)集成的信息。由于數(shù)據(jù)量巨大，OLAP 數(shù)據(jù)也存放在多個(gè)存儲(chǔ)介質(zhì)上。（5）訪問(wèn)模式：OLTP 系統(tǒng)的訪問(wèn)主要由短的、原子事務(wù)組成。這種系統(tǒng)需要并行控制和恢復(fù)機(jī)制。然而，對(duì) OLAP 系統(tǒng)的訪問(wèn)大部分是只讀操作（由于大部分?jǐn)?shù)據(jù)倉(cāng)庫(kù)存放歷史數(shù)據(jù)，而不是當(dāng)前數(shù)據(jù)），盡管許多可能是復(fù)雜的查詢。1、 概念分層及作用，舉例說(shuō)明。一個(gè)概念分層定義一個(gè)映射序列，將低層概念到更一般的高層概念。概念分層也可以通過(guò)將給定維或?qū)傩缘闹惦x散化或分組來(lái)定義，產(chǎn)生集合分組分層。可以在值組間定義全序或偏序。例子如圖關(guān)于維 price 的集合分組概念分層。其中，區(qū)間($X.$Y 表示由$X（不包括）到$Y（包括）。概念分層可以由系統(tǒng)用戶、領(lǐng)域?qū)＜?、知識(shí)工程師人工地提供，也可以根據(jù)數(shù)據(jù)分布的統(tǒng)計(jì)分析自動(dòng)地產(chǎn)生。對(duì)于一個(gè)給定的屬性或維，根據(jù)不同的用戶視圖，可能有多個(gè)概念分層。例如，用戶可能愿意用 inepensive, moderately_priced和 expensive 來(lái)組織price。6.ID3算法基本思想和算法描述，C4.5算法增加了那些功能？基本思想：首先找出最有判別力的因素，然后把數(shù)據(jù)分成多個(gè)子集，每個(gè)子集又選擇最有判別力的因素進(jìn)一步劃分，一直進(jìn)行到所有子集僅包含同一類型的數(shù)據(jù)為止。最后得到一棵決策樹(shù)，可以用它來(lái)對(duì)新的樣例進(jìn)行分類。算法描述：從訓(xùn)練集中隨機(jī)選擇一個(gè)既含正例又含反例的子集(稱為窗口)；用“建樹(shù)算法”對(duì)當(dāng)前窗口形成一棵決策樹(shù)；對(duì)訓(xùn)練集(窗口除外)中例子用所得決策樹(shù)進(jìn)行類別判定，找出錯(cuò)判的例子；若存在錯(cuò)判的例子，把它們插入窗口，重復(fù)步驟，否則結(jié)束。優(yōu)點(diǎn)：1、理論清晰，算法簡(jiǎn)單，很有實(shí)用價(jià)值的示例學(xué)習(xí)算法。2、計(jì)算時(shí)間是例子個(gè)數(shù)、特征屬性個(gè)數(shù)、節(jié)點(diǎn)個(gè)數(shù)之積的線性函數(shù)，總預(yù)測(cè)準(zhǔn)確率較令人滿意缺點(diǎn)：（1）ID3算法在選擇根結(jié)點(diǎn)和各內(nèi)部結(jié)點(diǎn)中的分枝屬性時(shí)，使用信息增益作為評(píng)價(jià)標(biāo)準(zhǔn)。信息增益的缺點(diǎn)是傾向于選擇取值較多的屬性，在有些情況下這類屬性可能不會(huì)提供太多有價(jià)值的信息（2）ID3算法只能對(duì)描述屬性為離散型屬性的數(shù)據(jù)集構(gòu)造決策樹(shù)C4.5是機(jī)器學(xué)習(xí)算法中的另一個(gè)分類決策樹(shù)算法，基于ID3算法進(jìn)行改進(jìn)后的一種重要算法，相比于ID3算法，改進(jìn)有如下幾個(gè)要點(diǎn)：（1）用信息增益率來(lái)選擇屬性。ID3選擇屬性用的是子樹(shù)的信息增益，這里可以用很多方法來(lái)定義信息，ID3使用的是熵（entropy， 熵是一種不純度度量準(zhǔn)則），也就是熵的變化值，而C4.5用的是信息增益率。（2）在決策樹(shù)構(gòu)造過(guò)程中進(jìn)行剪枝，因?yàn)槟承┚哂泻苌僭氐慕Y(jié)點(diǎn)可能會(huì)使構(gòu)造的決策樹(shù)過(guò)適應(yīng)（Overfitting），如果不考慮這些結(jié)點(diǎn)可能會(huì)更好。（3）對(duì)非離散數(shù)據(jù)也能處理。（4）能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。8、劃分算法的描述1、K均值：輸入：簇的數(shù)目 k 和包含 n 個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出：k 個(gè)簇，使平方誤差最小方法：(1)，隨機(jī)地選擇k個(gè)對(duì)象作為初始簇中心（2）根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象再只拍到最相似的簇（3）更新簇均值，即計(jì)算每個(gè)簇中對(duì)象的均值；（4）重復(fù)（2）（3）步，直到簇中心點(diǎn)不再發(fā)生變化。優(yōu)點(diǎn)：（1）思想簡(jiǎn)單易行；相對(duì)有效：O（tkn），n是多有對(duì)象的數(shù)目，K是簇的數(shù)目，t是迭代的次數(shù)，通常k，t<<n（2）經(jīng)常以局部最優(yōu)結(jié)束（3）時(shí)間復(fù)雜度接近線性；（4）對(duì)大數(shù)據(jù)集，是可伸縮和高效率的。缺點(diǎn)：（1）只有在簇的平均值被定義時(shí)才能使用，不適合分類屬性的數(shù)據(jù)；（2）必須實(shí)現(xiàn)給出要生成的簇的數(shù)目K（3）不能處理噪聲點(diǎn)和孤立點(diǎn)數(shù)據(jù)（4）不適合發(fā)現(xiàn)凸面向形狀的簇，或者大小差別很大的簇。2、K-中心點(diǎn)算法的輸入、輸出及聚類過(guò)程(流程)。輸入：結(jié)果簇的數(shù)目k，包含n個(gè)對(duì)象的數(shù)據(jù)集；輸出：k個(gè)簇，使得所有對(duì)象與其最近中心點(diǎn)的相異度總和最小。描述：隨機(jī)選擇k個(gè)對(duì)象作為初始中心點(diǎn)；計(jì)算其它對(duì)象與這k個(gè)中心的距離，然后把每個(gè)對(duì)象歸入離它“最近”的簇； 隨機(jī)地選擇一個(gè)非中心點(diǎn)對(duì)象Orandom，并計(jì)算用Orandom代替Oj的總代價(jià)S；如果S<0,則用Orandom代替Oj，形成新的k個(gè)中心點(diǎn)集合；重復(fù)迭代第3、4步，直到中心點(diǎn)不變?yōu)橹埂中心點(diǎn)算法的特點(diǎn)：（1）當(dāng)存在噪聲和離群點(diǎn)時(shí)，K中心點(diǎn)方法比K均值更健壯，因?yàn)橹行狞c(diǎn)不像均值那樣容易受離群點(diǎn)或其他極端值的影響。（2）K中心點(diǎn)方法的執(zhí)行代價(jià)比K均值算法高。（3）兩種方法都要指定簇的個(gè)數(shù)K.2OLAP上卷操作與SQL的group操作的異同？上卷：上卷操作通過(guò)沿概念分層向上攀升，或者通過(guò)維歸約，在數(shù)據(jù)方上進(jìn)行聚集。分層被定義為全序 street < city < province_or_state < country。所展示的上卷操作沿 location 的分層，結(jié)果數(shù)據(jù)方按 country，而不是按 city 對(duì)數(shù)據(jù)分組。 當(dāng)用維歸約進(jìn)行上卷時(shí)，一個(gè)或多個(gè)維由給定的數(shù)據(jù)方刪除SQL的group操作：是對(duì)一個(gè)屬性中相同值的數(shù)據(jù)進(jìn)行合并。