序列模式挖掘演算法

㈠ 數據挖掘概念綜述

數據挖掘概念綜述
數據挖掘又稱從資料庫中發現知識（KDD）、數據分析、數據融合（Data Fusion）以及決策支持。KDD一詞首次出現在1989年8月舉行的第11屆國際聯合人工智慧學術會議上。隨後在1991年、1993年和1994年都舉行KDD 專題討論會，匯集來自各個領域的研究人員和應用開發者，集中討論數據統計、海量數據分析算 法、知識表示、知識運用等問題。隨著參與人員的不斷增多，KDD國際會議發展成為年會。1998 年在美國紐約舉行的第四屆知識發現與數據 挖掘國際學術會議不僅進行了學術討論，並且有30多家軟體公司展示了他們的數據挖掘軟體產品，不少軟體已在北美、歐洲等國得到應用。
一、什麼是數據挖掘
1.1、數據挖掘的歷史
近十幾年來，人們利用信息技術生產和搜集數據的能力大幅度提高，千萬萬個資料庫被用於商業管理、政府辦公、科學研究和工程開發等等，這一勢頭仍將持續發展下去。於是，一個新的挑戰被提了出來：在這被稱之為信息爆炸的時代，信息過量幾乎成為人人需要面對的問題。如何才能不被信息的汪洋大海所淹沒，從中及時發現有用的知識，提高信息利用率呢？要想使數據真正成為一個公司的資源，只有充分利用它為公司自身的業務決策和戰略發展服務才行，否則大量的數據可能成為包袱，甚至成為垃圾。因此，面對」人們被數據淹沒，人們卻飢餓於知識」的挑戰。另一方面計算機技術的另一領域——人工智慧自1956年誕生之後取得了重大進展。經歷了博弈時期、自然語言理解、知識工程等階段，目前的研究 熱點是機器學習。機器學習是用計算機模擬人類學習的一門科學，比較成熟的演算法有神經網路、遺傳演算法等。用資料庫管理系統來存儲數據，用機器學習的方法來分析數據，挖掘大量數據背後的知識，這兩者的結合促成了資料庫中的知識發現（KDD：Knowledge Discovery in Databases）的產生，因此，數據挖掘和知識發現（DMKD）技術應運而生，並得以蓬勃發展，越來越顯示出其強大的生命力。
數據挖掘又稱從資料庫中發現知識（KDD）、數據分析、數據融合（Data Fusion）以及決策支持。KDD一詞首次出現在1989年8月舉行的第11屆國際聯合人工智慧學術會議上。隨後在1991年、1993年和1994年都舉行KDD 專題討論會，匯集來自各個領域的研究人員和應用開發者，集中討論數據統計、海量數據分析算 法、知識表示、知識運用等問題。隨著參與人員的不斷增多，KDD國際會議發展成為年會。1998 年在美國紐約舉行的第四屆知識發現與數據 挖掘國際學術會議不僅進行了學術討論，並且有30多家軟體公司展示了他們的數據挖掘軟體產品，不少軟體已在北美、歐洲等國得到應用。
2.2數據挖掘的概念
從1989年到現在，KDD的定義隨著人們研究的不斷深入也在不斷完善，目前比較公認的定義是Fayyad 等給出的：KDD是從數據集中識別出有效的、新穎的、潛在有用的以及最終可理解模式的高級處理過程。從定義可以看出，數據挖掘（DataMining）就是從大量的、不完全的、有雜訊的、模糊的、隨機的數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。人們把原始數據看作是形成知識的源泉，就像從礦石中采礦一樣。原始數據可以是結構化的，如關系資料庫中的數據，也可以是半結構化的，如文本、圖形、圖像數據，甚至是分布在網路上的異構型數據。發現知識的方法可以是數學的，也可以是非數學的；可以是演繹的，也可以是歸納的。發現了的知識可以被用於信息管理、查詢優化、決策支持、過程式控制制等，還可以用於數據自身的維護。因此，數據挖掘是一門很廣義的交叉學科，它匯聚了不同領域的研究者，尤其是資料庫、人工智慧、數理統計、可視化、並行計算等方面的學者和工程技術人員。
特別要指出的是，數據挖掘技術從一開始就是面向應用的。它不僅是面向特定資料庫的簡單檢索查詢調用，而且要對這些數據進行微觀、中觀乃至宏觀的統計、分析、綜合和推理，以指導實際問題的求解，企圖發現事件間的相互關聯，甚至利用已有的數據對未來的活動進行預測。
一般來說在科研領域中稱為KDD，而在工程領域則稱為數據挖掘。
二、數據挖掘的步驟
KDD包括以下步驟：
1、數據准備
KDD的處理對象是大量的數據，這些數據一般存儲在資料庫系統中，是長期積累的結果。但往往不適合直接在這些數據上面進行知識挖 掘，需要做數據准備工作，一般包括數據的選擇（選擇相關的數據）、凈化（消除噪音、冗餘數據）、推測（推算缺失數據）、轉換（離散值 數據與連續值數據之間的相互轉換，數據值的分組分類，數據項之間的計算組合等）、數據縮減（減少數據量）。如果KDD的對象是數據倉 庫，那麼這些工作往往在生成數據倉庫時已經准備妥當。數據准備是KDD 的第一個步驟，也是比較重要的一個步驟。數據准備是否做好將影 響到數據挖掘的效率和准確度以及最終模式的有效性。
2、數據挖掘
數據挖掘是KDD最關鍵的步驟，也是技術難點所在。研究KDD的人員中大部分都在研究數據挖掘技術，採用較多的技術有決策樹、分類、 聚類、粗糙集、關聯規則、神經網路、遺傳演算法等。數據挖掘根據KDD的目標，選取相應演算法的參數，分析數據，得到可能形成知識的模式 模型。
3、評估、解釋模式模型
上面得到的模式模型，有可能是沒有實際意義或沒有實用價值的，也有可能是其不能准確反映數據的真實意義，甚至在某些情況下是與事 實相反的，因此需要評估，確定哪些是有效的、有用的模式。評估可以根據用戶多年的經驗，有些模式也可以直接用數據來檢驗其准確性。 這個步驟還包括把模式以易於理解的方式呈現給用戶。
4、鞏固知識
用戶理解的、並被認為是符合實際和有價值的模式模型形成了知識。同時還要注意對知識做一
致性檢查，解決與以前得到的知識互相沖 突、矛盾的地方，使知識得到鞏固。
5、運用知識
發現知識是為了運用，如何使知識能被運用也是KDD的步驟之一。運用知識有兩種方法：一種是只需看知識本身所描述的關系或結果，就 可以對決策提供支持；另一種是要求對新的數據運用知識，由此可能產生新的問題，而需要對知識做進一步的優化
三、數據挖掘的特點及功能
3.1、數據挖掘的特點
數據挖掘具有如下幾個特點，當然，這些特點與數據挖掘要處理的數據和目的是密切相關的。
1、處理的數據規模十分巨大。
2、查詢一般是決策制定者（用戶）提出的即時隨機查詢，往往不能形成精確的查詢要求。
3、由於數據變化迅速並可能很快過時，因此需要對動態數據作出快速反應，以提供決策支持。
4、主要基於大樣本的統計規律，其發現的規則不一定適用於所有數據
3.2、數據挖掘的功能
數據挖掘所能發現的知識有如下幾種：
廣義型知識，反映同類事物共同性質的知識；
特徵型知識，反映事物各方面的特徵知識；
差異型知識，反映不同事物之間屬性差別的知識 ;關聯型知識，反映事物之間依賴或關聯的知識；
預測型知識，根據歷史的和當前的數據推測未來數據；偏離型知識，揭示事物偏離常規的異常現象。
所有這些知識都可以在不同的概念層次上被發現，隨著概念樹的提升，從微觀到中觀再到宏觀，以滿足不同用戶、不同層次決策的需要。例如，從一家超市的數據倉庫中，可以發現的一條典型關聯規則可能是」買麵包和黃油的顧客十有八九也買牛奶」，也可能是」買食品的顧客幾乎都用信用卡」，這種規則對於商家開發和實施客戶化的銷售計劃和策略是非常有用的。至於發現工具和方法，常用的有分類、聚類、減維、模式識別、可視化、決策樹、遺傳演算法、不確定性處理等。歸納起來，數據挖掘有如下幾個功能：
預測/驗證功能：預測/驗證功能指用資料庫的若干已知欄位預測或驗證其他未知欄位值。預測方法有統計分析方法、關聯規則和決策樹預測方法、回歸樹預測方法等。
描述功能：描述功能指找到描述數據的可理解模式。描述方法包括以下幾種：數據分類、回歸分析、簇聚、概括、構造依賴模式、變化和偏差分析、模式發現、路徑發現等。
四、數據挖掘的模式
數據挖掘的任務是從數據中發現模式。模式是一個用語言L來表示的一個表達式E，它可用來描述數據集F中數據的特性，E 所描述的數據是集 合F的一個子集FE。E作為一個模式要求它比列舉數據子集FE中所有元素的描述方法簡單。例如，「如果成績在81 ～90之間，則成績優良」可稱 為一個模式，而「如果成績為81、82、83、84、85、86、87、88、89 或90，則成績優良」就不能稱之為一個模式。
模式有很多種，按功能可分有兩大類：預測型（Predictive）模式和描述型（Descriptive）模式。
預測型模式是可以根據數據項的值精確確定某種結果的模式。挖掘預測型模式所使用的數據也都是可以明確知道結果的。例如，根據各種 動物的資料，可以建立這樣的模式：凡是胎生的動物都是哺乳類動物。當有新的動物資料時，就可以根據這個模式判別此動物是否是哺乳動物。
描述型模式是對數據中存在的規則做一種描述，或者根據數據的相似性把數據分組。描述型模式不能直接用於預測。例如，在地球上，70 ％的表面被水覆蓋，30 ％是土地。
在實際應用中，往往根據模式的實際作用細分為以下6 種：
1、分類模式
分類模式是一個分類函數（ 分 類 器），能夠把數據集中的數據項映射到某個給定的類上。分類模式往往表現為一棵分類樹，根據數據的 值從樹根開始搜索，沿著數據滿足的分支往上走，走到樹葉就能確定類別。
2、回歸模式
回歸模式的函數定義與分類模式相似，它們的差別在於分類模式的預測值是離散的，回歸模式的預測值是連續的。如給出某種動物的特徵，可以用分類模式判定這種動物是哺乳動物還是鳥類；給出某個人的教育情況、工作經驗，可以用回歸模式判定這個人的年工資在哪個范圍內，是在6000元以下，還是在6000元到1萬元之間，還是在1萬元以上。
3、時間序列模式
時間序列模式根據數據隨時間變化的趨勢預測將來的值。這里要考慮到時間的特殊性質，像一些周期性的時間定義如星期、月、季節、年 等，不同的日子如節假日可能造成的影響，日期本身的計算方法，還有一些需要特殊考慮的地方如時間前後的相關性（過去的事情對將來有 多大的影響力）等。只有充分考慮時間因素，利用現有數據隨時間變化的一系列的值，才能更好地預測將來的值。
4、聚類模式
聚類模式把數據劃分到不同的組中，組之間的差別盡可能大，組內的差別盡可能小。與分類模式不同，進行聚類前並不知道將要劃分成幾 個組和什麼樣的組，也不知道根據哪一（幾）個數據項來定義組。一般來說，業務知識豐富的人應該可以理解這些組的含義，如果產生的模式無法理解或不可用，則該模式可能是無意義的，需要回到上階段重新組織數據。
5、關聯模式
關聯模式是數據項之間的關聯規則。關聯規則是如下形式的一種規則：「在無力償還貸款的人當中，60％的人的月收入在3000元以下。」
6、序列模式
序列模式與關聯模式相仿，而把數據之間的關聯性與時間聯系起來。為了發現序列模式，不僅需要知道事件是否發生，而且需要確定事件 發生的時間。例如，在購買彩電的人們當中，60％的人會在3個月內購買影碟機
五、數據挖掘的發現任務
數據挖掘涉及的學科領域和方法很多，有多種分類法。根據挖掘任務分，可分為分類或預測模型發現、數據總結、聚類、關聯規則發現、序列模式發現、依賴關系或依賴模型發現、異常和趨勢發現等等；根據挖掘對象分，有關系資料庫、面向對象資料庫、空間資料庫、時態資料庫、文本數據源、多媒體資料庫、異質資料庫、遺產資料庫以及環球網Web;根據挖掘方法分，可粗分為：機器學習方法、統計方法、神經網路方法和資料庫方法。機器學習中，可細分為：歸納學習方法（決策樹、規則歸納等）、基於範例學習、遺傳演算法等。統計方法中，可細分為：回歸分析（多元回歸、自回歸等）、判別分析（貝葉斯判別、費歇爾判別、非參數判別等）、聚類分析（系統聚類、動態聚類等）、探索性分析（主元分析法、相關分析法等）等。神經網路方法中，可細分為：前向神經網路（BP演算法等）、自組織神經網路（自組織特徵映射、競爭學習等）等。資料庫方法主要是多維數據分析或OLAP 方法，另外還有面向屬性的歸納方法。
從挖掘任務和挖掘方法的角度而言有數據總結、分類發現、聚類和關聯規則發現四種非常重要的發現任務。
5.1、數據總結
數據總結目的是對數據進行濃縮，給出它的緊湊描述。傳統的也是最簡單的數據總結方法是計算出資料庫的各個欄位上的求和值、平均值、方差值等統計值，或者用直方圖、餅狀圖等圖形方式表示。數據挖掘主要關心從數據泛化的角度來討論數據總結。數據泛化是一種把資料庫中的有關數據從低層次抽象到高層次上的過程。由於資料庫上的數據或對象所包含的信息總是最原始、基本的信息（這是為了不遺漏任何可能有用的數據信息）。人們有時希望能從較高層次的視圖上處理或瀏覽數據，因此需要對數據進行不同層次上的泛化以適應各種查詢要求。數據泛化目前主要有兩種技術：多維數據分析方法和面向屬性的歸納方法。
1、多維數據分析方法是一種數據倉庫技術，也稱作聯機分析處理（OLAP）。數據倉庫是面向決策支持的、集成的、穩定的、不同時間的歷史數據集合。決策的前提是數據分析。在數據分析中經常要用到諸如求和、總計、平均、最大、最小等匯集操作，這類操作的計算量特別大。因此一種很自然的想法是，把匯集操作結果預先計算並存儲起來，以便於決策支持系統使用。存儲匯集操作結果的地方稱作多維資料庫。多維數據分析技術已經在決策支持系統中獲得了成功的應用，如著名的SAS數據分析軟體包、Business Object公司的決策支持系統Business Object,以及IBM公司的決策分析工具都使用了多維數據分析技術。
採用多維數據分析方法進行數據總結，它針對的是數據倉庫，數據倉庫存儲的是離線的歷史數據。
2、為了處理聯機數據，研究人員提出了一種面向屬性的歸納方法。它的思路是直接對用戶感興趣的數據視圖（用一般的SQL查詢語言即可獲得）進行泛化，而不是像多維數據分析方法那樣預先就存儲好了泛化數據。方法的提出者對這種數據泛化技術稱之為面向屬性的歸納方法。原始關系經過泛化操作後得到的是一個泛化關系，它從較高的層次上總結了在低層次上的原始關系。有了泛化關系後，就可以對它進行各種深入的操作而生成滿足用戶需要的知識，如在泛化關系基礎上生成特性規則、判別規則、分類規則，以及關聯規則等。
5.2、分類發現
分類在數據挖掘中是一項非常重要的任務，目前在商業上應用最多。分類的目的是學會一個分類函數或分類模型（也常常稱作分類器），該模型能把資料庫中的數據項映射到給定類別中的某一個。分類和回歸都可用於預測。預測的目的是從利用歷史數據紀錄中自動推導出對給定數據的推廣描述，從而能對未來數據進行預測。和回歸方法不同的是，分類的輸出是離散的類別值，而回歸的輸出則是連續數值。
要構造分類器，需要有一個訓練樣本數據集作為輸入。訓練集由一組資料庫記錄或元組構成，每個元組是一個由有關欄位（又稱屬性或特徵）值組成的特徵向量，此外，訓練樣本還有一個類別標記。一個具體樣本的形式可為：（ v1, v2, …， vn; c ）；其中vi表示欄位值，c表示類別。
分類器的構造方法有統計方法、機器學習方法、神經網路方法等等。統計方法包括貝葉斯法和非參數法（近鄰學習或基於事例的學習），對應的知識表示則為判別函數和原型事例。機器學習方法包括決策樹法和規則歸納法，前者對應的表示為決策樹或判別樹，後者則一般為產生式規則。神經網路方法主要是BP演算法，它的模型表示是前向反饋神經網路模型（由代表神經元的節點和代表聯接權值的邊組成的一種體系結構），BP演算法本質上是一種非線性判別函數。另外，最近又興起了一種新的方法：粗糙集（rough set），其知識表示是產生式規則。
不同的分類器有不同的特點。有三種分類器評價或比較尺度：1 預測准確度；2 計算復雜度；3 模型描述的簡潔度。預測准確度是用得最多的一種比較尺度，特別是對於預測型分類任務，目前公認的方法是10番分層交叉驗證法。計算復雜度依賴於具體的實現細節和硬體環境，在數據挖掘中，由於操作對象是巨量的資料庫，因此空間和時間的復雜度問題將是非常重要的一個環節。對於描述型的分類任務，模型描述越簡潔越受歡迎；例如，採用規則表示的分類器構造法就更有用，而神經網路方法產生的結果就難以理解。
另外要注意的是，分類的效果一般和數據的特點有關，有的數據雜訊大，有的有缺值， 有的分布稀疏，有的欄位或屬性間相關性強，有的屬性是離散的而有的是連續值或混合式的。目前普遍認為不存在某種方法能適合於各種特點的數據。
5.3、聚類
聚類是把一組個體按照相似性歸成若干類別，即」物以類聚」。它的目的是使得屬於同一類別的個體之間的距離盡可能的小，而不同類別上的個體間的距離盡可能的大。聚類方法包括統計方法、機器學習方法、神經網路方法和面向資料庫的方法。
在統計方法中，聚類稱聚類分析，它是多元數據分析的三大方法之一（其它兩種是回歸分析和判別分析）。它主要研究基於幾何距離的聚類，如歐式距離、明考斯基距離等。傳統的統計聚類分析方法包括系統聚類法、分解法、加入法、動態聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。這種聚類方法是一種基於全局比較的聚類，它需要考察所有的個體才能決定類的劃分；因此它要求所有的數據必須預先給定，而不能動態增加新的數據對象。聚類分析方法不具有線性的計算復雜度，難以適用於資料庫非常大的情況。
在機器學習中聚類稱作無監督或無教師歸納；因為和分類學習相比，分類學習的例子或數據對象有類別標記，而要聚類的例子則沒有標記，需要由聚類學習演算法來自動確定。很多人工智慧文獻中，聚類也稱概念聚類；因為這里的距離不再是統計方法中的幾何距離 ,而是根據概念的描述來確定的。當聚類對象可以動態增加時，概念聚類則稱是概念形成。
在神經網路中，有一類無監督學習方法：自組織神經網路方法；如Kohonen自組織特徵映射網路、競爭學習網路等等。在數據挖掘領域里，見報道的神經網路聚類方法主要是自組織特徵映射方法，IBM在其發布的數據挖掘白皮書中就特別提到了使用此方法進行資料庫聚類分割。
5.4、關聯規則發現
關聯規則是形式如下的一種規則，」在購買麵包和黃油的顧客中，有90%的人同時也買了牛奶」（麵包+黃油 （ 牛奶 ）。用於關聯規則發現的主要對象是事務型資料庫，其中針對的應用則是售貨數據，也稱貨籃數據。一個事務一般由如下幾個部分組成：事務處理時間 ,一組顧客購買的物品，有時也有顧客標識號（如信用卡號）。
由於條形碼技術的發展，零售部門可以利用前端收款機收集存儲大量的售貨數據。因此，如果對這些歷史事務數據進行分析，則可對顧客的購買行為提供極有價值的信息。例如，可以幫助如何擺放貨架上的商品（如把顧客經常同時買的商品放在一起），幫助如何規劃市場（怎樣相互搭配進貨）。由此可見，從事務數據中發現關聯規則，對於改進零售業等商業活動的決策非常重要。
如果不考慮關聯規則的支持度和可信度，那麼在事務資料庫中存在無窮多的關聯規則。事實上，人們一般只對滿足一定的支持度和可信度的關聯規則感興趣。在文獻中，一般稱滿足一定要求的（如較大的支持度和可信度）的規則為強規則。因此，為了發現出有意義的關聯規則，需要給定兩個閾值：最小支持度和最小可信度。前者即用戶規定的關聯規則必須滿足的最小支持度，它表示了一組物品集在統計意義上的需滿足的最低程度；後者即用戶規定的關聯規則必須滿足的最小可信度，它反應了關聯規則的最低可靠度。
在實際情況下，一種更有用的關聯規則是泛化關聯規則。因為物品概念間存在一種層次關系，如夾克衫、滑雪衫屬於外套類，外套、襯衣又屬於衣服類。有了層次關系後，可以幫助發現一些更多的有意義的規則。例如，」買外套，買鞋子」（此處，外套和鞋子是較高層次上的物品或概念，因而該規則是一種泛化的關聯規則）。由於商店或超市中有成千上萬種物品，平均來講，每種物品（如滑雪衫）的支持度很低，因此有時難以發現有用規則；但如果考慮到較高層次的物品（如外套），則其支持度就較高，從而可能發現有用的規則。另外，關聯規則發現的思路還可以用於序列模式發現。用戶在購買物品時，除了具有上述關聯規律，還有時間上或序列上的規律，因為，很多時候顧客會這次買這些東西，下次買同上次有關的一些東西，接著又買有關的某些東西。

㈡ GSP演算法的GSP演算法描述

GSP演算法 基本步驟如下：
1）掃描序列資料庫，得到長度為1的序列模式L1，作為初始的種子集
2）根據長度為i 的種子集Li ，通過連接操作和修剪操作生成長度為i+1的候選序列模式Ci+1；然後掃描序列資料庫，計算每個候選序列模式的支持度，產生長度為i+1的序列模式Li+1，並將Li+1作為新的種子集
3）重復第二步，直到沒有新的序列模式或新的候選序列模式產生為止
產生候選序列模式主要分兩步：
連接階段：如果去掉序列模式s1的第一個項目與去掉序列模式s2的最後一個項目所得到的序列相同，則可以將s1與s2進行連接，即將s2的最後一個項目添加到s1中
修切階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除
候選序列模式[ 的支持度計算：對於給定的候選序列模式集合C，掃描序列資料庫，對於其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，並增加其支持度計數
GSP需要多次掃描序列資料庫，在第一次掃描中，對所有的單個項目(1—序列模式)進行計數。利用頻繁1—序列模式生成候選頻繁2—序列模式，進行第二次掃描並求候選頻繁2—序列模式的支持數。使用頻繁2—序列模式生成候選頻繁3—序列模式，重復以上過程，直到找出所有的頻繁序列模式。 哈希樹GSP 採用哈希樹存儲候選序列模式。哈希樹的節點分為三類： 1、根節點；
2、內部節點；
3、葉子節點。
根節點和內部節點中存放的是一個哈希表，每個哈希表項指向其它的節點。而葉子節點內存放的是一組候選序列模式。 從根節點開始，用哈希函數對序列的第一個項目做映射來決定從哪個分支向下，依次在第n層對序列的第n個項目作映射來決定從哪個分支向下，直到到達一個葉子節點。將序列儲存在此葉子節點。
初始時所有節點都是葉子節點，當一個葉子節點所存放的序列數目達到一個閾值，它將轉化為一個內部節點。
候選序列模式支持度的計算
給定一個序列s是序列資料庫的一個記錄：
1）對於根節點，用哈希函數對序列s的每一個單項做映射來並從相應的表項向下迭代的進行操作 2）。
2）對於內部節點，如果s是通過對單項x做哈希映射來到此節點的，則對s中每一個和x在一個元素中的單項以及在x所在元素之後第一個元素的第一個單項做哈希映射，然後從相應的表項向下迭代做操作 2）或 3）。
3）對一個葉子節點，檢查每個候選序列模式c是不是s的子序列.如果是相應的候選序列模式支持度加一。
這種計算候選序列的支持度的方法避免了大量無用的掃描，對於一條序列，僅檢驗那些最有可能成為它子序列的候選序列模式。掃描的時間復雜度由O(n*m)降為O(n*t),其中n表示序列數量，m表示候選序列模式的數量，t代表哈希樹葉子節點的最大容量

㈢ 數據挖掘演算法有哪些

統計和可視化要想建立一個好的預言模型，你必須了解自己的數據。最基本的方法是計算各種統計變數（平均值、方差等）和察看數據的分布情況。你也可以用數據透視表察看多維數據。數據的種類可分為連續的，有一個用數字表示的值（比如銷售量）或離散的，分成一個個的類別（如紅、綠、藍）。離散數據可以進一步分為可排序的，數據間可以比較大小（如，高、中、低）和標稱的，不可排序（如郵政編碼）。圖形和可視化工具在數據准備階段尤其重要，它能讓你快速直觀的分析數據，而不是給你枯燥乏味的文本和數字。它不僅讓你看到整個森林，還允許你拉近每一棵樹來察看細節。在圖形模式下人們很容易找到數據中可能存在的模式、關系、異常等，直接看數字則很難。可視化工具的問題是模型可能有很多維或變數，但是我們只能在2維的屏幕或紙上展示它。比如，我們可能要看的是信用風險與年齡、性別、婚姻狀況、參加工作時間的關系。因此，可視化工具必須用比較巧妙的方法在兩維空間內展示n維空間的數據。雖然目前有了一些這樣的工具，但它們都要用戶「訓練」過他們的眼睛後才能理解圖中畫的到底是什麼東西。對於眼睛有色盲或空間感不強的人，在使用這些工具時可能會遇到困難。聚集（分群）聚集是把整個資料庫分成不同的群組。它的目的是要群與群之間差別很明顯，而同一個群之間的數據盡量相似。與分類不同（見後面的預測型數據挖掘），在開始聚集之前你不知道要把數據分成幾組，也不知道怎麼分（依照哪幾個變數）。因此在聚集之後要有一個對業務很熟悉的人來解釋這樣分群的意義。很多情況下一次聚集你得到的分群對你的業務來說可能並不好，這時你需要刪除或增加變數以影響分群的方式，經過幾次反復之後才能最終得到一個理想的結果。神經元網路和K-均值是比較常用的聚集演算法。不要把聚集與分類混淆起來。在分類之前，你已經知道要把數據分成哪幾類，每個類的性質是什麼，聚集則恰恰相反。關聯分析關聯分析是尋找資料庫中值的相關性。兩種常用的技術是關聯規則和序列模式。關聯規則是尋找在同一個事件中出現的不同項的相關性，比如在一次購買活動中所買不同商品的相關性。序列模式與此類似，他尋找的是事件之間時間上的相關性，如對股票漲跌的分析。關聯規則可記為A==>B，A稱為前提和左部（LHS），B稱為後續或右部（RHS）。如關聯規則「買錘子的人也會買釘子」，左部是「買錘子」，右部是「買釘子」。要計算包含某個特定項或幾個項的事務在資料庫中出現的概率只要在資料庫中直接統計即可。某一特定關聯（「錘子和釘子」）在資料庫中出現的頻率稱為支持度。比如在總共1000個事務中有15個事務同時包含了「錘子和釘子」，則此關聯的支持度為1.5%。非常低的支持度（比如1百萬個事務中只有一個）可能意味著此關聯不是很重要，或出現了錯誤數據（如，「男性和懷孕」）。要找到有意義的規則，我們還要考察規則中項及其組合出現的相對頻率。當已有A時，B發生的概率是多少？也即概率論中的條件概率。回到我們的例子，也就是問「當一個人已經買了錘子，那他有多大的可能也會買釘子？」這個條件概率在數據挖掘中也稱為可信度，計算方法是求百分比：（A與B同時出現的頻率）/（A出現的頻率）。讓我們用一個例子更詳細的解釋這些概念： 總交易筆數（事務數）：1,000包含「錘子」：50包含「釘子」：80包含「鉗子」：20包含「錘子」和「釘子」：15包含「鉗子」和「釘子」：10包含「錘子」和「鉗子」：10包含「錘子」、「鉗子」和「釘子」：5 則可以計算出： 「錘子和釘子」的支持度=1.5%（15/1,000）「錘子、釘子和鉗子」的支持度=0.5%（5/1,000）「錘子==>釘子」的可信度=30%（15/50）「釘子==>錘子」的可信度=19%（15/80）「錘子和釘子==>鉗子」的可信度=33%（5/15）「鉗子==>錘子和釘子」的可信度=25%（5/20）

㈣ 數據挖掘的常用方法有哪些

決策樹在解決歸類與預測上有著極強的能力，它以法則的方式表達，而這些法則則以一連串的問題表示出來，經由不斷詢問問題最終能導出所需的結果。典型的決策樹頂端是一個樹根，底部有許多的樹葉，它將紀錄分解成不同的子集，每個子集中的欄位可能都包含一個簡單的法則。此外，決策樹可能有著不同的外型，例如二元樹、三元樹或混和的決策樹型態。

2、神經網路法

神經網路法是模擬生物神經系統的結構和功能，是一種通過訓練來學習的非線性預測模型，它將每一個連接看作一個處理單元，試圖模擬人腦神經元的功能，可完成分類、聚類、特徵挖掘等多種數據挖掘任務。神經網路的學習方法主要表現在權值的修改上。其優點是具有抗干擾、非線性學習、聯想記憶功能，對復雜情況能得到精確的預測結果;缺點首先是不適合處理高維變數，不能觀察中間的學習過程，具有“黑箱”性，輸出結果也難以解釋;其次是需較長的學習時間。神經網路法主要應用於數據挖掘的聚類技術中。

3、關聯規則法

關聯規則是描述資料庫中數據項之間所存在的關系的規則，即根據一個事務中某些項的出現可導出另一些項在同一事務中也出現，即隱藏在數據間的關聯或相互關系。在客戶關系管理中，通過對企業的客戶資料庫里的大量數據進行挖掘，可以從大量的記錄中發現有趣的關聯關系，找出影響市場營銷效果的關鍵因素，為產品定位、定價與定製客戶群，客戶尋求、細分與保持，市場營銷與推銷，營銷風險評估和詐騙預測等決策支持提供參考依據。

4、遺傳演算法

遺傳演算法模擬了自然選擇和遺傳中發生的繁殖、交配和基因突變現象，是一種採用遺傳結合、遺傳交叉變異及自然選擇等操作來生成實現規則的、基於進化理論的機器學習方法。它的基本觀點是“適者生存”原理，具有隱含並行性、易於和其他模型結合等性質。主要的優點是可以處理許多數據類型，同時可以並行處理各種數據;缺點是需要的參數太多，編碼困難，一般計算量比較大。遺傳演算法常用於優化神經元網路，能夠解決其他技術難以解決的問題。

5、聚類分析法

聚類分析是把一組數據按照相似性和差異性分為幾個類別，其目的是使得屬於同一類別的數據間的相似性盡可能大，不同類別中的數據間的相似性盡可能小。根據定義可以把其分為四類：基於層次的聚類方法;分區聚類演算法;基於密度的聚類演算法;網格的聚類演算法。常用的經典聚類方法有K-mean，K-medoids，ISODATA等。

6、模糊集法

模糊集法是利用模糊集合理論對問題進行模糊評判、模糊決策、模糊模式識別和模糊聚類分析。模糊集合理論是用隸屬度來描述模糊事物的屬性。系統的復雜性越高，模糊性就越強。

7、web頁挖掘

通過對Web的挖掘，可以利用Web的海量數據進行分析，收集政治、經濟、政策、科技、金融、各種市場、競爭對手、供求信息、客戶等有關的信息，集中精力分析和處理那些對企業有重大或潛在重大影響的外部環境信息和內部經營信息，並根據分析結果找出企業管理過程中出現的各種問題和可能引起危機的先兆，對這些信息進行分析和處理，以便識別、分析、評價和管理危機。

8、邏輯回歸分析

反映的是事務資料庫中屬性值在時間上的特徵，產生一個將數據項映射到一個實值預測變數的函數，發現變數或屬性間的依賴關系，其主要研究問題包括數據序列的趨勢特徵、數據序列的預測以及數據間的相關關系等。

9、粗糙集法

是一種新的處理含糊、不精確、不完備問題的數學工具，可以處理數據約簡、數據相關性發現、數據意義的評估等問題。其優點是演算法簡單，在其處理過程中可以不需要關於數據的先驗知識，可以自動找出問題的內在規律;缺點是難以直接處理連續的屬性，須先進行屬性的離散化。因此，連續屬性的離散化問題是制約粗糙集理論實用化的難點。

10、連接分析

它是以關系為主體，由人與人、物與物或是人與物的關系發展出相當多的應用。例如電信服務業可藉連結分析收集到顧客使用電話的時間與頻率，進而推斷顧客使用偏好為何，提出有利於公司的方案。除了電信業之外，愈來愈多的營銷業者亦利用連結分析做有利於企業的研究。

㈤ 聚類演算法可以和時間序列相結合做預測嗎

你好，
如果你處理的數據本身就是時間序列數據，如果採用聚類的話，就會忽略數據的順序信息。也就是說並不知道得到那些簇之間的先後順序，既然不知道順序用時間序列來坐預測就沒有什麼意義。

你對數據先聚類後預測，我大致能了解你的意圖。你可以試著把聚類演算法換成序列模式挖掘演算法。比如，利用PrefixSpan找出頻繁出現的序列模式，那樣的話，給定一個序列模式，直接去匹配最符合的頻繁模式，就可以做簡單的預測。
此外，針對時間序列預測，有專門的比如ARIMA這種演算法來進行預測，為什麼要先聚類了？