【文章內(nèi)容簡介】 一概念層次關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)發(fā)展到多概念層次的關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)，并把研究的重點放在提高算法的效率和規(guī)?？墒湛s性上。它廣泛地運用于幫助市場導(dǎo)向、商品目錄設(shè)計客戶關(guān)系管理（CRM ）和其他各種商業(yè)決策過程中。關(guān)聯(lián)（Associations）分析的目的是為了挖掘隱藏在數(shù)據(jù)間的相互關(guān)系，即對于給定的一組項目和一個記錄集，通過對記錄集的分析，得出項目集中的項目之間的相關(guān)性 [15]。項目之間的相關(guān)性用關(guān)聯(lián)規(guī)則來描述，關(guān)聯(lián)規(guī)則反映了一組數(shù)據(jù)項之間的密切程度或關(guān)系。為了使后文的闡述更容易理解，這里先引入幾個定義。定義 1 令 I={i1，i 2，…,i n}是項目集，D 是全體事務(wù)的集合。事務(wù) T 是 I 上的一個子集，集合 T 包含在 I 中，每個事務(wù)用唯一的標(biāo)志 TID 來標(biāo)識。關(guān)聯(lián)規(guī)則是形如 X =〉Y 的蘊含式，其中 X 真包含在 I 中，Y 真包含在 I 中，且 X 與Y 沒有非空交集，X 稱為規(guī)則的條件，Y 稱為規(guī)則的結(jié)果。定義 2 關(guān)聯(lián)規(guī)則 X =〉Y 對事務(wù)集 D 的支持度（support）定義為 D 中包含有事務(wù) X 和 Y 的百分比。關(guān)聯(lián)規(guī)則 X =〉Y 對事務(wù)集合 D 的置信度（confidence ）定義為 D 中包含有 X 的事務(wù)數(shù)與同時包含 Y 的百分比。即：support(X =Y)＝(包含 X 和 Y 的事務(wù)數(shù) / 事務(wù)總數(shù))100％confidence(X =Y)＝(包含 X 和 Y 的事務(wù)數(shù) / 包含 X 的事務(wù)數(shù))100％9 / 51定義 3 置信度和支持度均大于給定閾值（即最小置信度閾值和最小支持度閾值） 。即：support(X =Y) ≥ min_supconfidence(X =Y) ≥ min_conf 的關(guān)聯(lián)規(guī)則稱為強規(guī)則；否則稱為弱規(guī)則。在關(guān)聯(lián)規(guī)則分析中數(shù)據(jù)挖掘主要就是對強規(guī)則的挖掘。通過設(shè)置最小支持度和最小置信度可以了解某些數(shù)據(jù)之間的關(guān)聯(lián)程度。強規(guī)則 X =Y 對應(yīng)的項集必定是頻繁集。因此，可以把關(guān)聯(lián)規(guī)則挖掘劃分為以下兩個子問題：核心問題：根據(jù)最小支持度找出事務(wù)集 D 中的所有頻繁項集；較易解決的問題：根據(jù)頻繁項集和最小置信度產(chǎn)生關(guān)聯(lián)規(guī)則。在了解了有關(guān)關(guān)聯(lián)規(guī)則的幾個定義后，再來理解關(guān)聯(lián)規(guī)則挖掘就容易多了，所謂關(guān)聯(lián)規(guī)則挖掘就是指給定一組 Item 和記錄集合，挖掘出 Item 間的相關(guān)性，使其置信度和支持度分別大于用戶給定的最小置信度和、最小支持度 [16]。根據(jù)劃分標(biāo)準(zhǔn)的不同，關(guān)聯(lián)規(guī)則挖掘的可以有如下幾種分類：基于規(guī)則中處理的變量的類別基于規(guī)則中處理的變量的類別,關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。所謂布爾型關(guān)聯(lián)規(guī)則，就是指如果規(guī)則考慮的關(guān)聯(lián)是項“在”或“不在” ，則關(guān)聯(lián)規(guī)則是布爾型的。例如，由購物籃分析得出的關(guān)聯(lián)規(guī)則。所謂量化（數(shù)值）型關(guān)聯(lián)規(guī)則，指的是如果描述的是量化的項或?qū)傩灾g的關(guān)聯(lián)，則該規(guī)則是量化型的關(guān)聯(lián)規(guī)則?；谝?guī)則中數(shù)據(jù)的抽象層次基于規(guī)則中數(shù)據(jù)的抽象層次,可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。單層的關(guān)聯(lián)規(guī)則指得是所有的變量都不涉及不同抽象層次的項或?qū)傩?。多層的關(guān)聯(lián)規(guī)則指得是變量涉及不同抽象層次的項或?qū)傩浴；谝?guī)則中涉及到的數(shù)據(jù)的維數(shù)基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù),關(guān)聯(lián)規(guī)則可以分為單維的和多維的。單維關(guān)聯(lián)規(guī)則是指處理單個維中屬性間的關(guān)系，即在單維的關(guān)聯(lián)規(guī)則中，只涉及到數(shù)據(jù)的一個維。多維關(guān)聯(lián)規(guī)則是指處理多個維中屬性之間的關(guān)系，即在多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會涉及多個維。給出了關(guān)聯(lián)規(guī)則的分類之后，接下來就可以考慮某個具體的關(guān)聯(lián)規(guī)則挖掘算法適用于哪一類規(guī)則的挖掘，某類關(guān)聯(lián)規(guī)則又可以用哪些不同的方法進(jìn)行處理。最簡單的是單維、單層、布爾型的關(guān)聯(lián)規(guī)則。前文已經(jīng)指出關(guān)聯(lián)規(guī)則挖掘即給定一組 Item 和記錄集合，挖掘出 Item 間的相關(guān)性，使其置信度和支持度分別大于用戶給定的最小置信度和最小支持度。10 / 51具體而言，在關(guān)聯(lián)規(guī)則挖掘算法中，把項目的集合稱為項集（itemset） ，包含有k 個項目的項集稱為 k項集。包含項集的事務(wù)數(shù)稱為項集的出現(xiàn)頻率，簡稱為項集的頻率或支持度計數(shù)。如果項集的出現(xiàn)頻率大于或等于最小支持度 s 與 D中事務(wù)總數(shù)的乘積，則稱該項集滿足最小支持度 s。如果項集滿足最小支持度，則稱該項集為頻繁項集（frequent itemset ） 。關(guān)聯(lián)規(guī)則的挖掘主要被分解為下面兩步：找出所有的頻繁項集，即找出支持度大于或等于給定的最小支持度閾值的所有項集?？梢詮?1 到 k 遞歸查找 k頻繁項集。由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，即找出滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則。對給定的 L，如果其非空子集 A 真包含于 L，sup(L)為 L 的支持度，sup(A)為 A 的支持度，則產(chǎn)生形式為 A =〉LA 的規(guī)則。下面就根據(jù)實際應(yīng)用重點介紹一下關(guān)聯(lián)規(guī)則挖掘的 Apriori 算法。Apriori算法是一種最有影響的挖掘布爾型關(guān)聯(lián)規(guī)則頻繁項集的算法。它的各種變形，用于提高算法的效率和可伸縮性。在說明 Apriori 算法之前，有必要先介紹一下頻繁項集的性質(zhì)，即 Apriori性質(zhì)：頻繁項集的所有非空子集都必須是頻繁的。Apriori 性質(zhì)基于如下事實：根據(jù)定義，如果項集 I 不滿足最小支持度閾值 min_sup，則 I 不是頻繁的，即sup（I） min_sup。如果將項 A 添加到 I， 則結(jié)果項集（即 I∪A）不可能比 I更頻繁出現(xiàn)。因此，I∪A 也不是頻繁的，即 sup（I∪A ） min_sup。頻繁項集的 Apriori 性質(zhì)用于壓縮搜索空間（剪枝） ，以提高逐層產(chǎn)生頻繁項集的效率。Apriori 算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。它使用一種稱作逐層搜索的迭代算法，k項集用于探索（k+1）項集。其基本思想是：通過掃描數(shù)據(jù)集，產(chǎn)生一個大的候選數(shù)據(jù)項集,并計算每個候選數(shù)據(jù)項發(fā)生的次數(shù)，然后基于預(yù)先給定的最小支持度生成頻繁 1項集的集合，該集合記作 L1；基于 L1 和數(shù)據(jù)集中的數(shù)據(jù)，產(chǎn)生頻繁 2項集 L2；用同樣的方法，直到生成頻繁 n項集 Ln，其中已不再可能生成滿足最小支持度的（n+1）－項集；從頻繁項集中導(dǎo)出規(guī)則。進(jìn)一步分析，我們可以看從中看出 Apriori 算法中的關(guān)鍵步驟是由 Lk1 找Lk，該步驟又可分為兩步：連接為找 Lk，通過 Lk1 與自己連接產(chǎn)生候選 K項集的集合。將該候選項集的集11 / 51合記作 Ck。設(shè) l1 和 l2 是 Lk1 中的項集，記號 li [j]表示 li 的第 j 項。執(zhí)行連接 Lk1和 Lk1，其中 Lk1 的元素是可連接，如果它們前（k2）個項相同而且第（k2）項不同（為簡單計，設(shè) l1[k1]l2[k1]） ，即：l1[1]= l2[1]∧ l 1[2]=l2[2]∧……∧l 1[k2]=l2[k2] ∧l 1[k1]l2[k1]則 Lk1 的元素 l1 和 l2 是可連接的。連接 l1 和 l2 產(chǎn)生的結(jié)果的項集是 l1[1]l1[2]……l1[k1]l2[k1]。剪枝Ck 是 Lk 的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁 k項集都包含在 Ck 中。掃描數(shù)據(jù)庫，確定 Ck 中每個候選的計數(shù)，從而確定 Lk。然而，C k 可能很大，這樣所涉及的計算量就很大。為壓縮 Ck，可以用以下辦法使用 Apriori 性質(zhì)：任何非頻繁的（k1） 項集都不可能是頻繁 k項集的子集。因此，如果一個候選 k項集的（k1）子集不在 Lk1 中，則該候選也不可能是頻繁的，從而可以由 Ck 中刪除。在實際運用中有一點需要注意， 那就是 Apriori 的候選產(chǎn)生檢查方法大幅度壓縮了候選項集的大小，并導(dǎo)致很好的性能。然而，它有兩種開銷可能并非微不足道的。首先，它可能產(chǎn)生大量候選項集。例如，如果有 104 個頻繁 1－項集，則需要產(chǎn)生 107 個頻繁 2－項集,并累計和檢查其頻繁性；為發(fā)現(xiàn)長度為100 的頻繁模式{a 1,a2,…,a100}，則需產(chǎn)生多達(dá)約 1030 個候選。其次，它可能需要重復(fù)的掃描數(shù)據(jù)庫，通過模式匹配檢查一個很大的候選集合。為了提高Apriori 算法的效率，已經(jīng)提出了許多 Apriori 算法的變形，這里囿于篇幅就不再進(jìn)一步展開了。 聚類分析數(shù)據(jù)挖掘方法聚類（clustering）是將物理或抽象對象的集合分組成為多個類或簇（cluster）的過程，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。相異度是根據(jù)描述對象的屬性值來計算的。距離是經(jīng)常采用的度量方式。在許多應(yīng)用場合，可以將一個蔟中的對象作為一個整體來對待 [17]。聚類與分類不同的是，它要劃分的類是未知的。即聚類是一種無指導(dǎo)學(xué)習(xí)，它不依賴預(yù)先定義的類和帶類標(biāo)號的訓(xùn)練實例。由于這個原因，聚類是觀察式學(xué)習(xí)，而不是示例式學(xué)習(xí)。聚類分析已經(jīng)廣泛的用在許多應(yīng)用中，包括模式識別、數(shù)據(jù)分析、圖象處理以及市場研究。通過聚類，人能夠識別密集的和稀疏的區(qū)域，因而發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的有趣的相互關(guān)系。以下是聚類分析的幾種典型應(yīng)用。12 / 51商業(yè)幫助市場分析人員從客戶基本庫中發(fā)現(xiàn)不同的客戶群，并且用不同的購買模式描述不同客戶群的特征。生物學(xué)推導(dǎo)植物或動物的分類，對基于進(jìn)行分類，獲得對種群中固有結(jié)構(gòu)的認(rèn)識。WEB 文檔分類通過對客戶瀏覽行為進(jìn)行分類，獲得不同客戶群體的各自的瀏覽特征。其他如地球觀測數(shù)據(jù)庫中相似地區(qū)的確定；各類保險投保人的分組；一個城市中不同類型、價值、地理位置房子的分組等。作為其他數(shù)據(jù)挖掘算法的預(yù)處理即先進(jìn)行聚類，然后再進(jìn)行分類等其他的數(shù)據(jù)挖掘。聚類分析是一種數(shù)據(jù)簡化技術(shù)，它把基于相似數(shù)據(jù)特征的變量或個案組合在一起。聚類分析源于許多研究領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計學(xué)、生物學(xué)以及機器學(xué)習(xí)。作為統(tǒng)計學(xué)的一個分支，聚類分析已經(jīng)被廣泛的研究了許多年，主要集中在基于距離的聚類分析。基于 Kmeans（K平均值） 、Kmedoids（K中心點）和其他一些方法的聚類分析工具已經(jīng)被加入到許多統(tǒng)計分析包或系統(tǒng)中。在數(shù)據(jù)挖掘領(lǐng)域，關(guān)于聚類分析的研究工作主要集中在為大型數(shù)據(jù)庫尋找適當(dāng)和有效的聚類分析方法?；钴S的研究主題集中在聚類方法的可伸縮性、方法對聚類復(fù)雜形狀和類型的數(shù)據(jù)的有效性、高維聚類分析技術(shù)以及針對大型數(shù)據(jù)庫中混合數(shù)值和分類數(shù)據(jù)的聚類方法。目前存在很多聚類算法。算法的選擇取決于數(shù)據(jù)的類型、聚類的目的和應(yīng)用。如果聚類分析被用做描述或探察的工具，可以對同樣的數(shù)據(jù)嘗試多種算法，以發(fā)現(xiàn)數(shù)據(jù)可能揭示的結(jié)果。主要的聚類分析方法有：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法。下面著重介紹一下基于劃分的方法。劃分方法（partitioning method）的基本思想是對于給定一個 n 個對象或元組的數(shù)據(jù)庫，用一個劃分方法構(gòu)建數(shù)據(jù)的 k 個劃分，每個劃分表示一個聚簇，并且 kn。也就是說，它將數(shù)據(jù)劃分成為 k 個組，同時滿足如下要求：每個組至少包括一個對象；每個對象必須屬于且只屬于一個組。為了達(dá)到全局最優(yōu)，基于劃分的聚類會要求窮舉所有可能的劃分。實際上，絕大多數(shù)應(yīng)用采用了以下兩個比較流行的啟發(fā)式方式：13 / 51K 平均算法。在該算法當(dāng)中，每個簇用該簇中對象的平均值來表示。K 中心點算法。在該算法中每個簇用接近聚類中心的一個對象來表示。K平均算法基于質(zhì)心的技術(shù)，即以 k 為參數(shù)，把 n 個對象分為 k 個簇，以使簇內(nèi)具有較高的相似度，而簇間的相似度較低。相似度的計算根據(jù)一個簇中對象的平均值來進(jìn)行。K平均算法的處理流程如下：首先隨機地選擇 k 個對象，每個對象初始地代表了一個簇的平均值或中心。對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇。然后重新計算每個簇的平均值。這個過程要不斷的重復(fù)，直到準(zhǔn)則函數(shù)收斂。也就是說，每個簇都不會再發(fā)生變化。這時認(rèn)為本算法可以結(jié)束了。這個算法嘗試找出使平方誤差函數(shù)值最小的 k 個劃分。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時，它的效果較好。對處理大數(shù)據(jù)集，該算法是相對可伸縮的和高效率的，因為它的復(fù)雜度是 O（nkt） ，其中，n 是所有對象的數(shù)目，k 是簇的數(shù)目，t 是迭代的次數(shù)。通常，kn，這個算法經(jīng)常以局部最優(yōu)結(jié)束。在本小節(jié)最后，給出一個關(guān)于 K平均算法的具體流程描述。算法：K平均。劃分的 K平均算法基于簇中對象的平均值輸入：簇的數(shù)目 K 和包含 n 個對象的數(shù)據(jù)庫輸出：K 個簇，使平方誤差準(zhǔn)則最小方法：任意選擇 K 個對象作為初始的簇中心；REPEAT根據(jù)簇中對象的平均值，將每個對象（重新）賦給最類似的簇；更新簇的平均值，即計算每個簇中對象的平均值； UNTIL 不再發(fā)生變化。 時序規(guī)則數(shù)據(jù)挖掘方法在介紹時序數(shù)據(jù)挖掘的具體方法之前，有必要先引入時序數(shù)據(jù)庫與序列數(shù)據(jù)庫的相關(guān)概念。時序（timeseries）數(shù)據(jù)庫就是由隨時間變化的序列值或事件組成的數(shù)據(jù)庫，其序列值通常是在等時間間隔測得的數(shù)據(jù)（如股票的每日收盤價等） 。與之相對的，序列數(shù)據(jù)庫則是由有序事件的序列組成的數(shù)據(jù)庫，它可以有時間標(biāo)記，也可以沒有時間標(biāo)記（如 Web 頁面訪問序列） 。值得注意的是：時序數(shù)據(jù)一定是序列數(shù)據(jù)；而序列數(shù)據(jù)卻不一定是時序數(shù)據(jù) [18]。時序數(shù)據(jù)挖掘主要有以下三種主要類型：時序數(shù)據(jù)的趨勢分析：分析時序數(shù)據(jù)隨數(shù)據(jù)變化的趨勢。14 / 51時序分析中的相似搜索：查詢與給