柚子快報(bào)激活碼778899分享：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘復(fù)習(xí)資料

http://yzkb.51969.com/

一、題型與考點(diǎn)[第一種]

1、解釋基本概念(中英互譯+解釋簡(jiǎn)單的含義)； 2、簡(jiǎn)答題(每個(gè)10分有兩個(gè)一定要記住)：

① 考時(shí)間序列Time series(第六章)的基本概念含義+解釋+作用（序列模式挖掘的作用）； ② 考聚類(第五章)重點(diǎn)考密度聚類的定義描述+DBSCAN算法的描述定義(+DBSCAN優(yōu)缺點(diǎn))+應(yīng)用；

3、考綜合題：

① C4.5(ID3)考偽代碼； ② kNN考偽代碼； ③ Apriori考偽代碼； ④ k-Means考偽代碼； ⑤ PageRank考偽代碼+定義+應(yīng)用（這個(gè)題目占比很大好好復(fù)習(xí)）； ⑥ EM算法應(yīng)該會(huì)考定義； ⑦ 閉合項(xiàng)目集會(huì)考； 考偽代碼的題目一定要去牢記，記住了應(yīng)該就差不多了(偽代碼應(yīng)該出的題目會(huì)比較簡(jiǎn)單一些，不考選擇填空)

4、考點(diǎn)詳解章節(jié)?

第一章+第二章應(yīng)該只考名詞解釋、中英互譯(比如說(shuō)數(shù)據(jù)挖掘、爬蟲、數(shù)據(jù)倉(cāng)庫(kù)、信息熵、知識(shí)發(fā)現(xiàn)、數(shù)據(jù)分析、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、分類聚類等等)； 第三章考Apriori算法+閉合項(xiàng)目集； 第四章考KNN算法+ID3算法+EM算法； 第五章非常重要考點(diǎn)多分?jǐn)?shù)很高(重點(diǎn)復(fù)習(xí))考聚類的技術(shù)方法+K中心點(diǎn)算法(定義簡(jiǎn)答）+AGNES算法+DIANA算法考大題+密度聚類方法考DBSCAN(重點(diǎn)） 第六章考時(shí)間序列+序列模式挖掘的作用 第七章考web數(shù)據(jù)來(lái)源+PageRank算法+基于隨機(jī)沖浪的PageRank算法+權(quán)威中心頁(yè)面定義 第八章應(yīng)該不考；

二、題型與考點(diǎn)[第二種]（ffjtql總結(jié)）

第一章 緒論

一、[課后習(xí)題]中英互譯與解釋 1、Data Mining：數(shù)據(jù)挖掘

?（1）【簡(jiǎn)單定義】從大型數(shù)據(jù)中挖掘所需要的知識(shí)（課后答案給的這個(gè)）； ?（2）【KDD看作數(shù)據(jù)挖掘的特例】從數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)以及其他數(shù)據(jù)存儲(chǔ)方式中挖掘有用知識(shí)的過(guò)程（P11）； ?（3）【作為KDD過(guò)程的一個(gè)步驟】KDD（知識(shí)發(fā)現(xiàn)）中通過(guò)特定的算法在可接受的計(jì)算效率限制內(nèi)生成特定模式的一個(gè)步驟（P11）； ?（4）【廣義】從大型數(shù)據(jù)集中，挖掘隱含在其中的、人們事先不知道的、對(duì)決策有用的知識(shí)的完整過(guò)程（P11）； ?（5）【狹義】從特定形式的數(shù)據(jù)集中提煉知識(shí)的過(guò)程（P11）。

2、Artificial Intelligence：人工智能 ????????研究如何應(yīng)用機(jī)器來(lái)模擬人類某些智能行為的基本理論、方法和技術(shù)的一門科學(xué)。 3、Machine Learning：機(jī)器學(xué)習(xí) ????????研究如何使用機(jī)器來(lái)模擬人類學(xué)習(xí)活動(dòng)的一門學(xué)科。 4、Knowledge Engineering：知識(shí)工程 ????????研究知識(shí)信息處理并探討開發(fā)知識(shí)系統(tǒng)的技術(shù)。 5、Information Retrieval：信息檢索 ????????研究合適的信息組織并根據(jù)用戶需求快速而準(zhǔn)確地查找信息的技術(shù)。通常指的是計(jì)算機(jī)息檢索，它以計(jì)算機(jī)技術(shù)為手段，完成電子信息的匯集、存儲(chǔ)和查找等的相關(guān)技術(shù)。 6、Data Visualization：數(shù)據(jù)可視化 ????????運(yùn)用計(jì)算機(jī)圖形學(xué)和圖像處理等技術(shù)，將數(shù)據(jù)換為圖形或圖像在屏幕上顯示出來(lái)。它是進(jìn)行人機(jī)交互處理、數(shù)據(jù)解釋以及提高系統(tǒng)可用性的重要手段。 7、OLTP(On-Line Transaction Processing)：聯(lián)機(jī)事務(wù)處理 ????????傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)的主要應(yīng)用，主要是基本的、日常的事務(wù)處理（增刪改查），例如銀行交易（CSDN）。 8、OLAP(On-Line Analytic Processing)：聯(lián)機(jī)分析處理 ????????數(shù)據(jù)倉(cāng)庫(kù)系統(tǒng)的主要應(yīng)用，支持復(fù)雜的分析操作，側(cè)重決策支持，并且提供直觀易懂的查詢結(jié)果（CSDN）。 9、Decision Support：決策支持 ????????決策者通過(guò)數(shù)據(jù)、模型和知識(shí)，以人機(jī)交互方式進(jìn)行半結(jié)構(gòu)化或非結(jié)構(gòu)化決策。 10、KDD(Knowledge Discovery in Databases)：知識(shí)發(fā)現(xiàn) ????????從數(shù)據(jù)中辨別有效的、新穎的、潛在有用的、最終可理解的模式的過(guò)程。 11、Transaction Database：事務(wù)數(shù)據(jù)庫(kù) ????????一個(gè)事務(wù)數(shù)據(jù)庫(kù)是對(duì)事務(wù)型數(shù)據(jù)的收集。 12、Distributed Database：分布式數(shù)據(jù)庫(kù) ????????物理上分散而邏輯上集中的數(shù)據(jù)庫(kù)系統(tǒng)【在邏輯上是一個(gè)統(tǒng)一的整體，在物理上則是分別存儲(chǔ)在不同的物理節(jié)點(diǎn)上】。

二、[補(bǔ)充]名詞解釋 1、大數(shù)據(jù)：

????????指一種規(guī)模大到在獲取、存儲(chǔ)、管理、分析方面大大超出了傳統(tǒng)數(shù)據(jù)庫(kù)軟件工具能力范圍的數(shù)據(jù)集合，具有海量的數(shù)據(jù)規(guī)模、快速的數(shù)據(jù)流轉(zhuǎn)、多樣的數(shù)據(jù)類型和價(jià)值密度低四大特征。 2、數(shù)據(jù)分析技術(shù)（必考）：

????????是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)集中識(shí)別有效的、新穎的、潛在有用的，以及最終可理解的模式的非平凡過(guò)程。它是一門涉及面很廣的交叉學(xué)科，包括機(jī)器學(xué)習(xí)、數(shù)理統(tǒng)計(jì)、神級(jí)網(wǎng)絡(luò)、數(shù)據(jù)庫(kù)、模式識(shí)別、粗糙集等相關(guān)技術(shù)。 3、廣義知識(shí)(Generalization)：

????????是指描述類別特征的概括性知識(shí)。這類數(shù)據(jù)挖掘系統(tǒng)是對(duì)細(xì)節(jié)數(shù)據(jù)所蘊(yùn)含的概念特征信息的概括和抽象的過(guò)程。 4、關(guān)聯(lián)知識(shí)(Association)：

????????反映一個(gè)事件和其他事件之間的依賴或關(guān)聯(lián)。關(guān)聯(lián)知識(shí)挖掘的目的就是找出數(shù)據(jù)庫(kù)中隱藏的關(guān)聯(lián)信息。 5、傳統(tǒng)數(shù)據(jù)倉(cāng)庫(kù)技術(shù)：

????????使用ETL(Extract,Transform,Load)或ETCL(Extract,Transform,Clean,Load)工具實(shí)現(xiàn)數(shù)據(jù)的導(dǎo)出、轉(zhuǎn)換、清洗和裝入工具。使用操作型數(shù)據(jù)存儲(chǔ)(Operational Data Store.,oDS)存儲(chǔ)明細(xì)數(shù)據(jù)，使用數(shù)據(jù)集市和數(shù)據(jù)倉(cāng)庫(kù)計(jì)數(shù)實(shí)現(xiàn)面向主題的歷史數(shù)據(jù)存儲(chǔ)，使用多維分析工具進(jìn)行前端展現(xiàn)，以及使用數(shù)據(jù)倉(cāng)庫(kù)工具提供的挖掘引擎或基于單獨(dú)的數(shù)據(jù)挖掘工具進(jìn)行預(yù)測(cè)分析等。 6、數(shù)據(jù)倉(cāng)庫(kù)(Data Warehouse)：

????????一種新型的數(shù)據(jù)存儲(chǔ)和處理手段，被數(shù)據(jù)庫(kù)廠商普遍接受并且相關(guān)輔助建模和管理工具快速推向市場(chǎng)，成為多數(shù)據(jù)源集成的一種有效的技術(shù)支撐環(huán)境。

第二章 知識(shí)發(fā)現(xiàn)過(guò)程與應(yīng)用結(jié)構(gòu) 一、知識(shí)發(fā)現(xiàn)（Knowledge Discovery in Database,KDD） ?【必考】一個(gè)系統(tǒng)化的工作，必須對(duì)可以利用的源數(shù)據(jù)進(jìn)行分析，確定合適的挖掘目標(biāo)，然后才能著手系統(tǒng)的設(shè)計(jì)和開發(fā)。KDD是一個(gè)多步驟的處理過(guò)程，一般分為問(wèn)題定義、數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘、模式評(píng)估等基本階段。 ?過(guò)程可以簡(jiǎn)單地概括為：首先從數(shù)據(jù)源中抽取感興趣的數(shù)據(jù)，并把它組織成適合挖掘的數(shù)據(jù)組織形式；然后，調(diào)用相應(yīng)的算法生成所需的知識(shí)；最后對(duì)生成的知識(shí)模式進(jìn)行評(píng)估，并把有價(jià)值的知識(shí)集成到企業(yè)的智能系統(tǒng)中。

三、階梯處理過(guò)程模型

各階段的主要任務(wù)是：

1、數(shù)據(jù)準(zhǔn)備：了解相關(guān)領(lǐng)域的情況，弄清楚用戶的要求，確定挖掘的總體目標(biāo)和方法并對(duì)原數(shù)據(jù)結(jié)構(gòu)加以分析、確定數(shù)據(jù)選擇原則等工作。 2、數(shù)據(jù)選擇：從數(shù)據(jù)庫(kù)中提取與KDD目標(biāo)相關(guān)的數(shù)據(jù)。 3、數(shù)據(jù)預(yù)處理：主要是對(duì)上一階段產(chǎn)生的數(shù)據(jù)進(jìn)行再加工，檢查數(shù)據(jù)的完整性及數(shù)據(jù)的一致性，對(duì)其中的噪聲數(shù)據(jù)進(jìn)行處理，對(duì)丟失的數(shù)據(jù)可以利用統(tǒng)計(jì)方法進(jìn)行填補(bǔ)。對(duì)一些不適合于操作的數(shù)據(jù)進(jìn)行必要的處理等。 4、數(shù)據(jù)縮減：對(duì)經(jīng)過(guò)預(yù)處理的數(shù)據(jù)，根據(jù)知識(shí)發(fā)現(xiàn)的任務(wù)對(duì)數(shù)據(jù)進(jìn)行抽取處理，使數(shù)據(jù)再次精簡(jiǎn)取其精華，更好地集中于用戶挖掘目標(biāo)上。 5、確定KDD的目標(biāo)：根據(jù)挖掘的目標(biāo)和用戶的要求，確定KDD所發(fā)現(xiàn)的具體知識(shí)模式和類型(如分類、聚類、關(guān)聯(lián)規(guī)則等)。 6、確定數(shù)據(jù)挖掘算法：根據(jù)上一階段所確定的模式，選擇合適的數(shù)據(jù)挖掘算法（包括選取合適的參數(shù)、知識(shí)表示方式，并保證數(shù)據(jù)挖掘算法與整個(gè)KDD的評(píng)判標(biāo)準(zhǔn)相一致）。 7、數(shù)據(jù)挖掘：運(yùn)用選定的算法，從數(shù)據(jù)中提取出用戶所需要的知識(shí)。 8、模式解釋：對(duì)發(fā)現(xiàn)的模式進(jìn)行解釋。在此過(guò)程中，為了取得更為有效的知識(shí)，可能會(huì)返回到前面的某些處理步驟中以改進(jìn)結(jié)果，保證提取出的知識(shí)是有效和可用的。 9、知識(shí)評(píng)價(jià)：將發(fā)現(xiàn)的知識(shí)以用戶能了解的方式呈現(xiàn)給用戶。這期間也包含對(duì)知識(shí)的一致性的檢查，以確信本次發(fā)現(xiàn)的知識(shí)不與以前發(fā)現(xiàn)的知識(shí)相抵觸。

第三章 關(guān)聯(lián)規(guī)則挖掘理論和算法

一、Apriori算法 1、概念與定理 2、偽代碼 （1）Apriori（發(fā)現(xiàn)頻繁項(xiàng)目集） （2）apriori-gen(Lk-1)（候選集產(chǎn)生） （3）has_infrequent_subset(c,Lk-1)（判斷候選集的元素） （4）從給定的頻繁項(xiàng)目集中生成強(qiáng)關(guān)聯(lián)規(guī)則 （5）遞歸測(cè)試一個(gè)頻繁項(xiàng)目集中的關(guān)聯(lián)規(guī)則 3、例題

二、Close算法 1、基本原理 ????????一個(gè)頻繁閉合項(xiàng)目集的所有閉合子集一定是頻繁的，一個(gè)非頻繁閉合項(xiàng)目集的所有閉合超集一定是非頻繁的。 2、閉合項(xiàng)集（P83例題） 例題勘誤： ? ????????由偽代碼可知，若p是其i項(xiàng)子集閉合的子集，則將其刪除。 ? ????????{BD}是子集{D}的閉合{BD}的子集，所以下文生成的FC2里面的BD應(yīng)該要?jiǎng)h掉，即FC2={AB，AC，BC}。

第四章 分類方法

一、k-Nearest Neighbors算法 1、相關(guān)概念

（1）距離度量：二維空間兩個(gè)點(diǎn)的歐幾里得距離（kNN算法常用距離，也被稱為L(zhǎng)2規(guī)范）計(jì)算公式為：

（2）K值選擇：在許多實(shí)際應(yīng)用中數(shù)據(jù)是不充足的。為了選擇好的模型，可以采用交叉驗(yàn)證方法。交叉驗(yàn)證的基本想法是重復(fù)地使用數(shù)據(jù)，把給定的數(shù)據(jù)進(jìn)行切分，將切分的數(shù)據(jù)組合為訓(xùn)練集與測(cè)試集，在此基礎(chǔ)上反復(fù)進(jìn)行訓(xùn)練測(cè)試以及模型的選擇。 （3）分類決策規(guī)則：kNN算法使用的分類決策規(guī)則是多數(shù)表決，如果損失函數(shù)為0-1損失函數(shù)，那么要使誤分類率最小即使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，多數(shù)表決規(guī)則實(shí)際上就等同于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。 （4）主要思想：計(jì)算每個(gè)訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的k個(gè)訓(xùn)練數(shù)據(jù)，k個(gè)數(shù)據(jù)中哪個(gè)類別的訓(xùn)練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個(gè)類別。

2、偽代碼 3、例題 例題勘誤： ????????本題的測(cè)試數(shù)據(jù)為<范可可，女，1.50>，并非<范可可，女，1.6>。

二、ID3算法 1、相關(guān)概念

?（1）期望信息：設(shè)S是s個(gè)數(shù)據(jù)樣本的集合。假定類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類Ci (i = 1,2，......，m)。設(shè)Si是類Ci中的樣本數(shù)。對(duì)一個(gè)給定的樣本分類所需的期望信息由下式給出：

?（2）熵值：設(shè)屬性A具有v個(gè)不同值{a1,a2,...,av}，可以用屬性A將S劃分為v個(gè)子集{S1,S2,...,Sv}，其中Si包含S中這樣一些樣本，它們?cè)贏上具有值aj。如果A作為測(cè)試屬性（即最好的分裂屬性），則這些子集對(duì)應(yīng)于包含集合S的結(jié)點(diǎn)生長(zhǎng)出來(lái)的分支。設(shè)Sij是子集Sj中類Cj的樣本數(shù)。根據(jù)由A劃分成子集的熵由下式給出：

?（3）信息增益：對(duì)于在A上分支將獲得的信息增益可以由下面的公式得到：

2、偽代碼 ? 3、例題

三、EM算法 1、定義 ????????最大期望算法（Expectation-Maximization Algorithm，又譯期望最大化算法）在統(tǒng)計(jì)中被用于尋找依賴于不可觀察的隱性變量的概率模型中參數(shù)的最大似然估計(jì)。 2、基本思想

第五章 聚類方法

一、聚類技術(shù)分類 1、劃分方法 （1）主要思想 ?????????給定一個(gè)有n個(gè)對(duì)象的數(shù)據(jù)集，劃分聚類技術(shù)將構(gòu)造數(shù)據(jù)k個(gè)劃分，每一個(gè)劃分就代表一個(gè)簇，k≤n。也就是說(shuō)它將數(shù)據(jù)劃分為k個(gè)簇，而且這k個(gè)劃分滿足下列條件：

?① 每一個(gè)簇至少包含一個(gè)對(duì)象； ?② 每一個(gè)對(duì)象屬于且僅屬于一個(gè)簇。

?????????對(duì)于給定的k，算法首先給出一個(gè)初始的劃分方法,以后通過(guò)反復(fù)迭代的方法改變劃分,使得每一次改進(jìn)之后的劃分方案都較前一次更好。所謂好的標(biāo)準(zhǔn)就是：同一簇中的對(duì)象越近越好，而不同簇中的對(duì)象越遠(yuǎn)越好。目標(biāo)是最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和。這里的遠(yuǎn)近或者相異度/相似度實(shí)際上是聚類的評(píng)價(jià)函數(shù)。 （2）代表算法 ?????????k-均值、k-中心點(diǎn)、k-模、k原型、PAM等。 2、層次方法 （1）凝聚層次聚類 ?????????凝聚的層次聚類是一種自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來(lái)越大的簇，直到所有的對(duì)象都在一個(gè)簇中，或者某 個(gè)終結(jié)條件被滿足，絕大多數(shù)層次聚類方法屬于這一類，它們只是在簇間相似度的定義上有所不同。代表是AGNES算法。 （2）分裂層次聚類 ?????????分裂的層次聚類與凝聚的層次聚類相反，采用自頂向下的策略，它首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來(lái)越小的簇，直到每個(gè)對(duì)象自成一簇，或者達(dá)到了某個(gè)終結(jié)條件。代表是DIANA算法。 3、基于密度的方法 ?????????密度聚類方法的指導(dǎo)思想是，只要一個(gè)區(qū)域中的點(diǎn)的密度大于某個(gè)域值，就把它加到與之相近的聚類中去。這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”聚類的缺點(diǎn)，可發(fā)現(xiàn)任意形狀的聚類，且對(duì)噪聲數(shù)據(jù)不敏感。但計(jì)算密度單元的計(jì)算復(fù)雜度大，需要建立空間索引來(lái)降低計(jì)算量，且對(duì)數(shù)據(jù)維數(shù)的伸縮性較差。這類方法需要掃描整個(gè)數(shù)據(jù)庫(kù)，每個(gè)數(shù)據(jù)對(duì)象都可能引起一次查詢，因此當(dāng)數(shù)據(jù)量大時(shí)會(huì)造成頻繁的/O操作。代表算法有DBSCAN、OPTICS、DENCLUE算法等。 4、基于模型的方法 ?????????SOM（SOM神經(jīng)網(wǎng)絡(luò)）和COBWEB（簡(jiǎn)單增量概念聚類算法）。

二、k-Means算法 1、基本概念 ?????????k-平均(k-Means)，也被稱為k-均值，是一種得到最廣泛使用的聚類算法。k-平均算法以k為參數(shù)，把個(gè)對(duì)象分為k個(gè)簇，以使簇內(nèi)具有較高的相似度。相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值來(lái)進(jìn)行。 ????????算法首先隨機(jī)地選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的平均值或中心。對(duì)剩余的每個(gè)對(duì)象根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。然后重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。 ?????????k-Means算法的準(zhǔn)則函數(shù)定義為：

????????即E是數(shù)據(jù)庫(kù)所有對(duì)象的平方誤差的總和。其中x是空間中的點(diǎn)，表示給定的數(shù)據(jù)對(duì)象，ˉxi是簇Ci的平均值。這可以保證生成的結(jié)果簇盡可能的緊湊和獨(dú)立。 2、偽代碼 3、例題 ? 4、性能分析 （1）優(yōu)點(diǎn)

① 是解決聚類問(wèn)題的一種經(jīng)典算法，簡(jiǎn)單、快速； ② 對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的； ③ 當(dāng)結(jié)果簇是密集的，它的效果較好。

（2）缺點(diǎn)

① 在簇的平均值被定義的情況下才能使用，可能不適用于某些應(yīng)用； ② 必須事先給出k（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果； ③ 不適合于發(fā)現(xiàn)非凸面形狀的簇或者大小差別很大的簇。而且它對(duì)于噪聲和孤立點(diǎn)數(shù)據(jù)是敏感的。

三、k-中心點(diǎn)算法 1、基本思路 ????????首先為每個(gè)簇任意選擇一個(gè)代表對(duì)象；剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給最近的一個(gè)簇。然后反復(fù)地用非代表對(duì)象來(lái)代替代表對(duì)象，以改進(jìn)聚類的質(zhì)量。這樣劃分方法仍然是基于最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和的原則來(lái)執(zhí)行的。 2、PAM ????????PAM(Partitioning Around Medoid,圍繞中心點(diǎn)的劃分)是最早提出的k-中心點(diǎn)算法之一，它選用簇中位置最中心的對(duì)象作為代表對(duì)象，試圖對(duì)個(gè)對(duì)象給出個(gè)劃分。代表對(duì)象也被稱為是中心點(diǎn)，其他對(duì)象則被稱為非代表對(duì)象。最初隨機(jī)選擇k個(gè)對(duì)象作為中心點(diǎn)，該算法反復(fù)地用非代表對(duì)象來(lái)代替代表對(duì)象，試圖找出更好的中心點(diǎn)，以改進(jìn)聚類的質(zhì)量。在每次迭代中，所有可能的對(duì)象對(duì)被分析，每個(gè)對(duì)中的一個(gè)對(duì)象是中心點(diǎn)，而另一個(gè)是非代表對(duì)象。對(duì)可能的各種組合，估算聚類結(jié)果的質(zhì)量。一個(gè)對(duì)象O_i可以被使最大平方誤差值減少的對(duì)象代替。在一次迭代中產(chǎn)生的最佳對(duì)象集合成為下次迭代的中心點(diǎn)。 3、偽代碼 ? ? ? 四、AGNES算法 1、基本概念 ????????AGNES(AGglomerative NESting)算法是凝聚的層次聚類方法。AGNES算法最初將每個(gè)對(duì)象作為一個(gè)簇，然后這些簇根據(jù)某些準(zhǔn)則被一步步地合并。例如，如果簇C1中的一個(gè)對(duì)象和簇C2中的一個(gè)對(duì)象之間的距離是所有屬于不同簇的對(duì)象間歐氏距離中最小的，C1和C2可能被合并。這是一種單鏈接方法，其每個(gè)簇可以被簇中所有對(duì)象代表，兩個(gè)簇間的相似度由這兩個(gè)不同簇中距離最近的數(shù)據(jù)點(diǎn)對(duì)的相似度來(lái)確定。聚類的合并過(guò)程反復(fù)進(jìn)行直到所有的對(duì)象最終合并形成一個(gè)簇。在聚類中，用戶能定義希望得到的簇?cái)?shù)目作為一個(gè)結(jié)束條件。 2、偽代碼 ? 3、例題 ? 五、DIANA算法 1、基本概念 ????????DIANA(Divisive ANAlysis)算法屬于分裂的層次聚類。與凝聚的層次聚類相反，它采用一種自頂向下的策略，它首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來(lái)越小的簇，直到每個(gè)對(duì)象自成一簇，或者達(dá)到了某個(gè)終結(jié)條件，例如達(dá)到了某個(gè)希望的簇?cái)?shù)目，或者兩個(gè)最近簇之間的距離超過(guò)了某個(gè)閾值。 ????????在DIANA方法的處理過(guò)程中，所有的對(duì)象初始都放在一個(gè)簇中。根據(jù)一些原則將該簇分裂。簇的分裂過(guò)程反復(fù)進(jìn)行，直到最終每個(gè)新的簇只包含一個(gè)對(duì)象。在聚類中，用戶能定義希望得到的簇?cái)?shù)目作為一個(gè)結(jié)束條件并使用下面兩種測(cè)度方法：

① 簇的直徑：在一個(gè)簇中的任意兩個(gè)數(shù)據(jù)點(diǎn)都有一個(gè)歐氏距離，這些距離中的最大值是簇的直徑。 ② 平均相異度（平均距離）：

2、偽代碼 ? 3、例題 ?

六、DBSCAN算法 1、基本概念 ????????DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一個(gè)比較有代表性的基于密度的聚類算法。與劃分和層次聚類方法不同，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類。 ????????DBSCAN的指導(dǎo)思想是，只要一個(gè)區(qū)域中，點(diǎn)的密度大于某個(gè)閾值，就把它加到與之相連的簇中去。

2、偽代碼 ? 3、例題

4、優(yōu)缺點(diǎn) （1）優(yōu)點(diǎn)

?① 聚類速度快且能夠有效處理噪聲點(diǎn)和發(fā)現(xiàn)任意形狀的空間聚類： ?② 與k-Means比較起來(lái)，不需要輸入要?jiǎng)澐值木垲悅€(gè)數(shù)： ?③ 聚類簇的形狀沒(méi)有偏倚： ?④ 對(duì)噪聲數(shù)據(jù)不敏感。

（2）缺點(diǎn)

?① 當(dāng)數(shù)據(jù)量增大時(shí)，要求較大的內(nèi)存支持I/O消耗也很大： ?② 當(dāng)空間聚類的密度不均勻、聚類間距差相差很大時(shí)，聚類質(zhì)量較差，因?yàn)檫@種情況下參數(shù)MinPts和Eps選取困難。 ?③ 算法聚類效果依賴與距離公式選取，實(shí)際應(yīng)用中常用歐式距離，對(duì)于高維數(shù)據(jù)，存在“維數(shù)災(zāi)難”。

第六章 時(shí)間序列和序列模式挖掘

一、時(shí)間序列及其應(yīng)用 1、基本概念? ????????所謂時(shí)間序列就是將某一指標(biāo)在不同時(shí)間上的不同數(shù)值，按照時(shí)間的先后順序排列而成的數(shù)列。由于前后時(shí)刻的數(shù)值或數(shù)據(jù)點(diǎn)的相關(guān)性往往呈現(xiàn)某種趨勢(shì)性或周期性變化，因此時(shí)間序列里蘊(yùn)藏著其他信息形式所不能代替的有用知識(shí)。 ????????所謂時(shí)間序列挖掘就是從時(shí)間序列數(shù)據(jù)中提取人們事先不知道的、但又是潛在有用的與時(shí)間屬性相關(guān)的信息和知識(shí)，并用于短期、中期或長(zhǎng)期預(yù)測(cè)。指導(dǎo)人們的社會(huì)、經(jīng)濟(jì)、軍事和生活等行為。通過(guò)對(duì)過(guò)去歷史行為的客觀記錄分析，揭示其內(nèi)在規(guī)律，進(jìn)而完成預(yù)測(cè)未來(lái)行為等決策性工作。 2、應(yīng)用? ????????時(shí)間序列分析的一個(gè)重要應(yīng)用是預(yù)測(cè)，即根據(jù)已知時(shí)間序列中數(shù)據(jù)的變化特征和趨勢(shì)，預(yù)測(cè)未來(lái)屬性值。 ????????從經(jīng)濟(jì)到工程技術(shù)，從天文到地理和氣象，幾乎在各種領(lǐng)域都會(huì)遇到時(shí)間序列，因此時(shí)間序列挖掘有著廣泛的數(shù)據(jù)基礎(chǔ)和廣闊的應(yīng)用前景。

二、時(shí)間序列預(yù)測(cè)的常用方法 1、確定性時(shí)間序列預(yù)測(cè)方法 ????????對(duì)于平穩(wěn)變化特征的時(shí)間序列，可以利用屬性現(xiàn)在的值預(yù)測(cè)將來(lái)的值。對(duì)于具有明顯的季節(jié)變動(dòng)的時(shí)間序列來(lái)說(shuō)，需要先將最近的觀察值去掉季節(jié)性因素的影響產(chǎn)生變化趨勢(shì)，然后結(jié)合季節(jié)性因素進(jìn)行預(yù)測(cè)。一種更科學(xué)的評(píng)價(jià)時(shí)間序列變動(dòng)的方法是把數(shù)據(jù)的變動(dòng)看成是長(zhǎng)期趨勢(shì)、季節(jié)變動(dòng)和隨機(jī)性變動(dòng)共同作用的結(jié)果。時(shí)間序列分析就是設(shè)法消除隨機(jī)性波動(dòng)、分解季節(jié)性變化、擬合確定性趨勢(shì)，因而形成對(duì)發(fā)展水平分析、趨勢(shì)變動(dòng)分析、周期波動(dòng)分析和長(zhǎng)期趨勢(shì)加周期波動(dòng)分析等一系列確定性時(shí)間序列預(yù)測(cè)方法。 ????????2、隨機(jī)性時(shí)間序列預(yù)測(cè)方法 通過(guò)建立隨機(jī)模型，對(duì)隨機(jī)時(shí)間序列進(jìn)行分析，可以預(yù)測(cè)未來(lái)值。 3、其他方法 ????????許多技術(shù)，如神經(jīng)網(wǎng)絡(luò)、遺傳算法，都可用于時(shí)間序列的預(yù)測(cè)。由于大量的時(shí)間序列是非平穩(wěn)的，因此探討多種技術(shù)結(jié)合來(lái)實(shí)現(xiàn)時(shí)間序列挖掘是必要的。 ? 三、基于ARMA模型的序列匹配算法 ????????通過(guò)建立隨機(jī)模型，對(duì)隨機(jī)時(shí)間序列進(jìn)行分析，可以預(yù)測(cè)未來(lái)值。若時(shí)間序列是平穩(wěn)的，可以用自回歸(Auto Regressive model,AR)模型、移動(dòng)回歸(Moving Average model,MA)模型或自回歸移動(dòng)平均(Auto Regressive Moving? ????????Average model,ARMA)模型進(jìn)行分析預(yù)測(cè)。ARMA模型是時(shí)序方法中最基本的、實(shí)際應(yīng)用最廣的時(shí)序模型。此后，AR模型逐步發(fā)展為ARMA模型、多維ARMA模型。ARMA通常被廣泛用于預(yù)測(cè)。由于ARMA模型是一個(gè)信息的凝聚器，可將系統(tǒng)的特性與系統(tǒng)狀態(tài)的所有信息凝聚在其中，因而它也可以用于時(shí)間序列的匹配。

四、序列挖掘 1、基本概念 ????????序列挖掘或稱序列模式挖掘，是指從序列數(shù)據(jù)庫(kù)中發(fā)現(xiàn)蘊(yùn)含的序列模式。時(shí)間序列分析和序列模式挖掘有許多相似之處，在應(yīng)用范疇、技術(shù)方法等方面也有很大的重合度。但序列挖掘一般是指相對(duì)時(shí)間或者其他順序出現(xiàn)的序列的高頻率子序列的發(fā)現(xiàn)，典型的應(yīng)用還是限于離散型序列。 2、應(yīng)用 ????????近年來(lái)序列模式挖掘已經(jīng)成為數(shù)據(jù)挖掘的一個(gè)重要方面，其應(yīng)用范圍也不局限于交易數(shù)據(jù)庫(kù)，在DNA分析等尖端科學(xué)研究領(lǐng)域、Web訪問(wèn)等新型應(yīng)用數(shù)據(jù)源等眾多方面得到針對(duì)性研究。 3、步驟

（1）排序階段：對(duì)數(shù)據(jù)庫(kù)進(jìn)行排序（Sort），排序的結(jié)果將原始的數(shù)據(jù)庫(kù)轉(zhuǎn)換成序列數(shù)據(jù)庫(kù)（比較實(shí)際可能需要其他的預(yù)處理手段來(lái)輔助進(jìn)行）； （2）大項(xiàng)集階段：這個(gè)階段要找出所有頻繁的項(xiàng)集（即大項(xiàng)集）組成的集合L。實(shí)際上，也同步得到所有大1-序列組成的集合，即{ | l∈L}； （3）轉(zhuǎn)換階段：在尋找序列模式的過(guò)程中，我們要不斷地進(jìn)行檢測(cè)一個(gè)給定的大序列集合是否包含于一個(gè)客戶序列中； （4）序列階段：利用轉(zhuǎn)換后的數(shù)據(jù)庫(kù)尋找頻繁的序列，即大序列(Large Sequence)； （5）選最大階段：在大序列集中找出最長(zhǎng)序列(Maximal Sequences)。

? 五、AprioriAll & AprioriSome 1、AprioriAll算法 ????????AprioriAll算法源于頻繁集算法Apriori,它把Apriori的基本思想（如果某個(gè)項(xiàng)集是頻繁的，那么它的所有子集也是頻繁的）擴(kuò)展到序列挖掘中，也是一個(gè)多遍掃描數(shù)據(jù)庫(kù)的算法。 在每一遍掃描中都利用前一遍的大序列來(lái)產(chǎn)生候選序列，然后在完成遍歷整個(gè)數(shù)據(jù)庫(kù)后測(cè)試它們的支持度。 ????????在第一遍掃描中，利用大項(xiàng)目集階段的輸出來(lái)初始化大1-序列的集合。 在每次遍歷中，從一個(gè)由大序列組成的種子集開始，利用這個(gè)種子集，可以產(chǎn)生新的潛在的大序列。 ????????在第一次遍歷前，所有在大項(xiàng)集階段得到的大1-序列組成了種子集。 2、AprioriSome算法 ????????AprioriSome算法可以看作是AprioriAll算法的改進(jìn)，具體過(guò)程分為兩個(gè)階段：

（1）前推階段用于找出指定長(zhǎng)度的所有大序列； （2）回溯階段用于查找其他長(zhǎng)度的所有大序列。

第七章 Web挖掘技術(shù)

一、Web挖掘的數(shù)據(jù)來(lái)源 1、服務(wù)器日志數(shù)據(jù) ????????個(gè)人瀏覽Web服務(wù)器時(shí)，服務(wù)器方將會(huì)產(chǎn)生三種類型的日志文件：Server logs、Error logs和Cookie logs,這些日志用于記錄用戶訪間的基本情況，因此也是進(jìn)行Web訪問(wèn)信息挖掘的主要數(shù)據(jù)源。 2、在線市場(chǎng)數(shù)據(jù) ????????在線市場(chǎng)數(shù)據(jù)是指和市場(chǎng)活動(dòng)相關(guān)的信息。例如一個(gè)電子商務(wù)站點(diǎn)，存儲(chǔ)相關(guān)的電子商務(wù)信息。從內(nèi)容上說(shuō)，不同目的的商務(wù)網(wǎng)站有不同的商務(wù)信息。但是，這類數(shù)據(jù)通常是用傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)。在線市場(chǎng)數(shù)據(jù)是業(yè)務(wù)數(shù)據(jù)，是進(jìn)行業(yè)務(wù)相關(guān)分析的主體。用戶的挖掘目標(biāo)只有結(jié)合在線市場(chǎng)數(shù)據(jù)分析才能達(dá)到目的。 3、Web頁(yè)面 ????????現(xiàn)有的Web數(shù)據(jù)挖掘方法大都是針對(duì)Web頁(yè)面開展的。目前的Web頁(yè)面大多滿足HTML標(biāo)準(zhǔn)。由于HTML頁(yè)面包含文本和多媒體信息(包括圖片，語(yǔ)音，圖像)，所以涉及數(shù)據(jù)挖掘領(lǐng)域中的文本挖掘和多媒體挖掘。現(xiàn)有的HTML頁(yè)面內(nèi)容，缺乏標(biāo)準(zhǔn)的描述方式，難以挖掘。為了解決這個(gè)問(wèn)題，1998年WWW社團(tuán)提出了XML語(yǔ)言標(biāo)準(zhǔn)(eXtensible Markup Language)。該標(biāo)準(zhǔn)通過(guò)把一些描述頁(yè)面內(nèi)容的標(biāo)記(tag)添加到HTML頁(yè)面中，用于對(duì)HTML頁(yè)面內(nèi)容進(jìn)行自描述，例如對(duì)一個(gè)內(nèi)容為科技論文的頁(yè)面添加相關(guān)標(biāo)記，描述其作者，關(guān)鍵詞等。XML的標(biāo)記并不是限制死的，是由頁(yè)面的創(chuàng)立者自己安排給出和定義的，但要遵循一定的規(guī)范。 4、Web頁(yè)面超鏈接關(guān)系 ????????Web頁(yè)面之間的超鏈接關(guān)系是一種重要的資源，頁(yè)面的設(shè)計(jì)者把它們認(rèn)為是重要的頁(yè)面地址添加到自己的頁(yè)面上。顯然，如果一個(gè)頁(yè)面被很多頁(yè)面引用，那么它一定是重要的。這就是從中需要挖掘的知識(shí)。 5、其他信息 ????????這些信息主要包括用戶注冊(cè)信息等一系列信息。為了更好地實(shí)現(xiàn)挖掘任務(wù)，適當(dāng)?shù)馗郊有畔ⅲㄈ缑枋鲇脩舻幕厩闆r和特征的信息）是必要的。 ? 二、Web結(jié)構(gòu)挖掘方法 1、頁(yè)面等級(jí)（PageRank）方法 （1）頁(yè)面等級(jí) ????????設(shè)u為一個(gè)Web頁(yè)，Bu為所有指向u的頁(yè)面的集合，F(xiàn)u為所有u指向的頁(yè)面的集合，c(<1)為一個(gè)歸一化的因子，那么u頁(yè)面的等級(jí)R(u)被定義為：

????????基本的頁(yè)面分級(jí)方法主要考慮一個(gè)頁(yè)面的入度，即通過(guò)進(jìn)入該頁(yè)面的頁(yè)面等級(jí)得到。同時(shí)在將一個(gè)頁(yè)面的等級(jí)值傳遞時(shí)，采用平均分配方法傳遞到所有它所指向的頁(yè)面，即每個(gè)從它鏈接處的頁(yè)面等分它的等級(jí)值。 （2）基于隨機(jī)沖浪模型的頁(yè)面等級(jí)值 ????????設(shè)u為一個(gè)Web頁(yè)，Bu為所有指向u的頁(yè)面的集合，F(xiàn)u為所有u指向的頁(yè)面的集合。假設(shè)用戶按著概率d隨機(jī)單擊一個(gè)超級(jí)鏈接來(lái)繼續(xù)瀏覽頁(yè)面，則基于隨機(jī)沖浪模型的頁(yè)面等級(jí)值可以通過(guò)下式計(jì)算：

????????d的經(jīng)驗(yàn)值被很多文獻(xiàn)推薦為0.85或0.5，這樣能最大程度保證等級(jí)值的傳遞一直順利地進(jìn)行下去，避免出現(xiàn)中斷或者被無(wú)限放大。 2、PageRank算法 （1）基本概念 ????????PageRank算法的核心部分可以從一個(gè)有向圖開始。最典型的方法是根據(jù)有向圖構(gòu)造一個(gè)鄰接矩陣來(lái)進(jìn)行處理。鄰接矩陣A=(a(i,j))中的元素a(i,j) (∈[0,1])表示從頁(yè)面j指向頁(yè)面i的概率。 ????????基本的PageRank算法在計(jì)算等級(jí)值時(shí)，每個(gè)頁(yè)面都將自己的等級(jí)值平均地分配給其引用的頁(yè)面節(jié)點(diǎn)。假設(shè)一個(gè)頁(yè)面的等級(jí)值為1，該頁(yè)面上共有n個(gè)超鏈接，其分配給每個(gè)超鏈接頁(yè)面的等級(jí)值就是1/n,那么就可以理解為該頁(yè)面以1/n的概率跳轉(zhuǎn)到任意一個(gè)其所引用的頁(yè)面上。 ????????一般地，把鄰接矩陣A轉(zhuǎn)換成所謂的轉(zhuǎn)移概率矩陣M來(lái)實(shí)現(xiàn)PageRank算法：

????????其中，Q是一個(gè)常量矩陣，最常用的是Q=(q(i,j)),q(i,j)=1/n. ????????轉(zhuǎn)移概率矩陣M可以作為一個(gè)向量變換矩陣來(lái)幫助完成頁(yè)面等級(jí)值向量R的迭代計(jì)算：

（2）偽代碼 ? （3）例題

3、權(quán)威頁(yè)面和中心頁(yè)面 （1）基本概念

?① 權(quán)威頁(yè)面是指包含需求信息的最佳資源頁(yè)面； ?② 中心頁(yè)面是一個(gè)包含權(quán)威頁(yè)面鏈接的頁(yè)面。

（2）HITS技術(shù)組成

?① 基于一組給定的關(guān)鍵字，可以找到相關(guān)的頁(yè)面（有可能相當(dāng)多）； ?② 權(quán)威頁(yè)面和中心頁(yè)面與上述頁(yè)面有關(guān)，具有最高權(quán)重的頁(yè)面被返回。

（3）HITS偽代碼 ?

? ?

柚子快報(bào)激活碼778899分享：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘復(fù)習(xí)資料

http://yzkb.51969.com/

好文閱讀