華南理工大學(xué)《數(shù)據(jù)挖掘》復(fù)習(xí)資料

1、華南理丄大學(xué)數(shù)據(jù)挖掘復(fù)習(xí)資料【英文縮寫(xiě)】BI（商務(wù)智能）:BusinessIntelligenceOLAP（聯(lián)機(jī)分析處理）:OnlineAnalyticalProcessingOLTP（聯(lián)機(jī)事務(wù)處理）：OnlineTransactionProcessingETL（提取/變換/裝入）：Extraction/Transformation/LoadingKDD（數(shù)據(jù)中的知識(shí)發(fā)現(xiàn)）：KnowledgeDiscoveryinDatabasesLecture1【知識(shí)發(fā)現(xiàn)的主要過(guò)程】(1) 數(shù)據(jù)清理(消除噪聲和不一致的數(shù)據(jù))(2) 數(shù)據(jù)集成(多種數(shù)據(jù)源可以組合在一起)(3) 數(shù)據(jù)選擇(從數(shù)據(jù)庫(kù)中提取與分析任

2、務(wù)相關(guān)的數(shù)據(jù))(4) 數(shù)據(jù)變換(數(shù)據(jù)變換或同意成適合挖掘的形式，如通過(guò)匯總或聚集操作)(5) 數(shù)據(jù)挖掘(基本步驟，使用只能方法提取數(shù)據(jù)模式)(6) 模式評(píng)估(根據(jù)某種興趣度度量，識(shí)別表示只是的真正有趣的模式)(7) 知識(shí)表示(使用可視化和只是表示技術(shù)，向用戶(hù)提供挖掘的知識(shí))【挖掘的知識(shí)類(lèi)型】(1)概念描述：特征劃與區(qū)分(概化、摘要、以及對(duì)比數(shù)據(jù)特征)關(guān)聯(lián)(相關(guān)性或者因果關(guān)系)(3) 分類(lèi)與預(yù)測(cè)：對(duì)類(lèi)或概念構(gòu)造模型或函數(shù)以便對(duì)未來(lái)數(shù)據(jù)進(jìn)行預(yù)測(cè)(4) 聚類(lèi)分析：類(lèi)標(biāo)識(shí)符是未知的，把數(shù)據(jù)分成不同的新類(lèi)，使得同一個(gè)類(lèi)中的元素具有極大的相似性，不同類(lèi)元素的相似性極小。(5) 趨勢(shì)與偏差分析：序列模式挖掘

3、(6) 孤立點(diǎn)分析：孤立點(diǎn)，不符合該類(lèi)數(shù)據(jù)的通用行為的數(shù)據(jù)，不是噪聲或異常?！緮?shù)據(jù)挖掘在互聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)的應(yīng)用】(1)Web用法挖掘(Web日志挖掘)：在分布式信息環(huán)境下捕獲用戶(hù)訪(fǎng)問(wèn)模式權(quán)威Web頁(yè)面分析：根據(jù)Web頁(yè)面的重要性、影響和主題，幫助對(duì)Web頁(yè)面定秩自動(dòng)Web頁(yè)面聚類(lèi)和分類(lèi)：給予頁(yè)面的內(nèi)容，以多維的方式對(duì)Web頁(yè)面分組和安排Web社區(qū)分析：識(shí)別隱藏的Web社會(huì)網(wǎng)絡(luò)和社團(tuán)，并觀(guān)察它們的演變Lecture2.【為什么需要數(shù)據(jù)預(yù)處理】現(xiàn)實(shí)世界中的數(shù)據(jù)很“臟”具有以下特性：(1) 不完整的：缺少屬性值，感興趣的屬性缺少屬性值，或僅包含聚集數(shù)據(jù)(2) 含噪聲的：包含錯(cuò)誤或存在孤立點(diǎn)(3)

4、不一致的：在名稱(chēng)或代碼之間存在著差異數(shù)據(jù)預(yù)處理技術(shù)可以改進(jìn)數(shù)據(jù)的質(zhì)量，從而有助于提高其后的挖掘過(guò)程的精度和性能?！緮?shù)據(jù)預(yù)處理的主要內(nèi)容】(1) 數(shù)據(jù)清洗(Datacleaning)填充遺失的數(shù)據(jù)，平滑噪聲數(shù)據(jù)，辨識(shí)或刪除孤立點(diǎn)，解決不一致性問(wèn)題(2) 數(shù)據(jù)集成(Dataintegration)對(duì)多個(gè)數(shù)據(jù)庫(kù)，數(shù)據(jù)立方或文件進(jìn)行集成(3) 數(shù)據(jù)變換(Datatransformation)規(guī)范化與聚集(Normalizationandaggregation)(4) 數(shù)據(jù)約簡(jiǎn)(Datareduction)得到數(shù)據(jù)集的壓縮表示，它小的多，但能產(chǎn)生同樣分析結(jié)果(5) 數(shù)據(jù)離散化(Datadiscretiz

5、ation)特別對(duì)數(shù)字值而言非常重要【分箱平滑】是一種處理噪聲數(shù)據(jù)的方法。先對(duì)數(shù)據(jù)進(jìn)行排序，然后把它們劃分到箱，然后通過(guò)箱平均值，箱中值等進(jìn)行平滑。(1) 等寬(距離)劃分根據(jù)屬性值的范圍劃分成N等寬的區(qū)間。很直接，但孤立點(diǎn)將會(huì)對(duì)此方法有很大的影響(2) 等深(頻率)劃分劃分成N個(gè)區(qū)間，每個(gè)區(qū)間含有大約相等地樣本數(shù)。具有較好的數(shù)據(jù)擴(kuò)展性【無(wú)監(jiān)督離散化】分箱、直方圖分析、聚類(lèi)分析【有監(jiān)督離散化】離散化過(guò)程使用類(lèi)信息，基于熵的離散化：(1) 給定樣本集S，根據(jù)分解值T分為兩部分，計(jì)算熵：(2) 選擇某一邊界T使熵最大.(3) 遞歸地用于所得到的劃分，直到滿(mǎn)足某個(gè)終止條件。數(shù)據(jù)清理缺失值的處理方法：

6、(1) 忽略元組：當(dāng)缺失類(lèi)標(biāo)號(hào)時(shí)通常忽略元組。除非元組有多個(gè)屬性缺失值，否則該方法不是很有效。當(dāng)每個(gè)屬性缺失值的百分比變化很大時(shí)，它的性能特別差。(2) 人工填寫(xiě)缺失值：該方法很費(fèi)時(shí)，當(dāng)數(shù)據(jù)集很大，缺少很多值時(shí)，該方法不可行。(3)使用一個(gè)全局常量填充缺失值：將缺失的屬性值用同一個(gè)常數(shù)(如unknow)替換。如果缺失值都用unknow替換，則挖掘程序則可能誤以為它們行程了一個(gè)有趣的概念，因?yàn)樗鼈兌季哂邢嗤闹?。因此，盡管該方法簡(jiǎn)單，但是并不十分可靠。(4) 使用屬性的均值填充缺失值(5) 使用與給定元組屬同一類(lèi)的所有樣本的屬性均值(6) 使用最可能的值填充缺失值：可以用回歸、使用貝葉斯形式化的

7、基于推理的工具或決策樹(shù)歸納確定。(3) (6)使數(shù)據(jù)偏置。填入的值可能不正確。方法6是最流行的策略，與其他方法相比，它使用已有的數(shù)據(jù)大部分信息來(lái)預(yù)測(cè)缺失值。缺失值不代表數(shù)據(jù)有錯(cuò)誤(例如，信用卡中，有信息是駕照號(hào)碼，如果沒(méi)有駕照號(hào)碼，該空則可以是缺失的)(1) 企業(yè)倉(cāng)庫(kù)(Enterprisewarehouse)搜集了關(guān)于主題的所有信息，跨越整個(gè)組織。數(shù)據(jù)集市(DataMart)包含企業(yè)范圍數(shù)據(jù)的一個(gè)子集，對(duì)于特定的用戶(hù)是有用的，其范圍限于選定的主題。虛擬倉(cāng)庫(kù)(Virtualwarehouse)操作數(shù)據(jù)庫(kù)上視圖的一組集合。為了有效處理查詢(xún)，只有一些可能的匯總視圖被物化。【為什么需要構(gòu)建單獨(dú)隔離的數(shù)

8、據(jù)倉(cāng)庫(kù)】(1) 使得操作數(shù)據(jù)庫(kù)與數(shù)據(jù)倉(cāng)庫(kù)都獲得高性能DBMSOLTP:訪(fǎng)問(wèn)方法,索引,并發(fā)控制,數(shù)據(jù)恢復(fù)。WarehouseOLAP:復(fù)雜OLAP查詢(xún)，多維視圖，整理。(2) 對(duì)數(shù)據(jù)與功能的要求不同:(a) 丟失的數(shù)據(jù)：決策支持需要?dú)v史數(shù)據(jù)，而傳統(tǒng)數(shù)據(jù)庫(kù)并不一定維護(hù)歷史數(shù)據(jù)。(b) 數(shù)據(jù)整理:決策支持需對(duì)異構(gòu)數(shù)據(jù)源進(jìn)行數(shù)據(jù)整理。(c) 數(shù)據(jù)質(zhì)量:不同的數(shù)據(jù)源常常具有不一致的數(shù)據(jù)表示，編碼結(jié)構(gòu)與格式。Lecture3.【數(shù)據(jù)倉(cāng)庫(kù)的特征】(1) 面向主題的數(shù)據(jù)倉(cāng)庫(kù)圍繞一些主題來(lái)組織的。(2) 集成的數(shù)據(jù)倉(cāng)庫(kù)是將多個(gè)異構(gòu)數(shù)據(jù)源集成在一起(3) 時(shí)變的數(shù)據(jù)存儲(chǔ)從歷史的角度提供信息。(4) 非易失的數(shù)據(jù)

9、倉(cāng)庫(kù)總是物理地分別存放數(shù)據(jù)【度量的分類(lèi)】(1) 分布式度量(distributivemeasure)是一種可以通過(guò)如下方法計(jì)算度量：可以將數(shù)據(jù)集劃分成較小的子集，計(jì)算每個(gè)子集的度量，然后合并計(jì)算結(jié)果，得到原數(shù)據(jù)集的度量值(2) 代數(shù)度量(algebraicmeasure)是可以通過(guò)應(yīng)用一個(gè)代數(shù)函數(shù)于一個(gè)或多個(gè)分布度量計(jì)算的度量(3) 整體度量(holisticmeasure)必須對(duì)整個(gè)數(shù)據(jù)集計(jì)算的度量。整體度量不能通過(guò)將給定的數(shù)據(jù)集劃分成子集合并每個(gè)子集上度量得到的值來(lái)計(jì)算【常見(jiàn)的OLAP操作】(1) 上卷Rollup(上鉆drill-up):通過(guò)一個(gè)維的概念分層向上攀升或通過(guò)維規(guī)約，在數(shù)據(jù)立

10、方體上進(jìn)行聚集。(2) 下鉆Drilldown(rolldown):上卷的逆操作，它由不太詳細(xì)的數(shù)據(jù)得到更詳細(xì)的數(shù)據(jù)?？梢酝ㄟ^(guò)沿維的概念分層向下或引入新的維實(shí)現(xiàn)。切片Slice與切塊dice投影與選擇。(4) 轉(zhuǎn)軸Pivot(rotate)是一種目視操作，它轉(zhuǎn)動(dòng)數(shù)據(jù)的視角，提供數(shù)據(jù)的替代表示(5) 其它操作鉆過(guò)drillacross：執(zhí)行涉及多個(gè)事實(shí)表的查詢(xún)。鉆透drillthrough：使用SQL的機(jī)制，鉆到數(shù)據(jù)立方的底層,到后端關(guān)系表。【數(shù)據(jù)倉(cāng)庫(kù)的設(shè)計(jì)模式】最流行的數(shù)據(jù)倉(cāng)庫(kù)數(shù)據(jù)模型是多維模型，以以下形式存在：(1)星型模式(Starschema)一個(gè)事實(shí)表以及一組與事實(shí)表連結(jié)的維表。雪花模

11、式(Snowflakeschema)雪花模式是星型模式的變種，其中某些維表是規(guī)范化的，因而把數(shù)據(jù)進(jìn)一步分解到附加的表中。事實(shí)星座(Factconstellations)多個(gè)事實(shí)表分享共同的維表，這種模式可以看作星型模式的集合，因此稱(chēng)為星系模式(galaxyschema)或事實(shí)星座。Month【數(shù)據(jù)倉(cāng)庫(kù)的多層結(jié)構(gòu)】通常，數(shù)據(jù)倉(cāng)庫(kù)采用三層結(jié)構(gòu)：(1)底層是倉(cāng)庫(kù)數(shù)據(jù)服務(wù)器幾乎總是關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)，使用后端工具和實(shí)用程序由操作數(shù)據(jù)庫(kù)或者其他外部數(shù)據(jù)源提取數(shù)據(jù)中間層是OLAP服務(wù)器直接實(shí)現(xiàn)多維數(shù)據(jù)和操作(3)頂層是前端客戶(hù)層包括查詢(xún)和報(bào)表工具、分析工具和/或數(shù)據(jù)挖掘工具DataSourcesDateSlo

12、raLicOLAPEngineFronl-EndTools【數(shù)據(jù)倉(cāng)庫(kù)的視圖】(1) 自頂向下視圖可以選擇數(shù)據(jù)倉(cāng)庫(kù)所需要的相關(guān)信息。這些信息能夠滿(mǎn)足當(dāng)前和未來(lái)商務(wù)的需求。(2) 數(shù)據(jù)源視圖：解釋操作數(shù)據(jù)庫(kù)系統(tǒng)收集、存儲(chǔ)和管理的信息。這些信息可能以不同的詳細(xì)程度和精度建檔，存放在由個(gè)別數(shù)據(jù)源表到集成的數(shù)據(jù)源表中。通常，數(shù)據(jù)源用傳統(tǒng)的數(shù)據(jù)建模技術(shù)，如ER模型或者CASE工具建模。(3) 數(shù)據(jù)倉(cāng)庫(kù)視圖：包括事實(shí)表和維表。提供存放在數(shù)據(jù)倉(cāng)庫(kù)內(nèi)部的信息。包括預(yù)計(jì)算的總和與計(jì)數(shù)，以及提供歷史別進(jìn)的關(guān)于源、原始日期和時(shí)間等信息。(4) 商務(wù)視圖：是從最終用戶(hù)的角度透視數(shù)據(jù)倉(cāng)庫(kù)中的數(shù)據(jù)?！緮?shù)據(jù)立方的兩種表】(維

13、表、事實(shí)表)？立方體：立方格：立方體物化概念:實(shí)現(xiàn)把數(shù)據(jù)匯總算出來(lái)(不是臨時(shí)提交時(shí)才計(jì)算)一個(gè)n維立方體(n-D)稱(chēng)為基本方體；0-D方體存放最高層的匯總，稱(chēng)為定點(diǎn)方體。方體的格稱(chēng)為數(shù)據(jù)立方體。數(shù)據(jù)立方由維和度量組成【OLTP與OLAP的主要區(qū)別】用戶(hù)和系統(tǒng)的面向性：OLTP系統(tǒng)是面向顧客的，用于辦事員、客戶(hù)和信息技術(shù)專(zhuān)業(yè)人員的事務(wù)和查詢(xún)處理。OLAP系統(tǒng)是面向市場(chǎng)的，用于知識(shí)工人的數(shù)據(jù)分析。數(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)

14、 數(shù)據(jù)庫(kù)設(shè)計(jì)：通常，OLTP系統(tǒng)采用實(shí)體-聯(lián)系(ER)數(shù)據(jù)模型和面向應(yīng)用的數(shù)據(jù)庫(kù)設(shè)計(jì)。而OLAP系統(tǒng)通常采用星形或雪花模型和面向主題的數(shù)據(jù)庫(kù)設(shè)計(jì)。(4) 視圖：OLTP系統(tǒng)主要關(guān)注企業(yè)或部門(mén)的當(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ì)上。訪(fǎng)問(wèn)模式：OLTP系統(tǒng)的訪(fǎng)問(wèn)模式主要由短的原子事務(wù)組成。這種系統(tǒng)需要并發(fā)控制和恢復(fù)機(jī)制。然而，對(duì)OLAP系統(tǒng)的訪(fǎng)問(wèn)大部分是只讀操作(大多是歷史數(shù)據(jù))，盡管許多可能是復(fù)雜的查詢(xún)。OLTP

15、和OLAP的其他區(qū)別包括數(shù)據(jù)庫(kù)大小、操作的頻繁程度、性能度量等。如下圖OT.TPOLAP用戶(hù)員工,IT專(zhuān)山人員卻識(shí)工作者功能每天的日常操作決策支持DBS計(jì)面向應(yīng)用+ER面向電題+弘前與前的.詳細(xì)的數(shù)據(jù)歷史的，匯總的，多錐的集成的，整理過(guò)的重尖的特定的訪(fǎng)問(wèn)讀茸索引爭(zhēng)出掃描匚作單元短的，簡(jiǎn)單的事務(wù)處理復(fù)雜査詢(xún)記錄數(shù)/査詢(xún)幾十百萬(wàn)用戶(hù)數(shù)上千百M(fèi)規(guī)模IOOM13-GB100GB-TBmetrictransactionthroughputquerrtlirougliputresponseLecture4.【關(guān)聯(lián)規(guī)則的確定性度量與實(shí)用性度量】確定性度量：支持度(Support)，事務(wù)包含XuY的概率，即s

16、upport=P(XuY)實(shí)用性度量：置信度(Confidence)，事務(wù)同時(shí)包含X與Y的條件概率，即confidence=P(Y|X).*【問(wèn)題的分類(lèi)】Lecture5.【兩種學(xué)習(xí)模型】有監(jiān)督學(xué)習(xí)模型：提供了每個(gè)訓(xùn)練元組的類(lèi)標(biāo)號(hào)，稱(chēng)作監(jiān)督學(xué)習(xí)，即分類(lèi)器的學(xué)習(xí)在被告知每個(gè)訓(xùn)練元組屬于哪個(gè)類(lèi)的監(jiān)督下進(jìn)行。無(wú)監(jiān)督學(xué)習(xí)(聚類(lèi))模型：每個(gè)訓(xùn)練元組的類(lèi)標(biāo)號(hào)都是未知的，并且要學(xué)習(xí)的類(lèi)的個(gè)數(shù)或集合也可能事先不知道。【評(píng)估分類(lèi)器準(zhǔn)確率的方法】PPT版劃分法：適用于大規(guī)模數(shù)據(jù)。把樣本劃分成2個(gè)獨(dú)立的數(shù)據(jù)集合。交叉驗(yàn)證：適用于中型規(guī)模數(shù)據(jù)。把數(shù)據(jù)集劃分成k個(gè)子樣本集合，使用k-1個(gè)子樣本集合作為訓(xùn)練集，另一個(gè)作為

17、測(cè)試集，亦稱(chēng)k-折交叉驗(yàn)證。留一測(cè)試：適用于小規(guī)模數(shù)據(jù)。k=n(n-折交叉驗(yàn)證)。教材版保持方法和隨機(jī)子抽樣：保持方法把給定數(shù)據(jù)隨機(jī)分成兩個(gè)獨(dú)立的集合:訓(xùn)練集和檢驗(yàn)集，使用訓(xùn)練集導(dǎo)出模型，其準(zhǔn)確率用檢驗(yàn)集估計(jì).隨機(jī)子抽樣是保持方法的變型,將保持方法重復(fù)k次，總準(zhǔn)確率估計(jì)取每次迭代準(zhǔn)確率的平均值交叉確認(rèn)：把數(shù)據(jù)集劃分成k個(gè)子樣本集合，使用k-1個(gè)子樣本集合作為訓(xùn)練集，另一個(gè)作為測(cè)試集，亦稱(chēng)k-折交叉驗(yàn)證。自助法：從給定訓(xùn)練元組中有放回均勻抽樣【基于規(guī)則的分類(lèi)器】?jī)?nèi)容：前件，后件，覆蓋學(xué)習(xí)規(guī)則：分治法規(guī)則能夠覆蓋整個(gè)示例空間嗎？：缺省規(guī)則如何學(xué)到最優(yōu)規(guī)則？：NPhard問(wèn)題*【P,NP,NPC,N

18、P-Hard】P問(wèn)題：在多項(xiàng)式時(shí)間內(nèi)能解決的問(wèn)題NP問(wèn)題：在多項(xiàng)式時(shí)間內(nèi)能驗(yàn)證的問(wèn)題NPC問(wèn)題：所有NP問(wèn)題能在多項(xiàng)式時(shí)間內(nèi)規(guī)約到該問(wèn)題.且該問(wèn)題本身屬于NP問(wèn)題NP-Hard問(wèn)題：所有NP問(wèn)題能在多項(xiàng)式時(shí)間內(nèi)規(guī)約到該問(wèn)題【屬性之間相似性計(jì)算】(1)區(qū)間標(biāo)度變量：1計(jì)算均值絕對(duì)偏差：Sj-I+Ir叫【十*IJt吋一竹f)2.計(jì)算標(biāo)準(zhǔn)度量值或z-score對(duì)稱(chēng)二元變量(binary)：簡(jiǎn)單匹配系數(shù)(3)非對(duì)稱(chēng)二元變量(binary)：Jaccard系數(shù)力仏門(mén)Lecture6.*【近似比】分類(lèi)變量(nominal、categorical)：方法1:簡(jiǎn)單匹配(不匹配率)-側(cè)：叢配的數(shù)1尹：全部變量的

19、數(shù)仃對(duì)于優(yōu)化問(wèn)題，算法A的近似比a(n)三1最小化：a(n)=cost(A)/cost(opt)最大化：a(n)=cost(opt)/cost(A)方法2:使用一組二元變量對(duì)標(biāo)稱(chēng)型變量的每一個(gè)狀態(tài)設(shè)置一個(gè)二元變量*【聚類(lèi)半徑、直徑、分離度】直徑：類(lèi)內(nèi)最大點(diǎn)距離半徑：類(lèi)內(nèi)最小點(diǎn)距離分離度：類(lèi)間最小點(diǎn)距離(5) 連續(xù)變量(realvalue)、序數(shù)變量(orderedset):1. 離散化2. 用它們的秩r替換xfrifeMf3. 將每一個(gè)變量的范圍映射到0,1J一】7二礦-4. 用計(jì)算區(qū)間值變量同樣的方法計(jì)算非相似性(6) 向量對(duì)象:余弦相似性Ts(x.y)=【常見(jiàn)的聚類(lèi)優(yōu)化目標(biāo)】1.Minko

20、wski距離:如)屮-屮嘰-屮+%-唧)2.如果q=1,d是Manhattan距離:尹3.如果q=2,d是Euclidean距離2+卜I兀一兀|2)1PJP【聚類(lèi)分析常用的數(shù)據(jù)結(jié)構(gòu)】1.數(shù)據(jù)矩陣(2模)：用p個(gè)變量(也稱(chēng)度量和或?qū)傩?表示n個(gè)對(duì)象XH“xlfxlp(1) k-Center：最大半徑最小化minr(P)T(2) k-Cluster：最大直徑最小化min(F)T(3) 聚類(lèi)分離度的最大化max5(P)(4) k-median：聚類(lèi)內(nèi)部距離之和的最小化mmZ工乳6)止耳j-LCjECi(5) k-means：聚類(lèi)內(nèi)部距離平方之和的最小化nunXUxjf0d(2fl)0心)I-J(3,

21、2)01)，則成為周期的。一個(gè)馬爾科夫鏈所有狀態(tài)都是非周期的，則為非周期。解決方案：指定一個(gè)參數(shù)，將每一個(gè)網(wǎng)頁(yè)(狀態(tài))都以概率d指向其它所有網(wǎng)頁(yè)。此方法順便解決了不可約問(wèn)題，處理后(原始文獻(xiàn)阻尼因子d=0.85)：帀其中E=ee”E=ones(n)，令eTP=n:P=(l-d)e+dArP尸工禺因此，每個(gè)網(wǎng)頁(yè)優(yōu)點(diǎn)：(1) 防欺騙網(wǎng)頁(yè)所有者難以設(shè)置其它重要網(wǎng)頁(yè)指向自己的網(wǎng)頁(yè).(2) ageRank值獨(dú)立于查詢(xún)，是一種全局度量.PageRank值是通過(guò)所有網(wǎng)頁(yè)計(jì)算得到并加以存儲(chǔ)，而不是提交查詢(xún)時(shí)才計(jì)算.缺點(diǎn)：不能區(qū)分全局重要性網(wǎng)頁(yè)和查詢(xún)主題重要性網(wǎng)頁(yè)【HITS】基本思想：*內(nèi)容一個(gè)好的匯集網(wǎng)頁(yè)指向

22、了許多權(quán)威性網(wǎng)頁(yè)*一個(gè)好的權(quán)威性網(wǎng)頁(yè)被許多好的匯集性網(wǎng)頁(yè)所指向.*因此，二者相互強(qiáng)化.與PageRank是一個(gè)靜態(tài)算法不同，HITS是基于查詢(xún)的搜索算法，當(dāng)用戶(hù)提交一個(gè)查詢(xún)時(shí)-HITS首先對(duì)搜索引擎返回的相關(guān)網(wǎng)頁(yè)列表進(jìn)行擴(kuò)展-然后產(chǎn)生擴(kuò)展集合的兩個(gè)排序：權(quán)威性排序(authorityranking)及匯集性排序(hubranking).Authority:粗略地講，一個(gè)權(quán)威性網(wǎng)頁(yè)具有很多的入邊.-該網(wǎng)頁(yè)具有相關(guān)主題的權(quán)威性?xún)?nèi)容-許多人相信該網(wǎng)頁(yè)并指向它.Hub:一個(gè)匯集性網(wǎng)頁(yè)具有很多出邊.-該網(wǎng)頁(yè)把特定主題網(wǎng)頁(yè)進(jìn)行了組織-指向了該主題的許多權(quán)威性網(wǎng)頁(yè).算法：11ITS-ltcrMe(G)tin

23、IQ-L-_IhkiKcpenIif上h:normalizeak.normalizeuntil/jt-aiidhkdonorchange:iignificuntlv:rciLirtianda=LThhLa1. 根據(jù)查詢(xún)?cè)~q,搜集t個(gè)排序最高的網(wǎng)頁(yè)集合W(rootset)2. 把所有W指向的網(wǎng)頁(yè)和指向W的網(wǎng)頁(yè)添加到W中，得到基集S(baseset)3. HITS對(duì)S中每個(gè)網(wǎng)頁(yè)分配authorityscore和hubscore.4. 建立鄰接矩陣L：Zj.=min_sup，輸出此規(guī)則卄t事務(wù)泗曲-訶計(jì)數(shù)_事務(wù)計(jì)勤其中sup(m-(|-m)=【頻繁模式樹(shù)的構(gòu)造】TID100ficfd,卑Atn,p2

24、00氏Xa購(gòu),姙300b,f,h,j,偽w400ft,c,k,srp500rninspporf=31. 從頻繁1項(xiàng)表由下往上掃描，不掃描最上面的元素例子：此例中依次掃描p,m,b,a,c2. 找出每個(gè)元素的”條件模式基”(即父路徑)例子：m的條件模式基f,c,a:2和f,c,a,b:13. 找出每個(gè)元素的”條件FP樹(shù)”(即父路徑”經(jīng)過(guò)次數(shù)”大于等于最小支持度的”路徑”)(a:2,b:2,c:2,a:1,b:1可以合并為a:3,b:3,c:2)例子：m的條件FP樹(shù)f:3,c:3,a:34. 元素x的條件FP樹(shù)的子集，加上X，即為頻繁模式仇卿咖訛呃ficra,m,jf【關(guān)聯(lián)規(guī)則的提升度】Corr(

25、A,B)=P(AB)/(P(A)P(B)=P(B|A)P(A)/(P(A)P(B)=P(B|A)/P(B)1,正相關(guān)；=1,獨(dú)立；1,負(fù)相關(guān)1.根據(jù)事務(wù)，統(tǒng)計(jì)出頻繁1-項(xiàng)集，并排序。(支持度相同則按出現(xiàn)次序排序)2.根據(jù)頻繁1-項(xiàng)集，把原事務(wù)中小于最小支持度的元素刪除。并且把剩余元素按頻繁項(xiàng)表排序。3.創(chuàng)建根節(jié)點(diǎn)，對(duì)事務(wù)表的元素逐個(gè)添加到樹(shù)中。例如，*對(duì)于事務(wù)TID=100,先添加f，計(jì)數(shù)為1；Video40003007500NonVideo20005002500Slim6000400010000例子：GameNonGameSumCorr(Video,Game)=0.4/(0.75*0.6)=

26、0.89fc的邊已存在，c計(jì)數(shù)+1.根節(jié)點(diǎn)-f-c-a-b邊不存在，創(chuàng)建b，VideoGame4000/10000,4000/7500GanicVideo4000/10000.4000/6000計(jì)數(shù)為1.例子Lecture5.agericome$iudtncreditratmg|buy$ccmpuler=30highnofarrw40meciuimnofpirlowvesfaryesMDlow怦eudlentrw31.40law/esexcellent序5meciumnofairm5law怦faryesmediumyesfary&s5mediumyesexcellentyesJI.40medi

27、umrtoexcellentyes3140highyesfairys40mediuninorw類(lèi):Cl:buys_computerC2:buys_coinpiiter求樣也age=30,Income=niedium,Student=yesCredit=Fair【信息增益的計(jì)算】期望信息：設(shè)樣本集合s含有si個(gè)類(lèi)為Ci的元組,i=1,m,則對(duì)一個(gè)給定的樣本分類(lèi)所需的期望信息是：“、豊覧、St1(57,52Jm)-XLOg-1-1S5熵：具有值口衛(wèi)2，.幾的屬性A的熵E(A)為屬性A導(dǎo)致的s的劃分的期望信息的加權(quán)平均和：E(A)-藝占門(mén)+占測(cè)f片,)J-5信息增益：Gam(A)-I(sE(A)卩0

28、驢=叱3曠|buy$_cottiiu-2;9=O+222Pfafe0D4P(trLit_ratiJig=fair|buys_compulr=ttes；r)=fi/9=ft67P(crediJ_iating=bfaii+h|buys_co(iTipiitei=uc)=2./5=0.4P(X|Ci):鞏Xbuys_coiJipiitfir=bbyes)=0.222x0.444x0.667x0.0.667=0.044P(X|buy&_computei=06xQ.Jx0.2x0.4=0.019P(X|CI)xP(Ci)：P(X|yes)xP(ye)=0.028P(X|no)xP(iio)=0.007所

29、X屬J啖wbnyscompiiteFH例子：I苫切序十勺J【基于規(guī)則的分類(lèi)器】*【決策樹(shù)算法】i創(chuàng)建根節(jié)點(diǎn)2若所有樣本為類(lèi)x,標(biāo)記為類(lèi)x3.若Attribute為空，標(biāo)記為最普遍的類(lèi)4選擇IG最大的屬性，每個(gè)可能值建立子節(jié)點(diǎn)，遞歸解決【決策樹(shù)算法時(shí)間復(fù)雜性】給定訓(xùn)練集D,算法的計(jì)算復(fù)雜度為O(nx|D|xlog|D|)其中n是D中的元組數(shù)，|D|是D中訓(xùn)練元組數(shù)利用分治法學(xué)習(xí)規(guī)則Scp3rstcundCoiiqucr(D)設(shè)為D中類(lèi)c的示例集合；ForcuchclssscWhile(Dr工0)R0010d0001110J1J-00001000000MLLJLecture6.【k-means聚類(lèi)

30、】算法參照【概念題篇】例子：i23456(12,億劉(13,11)1(23,10)(IS,23)(20,$對(duì)象如下，妒2步驟L任意選擇兩個(gè)對(duì)象作為種丁,如2和4步驟Z分配剩下的對(duì)象所有反例已被覆蓋，得到規(guī)則:(C=1)A(D=1)T(Class=1)*【樣本復(fù)雜性】No21125125234ftIflt45317旳4G2?MI7J因此，有2個(gè)聚類(lèi)；1,2,3和陸56-兩亍聚類(lèi)內(nèi)部每亍對(duì)象與對(duì)應(yīng)的聚類(lèi)屮心旳平方i吳差和為步騾3,計(jì)算每個(gè)聚類(lèi)的中心-Chuter:1=(12+74-13)/3,(8+-31)/3)=(10.67,9.33)-Cluster2:=(23+18+20/3,(1023+1

31、83)=(20.35,17)步驟4”堂新分配對(duì)象(停止).假設(shè)空間H中學(xué)習(xí)一個(gè)學(xué)習(xí)幾率06錯(cuò)誤率一Inb例子:_無(wú)偏概念類(lèi)H,含有與X個(gè)樣本，每個(gè)樣本有n個(gè)【k-center聚類(lèi)】和k-means大致一樣，只不過(guò)在第二次及之后的迭代，計(jì)算的參照點(diǎn)不是質(zhì)心，而是新的中心對(duì)象。每次迭代判斷代價(jià)變化，若代價(jià)差小于0,接受此次布爾特征空間山2，每個(gè)樣本X債得出m-(2nIn2+In)(7改變。I由新廿配給口2厳甘配松I?Endwn3十城生變f匕4.戢靳井配給+甜中心一烷擁前出中心點(diǎn)緊奧代冊(cè)豳檢的四科?！灸蹖哟尉垲?lèi)法】單鏈接算法例子：給定5個(gè)對(duì)象間的距離如卜表-現(xiàn)在，我們得到2個(gè)聚類(lèi)1,3,4和匚5步

32、驟5計(jì)算164的2,5聚類(lèi)山；.門(mén)畀廠(chǎng)史型騷也$屛焊4中血4_斗No2,51,3,4陽(yáng)2,4040*步驟1;每個(gè)對(duì)象當(dāng)做個(gè)聚類(lèi).步驟2：找出r述5個(gè)聚類(lèi)中最近的兩個(gè)聚類(lèi)2和）因?yàn)樗鼈兊木嚯x最小:氐=1.所以,2和5凝聚成一個(gè)新的聚類(lèi)2.5._距離D251=mind2lhd?1min657-6lx?,d23.d5J=min4.5=4“尸mmd汕d34=min4a5=4!0】$年5戸門(mén)日星期三No2,邸1342,50160342044350-3農(nóng)狙的-聚類(lèi)1,比4和2d凝聚成一個(gè)唯一的聚類(lèi)1,2,3A5.-4個(gè)聚類(lèi)2,5,1,3,4中最近的2個(gè)聚類(lèi)是1和3一因此*1和3凝聚成一個(gè)新的聚類(lèi)一現(xiàn)在，我

33、們有3個(gè)聚類(lèi)：13b2,5,4.-步驟4計(jì)算聚類(lèi)1/與2,5,4ZM的跖離-Dli3K2.,=nundl；i!,di2r5mm6A-4-DE34=nnn持匿4/500乜丨1-花生醬3/5花生醬FT沁件奶啤酒2/52/5組合連接L1中的各項(xiàng)目產(chǎn)生2-候選集C2，計(jì)算其支持度，取出支持度小于supmin的項(xiàng)集，形成2-頻繁集L2,如下表所示：項(xiàng)恥支持度項(xiàng)集“佰包、花主醬面包、花生醬S.?至此，所有頻繁集都被找到，算法結(jié)束，所以，confidence(面包花生醬)=(4/5)/(3/5)=4/3confminconfidence(花生醬f面包)=(3/5)/(4/5)=3/4confmin所以，關(guān)聯(lián)規(guī)則面包-花生醬、花生醬-面包均是強(qiáng)關(guān)聯(lián)規(guī)則。2給定以下數(shù)據(jù)集(2,4,10,12,15,3,21),進(jìn)行K-Means聚類(lèi)，設(shè)定聚類(lèi)數(shù)為2個(gè),相似度按照歐式距離計(jì)算。(10分)從數(shù)據(jù)集X中隨機(jī)地選擇k個(gè)數(shù)據(jù)樣本作為聚類(lèi)的出示代表點(diǎn)，每一個(gè)代表點(diǎn)表示一個(gè)類(lèi)別，由題可知k=2,則可設(shè)ml=2,m2=4：對(duì)于X中的任意數(shù)據(jù)樣本xm(lvxmvtotal),計(jì)算它與k個(gè)初始代表點(diǎn)的距離，并且將它劃分到距離最近的初始代表點(diǎn)所表示的類(lèi)別中：當(dāng)m1=2時(shí)，樣本(2,4,10,12,15,3,21)距離該代表點(diǎn)的距離分別為2，8，l0，l3，l，l9