頻繁模式挖掘，關(guān)系挖掘，以及相互關(guān)系挖掘
所謂頻繁模式挖掘，指的是比如在商品交易數(shù)據(jù)庫記錄中，找出一起出現(xiàn)的商品集合，這些商品集合出現(xiàn)的頻率要高于一個閾值，這些經(jīng)常出現(xiàn)的商品集合稱之為頻繁模式。
頻繁模式的思路很簡單，首先統(tǒng)計出每個單個商品出現(xiàn)的次數(shù)，這就構(gòu)成了一個一維表。然后再根據(jù)一維表，商品兩兩組合產(chǎn)生一個二維表。然后再由二維表產(chǎn)生三維表，直至到n維表。其中可以利用apriori，進行剪枝，也就是說一維表中如果出現(xiàn)的頻率低于閾值的商品，就可以直接去掉，應(yīng)為包含該商品的高維商品集合的出現(xiàn)頻率不可能高于該閾值，可以直接剪枝去掉。
頻繁模式挖掘還有一種更加高效的方式，就是FP Growth，該方法通過掃描一遍數(shù)據(jù)庫，在內(nèi)存中構(gòu)造一顆FPtree，基于這棵樹就可以產(chǎn)生所有的頻繁模式。很顯然FP Growth算法的效率要高很多，但是其缺陷也很明顯，在內(nèi)存中維護一顆FPtree的開銷也是很大的。為了解決這個問題，一個直接的思路是將數(shù)據(jù)庫水平分表到各臺機器上，在各臺機器上執(zhí)行本地的FPGrowth，然后再將各臺機器上的結(jié)果匯總起來，得到最終的FP Growth的結(jié)果。
所謂關(guān)系挖掘，值得是挖掘出各個項目之間的因果關(guān)系。關(guān)系挖掘的基礎(chǔ)是頻繁模式挖掘，通過頻繁模式挖掘，很容易得出關(guān)系，舉例就很容易明白，比如我們得到一個頻繁集合：
那么通過排列組合可以得到l的子集集合：
那么很容易得到下面的推理集合，也就是挖掘出的關(guān)系：
所有的關(guān)系挖掘本質(zhì)上都是基于頻繁模式推導(dǎo)出來的。
在關(guān)系挖掘中，有一種非常有用的關(guān)系模式挖掘:mining quantitative associationrules。所謂quantitative association rules是這樣一種關(guān)系模式：
該關(guān)系模式的挖掘，首先是確定我們所感興趣的屬性：quan1,quan2,cat，然后根據(jù)事先確定的間隔，將quan1，quan2按照一定的間隔劃分成一定的catorgory，然后進行頻繁模式挖掘，得出一些關(guān)系，然后將這些關(guān)系按照grid進行聚合，生成最后的關(guān)系模式。
通過關(guān)系挖掘挖出的關(guān)系中往往有很多不是非常有用，因此需要通過另外的指標(biāo)排除一些這樣的關(guān)系，這個指標(biāo)就是correlation，如下：
Correlation是用來衡量A，B之間的相關(guān)性，從而排除那些沒有意義的規(guī)則。
對于上述所提到的關(guān)系挖掘，有一種稱之為constraint-based associationmining，這是一種特殊的關(guān)系挖掘，它對于所挖掘出的條件加了一些限制條件，這些限制條件可能是由用戶提出的，其主要目的是排除一些不感興趣的關(guān)系。對于這種關(guān)系挖掘，最直接的辦法先按照最普通的關(guān)系挖掘方法進行挖掘，然后利用條件來對結(jié)果進行。但是還有更好的方法，就是在挖掘的過程中利用這些條件，從而縮小整個挖掘過程中的searchspace，從而提高效率。這些限制條件分為這么幾種：antimonotonic，monotonic，succinct，convertible，inconvertible，針對每一種的限制條件，都有一些通用的方法或策略來縮小挖掘的searchspace，可參閱相關(guān)資料。
分類和預(yù)測
分類樹
分類樹是一種很常用的分類方法，它該算法的框架表述還是比較清晰的，從根節(jié)點開始不斷得分治，遞歸，生長，直至得到最后的結(jié)果。根節(jié)點代表整個訓(xùn)練樣本集,通過在每個節(jié)點對某個屬性的測試驗證,算法遞歸得將數(shù)據(jù)集分成更小的數(shù)據(jù)集.某一節(jié)點對應(yīng)的子樹對應(yīng)著原數(shù)據(jù)集中滿足某一屬性測試的部分數(shù)據(jù)集.這個遞歸過程一直進行下去。
該算法是數(shù)據(jù)挖掘中常用的一類方法。
貝葉斯分類器
貝葉斯分類的思想很簡單，就是計算屬性和分類之間的條件概率，選擇使得條件概率最大的分類作為最終的分類結(jié)果，這是一種基于統(tǒng)計的分類方法，得到了廣泛的引用。
貝葉斯分類器分為兩種，一種是樸素貝葉斯分類器，它基于貝葉斯理論：
其中X代表特征向量, C代表分類.我們的目標(biāo)就是找出使得這個后驗概率最大的那個類.
其中需要注意的是X中的各個特征分量是分布獨立的.這樣就有:
樸素貝葉斯分類器最經(jīng)典的應(yīng)用場景就是垃圾郵件過濾。
樸素貝葉斯分類器的升級版本就是貝葉斯網(wǎng)絡(luò)，因為樸素貝葉斯網(wǎng)絡(luò)假設(shè)樣本的特征向量的各個特征屬性是獨立的，但對于現(xiàn)實世界，這樣的建模未必合理，因此有人就提出了貝葉斯網(wǎng)絡(luò)，貝葉斯網(wǎng)絡(luò)假設(shè)各個屬性之間是存在條件概率的。貝葉斯網(wǎng)絡(luò)是一個各個屬性組成的有向拓撲網(wǎng)絡(luò)，每條邊代表條件概率，通過貝葉斯網(wǎng)絡(luò)能夠計算出各個屬性相互組合的條件概率。
基于規(guī)則的分類器
這種分類器利用IF THEN的規(guī)則來進行分類。對于如何產(chǎn)生規(guī)則，有兩種方法：
第一種方法，就是從決策樹中生成規(guī)則。因為決策樹天然的就是規(guī)則。
第二種方法，是采用Sequential CoveringAlgorithm，直接從訓(xùn)練樣本中生成規(guī)則集。該方法的思路是一種general-to-specific的方法，該方法從一個空規(guī)則開始，然后向規(guī)則中依次逐漸增加屬性測試條件，選擇該屬性測試值（也就是測試分界點，attr< val）的依據(jù)就是是否能夠最大限度得改進規(guī)則的分類質(zhì)量。
基于神經(jīng)網(wǎng)絡(luò)的分類器
神經(jīng)網(wǎng)絡(luò)分類器是依據(jù)屬性構(gòu)造一個網(wǎng)絡(luò)拓撲結(jié)構(gòu)，該拓撲結(jié)構(gòu)的邊具有權(quán)重值，我們的目的是不斷得利用訓(xùn)練樣本然后不斷得更新神經(jīng)網(wǎng)絡(luò)的邊權(quán)重值。然后利用該網(wǎng)絡(luò)就可以得到輸出的分類。
該算法模擬神經(jīng)的組成結(jié)構(gòu)，利用了單元之間的反饋機制。但該算法的缺點也很明顯，網(wǎng)絡(luò)拓撲結(jié)構(gòu)的確定沒有明確統(tǒng)一的方法論，很多只能靠規(guī)劃者的經(jīng)驗，因此訓(xùn)練結(jié)果往往因人而異，限制了神經(jīng)網(wǎng)絡(luò)的使用。
支持向量機分類器
支持向量機是在訓(xùn)練樣本空間中構(gòu)造超平面來對樣本進行分類，它的優(yōu)勢是對高維度不敏感。但效率較低，實施較為復(fù)雜。
關(guān)聯(lián)分類器
關(guān)聯(lián)分類器的思路很簡單，前面我們提到頻繁模式挖掘，我們將樣本的某一屬性的（屬性，值）對作為一個條目，我們找出經(jīng)常在一起出現(xiàn)的條目集合，然后找出這些頻繁項目集合，這些頻繁項目集合對應(yīng)的樣本集合中占主流的分類就作為關(guān)聯(lián)規(guī)則的分類結(jié)果，該結(jié)果如下：
關(guān)聯(lián)分類器有三種方法：CBA， CMAR和CPAR
Lazy Learner
Lazy Learner主要有兩種分類器：Knn分類器和Cbr分類器。
Knn分類器思路很直接，找出和待分類樣本最近的K的樣本，然后將這k個樣本中占主流的的類別作為分類結(jié)果分配給待分類樣本。該分類器的關(guān)鍵在于如何確定k，一種思路是根據(jù)經(jīng)驗，另外一種思路是迭代，讓k從1開始遞增，計算每個k取值時對某一測試集的錯誤率，選擇錯誤最小的那個k。另外一個關(guān)鍵就是如何快速得找出k個最近的鄰居，這需要我們對各個樣本點進行事先排序，并設(shè)計一個合適的數(shù)據(jù)結(jié)構(gòu)，使得找出k個最近鄰居的復(fù)雜度降為log|D|.
預(yù)測
所謂預(yù)測，就是根據(jù)既有的數(shù)據(jù)預(yù)測新出現(xiàn)的數(shù)據(jù)的預(yù)測值。預(yù)測有兩種方法，線性回歸和非線性回歸。所謂線性回歸，指的是
Y = b + wX 公式1
其中X可以是向量，比如(x1,x2)，因此線性回歸則變成
y=w0+w1*x1+w2*x2 公式2
對于公式1，其目標(biāo)就是求出w向量。那么比較常用的方法就是最小二乘法，使得求出的w對于已有的樣本使其方差和最小。方差和就是目標(biāo)函數(shù)，目標(biāo)函數(shù)就是自變量w的一個函數(shù)，通過求導(dǎo)求極值，很容易得到使得目標(biāo)函數(shù)最小的w的值。通過一些軟件包，如SAS，matlab，SPSS很容易做這種線性回歸的w計算。
并不是所有的模型都是線性模型，實際的問題中很多模型是非線性的，比如多項式，如下
y = w0 +w1*x+w2*x*x + w3*x*x*x
解決這種問題的思路是將非線性模型轉(zhuǎn)化為線性模型，然后再用線性回歸的方法來解決。比如上面的多項式公式，我們令
x1=x x2=x*x x3=x*x*x
這樣就變成了y = w0 + w1*x1 + w2*x2 + w3*x3，這就變成了線性回歸的問題。
聚類
聚類是數(shù)據(jù)挖掘需要解決的另外一個問題，分類是我們知道確切的分類結(jié)果，知道我們需要將樣本分成具體的哪幾類。而聚類問題是實現(xiàn)不知道我們的樣本具體屬于哪些類別，而需要我們從樣本中發(fā)掘出這些類別。下面談幾種較為通用的聚類方法談?wù)劇?/p>
基于分區(qū)的聚類法
該方法的一個典型的方法就是K-means，該方法非常簡單，首先確定我們需要將數(shù)據(jù)樣本分成多少個類，這個需要確定，我們稱之為k。然后從樣本中任意選擇k個樣本作為k個類的中心，然后計算每個樣本到這k個中心的距離，把他們分配到最相近的類。這樣就得到k個聚類，然后重新計算這k個聚類的中心，然后再重復(fù)前面的過程，直至沒有樣本被重新分配從而達到收斂。下面是k-means的偽碼
基于層次的分類法
基于層次的分類法有兩種：凝聚和分裂。
凝聚：它基于一種自底而上的策略，在最開始的時候，每個樣本都代表一個聚類，然后計算兩兩之間的區(qū)分度，然后進行合并，這個合并一直按照這樣的方式持續(xù)下去，直至所有的樣本都被合并為一個類。
分裂：它基于一種自上而下的策略，在最開始的時候，所有的樣本都是一個類，然后會依據(jù)一些區(qū)分方法，進行分裂，直至每個樣本都分裂成一個聚類。
基于層次的分類法，其意義在于其他的聚類方法引入這種基于層次的思路，可以被改造成一個多階段的的聚類方法，可以大大改進聚類的質(zhì)量。
基于密度的分類法
這種方法的一個代表就是DBSCAN。要理解DBSCAN，首先要明白這么幾種概念：
某一樣本在e半徑內(nèi)的鄰居稱之為e-鄰居。
如果某一樣本的e-鄰居個數(shù)大于某一最小值，那該樣本被稱之為核心樣本。
如果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，它比較晦澀，從表面上來看，它似乎不是一種顯然的聚類法。首先我們先劃分一些層次，每個層次上我們根據(jù)維度或者概念分層不同的cell，實際上這里的每個層次對應(yīng)的是樣本的一個分辨率。每個高層的cell在其下一層中被對應(yīng)得劃分成多個cell，每個cell我們都計算出它的統(tǒng)計信息，估計出它的分布。利用這樣的結(jié)構(gòu)，我們很容易進行查詢，比如我們查詢具有某些屬性的樣本，我們從上到下開始，根據(jù)cell的統(tǒng)計信息計算query在每個cell的置信區(qū)間，找出最大的那個cell，然后到下一層，依次直至到最底層。這樣的好處是，我們不用計算所有的樣本，算法每進一層都會拋棄不相關(guān)的樣本，所需的計算量會越來越少，那么速度就會很快。
這種方法雖然不是一種顯然的聚類法，但它確實可以用來聚類，因為query返回的樣本實際上就是某一聚類。Query本質(zhì)上于聚類問題是有等價性的。
基于模型的聚類法
這種聚類法可以用來增強K-means。樣本假設(shè)可以被分為K個聚類，每個聚類可以被看成一種分布，比如高斯分布（高斯分布很符合K-means），K個聚類就是K個高斯分布模型，但我們不知道K個模型的具體參數(shù)。由于這是k個不同的高斯模型的混合體，因此每個樣本實際上除了本身屬性值之外還包含了一個隱藏變量（該隱藏變量用以表示該樣本是由哪個高斯模型產(chǎn)生的），這實際上就是一個典型的EM算法的應(yīng)用場景，除了估計這k個模型的參數(shù)，還需要估計隱藏變量。接下來就是利用EM來估計這些參數(shù)（模型參數(shù)和隱藏變量），估計出的隱藏變量就代表樣本的聚類。
對高維樣本進行聚類
CLIQUE是這種方法的一個代表，其思想是從低維到高維（1維到n維）進行查詢，首先在低維空間內(nèi)找到densentiyunit，然后在低維空間的densentiy unit中在繼續(xù)尋找較高維空間中的densentiyunit。它本質(zhì)上也是grid聚類法，它不是一種顯然的聚類法，也是通過query來實現(xiàn)隱式得聚類。
有限制條件的聚類
這種聚類方法需要有一些特別的策略，需要針對不同場景，不能一概而論。這里就不講了。
奇點檢測
檢測奇點非常有用，用于檢測那些不同尋常的數(shù)據(jù)。比如最常用的思路是基于距離的，如果一個樣本在一定距離內(nèi)的鄰居很少，那么他就可以被認為是奇點。另外還有基于統(tǒng)計概率的，基于密度的等等。
聯(lián)系客服
