【正文】 后，我們?cè)噲D產(chǎn)生 C5，這時(shí)的結(jié)果為空。第三次遍歷后， apriorigenerate 函數(shù)以 L2作為輸入?yún)?shù)來產(chǎn)生 C3。同時(shí)我們也刪除在前推階段找到的那些非最大 (nonmaximal)的大序列。但是，在第 k 次遍歷的時(shí)候，我們可能沒有 Lk1，因?yàn)槲覀儧]有計(jì)算過 (k1)候選序列。這種情形下， AprioriSome 算法就退化為AprioriAll 算法了。 elsif (hitk ) return k + 4。如附圖 。 k ) do if (Lk not found in forward phase) then begin Delete all sequences in Ck contained in Some Li, i k。 else Ck = New candidates generated from Ck1。 // so that we have a nice loop condition last = 1。 L1 L2 L4 L3 圖 1Sequences Support 1 4 2 2 3 4 4 4 5 4 2Sequences Support 1 2 2 1 3 4 1 4 3 1 5 3 2 3 2 2 4 2 3 4 3 3 5 2 4 5 2 3Sequences Support 1 2 3 2 1 2 4 2 1 3 4 3 1 3 5 2 2 3 4 2 4Sequences Support 1 2 3 4 2 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 15 第五次遍歷沒有產(chǎn)生候選，最大序列是以下三個(gè)： 1 2 3 4,1 3 5和 4 5。客戶序列已經(jīng)以轉(zhuǎn)換的形式出現(xiàn)了，每一條交易都被包含其中的大項(xiàng)集取代，大項(xiàng)集則由整數(shù)代替。 附圖 函數(shù) Large 3Sequence Candidate 4Sequence (after join) Candidate 4Sequence (after pruning) 1 2 3 1 2 4 1 3 4 1 3 5 2 3 4 1 2 3 4 1 2 4 3 1 3 4 5 1 3 5 4 1 2 3 4 圖 選序列的產(chǎn)生 在圖 ，考察第一列中顯示的 L3(the set of 3sequence)。在第一次遍歷時(shí)，大項(xiàng)集階段的輸出被用來初始化大 1序列的集合。 圖 算法 注 ：所有算法表示中， Lk代表所有 k序列組成的集合， Ck 代表候選 k序列組成的集合。 ? AprioriAll 算法 L1 = {large 1sequences}。 countall 累計(jì)所有大序 列，包括非最大序 列 (nonmaximal sequence)，在找最大階段 (maximal phase)，這些非最大序列必須被刪除。在每次遍歷中，我們從一個(gè)由大序列 (large sequence)組成的種子集 (seed set)開始，利用這個(gè)種子集 ，可以產(chǎn)生新的潛在的大序列。在序列階段找到所有的大序列之后，下述算法可以用來找出最大序列。比如，在對(duì) ID 號(hào)為 2 的客戶序列進(jìn)行轉(zhuǎn)換的時(shí)候，交易（ 10，20）被剔除了，因?yàn)樗]有包含任何大項(xiàng)集；交易（ 40， 60， 70）則被大項(xiàng)集的集合{（ 40），（ 70），（ 40， 70） }代替。但是，在計(jì)算客戶總數(shù)的時(shí)候，它仍將被計(jì)算在內(nèi)。為了使這個(gè)過程盡量的快，我們用另一種形式來替換每一個(gè)客戶序列。在圖 ，大項(xiàng)集分別是 (30)， (40)，(70)， (40， 70)和 (90)。 2) 大項(xiàng)集階段 (Litemset Phase) 在這個(gè)階段我們找出所有大項(xiàng)集組成的集合 L。 注意 ：大序列中的每一個(gè)項(xiàng)集都必須具有最小支持。 有兩個(gè)序列 x和 y， x?y 表示 x和 y 經(jīng)過連接運(yùn)算形成的新的序列。最后我們得到圖 _3 的結(jié)果。序列模式 (30) (40,70) 被客戶 2 和客戶 4 所支持。圖 _2 則以客戶序列集的形式表示了該數(shù)據(jù)庫(kù)。一個(gè)具體序列的 支持 (support)定義為那一部分 支持 該序列的客戶總數(shù)。 Ti中的項(xiàng)集定義成 itemset(Ti)。 一個(gè)客戶所有的 事務(wù) (transactions)可以綜合的看成是一個(gè)序列，每一個(gè)事務(wù)都由相應(yīng)的一個(gè)項(xiàng)集來表示。比如 序列 (3) (4,5) (8) 包含于序列 (7) (3,8) (9) (4,5,6) (8) ，因?yàn)?(3)包含于 (3,8)， (4,5)包含于 (4,5,6)以及 (8)包含于 (8)。 (1) 項(xiàng)集 (itemset)是由 項(xiàng) (item)組成的一個(gè)非空集合。值得數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 9 注意的是租借這三部電影的行為并不一定需要是連續(xù)的。在剪枝階段 {1 3 4 5}將被刪除，因?yàn)樗囊粋€(gè)子集 {1 4 5}不在 L3之中。 圖 算法 apriorigen 函數(shù)以 Lk1(所有大 (k1)項(xiàng)集 )作為輸入?yún)?shù)，返回所有大 k項(xiàng)集的集合Lk，以以下兩步實(shí)現(xiàn)： 第一步，聯(lián)合 insert into Ck select , ,… , from Lk1p,Lk1q where = ,… , = , 。 k++) do begin Ck = apriorigen ( Lk1)。 這里我們討論 (1)中的 Apriori 算法，因?yàn)楦鶕?jù)此算法得到的大項(xiàng)集，在序列模式階段是有實(shí)際用處的。用戶在購(gòu)買物品時(shí)，除了具有上述關(guān)聯(lián)規(guī)律，還有時(shí)間上或序列上的規(guī)律，因?yàn)?，很多時(shí)候顧客會(huì)這次買這些東西，下次買同上次有關(guān)的一些東西，接著又買有關(guān)的某些東西。例如 ”買外套 → 買鞋子 (此處，外套和鞋子是較高層次上的物品或概念，因而該規(guī)則是一種泛化的關(guān)聯(lián)規(guī)則 )。后者即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須 滿足的最小可信度，它反應(yīng)了關(guān)聯(lián)規(guī)則的最低可靠度。事實(shí)上，人們一般只對(duì)滿足一定的支持度和可信度的關(guān)聯(lián)規(guī)則感興趣。 (1) 稱物品集 X 具有大小為 s 的支持度，如果 D 中有 s%的事務(wù)支持物品集 X。 b.) 關(guān)聯(lián)規(guī)則的形式 設(shè) I = {i1， i2， ...， im}是一組物品集 (一個(gè)商場(chǎng)的物品可能有上萬種 )， D是一組事務(wù)集 (稱數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 7 之為事務(wù)數(shù)據(jù)庫(kù) )。這些投保人的個(gè)人信息就可以看作事務(wù)中的物品。 有些數(shù)據(jù)不像售貨數(shù)據(jù)那樣很容易就能看出一個(gè)事務(wù)是許多物品的集合，但稍微轉(zhuǎn)換一下思考角度，仍然可以像售貨數(shù)據(jù)一樣處理。 現(xiàn)實(shí)中，這樣的例子很多。同一個(gè)顧客在一個(gè)交易時(shí)間只能進(jìn)行一次交易 (這是顯而易見的 )，我們不去考慮顧客在一次交易中所購(gòu)買物品的數(shù)量，每種物品 (也就是商品 )都由一個(gè)二進(jìn)制變量代替，而不管它是否在交易中被購(gòu)買與否 。因此 ,如果對(duì)這些歷史事務(wù)數(shù)據(jù)進(jìn)行分析 ,則可對(duì)顧客的購(gòu)買行為提供極有價(jià)值的信息。條形碼 (barcode)技術(shù)的進(jìn)步使得零售商有能力收集和儲(chǔ)存大量的銷售數(shù)據(jù)，稱為 貨籃(basket)數(shù)據(jù)。以下的討論 將針對(duì)序列模式，而關(guān)聯(lián)規(guī)則在此過程中將會(huì)得到闡述。聚類模式、關(guān)聯(lián)模式、序列模式則是非監(jiān)督知識(shí)，因?yàn)樵谀Ｊ浇⑶敖Y(jié)果是未知的，模式的產(chǎn)生不受任何監(jiān)督。 在解決實(shí)際問題時(shí)，經(jīng)常要同時(shí)使用多種模式。關(guān)聯(lián)規(guī)則是如下形式的一種規(guī)則：“在無力償還貸款的人當(dāng)中， 60％的人的月收入在 3000 元以下。 4. 聚類模式 聚類模式把數(shù)據(jù)劃分到不同的組中，組之間的差別盡可能大，組內(nèi)的差別盡可能小。如給出某種動(dòng)物的特征，可 以用分類模式判定這種動(dòng)物是哺乳動(dòng)物還是鳥類；給出某個(gè)人的教育情況、工作經(jīng)驗(yàn)，可以用回歸模式判定這個(gè)人的年工資在哪個(gè)范圍內(nèi)，是在 6000 元以下，還是在 6000 元到 1 萬元之間，還是在 1 萬元以上。例如，在地球上， 70％的表面被水覆蓋， 30％是土地。例如，根據(jù)各種動(dòng)物的資料，可以建立這樣的模式：凡是胎生的動(dòng)物都是哺乳類動(dòng)物。例如，“如果成績(jī)?cè)?81～ 90 之間，則成績(jī)優(yōu)良”可稱為一個(gè)模式，而“如果成 績(jī)?yōu)?8 8 8 8 8 8 8 889 或 90，則成績(jī)優(yōu)良”就不能稱之為一個(gè)模式。一般在科研領(lǐng)域中稱為 KDD，而在工程領(lǐng)域則稱為 數(shù)據(jù)挖掘 。 數(shù)據(jù)挖掘是 KDD 最核心的部分，是采用機(jī)器學(xué)習(xí)、統(tǒng)計(jì)等方法進(jìn)行知識(shí)學(xué)習(xí)的階段。 1989年 8月在美國(guó)底特律召開的第 11 屆國(guó)際人工智能聯(lián)合會(huì)議的專題討論會(huì)上首次出現(xiàn) KDD 這 個(gè)術(shù)語。機(jī)器學(xué)習(xí)是用計(jì)算機(jī)模擬人類學(xué)習(xí)的一門科學(xué)，比較成熟的算法有神經(jīng)網(wǎng)絡(luò)、遺傳算法等。目前的數(shù)據(jù)庫(kù)系統(tǒng)可以高效地實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計(jì)等功能，但無法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測(cè)未來的發(fā)展趨勢(shì)。通過對(duì)這些數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘我們可以找到對(duì)于商業(yè)銷售及生產(chǎn)極為有效的一些信息 (這些信息通過具體的模式得到反映 )，從而可以提高銷售和生產(chǎn)效率，降低成本，取得最大的 商業(yè)效益，這就是數(shù)據(jù)挖掘的意義所在。應(yīng)用條形碼技術(shù)采集的大量銷售數(shù)據(jù)成為挖掘的基礎(chǔ)。激增的數(shù)據(jù)背后隱藏著許多重要的信息，人 們希望能夠?qū)ζ溥M(jìn)行更高層次的分析，以便更好地利用這些數(shù)據(jù)。經(jīng)歷了博弈時(shí)期、自然語言理解、知識(shí)工程等階段，目前的研究熱點(diǎn)是機(jī)器學(xué)習(xí)。從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)出來的知識(shí)可以用在信息管理、過程控制、科學(xué)研究、決策支持等許多方面。 1998 年在美國(guó)紐約舉行的第四屆知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘國(guó)際學(xué)術(shù)會(huì)議不僅進(jìn)行了學(xué)術(shù)討論，并且有 30 多家軟件公司展示了他們的數(shù)據(jù)挖掘軟件產(chǎn)品，不少軟件已在北美、歐洲等國(guó)得到應(yīng)用。人們往往不嚴(yán)格區(qū)分?jǐn)?shù)據(jù)挖掘和數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)，把兩者混淆使用。 E 作為一個(gè)模式要求它比列舉數(shù)據(jù)子集 FE 中所有元素的描述方法簡(jiǎn)單 。挖掘預(yù)測(cè)型模式所使用的數(shù)據(jù)也都是可以明確知道結(jié)果的。描述型模式不能直接用于預(yù)測(cè)。 2. 回歸模式 回歸模式的函數(shù)定義與分類模式相似，它們的差別在于分類模式的預(yù)測(cè)值是離散的，回歸模式的預(yù)測(cè)值是連續(xù)的。只有充分考慮時(shí)間因素，利用現(xiàn)有數(shù)據(jù)隨時(shí)間變 化的一系列的值，才能更好地預(yù)測(cè)將來的值。 5. 關(guān)聯(lián)模式 關(guān)聯(lián)模式是數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)規(guī)則。例如，在購(gòu)買彩電的人們當(dāng)中，60％的人會(huì)在 3 個(gè)月內(nèi)購(gòu)買影碟機(jī)。一般在建立這些模式時(shí)，使用一部分?jǐn)?shù)據(jù)作為樣本，用另一部分?jǐn)?shù)據(jù) 來檢驗(yàn)、校正模式。 關(guān)聯(lián)規(guī)則是關(guān)聯(lián)模式的基礎(chǔ)，而 序列模式與關(guān)聯(lián)模式相仿，只是更進(jìn)一步把數(shù)據(jù)之間 的關(guān)聯(lián)性與時(shí)間聯(lián)系起來。 數(shù)據(jù)挖掘是由大多數(shù)大型零售商面臨的決策支持 (decision support)問題所促使產(chǎn)生的。 由于條形碼技術(shù)的發(fā)展 ,零售部門可以利用前端收款機(jī)收集存儲(chǔ)大量的售貨數(shù)據(jù)。 【論述與證明】 1) 數(shù)據(jù)源的形式 我們給定一個(gè)由 客戶交易 (customer transaction)組成的大型數(shù)據(jù)庫(kù)，每個(gè) 交易 (transaction)由 客戶號(hào) (customerid)， 交易時(shí)間 (transactiontime)以及在交易中購(gòu)買的 項(xiàng)