頻繁模式挖掘，關系挖掘，以及相互關系挖掘

所謂頻繁模式挖掘，指的是比如在商品交易數據庫記錄中，找出一起出現的商品集合，這些商品集合出現的頻率要高于一個閾值，這些經常出現的商品集合稱之為頻繁模式。

頻繁模式的思路很簡單，首先統(tǒng)計出每個單個商品出現的次數，這就構成了一個一維表。然后再根據一維表，商品兩兩組合產生一個二維表。然后再由二維表產生三維表，直至到n維表。其中可以利用apriori，進行剪枝，也就是說一維表中如果出現的頻率低于閾值的商品，就可以直接去掉，應為包含該商品的高維商品集合的出現頻率不可能高于該閾值，可以直接剪枝去掉。

頻繁模式挖掘還有一種更加高效的方式，就是FP Growth，該方法通過掃描一遍數據庫，在內存中構造一顆FP tree，基于這棵樹就可以產生所有的頻繁模式。很顯然FP Growth算法的效率要高很多，但是其缺陷也很明顯，在內存中維護一顆FP tree的開銷也是很大的。為了解決這個問題，一個直接的思路是將數據庫水平分表到各臺機器上，在各臺機器上執(zhí)行本地的FP Growth，然后再將各臺機器上的結果匯總起來，得到最終的FP Growth的結果。

所謂關系挖掘，值得是挖掘出各個項目之間的因果關系。關系挖掘的基礎是頻繁模式挖掘，通過頻繁模式挖掘，很容易得出關系，舉例就很容易明白，比如我們得到一個頻繁集合：

那么通過排列組合可以得到l的子集集合：

那么很容易得到下面的推理集合，也就是挖掘出的關系：

所有的關系挖掘本質上都是基于頻繁模式推導出來的。

在關系挖掘中，有一種非常有用的關系模式挖掘:mining quantitative association rules。所謂quantitative association rules是這樣一種關系模式：

該關系模式的挖掘，首先是確定我們所感興趣的屬性：quan1,quan2,cat，然后根據事先確定的間隔，將quan1，quan2按照一定的間隔劃分成一定的catorgory，然后進行頻繁模式挖掘，得出一些關系，然后將這些關系按照grid進行聚合，生成最后的關系模式。

通過關系挖掘挖出的關系中往往有很多不是非常有用，因此需要通過另外的指標排除一些這樣的關系，這個指標就是correlation，如下：

Correlation是用來衡量A，B之間的相關性，從而排除那些沒有意義的規(guī)則。

對于上述所提到的關系挖掘，有一種稱之為constraint-based association mining，這是一種特殊的關系挖掘，它對于所挖掘出的條件加了一些限制條件，這些限制條件可能是由用戶提出的，其主要目的是排除一些不感興趣的關系。對于這種關系挖掘，最直接的辦法先按照最普通的關系挖掘方法進行挖掘，然后利用條件來對結果進行。但是還有更好的方法，就是在挖掘的過程中利用這些條件，從而縮小整個挖掘過程中的search space，從而提高效率。這些限制條件分為這么幾種：antimonotonic，monotonic，succinct，convertible，inconvertible，針對每一種的限制條件，都有一些通用的方法或策略來縮小挖掘的search space，可參閱相關資料。

分類和預測

分類樹

分類樹是一種很常用的分類方法，它該算法的框架表述還是比較清晰的，從根節(jié)點開始不斷得分治，遞歸，生長，直至得到最后的結果。根節(jié)點代表整個訓練樣本集,通過在每個節(jié)點對某個屬性的測試驗證,算法遞歸得將數據集分成更小的數據集.某一節(jié)點對應的子樹對應著原數據集中滿足某一屬性測試的部分數據集.這個遞歸過程一直進行下去。

該算法是數據挖掘中常用的一類方法。

貝葉斯分類器

貝葉斯分類的思想很簡單，就是計算屬性和分類之間的條件概率，選擇使得條件概率最大的分類作為最終的分類結果，這是一種基于統(tǒng)計的分類方法，得到了廣泛的引用。

貝葉斯分類器分為兩種，一種是樸素貝葉斯分類器，它基于貝葉斯理論：

其中X代表特征向量, C代表分類.我們的目標就是找出使得這個后驗概率最大的那個類.

其中需要注意的是X中的各個特征分量是分布獨立的.這樣就有:

樸素貝葉斯分類器最經典的應用場景就是垃圾郵件過濾。

樸素貝葉斯分類器的升級版本就是貝葉斯網絡，因為樸素貝葉斯網絡假設樣本的特征向量的各個特征屬性是獨立的，但對于現實世界，這樣的建模未必合理，因此有人就提出了貝葉斯網絡，貝葉斯網絡假設各個屬性之間是存在條件概率的。貝葉斯網絡是一個各個屬性組成的有向拓撲網絡，每條邊代表條件概率，通過貝葉斯網絡能夠計算出各個屬性相互組合的條件概率。

基于規(guī)則的分類器

這種分類器利用IF THEN的規(guī)則來進行分類。對于如何產生規(guī)則，有兩種方法：

第一種方法，就是從決策樹中生成規(guī)則。因為決策樹天然的就是規(guī)則。

第二種方法，是采用Sequential Covering Algorithm，直接從訓練樣本中生成規(guī)則集。該方法的思路是一種general-to-specific的方法，該方法從一個空規(guī)則開始，然后向規(guī)則中依次逐漸增加屬性測試條件，選擇該屬性測試值（也就是測試分界點，attr < val）的依據就是是否能夠最大限度得改進規(guī)則的分類質量。

基于神經網絡的分類器

神經網絡分類器是依據屬性構造一個網絡拓撲結構，該拓撲結構的邊具有權重值，我們的目的是不斷得利用訓練樣本然后不斷得更新神經網絡的邊權重值。然后利用該網絡就可以得到輸出的分類。

該算法模擬神經的組成結構，利用了單元之間的反饋機制。但該算法的缺點也很明顯，網絡拓撲結構的確定沒有明確統(tǒng)一的方法論，很多只能靠規(guī)劃者的經驗，因此訓練結果往往因人而異，限制了神經網絡的使用。

支持向量機分類器

支持向量機是在訓練樣本空間中構造超平面來對樣本進行分類，它的優(yōu)勢是對高維度不敏感。但效率較低，實施較為復雜。

關聯(lián)分類器

關聯(lián)分類器的思路很簡單，前面我們提到頻繁模式挖掘，我們將樣本的某一屬性的（屬性，值）對作為一個條目，我們找出經常在一起出現的條目集合，然后找出這些頻繁項目集合，這些頻繁項目集合對應的樣本集合中占主流的分類就作為關聯(lián)規(guī)則的分類結果，該結果如下：

關聯(lián)分類器有三種方法：CBA， CMAR和CPAR

Lazy Learner

Lazy Learner主要有兩種分類器：Knn分類器和Cbr分類器。

Knn分類器思路很直接，找出和待分類樣本最近的K的樣本，然后將這k個樣本中占主流的的類別作為分類結果分配給待分類樣本。該分類器的關鍵在于如何確定k，一種思路是根據經驗，另外一種思路是迭代，讓k從1開始遞增，計算每個k取值時對某一測試集的錯誤率，選擇錯誤最小的那個k。另外一個關鍵就是如何快速得找出k個最近的鄰居，這需要我們對各個樣本點進行事先排序，并設計一個合適的數據結構，使得找出k個最近鄰居的復雜度降為log|D|.

預測

所謂預測，就是根據既有的數據預測新出現的數據的預測值。預測有兩種方法，線性回歸和非線性回歸。所謂線性回歸，指的是

Y = b + wX 公式1

其中X可以是向量，比如(x1,x2)，因此線性回歸則變成

y=w0+w1*x1+w2*x2 公式2

對于公式1，其目標就是求出w向量。那么比較常用的方法就是最小二乘法，使得求出的w對于已有的樣本使其方差和最小。方差和就是目標函數，目標函數就是自變量w的一個函數，通過求導求極值，很容易得到使得目標函數最小的w的值。通過一些軟件包，如SAS，matlab，SPSS很容易做這種線性回歸的w計算。

并不是所有的模型都是線性模型，實際的問題中很多模型是非線性的，比如多項式，如下

y = w0 +w1*x+w2*x*x + w3*x*x*x

解決這種問題的思路是將非線性模型轉化為線性模型，然后再用線性回歸的方法來解決。比如上面的多項式公式，我們令

x1=x x2=x*x x3=x*x*x

這樣就變成了y = w0 + w1*x1 + w2*x2 + w3*x3，這就變成了線性回歸的問題。

聚類

聚類是數據挖掘需要解決的另外一個問題，分類是我們知道確切的分類結果，知道我們需要將樣本分成具體的哪幾類。而聚類問題是實現不知道我們的樣本具體屬于哪些類別，而需要我們從樣本中發(fā)掘出這些類別。下面談幾種較為通用的聚類方法談談。

基于分區(qū)的聚類法

該方法的一個典型的方法就是K-means，該方法非常簡單，首先確定我們需要將數據樣本分成多少個類，這個需要確定，我們稱之為k。然后從樣本中任意選擇k個樣本作為k個類的中心，然后計算每個樣本到這k個中心的距離，把他們分配到最相近的類。這樣就得到k個聚類，然后重新計算這k個聚類的中心，然后再重復前面的過程，直至沒有樣本被重新分配從而達到收斂。下面是k-means的偽碼

基于層次的分類法

基于層次的分類法有兩種：凝聚和分裂。

凝聚：它基于一種自底而上的策略，在最開始的時候，每個樣本都代表一個聚類，然后計算兩兩之間的區(qū)分度，然后進行合并，這個合并一直按照這樣的方式持續(xù)下去，直至所有的樣本都被合并為一個類。

分裂：它基于一種自上而下的策略，在最開始的時候，所有的樣本都是一個類，然后會依據一些區(qū)分方法，進行分裂，直至每個樣本都分裂成一個聚類。

基于層次的分類法，其意義在于其他的聚類方法引入這種基于層次的思路，可以被改造成一個多階段的的聚類方法，可以大大改進聚類的質量。

基于密度的分類法

這種方法的一個代表就是DBSCAN。要理解DBSCAN，首先要明白這么幾種概念：

某一樣本在e半徑內的鄰居稱之為e-鄰居。

如果某一樣本的e-鄰居個數大于某一最小值，那該樣本被稱之為核心樣本。

如果q是核心樣本，p是q的e-鄰居，那么p是q的直接密度可達。

對于一個樣本鏈p1,p2,..pn，如果p1=q,pn=p，pi+1是pi的直接可達，那么p就是q的密度可達。

如果p,q都是o的密度可達，那么p，q就是密度連通的。

有了這些概念，算法就很簡單了，首先找出樣本中所有的核心樣本，那么基于這些核心樣本，這些核心樣本就代表某一個聚類。遍歷這些核心樣本，不斷找到他們的密度可達的樣本，其間某些樣本就會被不斷合并，直至所有的樣本分類趨于穩(wěn)定，不會再有新的點被加入各個聚類。

基于grid的聚類法

該算法的代表是STING，它比較晦澀，從表面上來看，它似乎不是一種顯然的聚類法。首先我們先劃分一些層次，每個層次上我們根據維度或者概念分層不同的cell，實際上這里的每個層次對應的是樣本的一個分辨率。每個高層的cell在其下一層中被對應得劃分成多個cell，每個cell我們都計算出它的統(tǒng)計信息，估計出它的分布。利用這樣的結構，我們很容易進行查詢，比如我們查詢具有某些屬性的樣本，我們從上到下開始，根據cell的統(tǒng)計信息計算query在每個cell的置信區(qū)間，找出最大的那個cell，然后到下一層，依次直至到最底層。這樣的好處是，我們不用計算所有的樣本，算法每進一層都會拋棄不相關的樣本，所需的計算量會越來越少，那么速度就會很快。

這種方法雖然不是一種顯然的聚類法，但它確實可以用來聚類，因為query返回的樣本實際上就是某一聚類。Query本質上于聚類問題是有等價性的。

基于模型的聚類法

這種聚類法可以用來增強K-means。樣本假設可以被分為K個聚類，每個聚類可以被看成一種分布，比如高斯分布（高斯分布很符合K-means），K個聚類就是K個高斯分布模型，但我們不知道K個模型的具體參數。由于這是k個不同的高斯模型的混合體，因此每個樣本實際上除了本身屬性值之外還包含了一個隱藏變量（該隱藏變量用以表示該樣本是由哪個高斯模型產生的），這實際上就是一個典型的EM算法的應用場景，除了估計這k個模型的參數，還需要估計隱藏變量。接下來就是利用EM來估計這些參數（模型參數和隱藏變量），估計出的隱藏變量就代表樣本的聚類。

對高維樣本進行聚類

CLIQUE是這種方法的一個代表，其思想是從低維到高維（1維到n維）進行查詢，首先在低維空間內找到densentiy unit，然后在低維空間的densentiy unit中在繼續(xù)尋找較高維空間中的densentiy unit。它本質上也是grid聚類法，它不是一種顯然的聚類法，也是通過query來實現隱式得聚類。

有限制條件的聚類

這種聚類方法需要有一些特別的策略，需要針對不同場景，不能一概而論。這里就不講了。

奇點檢測

檢測奇點非常有用，用于檢測那些不同尋常的數據。比如最常用的思路是基于距離的，如果一個樣本在一定距離內的鄰居很少，那么他就可以被認為是奇點。另外還有基于統(tǒng)計概率的，基于密度的等等。