《《大數(shù)據(jù)》第3章數(shù)據(jù)挖掘算法(下)》由會員分享，可在線閱讀，更多相關《《大數(shù)據(jù)》第3章數(shù)據(jù)挖掘算法(下)（34頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,大數(shù)據(jù),BIG DATA,3.1,數(shù)據(jù)挖掘概述,第三章數(shù)據(jù)挖掘算法,3.2,分類,3.3,聚類,3.1,數(shù)據(jù)挖掘概述,3.5,預測規(guī)模,習題,3.6,數(shù)據(jù)挖掘算法綜合應用,3.4,關聯(lián)規(guī)則,of,65,2,3.4,關聯(lián)規(guī)則,關聯(lián)規(guī)則是數(shù),據(jù),據(jù)挖掘中最活,躍,躍的研究方法,之,之一，是指搜,索,索業(yè)務系統(tǒng)中,的,的所有細節(jié)或,事,事務，找出所,有,有能把一組事,件,件或數(shù)據(jù)項與,另,另一組事件或,數(shù),數(shù)據(jù)項聯(lián)系起,來,來的規(guī)則，以,獲,獲得存在于數(shù),據(jù),據(jù)庫中的不為,人,人知的或不能,確,確定的信息，,它,它側

2、重于確定,數(shù),數(shù)據(jù)中不同領,域,域之間的聯(lián)系,，,，也是在無指,導,導學習系統(tǒng)中,挖,挖掘本地模式,的,的最普通形式,。,。,More,應用市場：,市場貨籃分析、交,叉,叉銷售（,Crossing Sale,）、部分分類,（,（,Partial Classification,）、金融服務,（,（,Financial Service,），以及通信,、,、互聯(lián)網(wǎng)、電子商務,第三章 數(shù)據(jù),挖,挖掘算法,of,65,3,3.4,關聯(lián)規(guī)則,第三章 數(shù)據(jù),挖,挖掘算法,一般來說，關,聯(lián),聯(lián)規(guī)則挖掘是,指,指從一個大型,的,的數(shù)據(jù)集（,Dataset,）發(fā)現(xiàn)有趣的,關,關聯(lián)（,Association,）或相

3、關關系,（,（,Correlation,），即從數(shù)據(jù),集,集中識別出頻,繁,繁出現(xiàn)的屬性,值,值集（,Sets of AttributeValues,），也稱為頻,繁,繁項集（,Frequent Itemsets,，頻繁集），,然,然后利用這些,頻,頻繁項集創(chuàng)建,描,描述關聯(lián)關系,的,的規(guī)則的過程,。,。,3.4.1,關聯(lián)規(guī)則的概念,關聯(lián)規(guī)則挖掘問題,：,發(fā)現(xiàn)所有的頻繁項,集,集是形成關聯(lián),規(guī),規(guī)則的基礎。,通,通過用戶給定,的,的最小支持度,，,，尋找所有支,持,持度大于或等,于,于,Minsupport,的頻繁項集。,通過用戶給定,的,的最小可信度,，,，在每個最大,頻,頻繁項集中，,尋,

4、尋找可信度不,小,小于,Minconfidence,的關聯(lián)規(guī)則。,發(fā)現(xiàn)頻繁項集,生成關聯(lián)規(guī)則,如何迅速高效,地,地發(fā)現(xiàn)所有頻,繁,繁項集，是關,聯(lián),聯(lián)規(guī)則挖掘的,核,核心問題，也,是,是衡量關聯(lián)規(guī),則,則挖掘算法效,率,率的重要標準,。,。,of,65,4,3.4,關聯(lián)規(guī)則,第三章 數(shù)據(jù),挖,挖掘算法,3.4.2,頻繁項集的產(chǎn)生及,其,其經(jīng)典算法,格結構（,Lattice Structure,）常常被用來,枚,枚舉所有可能,的,的項集。,圖,3-10,項集的格,of,65,5,3.4,關聯(lián)規(guī)則,第三章 數(shù)據(jù),挖,挖掘算法,3.4.2,頻繁項集的產(chǎn)生及,其,其經(jīng)典算法,格結構（,Lattice

5、Structure,）常常被用來,枚,枚舉所有可能,的,的項集。,查找頻繁項目集,經(jīng)典的查找策略,基于精簡,集的,查找策略,基于最大頻繁,項集的,查找策略,按照挖掘的策略不同,經(jīng)典的挖掘完全頻繁項集方法,基于廣度優(yōu)先搜索策略的關聯(lián)規(guī)則算法,基于深度優(yōu)先搜索,策略,的算法,Apriori,算法,、,DHP,算法,FP-Growth,算法,、,ECLAT,算法,COFI,算法,與,經(jīng)典,查找不同,方法,基于精簡集的方法,基于最大頻繁項目集的方法,A-close,算法,MAFIA,算法,、,GenMax,算法,DepthProject,算法,of,65,6,3.4,關聯(lián)規(guī)則,第三章 數(shù)據(jù),挖,挖掘算

6、法,3.4.2,頻繁項集的產(chǎn)生及,其,其經(jīng)典算法,1,Apriori,算法,Apriori,算法基于頻繁,項,項集性質的先,驗,驗知識，使用,由,由下至上逐層,搜,搜索的迭代方,法,法，即從頻繁,1,項集開始，采,用,用頻繁,k,項集搜索頻繁,k,+1,項集，直到不,能,能找到包含更,多,多項的頻繁項,集,集為止。,Apriori,算法由以下步,驟,驟組成，其中,的,的核心步驟是,連,連接步和剪枝,步,步：,生成頻繁,1,項集,L,1,連接步,剪枝步,生成頻繁,k,項集,L,k,重復步驟（,2,）（,4,），直到不能,產(chǎn),產(chǎn)生新的頻繁,項,項集的集合為,止,止，算法中止,。,。,性能瓶頸,Ap

7、riori,算法是一個多,趟,趟搜索算法,可能產(chǎn)生龐大,的,的候選項集,of,65,7,3.4,關聯(lián)規(guī)則,第三章 數(shù)據(jù),挖,挖掘算法,3.4.2,頻繁項集的產(chǎn)生及,其,其經(jīng)典算法,2,FP-Growth,算法,頻繁模式樹增,長,長算法（,Frequent Pattern TreeGrowth,）采用分而治之的基,本,本思想，將數(shù),據(jù),據(jù)庫中的頻繁,項,項集壓縮到一,棵,棵頻繁模式樹,中,中，同時保持,項,項集之間的關,聯(lián),聯(lián)關系。然后,將,將這棵壓縮后,的,的頻繁模式樹,分,分成一些條件,子,子樹，每個條,件,件子樹對應一,個,個頻繁項，從,而,而獲得頻繁項,集,集，最后進行,關,關聯(lián)規(guī)則挖掘

8、。,FP-Growth,算法由以下步,驟,驟組成：,掃描事務數(shù)據(jù),庫,庫,D,，生成頻繁,1,項集,L,1,將頻繁,1,項集,L,1,按照支持度遞,減,減順序排序，,得,得到排序后的,項,項集,L,1,構造,FP,樹,通過后綴模式,與,與條件,FP,樹產(chǎn)生的頻繁,模,模式連接實現(xiàn),模,模式增長,1,2,3,4,圖,3-11FP,樹的構造,of,65,8,3.4,關聯(lián)規(guī)則,第三章 數(shù)據(jù),挖,挖掘算法,3.4.2,頻繁項集的產(chǎn)生及,其,其經(jīng)典算法,3,辛普森悖論,雖然關聯(lián)規(guī)則,挖,挖掘可以發(fā)現(xiàn),項,項目之間的有,趣,趣關系，在某些情況下,，,，隱藏的變量,可,可能會導致觀,察,察到的一對變,量,量

9、之間的聯(lián)系,消,消失或逆轉方,向,向，這種現(xiàn)象,就,就是所謂的辛,普,普森悖論（,Simpsons Paradox,）。,為了避免辛普,森,森悖論的出現(xiàn),，,，就需要斟酌,各,各個分組的權,重,重，并以一定,的,的系數(shù)去消除,以,以分組數(shù)據(jù)基,數(shù),數(shù)差異所造成,的,的影響。同時,必,必須了解清楚,情,情況，是否存,在,在潛在因素，,綜,綜合考慮。,of,65,9,3.4,關聯(lián)規(guī)則,第三章 數(shù),據(jù),據(jù)挖掘算法,3.4.3,分類技術,分類技術或,分,分類法（,Classification,）是一種根,據(jù),據(jù)輸入樣本,集,集建立類別,模,模型，并按,照,照類別模型,對,對未知樣本,類,類標號進行,標

10、,標記的方法,。,。,根據(jù)所采用,的,的分類模型,不,不同,基于決策樹模型,的,的數(shù)據(jù)分類,基于統(tǒng)計模型的,數(shù),數(shù)據(jù)分類,基于神經(jīng)網(wǎng)絡模,型,型的數(shù)據(jù)分類,基于案例推理的,數(shù),數(shù)據(jù)分類,基于實例的數(shù)據(jù),分,分類,1,決策樹,決策樹就是通過,一,一系列規(guī)則對數(shù),據(jù),據(jù)進行分類的過,程,程。,決策樹分類算法,通,通常分為兩個步,驟,驟：構造決策樹,和,和修剪決策樹。,of,65,10,3.4,關聯(lián)規(guī)則,第三章 數(shù)據(jù)挖,掘,掘算法,3.4.3,分類技術,構造決策樹,修剪決策樹,根據(jù)實際需求及所處,理,理數(shù)據(jù)的特性，,選,選擇類別標識屬,性,性和決策樹的決,策,策屬性集,在決策屬性集中,選,選擇最有分

11、類標,識,識能力的屬性作,為,為決策樹的當前,決,決策節(jié)點,根據(jù)當前決策節(jié),點,點屬性取值的不,同,同，將訓練樣本,數(shù),數(shù)據(jù)集劃分為若,干,干子集,子集中的所有元組都屬于同一類。,該子集是已遍歷了所有決策屬性后得到的。,子集中的所有剩余決策屬性取值完全相同，已不能根據(jù)這些決策屬性進一步劃分子集。,針對上一步中得到的每一個子集，重復,進行,以上,兩,個步驟，直到最后的子集符合約束的,3,個條件之一,根據(jù)符合條件不同生,成,成葉子節(jié)點,對決策樹進行修,剪,剪，除去不必要,的,的分枝，同時也,能,能使決策樹得到,簡,簡化。,常用的決策樹修,剪,剪策略,基于代價復雜度,的,的修剪,悲觀修剪,最小描述長

12、度,修剪,按照修剪的先后,順,順序,先剪枝（,Pre-pruning,）,后剪枝（,Post-pruning,）,of,65,11,3.4,關聯(lián)規(guī)則,第三章 數(shù)據(jù)挖,掘,掘算法,3.4.3,分類技術,2,k-,最近鄰,最臨近分類基于類比學習，是一種基于實例的學習，它使用具體的訓練實例進行預測，而不必維護源自數(shù)據(jù)的抽象（或模型）。它采用,n,維數(shù),值屬性描述訓練樣本，每個樣本代表,n,維,空間的一個點，即所有的訓練樣本都存放在,n,維,空間中。若給定一個未知樣本，,k-,最近鄰分類法搜索模式空間，計算該測試樣本與訓練集中其他樣本的鄰近度，找出最接近未知樣本的,k,個,訓練樣本，這,k,個訓練樣本

13、,就是未知樣本的,k,個,“近鄰”。其中的“鄰近度”一般采用歐幾里得距離定義：兩個,點,和,的,Euclid,距離,是,。,最近鄰分類是基,于,于要求的或懶散,的,的學習法，即它,存,存放所有的訓練,樣,樣本，并且直到,新,新的（未標記的,）,）樣本需要分類,時,時才建立分類。,其,其優(yōu)點是可以生,成,成任意形狀的決,策,策邊界，能提供,更,更加靈活的模型,表,表示。,of,65,12,3.4,關聯(lián)規(guī)則,第三章 數(shù)據(jù)挖,掘,掘算法,3.4.4,案例：保險客戶風險,分,分析,1,挖掘目標,由過去大量的經(jīng),驗,驗數(shù)據(jù)發(fā)現(xiàn)機動,車,車輛事故率與駕,駛,駛者及所駕駛的,車,車輛有著密切的,關,關系，影

14、響駕駛,人,人員安全駕駛的,主,主要因素有年齡,、,、性別、駕齡、,職,職業(yè)、婚姻狀況,、,、車輛車型、車,輛,輛用途、車齡等。因此，,客,客戶風,險,險分析,的,的挖掘,目,目標就,是,是上述,各,各主要,因,因素與,客,客戶風,險,險之間,的,的關系,，,，等等,。,。,2,數(shù)據(jù),預,預處理,數(shù)據(jù)準,備,備與預,處,處理是,數(shù),數(shù)據(jù)挖,掘,掘中的,首,首要步,驟,驟，高,質,質量的,數(shù),數(shù)據(jù)是,獲,獲得高,質,質量決,策,策的先,決,決條件,。,。在實,施,施數(shù)據(jù),挖,挖掘之,前,前，及,時,時有效,的,的數(shù)據(jù),預,預處理,可,可以解,決,決噪聲,問,問題和,處,處理缺,失,失的信,息,息

15、，將,有,有助于,提,提高數(shù),據(jù),據(jù)挖掘,的,的精度,和,和性能,。,。,去除數(shù)據(jù)集,之,之中的,噪,噪聲數(shù),據(jù),據(jù)和無,關,關數(shù)據(jù),，,，處理,遺,遺漏數(shù),據(jù),據(jù)和清,洗,洗“臟,”,”數(shù)據(jù)等,。,數(shù)據(jù)清,洗,洗處理,通,通常包,括,括處理,噪,噪聲數(shù),據(jù),據(jù)、填,補,補遺漏,數(shù),數(shù)據(jù)值,/,除去異,常,常值、,糾,糾正數(shù),據(jù),據(jù)不一,致,致的問,題,題，等,等,等。,在處理,完,完噪聲,數(shù),數(shù)據(jù)后,，,，就可,以,以對數(shù),據(jù),據(jù)進行,轉,轉化，,主,主要的,方,方法有,：,聚集,忽略無關屬性,連續(xù)型屬性離,散,散化等。,數(shù)據(jù)清,洗,洗,數(shù)據(jù)轉,化,化,of,65,13,3.4,關聯(lián),規(guī),規(guī)

16、則,第三章,數(shù),數(shù)據(jù)挖掘,算,算法,3.4.4,案例：保險客,戶,戶風險分,析,析,3,關聯(lián)規(guī),則,則挖掘,影響駕駛人員安全駕駛的主要因素,年齡,性別,駕,齡,職業(yè),婚姻狀況,車輛,車型,車輛,用途,車齡,其他,根據(jù)前述關聯(lián)規(guī)則的生成方法，得到挖掘出來的客戶風險關聯(lián)規(guī)則,序號,關聯(lián)規(guī)則,支持度,置信度,1,駕齡（,X,，,A,）被保車輛的價值（,X,，,A,）,年賠付金額（,X,，,B,）,0.1825,0.2965,2,投保人年齡（,X,，,A,）駕齡（,X,，,A,）,年賠付次數(shù)（,X,，,B,）,0.1679,0.2571,3,駕齡（,X,，,B,）車輛用途（,X,，,A,）,年賠付金額（,X,，,B,）,0.1663,0.3337,4,駕齡（,X,，,B,）車輛用途（,X,，,B,）,年賠付次數(shù)（,X,，,A,）,0.1789,0.4851,5,駕齡（,X,，,B,）被保車輛的價值（,X,，,C,）,年賠付金額（,X,，,C,）,0.1809,0.3003,6,駕齡（,X,，,C,）車輛用途（,X,，,B,）,年賠付次數(shù)（,X,，,A,）,0.1994,0.5864,7,駕齡（