《《大數(shù)據(jù)》第3章數(shù)據(jù)挖掘算法(下)》由會(huì)員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)》第3章數(shù)據(jù)挖掘算法(下)（34頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、則,第三章,數(shù),數(shù)據(jù)挖掘,算,算法,3.4.4,案例：保險(xiǎn)客,戶,戶風(fēng)險(xiǎn)分,析,析,3,關(guān)聯(lián)規(guī),則,則挖掘,影響駕駛?cè)藛T安全駕駛的主要因素,年齡,性別,駕,齡,職業(yè),婚姻狀況,車輛,車型,車輛,用途,車齡,其他,根據(jù)前述關(guān)聯(lián)規(guī)則的生成方法，得到挖掘出來(lái)的客戶風(fēng)險(xiǎn)關(guān)聯(lián)規(guī)則,序號(hào),關(guān)聯(lián)規(guī)則,支持度,置信度,1,駕齡（,X,，,A,）被保車輛的價(jià)值（,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,）被保車輛的價(jià)值（,X,，,C,）,年賠付金額（,X,，,C,）,0.1809,0.3003,6,駕齡（,X,，,C,）車輛用途（,X,，,B,）,年賠付次數(shù)（,X,，,A,）,0.1994,0.5864,7,駕齡（