大數(shù)據(jù)技術(shù)在企業(yè)創(chuàng)新背景下高

校物流人才培養(yǎng)中的轉(zhuǎn)化與應(yīng)用

第六章1數(shù)據(jù)挖掘基本算法

主講：朱明

高級I:程加、高級技師、國家經(jīng)濟(jì)師

高級國家職業(yè)技能簽定考評員

高級技能專業(yè)教加

朱明■■百度個人主頁朱明工作室

口知足常樂，歷經(jīng):兵農(nóng)

□歷經(jīng)：兵團(tuán)開車，赤腳醫(yī)生、教師、地方修車，

□企業(yè)管理：技術(shù)、運(yùn)營、物流、安全、保衛(wèi),

□職任：客運(yùn)站長、公司經(jīng)理，集團(tuán)技術(shù)總監(jiān)，

□總經(jīng)理及法人代表。

□學(xué)歷：本科、MBA,

□專業(yè)：汽車維修與使用、企業(yè)管理、經(jīng)濟(jì)管理。

□職業(yè)資格與職稱：高級工程師、高級技師、國家經(jīng)濟(jì)師、

高級技能專業(yè)教師、高級國家職業(yè)資格考評員。

□管理科學(xué)研究院特約講師、

□管理顧問有限公司高級講師。

□客座任教：大學(xué)、技師學(xué)院、國家職業(yè)資格培訓(xùn)與考評及

□企業(yè)內(nèi)部職業(yè)培訓(xùn)。

第六章數(shù)據(jù)挖掘基本算法

?6.1分類規(guī)則挖掘

?6.2預(yù)測分析與趨勢分析規(guī)則

I—?6.3數(shù)據(jù)挖掘的關(guān)聯(lián)算法

?6.4數(shù)據(jù)挖掘的聚類算法

?6.5數(shù)據(jù)挖掘的統(tǒng)計分析算法

?6.6數(shù)據(jù)挖掘的品種優(yōu)化算法

?6.7數(shù)據(jù)挖掘的進(jìn)化算法

年

6.3數(shù)據(jù)挖掘的關(guān)聯(lián)算法2022-2O23WJft#i

?6.3.1關(guān)聯(lián)規(guī)則的概念及分類

?6.3.2簡單形式的關(guān)聯(lián)規(guī)則算法（單維、單層和布爾

關(guān)聯(lián)規(guī)則）

?6.3.3多層和多維關(guān)聯(lián)規(guī)則的挖掘

?6.3.4貨籃子分析存在的問題

?6.3.5關(guān)聯(lián)分析的其他算法

?6.3.6挖掘序列模式*

6.3.1關(guān)聯(lián)規(guī)則的概念及分類任

?(D關(guān)聯(lián)規(guī)則的概念

?關(guān)聯(lián)規(guī)則挖掘是尋找數(shù)據(jù)項(xiàng)中的有趣聯(lián)系，決定哪些事情將一起發(fā)

生。

?在數(shù)據(jù)挖掘中，關(guān)聯(lián)規(guī)則就是描述這種在一個事務(wù)中物品之間同時

出現(xiàn)的規(guī)律的知識模式。更確切地說，關(guān)聯(lián)規(guī)則通過量化的數(shù)字描

述物品甲的出現(xiàn)與物品乙的出現(xiàn)有多大的影響。

?在實(shí)際情況下，一種更有用的關(guān)聯(lián)規(guī)則是泛化關(guān)聯(lián)規(guī)則。

?關(guān)聯(lián)規(guī)則模式屬于描述模式，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的算法屬于無監(jiān)督學(xué)習(xí)

的方法。

6.3.1關(guān)聯(lián)規(guī)則的概念及分類任

?在事務(wù)數(shù)據(jù)庫中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則首先是由R.Agrawal等人提出的，其

形式化描述如下：

?定義6.2設(shè)1=042啟，…,im｝是由m個不同的數(shù)據(jù)項(xiàng)組成的集合，其

中的元素稱為項(xiàng)（item）,項(xiàng)的集合稱為項(xiàng)集，包含k個項(xiàng)的項(xiàng)集

稱為k項(xiàng)集。給定一個事務(wù)（交易）D,即交易數(shù)據(jù)庫，其中的每

一個事務(wù)（交易）T是數(shù)據(jù)項(xiàng)I的一個子集，即Td,T有一個唯一的

標(biāo)識符TID；當(dāng)且僅當(dāng)XqT時，稱交易T包含項(xiàng)集X；那么關(guān)聯(lián)規(guī)則

就形如“X=>Y”的蘊(yùn)含式；其中，Xcl,Ycl,XnY=0,即表示

滿足X中條件的記錄也一定滿足Y。關(guān)聯(lián)規(guī)則X=Y在交易數(shù)據(jù)庫中

成立，具有支持度s和具有置信度c。

6.3.1關(guān)聯(lián)規(guī)則的概念及分類任

?交易數(shù)據(jù)集D中具有支持度s,即D中至少有s%的事務(wù)包含XUY,

描述為：

support(X=>Y)=P(XUY)

?交易數(shù)據(jù)集D中具有置信度c,即D中包含X的事務(wù)至少有c%同時也

包含Y,描述為：

confidence(X=>Y)=P(Y|X)

?通常稱滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則

(strong)。

?一般將最小支持度記為m/csup,將最小置信度記為m/ccocf。

6.3.1關(guān)聯(lián)規(guī)則的概念及分類由

?在交易數(shù)據(jù)庫D中找出具有用戶給定的最小支持度和最小置信度的

關(guān)聯(lián)規(guī)則可以分解為兩個子問題：

1)找出存在于事務(wù)數(shù)據(jù)庫中所有大項(xiàng)集。If項(xiàng)集X的支持度support

(X)>minsupthenX稱為大項(xiàng)集(largeitemset),滿足最力、支持

度的項(xiàng)集也稱為頻繁項(xiàng)集(frequentitemset)o

2)利用大項(xiàng)集生成關(guān)聯(lián)規(guī)則，對每一大項(xiàng)集X,若YuX,Y=0,并且

support(Y)/support(X)>minconf0

6.3.1關(guān)聯(lián)規(guī)則的概念及分類”

?為了發(fā)現(xiàn)出有意義的關(guān)聯(lián)規(guī)則，必需給定兩個閾值，即最小支持度

和最小萬信度。

?最小支持度是用戶規(guī)定的關(guān)聯(lián)規(guī)則必需滿足的最小支持度，它表示

一組物品集在統(tǒng)計意義上的需滿足的最低程度，即衡量關(guān)聯(lián)規(guī)則在

整個數(shù)據(jù)集中的統(tǒng)計重要性。

?最小置信度是用戶規(guī)定的關(guān)聯(lián)規(guī)則必需滿足的最小可信度，它反映

了關(guān)聯(lián)規(guī)則的最低可靠度，即衡量關(guān)聯(lián)規(guī)則的可信程度。

?關(guān)聯(lián)分析可用于銷售配貨、商品陳列設(shè)計、產(chǎn)品目錄設(shè)計、產(chǎn)品定

價和促銷等，也可以使我們從客戶的購買模式中推知他們的嗜好。

6.3.1關(guān)聯(lián)規(guī)則的概念及分類#

?發(fā)現(xiàn)關(guān)聯(lián)規(guī)則通常要經(jīng)過以下三個步驟：

?D連接數(shù)據(jù)，作數(shù)據(jù)準(zhǔn)備；

?2）給定最小支持度和最小可信度，利用數(shù)據(jù)挖掘工具提供的算法

發(fā)現(xiàn)關(guān)聯(lián)規(guī)則；

?3）可視化顯示、理解、評估關(guān)聯(lián)規(guī)則。

6.3.1關(guān)聯(lián)規(guī)則的概念及分類'

?關(guān)聯(lián)規(guī)則的優(yōu)缺點(diǎn)：

?優(yōu)點(diǎn)：

@它可以產(chǎn)生清晰有用的結(jié)果；

@它支持間接數(shù)據(jù)挖掘；

@可以處理變長的數(shù)據(jù)；

@它的計算的消耗量是可以預(yù)見的。

?缺點(diǎn)：

@當(dāng)問題變大時，計算量增長得厲害;

@難以決定正確的數(shù)據(jù)；

@容易忽略離群數(shù)據(jù)。

6.3.1關(guān)聯(lián)規(guī)則的概念及分類

?(2)關(guān)聯(lián)規(guī)則的分類

表6.8關(guān)聯(lián)規(guī)則的分類

分類標(biāo)準(zhǔn)類別

規(guī)則中所處理的值布爾關(guān)聯(lián)規(guī)則與量化關(guān)聯(lián)規(guī)則

規(guī)則中所涉及的數(shù)據(jù)維單維關(guān)聯(lián)規(guī)則與多維關(guān)聯(lián)規(guī)則

規(guī)則中所涉及的抽象層單層關(guān)聯(lián)規(guī)則與多層關(guān)聯(lián)規(guī)則

規(guī)則中的擴(kuò)充最大的模式與頻繁閉項(xiàng)集

關(guān)聯(lián)特性分類分析與相關(guān)分析

6.3.2簡單形式的關(guān)聯(lián)規(guī)則算法

?簡單形式的關(guān)聯(lián)規(guī)則算法（單維、單層和布爾關(guān)聯(lián)規(guī)則）主要是經(jīng)

典頻集方法（基于Apriori的頻集方法）。

（1）簡單形式的關(guān)聯(lián)規(guī)則的核心算法

?是一個兩階段頻集思想的方法。

?關(guān)聯(lián)規(guī)則算法的設(shè)計可以分解為兩個子問題：

1）找到所有支持度大于最小支持度的項(xiàng)集，即頻集。由k個數(shù)據(jù)頻集

稱為k項(xiàng)頻集，找出所有的頻集由Apriori算法實(shí)現(xiàn)。

Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集都必須也是頻繁的。

6.3.2簡單形式的關(guān)聯(lián)規(guī)則算法

2)使用第1步找到的頻集產(chǎn)生期望的規(guī)則。

?為了生成所有頻集，使用遞推的方法：首先產(chǎn)生頻繁1項(xiàng)集然

后產(chǎn)生頻繁2項(xiàng)集l_2,直到有某個r值使得L,為空，這時算法停止。

?這里在k次循環(huán)中，過程先產(chǎn)生候選k項(xiàng)集的集合CQCk中的每一

個項(xiàng)集是對兩個只有一個項(xiàng)不同的屬于LRI的頻集做一個(k?2)連接

來產(chǎn)生的。Ck中的項(xiàng)集是用來產(chǎn)生頻集的候選集，最后的頻集Lk必

須是Ck的一個子集。Ck中的每個元素須在交易數(shù)據(jù)庫中進(jìn)行驗(yàn)證

來決定是否加入,這里的驗(yàn)證過程是算法性能的一個瓶頸。

2022年-2023年購斯

6.3.2簡單形式的關(guān)聯(lián)規(guī)則算法

?Apriori算法的核心思想

-large1-itemsets};〃發(fā)現(xiàn)1項(xiàng)頻集

for(k=2;Lk,1=0;k++)dobegin

Ck=apriori-gen(L^,minsup);〃根據(jù)k-1項(xiàng)頻集產(chǎn)生新

的k項(xiàng)候選集

foralltransactionstcD;//遍歷數(shù)據(jù)庫確定每個候選集

的支持頻度

Ct=subset(Ck，t);〃事務(wù)t中包含的候選集

forall蚓AdidatesceCtdo

c.count++;

Lk={ceCk|c.count>minsup}

6.3.2簡單形式的關(guān)聯(lián)規(guī)則算法

?apriori-gen函數(shù)以1_公1作為輸入?yún)?shù)，返回所有大k項(xiàng)集的集合!_匕

具體實(shí)現(xiàn)如下：

第一步：聯(lián)合，將兩個項(xiàng)連接在一起

Procedureapriori-gen(Lk^,minsup)

insertintoCk

selectp.item1,p.item2,...,p.item(k-1),q.item(k-1)

fromLk.iP，Lk」q

wherep.item1=qJtem1,...,p.item(k-2)=qjtem(k-2),p.item(k-

1)<q.item(k-1)

6.3.2簡單形式的關(guān)聯(lián)規(guī)則算法

?第二步，剪枝(pruning),如果存在c的(k-1)子序列不包含于L。

中，則刪除所有項(xiàng)集ceCk。

ForallitemsetsceCkdo

forall(k-1)subsetssofcdo

if(s.Lk”)then

deletefromCk

加22年-2023年購新

Apriori算法示例

DatabaseTDB{A}2

L1{A}2

{B}3

{B}3

{C}3

1stscan{C}3

{D}1

{E}3

{E}3

{A.B}1

{A-C)2

{A.E)1

{B.C)2

{B.E}3

{CE}2

3rdscan4

{B,C.E)

{B.C.E)2

6.3.2簡單形式的關(guān)聯(lián)規(guī)則算法

（2）頻集算法的幾種優(yōu)化方法

?1）基于劃分的方法

?2）基于hash的方法

?3）基于采樣的方法

?4）減少交易的個數(shù)

6.3.2簡單形式的關(guān)聯(lián)規(guī)則算法

(3)其他的頻集挖掘方法

?基于Apriori方法的缺陷及解決辦法

1)可能產(chǎn)生大量的候選集—FP-growth

2)無法對稀有信息進(jìn)行分析—挖掘高可信度的規(guī)則：計算特征、

生成候選集、過濾候選集

6.3.3多層和多維關(guān)聯(lián)規(guī)則的挖掘

（D多層關(guān)聯(lián)規(guī)則

?多層關(guān)聯(lián)規(guī)則的分類：根據(jù)規(guī)則中涉及的層次，多

層關(guān)聯(lián)規(guī)則可以分為同層關(guān)聯(lián)規(guī)則和層間關(guān)聯(lián)規(guī)

則。

?多層關(guān)聯(lián)規(guī)則的挖掘基本上可以沿用“支持度-可

信度”的框架。不過在支持度設(shè)置的問題上有一些

要考慮的問題。

?同層關(guān)聯(lián)規(guī)則可以采用兩種支持度策略：

D統(tǒng)一的最小支持度。對于不同的層次，都使用同

一個最小支持度。

2）遞減的最小支持度。每個層次都有不同的最小支

持度，較低層次的最小支持度相對較小。同時還可

以用上層挖掘得到的信息進(jìn)行一些過濾工作。

6.3.3多層和多維關(guān)聯(lián)規(guī)則的挖掘

（2）多維關(guān)聯(lián)規(guī)則

?根據(jù)是否允許同一個維重復(fù)出現(xiàn)，可以細(xì)分為維間的關(guān)聯(lián)規(guī)則（不

允許維重復(fù)出現(xiàn)）和混合維關(guān)聯(lián)規(guī)則（允許維在規(guī)則的左右同時出

現(xiàn)）。

?例：

年齡（X,”20…30”）U購買（X/筆記本電腦”尸。購買（X：打印機(jī)”）

6.3.3多層和多維關(guān)聯(lián)規(guī)則的挖掘

?在挖掘維間關(guān)聯(lián)規(guī)則和混合關(guān)聯(lián)規(guī)則的時候，還要考慮不同的字段

種類：種類型和數(shù)值型。

?對于種類型的字段，原先的算法都可以處理。

?對于數(shù)值型的字段可以采用以下幾種方法進(jìn)行處理：

D數(shù)值字段被分成一些預(yù)定義的層次結(jié)構(gòu)。這些區(qū)間都是用戶預(yù)先

定義的，得出的規(guī)則叫做靜態(tài)數(shù)量關(guān)聯(lián)規(guī)則。

2）數(shù)值字段根據(jù)數(shù)據(jù)的分布分成了一些布爾字段。每個布爾字段都

表示一個數(shù)值字段的區(qū)間，屬于其中則為1,反之為0。這種分法是

動態(tài)的，得出的規(guī)則叫做布爾數(shù)量關(guān)聯(lián)規(guī)則。

6.3.3多層和多維關(guān)聯(lián)規(guī)則的挖掘

3）數(shù)值字段被分成一些能體現(xiàn)它含義的區(qū)間。它考慮了數(shù)據(jù)之間的

距離的因素，得出的規(guī)則叫做基于距離的關(guān)聯(lián)規(guī)則。

4）直接用數(shù)值字段中的原始數(shù)據(jù)進(jìn)行分析。使用一些統(tǒng)計的方法對

數(shù)值字段的值進(jìn)行分析，并且結(jié)合多層關(guān)聯(lián)規(guī)則的概念，在多個層

次之間進(jìn)行比較從而得出一些有用的規(guī)則。得出的關(guān)聯(lián)規(guī)則叫做多

層數(shù)量關(guān)聯(lián)規(guī)則。

6.3.3多層和多維關(guān)聯(lián)規(guī)則的挖掘

（3）關(guān)聯(lián)規(guī)則價值衡量的方法

?系統(tǒng)客觀的層面和用戶主觀的層面。

?1）系統(tǒng)客觀層面（支持度、置信度、興趣度、收集強(qiáng)度）：使用

“支持度和信任度”框架可能會產(chǎn)生一些不正確的規(guī)則。只憑支持

度和信任度閾值未必總能找出符合實(shí)際的規(guī)則。

?2）用戶主觀層面：只有用戶才能決定規(guī)則的有效性、可行性。所

以，應(yīng)該將用戶的需求和系統(tǒng)更加緊密地結(jié)合起來。可以采用基于

約束的數(shù)據(jù)挖掘方法。具體約束的內(nèi)容有：數(shù)據(jù)約束、限定數(shù)據(jù)挖

掘的維和層次、規(guī)則約束。

6.3.4貨籃子分析存在的問題.

?(D即使沒有支持度度量統(tǒng)計重要性，我們一樣可以采用一種直

接量度來度量產(chǎn)品關(guān)聯(lián)的統(tǒng)計重要性。

?(2)如果只考慮銷售額，我們也可以定義一種金額支持度作為量

度，這樣的話，我們可以忽略那些銷售額相對較小的關(guān)聯(lián)關(guān)系，通

過這種方式，我們可以發(fā)現(xiàn)那些出現(xiàn)次數(shù)稀少，但是卻包含有大金

額的產(chǎn)品。

6.3.5關(guān)聯(lián)分析的其他算法?

(1)發(fā)現(xiàn)關(guān)聯(lián)分析的更好方法

?共同發(fā)生的概率與隨機(jī)期望的值不同時，表達(dá)式“如果顧客購買了

A,也可能購買B,X%的概率”的關(guān)聯(lián)才最有意義。

?相關(guān)性結(jié)構(gòu)著眼于事務(wù)數(shù)據(jù)中統(tǒng)計相關(guān)的數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)，即只

考慮同時發(fā)生的百分比與隨機(jī)發(fā)生的百分比有顯著不同的數(shù)據(jù)項(xiàng)。

例如：面包和牛奶；可口可樂與百事可樂

?［期望同時發(fā)生的概率-實(shí)際同時發(fā)生的概率］2/期望同時發(fā)生的概率

6.3.5關(guān)聯(lián)分析的其他算法

（2）統(tǒng)計相關(guān)以外的信息

1）量化相關(guān)性的一個方法就是考慮影響度，即實(shí)際或觀測到的共同

發(fā)生的概率被期望同時發(fā)生的概率相除的比率。

影響度=實(shí)際同時發(fā)生的概率/期望同時發(fā)生的概率

?如果產(chǎn)品相互獨(dú)立，影響度近似為1,如果產(chǎn)品相關(guān)，則不為0。

?例：

影響度（可口可樂+百事可樂）=0.01/25=0.0004,影響程度明顯不為0,

表示產(chǎn)品非常相關(guān)。

影響度（面包+牛奶）=12.1/12=1.008,影響度十分接近1,表明產(chǎn)品相

互獨(dú)立。

6.3.5關(guān)聯(lián)分析的其他算法

?2）較為直觀的計量是事件A對事件B的lift值。

Lift（事件A對事件B）=（實(shí)際A,B同時出現(xiàn)的概率一期望A,B同時出現(xiàn)的

概率）/A出現(xiàn)的概率

?Lift是卜1,1］區(qū)間內(nèi)的數(shù)值，當(dāng)事件相互獨(dú)立時接近于0,事件正相關(guān)

時值為正（彼此吸引），負(fù)相關(guān)時值為負(fù)（相互排斥）。

?例：

?Lift（可口可樂對百事可樂尸0.001-0.25/0.50=。498

?這一負(fù)值意味著兩種產(chǎn)品相互排斥。

6.3.5關(guān)聯(lián)分析的其他算法

(3)理解關(guān)聯(lián)

?為了采取更為精確的營銷活動，應(yīng)該找出為什么一些產(chǎn)品同時出現(xiàn)

的概率比隨機(jī)發(fā)生的更大(或更小)。

?混合購買傾斜法

例如：

?橙汁和蘇打水/全麥面包和土豆片

?可口可樂和百事可樂/人口統(tǒng)計信息

?嬰兒食品/補(bǔ)鈣食品

6.3.5關(guān)聯(lián)分析的其他算法…

(4)有效可行的市場籃子分析

?1)考慮“如果顧客購買產(chǎn)品A,則有X%的可能購買產(chǎn)品B”必須謹(jǐn)

慎。應(yīng)將搜索限制在那些不同于隨機(jī)發(fā)生的關(guān)聯(lián)上，因?yàn)檫@些關(guān)聯(lián)

最有可能導(dǎo)致可行的營銷決策。

?2)不能魯莽地舍去支持度較低的關(guān)聯(lián)。

?3)一旦發(fā)現(xiàn)有顯著非隨機(jī)關(guān)聯(lián)的產(chǎn)品集合，必須進(jìn)一步分析是什

么導(dǎo)致非隨機(jī)關(guān)聯(lián)。

加22年-2023年購新

6.3.6挖掘序列模式

(1)序列模式的概念及定義

?序列模式定義：給定一個由不同序列組成的集合，其中，每個序列

由不同的元素按順序有序排列，每個元素由不同項(xiàng)目組成，同時給

定一個用戶指定的最小支持度閾值。

?序列模式挖掘就是找出所有的頻繁子序列，即該子序列在序列集中

的出現(xiàn)頻率不低于用戶指定的最小支持度閾值。

?序列模式的元素也可以不只是一個元素，它也可以是一個項(xiàng)集。

?內(nèi)部元素不分排列順序。

加22年-2023年購新

6.3.6挖掘序列模式

?假定項(xiàng)集中的項(xiàng)由一些連續(xù)整數(shù)代替，即項(xiàng)集

/=0也…Jm},/；.（14j《m）是一個項(xiàng)。

?序列s記為s=（s]S2…s',其中Sj（1<j<n）代表的是

一個項(xiàng)集（也稱序列s的元素）。

?兩個序列"包田2,…鳳）和b=（bi，b2,如果存

在整數(shù)由2〈,…,V]且包含于匕1,外包含于如,?…

an包含于bin,即a2cbi2,ancbin,則

稱序列a包含于序列b,也稱序列a為序列b的子序列，

又稱序列b包含序列a,記為aqb。

?在一個序列集中如果序列s不包含于任何其他序列中,

則序列s為最大的（maximal）。

加22年-2023年購新

6.3.6挖掘序列模式

?序列是不同項(xiàng)目集的有序排列，序列S可以表示為S

=佝后2…s)Sj(1<j<n)為項(xiàng)目集，也稱為序列s

的元素(element)。序列的元素可以表示為

(x1x2...xm),xk(1<k<m)為不同的項(xiàng)目。

?如果一個序列只有一個項(xiàng)目，則括號可以省略。

?一個序列包含的所有項(xiàng)目的個數(shù)稱為序列的長度。

長度為/的序列記為/-序列。

?序列a在序列數(shù)據(jù)庫S中的支持?jǐn)?shù)為序列數(shù)據(jù)庫S中

包含a序列的序列個數(shù)，記為Support(a),給定支持

度閾值》如果序列a在序列數(shù)據(jù)庫中的支持?jǐn)?shù)不低

于3則稱序列a為序列模式。

加22年-2023年購新

6.3.6挖掘序列模式

?例6.6：設(shè)序列數(shù)據(jù)庫如下所示，并設(shè)用戶指定的最小支持度min-

support=2o

Sequence_idSequence

10<a(abc)(ac)d(cf)>

20<(ad)c(bc)(ae)>

30<(ef)(ab)(df)cb>

40<eg(af)cbc>

序列va(bc)df＞是序列va(abc)(ac)d(cf)＞的子序列

■序列v(ab)c＞是長度為3的序列模式

加22年-2023年購新

6.3.6挖掘序列模式

?問題描述：給定序列數(shù)據(jù)庫和最小支持度閾值，序列模式挖掘就是

要找出序列數(shù)據(jù)庫中所有的序列模式。

?系統(tǒng)規(guī)定：由于同一個元素中的項(xiàng)目之間排列沒有順序，為了表達(dá)

的唯一性，我們將同一個元素內(nèi)部的不同項(xiàng)目按照字典順序排列。

?一個客戶所有的事務(wù)可以綜合地看成是一個序列，每一個事務(wù)都由

相應(yīng)的一個項(xiàng)集來表示。事務(wù)按交易時間排列就成了一個序列。我

彳門稱這樣的序列%為方序利(customersequence)。通常講一個

客戶的交易按交易時間排序成T「T2,…,Tn。］中的項(xiàng)集定義成

itemset(T)。這樣，這個客戶的客戶序列就成了這樣的一個序列：<

itemsetjTJ,itemset(T2),...,itemset(Tn)>o

加22年-2023年購新

6.3.6挖掘序列模式

?如果一個序列S包含于一個客戶序列中，則我們稱該客戶支持

(support)序歹Us。

?一個具體序列的支持(support)定義為那一部分支持該序列的客戶

總數(shù)。

?給定一個客戶交易組成的數(shù)據(jù)庫D,挖掘序列模式的問題就是在那

些具有客戶指定最小支持度(minimumsupport)的序列中找出最

大序列。而每個這樣的最大序列就代表了一個序列模式(sequence

pattern)。

加22年-2023年購新

6.3.6挖掘序列模式

?實(shí)現(xiàn)算法可以分五個具體階段來找出所有的序列模式，分別是排序

階段、大項(xiàng)集階段、轉(zhuǎn)換階段、序列階段以及最大值階段。

?序列模式分析規(guī)則挖掘的重點(diǎn)在于分析數(shù)據(jù)間的前后（因果）關(guān)系,

可以發(fā)現(xiàn)客戶潛在的購物模式，規(guī)則是“先購買了商品X的顧客后

購買產(chǎn)品Y”，置信度和支持度由決策者輸入。

?序列模式挖掘是基于時間或者其他序列的經(jīng)常發(fā)生的模式。

?應(yīng)用領(lǐng)域：客戶購買行為模式預(yù)測、Web訪問模式預(yù)測、疾病診斷、

自然災(zāi)害診斷、DNA序列分析。

加22年-2023年購新

6.3.6挖掘序列模式

?序列模式挖掘的很多參數(shù)對挖掘的結(jié)果有很大影響。

1）時間序列T的持續(xù)時間，即這個時間序列的有效時間或者是用戶選

擇的一個時間段。

2）時間折疊窗口M在一段時間內(nèi)發(fā)生的幾件事件可以被看作是同

時發(fā)生的。

3）時間間隔力f,這個參數(shù)表示發(fā)現(xiàn)的模式的時間間隔。

?int=0

?min_inerval<int<max_interval

?int=c

卬即發(fā)審

6.3.6挖掘序列模式2023-3023

(2)序列模式挖掘的主要算法

GSP算法：類似于Apriori算法。

Prefixspan算法：采用分而治之的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個

更小的投影數(shù)據(jù)庫，然后在各個投影數(shù)據(jù)庫上進(jìn)行序列模式挖掘。

加22年-2023年購新

6.3.6挖掘序列模式

?上述算法存在的主要問題：

@缺少時間限制：用戶可能需要指定序列模式的相

鄰元素之間的時間間隔。例如，一個序列模式可

能會發(fā)現(xiàn)客戶在購買了物品A后的第三年購買物

品B。我們需要的卻是給定時間間隔內(nèi)用戶的購

買意向。

?事務(wù)的定義過于嚴(yán)格：一個事務(wù)中包含在客戶的

一次購買行為中所購買的所有物品?？赡苄枰?/p>

定一個滑動時間窗口，客戶在滑動時間窗口的時

間段內(nèi)的所有的購買行為均作為一個事務(wù)。

?缺少分類層次：只能在項(xiàng)目的原始級別上進(jìn)行挖

加22年-2023年購新

6.3.6挖掘序列模式

(2)序列模式挖掘的主要算法

1)GSP算法

①掃描序列數(shù)據(jù)庫，得到長度為I的序列模式I，作為初始的種子集。

②掃描長度為i的種子集L1,通過連接操作和剪切操作生成長度為i+1

的候選序列模式G+1；然后掃描序列數(shù)據(jù)庫，計算每個候選序列模

式的支持?jǐn)?shù)，產(chǎn)生長度為i+1的序列模式Li,并將Lj+1作為新的種

子集。

③重復(fù)第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止。

=>C2nL2=>C3nL3nC4nL4n

2儂卬-3023年”就

6.3.6挖掘序列模式

?產(chǎn)生候選序列模式主要分為兩步：

?連接階段：如果去掉序列模式S1的第一個項(xiàng)目與去掉序列模式S2的

最后一個項(xiàng)目所得到的序列相同，則可以將Si與S2進(jìn)行連接，即將

S2的最后一個項(xiàng)目添加到中。

?剪切階段：若某候選序列模式的某個子序列不是序列模式，則此候

選序列模式不可能是序列模式，將它從候選序列模式中刪除。

加22年-2023年購新

6.3.6挖掘序列模式

?例：下圖演示了如何從長度為3的序列模式產(chǎn)生長度為4的候選序列

模式。

SequentialpatternsCandidate4-Sequences

Withlength3AfterJoinAfterPinning

3><(1,2)(3,4)><(U)(3,4)>

<(1,2)4><(1,2)35)

<1(3,4)>

<(13)5>

<2(3,4)>

<235>

加22年-2023年購新

6.3.6挖掘序列模式

?候選序列模式的支持度計算：對于給定的候選序列模式集合C,掃

描序列數(shù)據(jù)庫，對于其中的每一條序列d,找出集合C中被d所包含

的所有候選序列模式，并增加其支持度計數(shù)。

?GSP算法存在的主要問題：

?D如果序列數(shù)據(jù)庫的規(guī)模較大，則有可能會產(chǎn)生大量的候選序列

模式；

?2）需要對序列數(shù)據(jù)庫進(jìn)行循環(huán)掃描；

?3）對于序列模式的長度比較長的情況，由于其對應(yīng)的短的序列模

式規(guī)模太大，本算法很難處理。

加22年-2023年購新

6.3.6挖掘序列模式

2)PrefixSpan算法(基于前綴投影的序列模式挖

掘算法)

?相關(guān)定義如下：」，，

①前善設(shè)每個元素中就躇項(xiàng)鼠安照字典序排列。

一款定劇壇電佛且也岫：畫項(xiàng)目崢品中項(xiàng)目的后面

(m<n),如果

則稱P是a的前綴。

2022年-2O23WJft#i

6.3.6挖掘序列模式

②投影。給定序列a和再如果