2021數(shù)據(jù)挖掘十大算法詳解

數(shù)據(jù)挖掘十大算法詳解22目錄介紹0C4.51k-means2SVM3支持向量機3.1拉格朗日對偶3.2最優(yōu)間隔分類器3.3核函數(shù)3.4SMO算法詳解3.5Apriori4EM5PageRank6AdaBoost7kNN8NaiveBayes9CART10數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解PAGE3介紹PAGE3介紹數(shù)據(jù)挖掘十大算法詳解 數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解C4.5PAGE10C4.5PAGE10學(xué)習(xí)筆記--決策樹C4.5 在網(wǎng)上和教材上也看了有很多數(shù)據(jù)挖掘方面的很多知識，自己也學(xué)習(xí)很多，就準(zhǔn)備習(xí)和別人分享的結(jié)合去總結(jié)下，以備以后自己回頭看，看別人總還是比不上自己寫點，及有些不懂或者是沒有必要。定義：分類樹（決策樹）是一種十分常用的分類方法。他是一種監(jiān)管學(xué)習(xí)，所謂監(jiān)管學(xué)習(xí)說白了很簡單，就是給定一堆樣本，每個樣本都有一組屬性和一個類別，這些類別是事先確定的，那么通過學(xué)習(xí)得到一個分類器，這個分類器能夠?qū)π鲁霈F(xiàn)的對象給出正確的分類。這樣的機器學(xué)習(xí)就被稱之為監(jiān)督學(xué)習(xí)。分類本質(zhì)上就是一個map的過程。C4.5分類樹就是決策算法中最流行的一種。算法簡介：1. Function1. FunctionC4.5(R:包含連續(xù)屬性的無類別屬性集合,C:類別屬性,S:訓(xùn)練集)2. 回一棵決策樹*/ 3. Begin 23. EndC4.5C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm);22.再分別構(gòu)造以下樹:21.返回一棵樹，其根標(biāo)記為D;樹枝標(biāo)記為d1,d2...dm;20.將分別由對應(yīng)于D的值為dj的記錄組成的S的子集賦給{sj/j=1,2...m};19.將屬性D的值賦給{dj/j=1,2...m}；18.將R中屬性之間具有最大信息增益的屬性(D,S)賦給D;17.End；16.將Ri點的基于{<=Aj,>Aj}的最大信息增益屬性(Ri,S)賦給A；15.ForjFrom2Tom-1DoAj=A1+j*(A1Am)/m;14.將Rm的最大值賦給Am；/*m值手工設(shè)置*/13.將Ri的最小值賦給A1：12.Begin11.If屬性Ri為連續(xù)屬性，則10.For所有的屬性R(Ri)Do9.[注意未出現(xiàn)錯誤則意味著是不適合分類的記錄]；8.IfR為空,則返回一個單節(jié)點,其值為在S的記錄中找出的頻率最高的類別屬性值;7.返回一個帶有該值的單個節(jié)點;6.IfS是由相同類別屬性值的記錄組成,5.IfS為空,返回一個值為Failure的單個節(jié)點;4.FunctionC4.5(R:FunctionC4.5(R:包含連續(xù)屬性的無類別屬性集合,C:類別屬性,S:訓(xùn)練集)回一棵決策樹*/ Begin IfS為空,返回一個值為Failure的單個節(jié)點; IfS是由相同類別屬性值的記錄組成, 返回一個帶有該值的單個節(jié)點; IfR為空,則返回一個單節(jié)點,其值為在S的記錄中找出的頻率最高的類別屬性值; 著是不適合分類的記錄]； For所有的屬性R(Ri)Do If屬性Ri為連續(xù)屬性，則 Begin ForjFrom2Tom-1DoAj=A1+j*(A1Am)/m; 將Ri點的基于{<=Aj,>Aj}的最大信息增益屬性(Ri,S)賦給A； End； 具有最大信息增益的屬性(D,S)賦給D; 的S的子集賦給{sj/j=1,2...m}; 樹枝標(biāo)記為d1,d2...dm; 再分別構(gòu)造以下樹: C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm); C4.5該算法的框架表述還是比較清晰的，從根節(jié)點開始不斷得分治，遞歸，生長，直至得到最后的結(jié)果。根節(jié)點代表整個訓(xùn)練樣本集,通過在每個節(jié)點對某個屬性的測試驗證,算法遞歸據(jù)集分成更小的數(shù)據(jù)集.某一節(jié)點對應(yīng)的子樹對應(yīng)著原數(shù)據(jù)集中滿足某一屬性測試的部分?jǐn)?shù)據(jù)集.這個遞歸過程一直進行下去,直到某一節(jié)點對應(yīng)的子樹對應(yīng)的數(shù)據(jù)集都屬于同一個類為止例如數(shù)據(jù)集對應(yīng)得到的決策樹如下:分類樹中的測試是怎樣的？分類樹中的測試是針對某一個樣本屬性進行的測試。樣本的屬性有兩種，一種是離散變量，一種是連續(xù)變量。對于離散變量，這很簡單，離散變量對應(yīng)著多個值，每個值就對應(yīng)著測試的一個分支，測試就是驗證樣本對應(yīng)的屬性值對應(yīng)哪個分支。這樣數(shù)據(jù)集就會被分成幾個小組。對于連續(xù)變量，所有連續(xù)變量的測試分支都是2條，其測試分支分別對應(yīng)著就是對應(yīng)的閥值)。如何選擇測試？分類樹中每個節(jié)點對應(yīng)著測試，但是這些測試是如何來選擇呢？C4.5根據(jù)信息論標(biāo)準(zhǔn)來選擇測試，比如增益（在信息論中，熵對應(yīng)著某一分布的信息量，其值同時也對應(yīng)著要完全無損表示該分布所需要的最小的比特數(shù)，本質(zhì)上熵對應(yīng)著不確定性，可能的變化的豐富程度。所謂增益，就是指在應(yīng)用了某一測試之后，其對應(yīng)的可能性豐富程度下降，不確定性減小，這個減小的幅度就是增益，其實質(zhì)上對應(yīng)著分類帶來的好處）或者增益比（這個指標(biāo)實際上就等于增益/熵，之所以采用這個指標(biāo)是為了克服采用增益作為衡量標(biāo)準(zhǔn)的缺點，采用增益作衡量標(biāo)準(zhǔn)會導(dǎo)致分類樹傾向于優(yōu)先選擇那些具有比較多的分支的測試，這種傾向需要被抑制）。算法在進行Tree-Growth時，總是“貪婪得”選擇那些信息論標(biāo)準(zhǔn)最高的那些測試。如何選擇連續(xù)變量的閾值？在《分類樹中的測試是怎樣的？》中提到連續(xù)變量的分支的閾值點為a，這閾值如何確定呢？很簡單，把需要處理的樣本（對應(yīng)根節(jié)點）或樣本子集（對應(yīng)子樹）按照連續(xù)變量的大小從小到大進行排序，假設(shè)該屬性對應(yīng)的不同的屬性值一共有N個，那么總共有N-1個可能的候選分割閾值點，每個候選的分割閾值點的值為上述排序后的屬性值鏈表中兩兩前后連續(xù)元素的中點，那么我們的任務(wù)就是從這個N-1個候選分割閾值點中選出一個，使得前面提到的信息論標(biāo)準(zhǔn)最大。舉個例子，對play數(shù)據(jù)集，我們來處理溫度屬性，來選擇合適的閾值度大小對對應(yīng)樣本進行排序如下：那么可以看到有13個可能的候選閾值點，比如middle[64,65],middle[65,68]….,middle[83,85]。那么最優(yōu)的閾值該選多少呢？應(yīng)該是middle[71,72]，如上圖中紅線所示。為什么呢？如下計算：通過上述計算方式，0.939是最大的，因此測試的增益是最小的。（測試的增益和測試后的熵是成反比的，這個從后面的公式可以很清楚的看到）。根據(jù)上面的描述，我們需要對每個候選分割閾值進行增益或熵的計算才能得到最優(yōu)的閾值，我們需要算N-1次增益或熵（對應(yīng)這個變量而言就是13次計算）。能否有所改進呢？少算幾次，加快速度。答案是可以該進，如下圖：該圖中的綠線代表可能的最優(yōu)分割閾值點，根據(jù)信息論知識，像m（紅線所示）這個分割點，72,75屬于同一個類，這樣的分割點是不可能有信息增益的。（把同一個類了不同的類，這樣的閾值點顯然不會有信息增益，因為這樣的分類沒能幫上忙，減少可能性）哪個屬性是最佳的分類屬性？信息論標(biāo)準(zhǔn)有兩種，一種是增益，一種是增益比。首先來看看增益Gain的計算為了精確地定義信息增益，我們先定義信息論中廣泛使用的一個度量標(biāo)準(zhǔn)，稱為熵（entropy），它刻畫了任意樣例集的純度（purity）。給定包含關(guān)于某個目標(biāo)概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為：上述公式中，p+代表正樣例，比如在本文開頭第二個例子中p+則意味著去打羽毛球，而p-代表反樣例，不去打球。舉例來說，假設(shè)S是一個關(guān)于布爾概念的有14個樣例的集合，它包括9個正例和5個反例（我們采用記號[9+，5-]來概括這樣的數(shù)據(jù)樣例），那么S相對于這個布爾樣例的熵為：EntropyEntropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。上述公式的值為0.940。它的信息論含義就是我要想把Play？這個信息傳遞給別人話，平均來我至少需要0.940個bit來傳遞這個信息。C4.5的目標(biāo)就是經(jīng)過分類來減小這個熵。那么我們來依次考慮各個屬性測試，通過某一屬性測試我們將樣本分成了幾個子集，這使得樣本逐漸變得有序，那么熵肯定變小了。這個熵的減小量就是我們選擇屬性測試的依據(jù)。信息增益Gain(S,A)定義已經(jīng)有了熵作為衡量訓(xùn)練樣例集合純度的標(biāo)準(zhǔn)，現(xiàn)在可以定義屬性分類訓(xùn)練數(shù)據(jù)的效力的度量標(biāo)準(zhǔn)。這個標(biāo)準(zhǔn)被稱為“信息增益（informationgain）”。簡單的說，一個屬性的信息增益就是由于使用這個屬性分割樣例而導(dǎo)致的期望熵降低(或者說，樣本按照某屬性劃分時造成熵減少的期望)。更精確地講，一個屬性A相對樣例集合S的信息增益Gain(S,A)被定義為：其中Values(A)是屬性A所有可能值的集合，是S中屬性A的值為v的子集。換句話來講，Gain(S,A)是由于給定屬性A的值而得到的關(guān)于目標(biāo)函數(shù)值的信息。當(dāng)對S的一個任意成員的目標(biāo)值編碼時，Gain(S,A)的值是在知道屬性A的值后可以節(jié)省的二進制位數(shù)。它的實質(zhì)是把數(shù)據(jù)集D根據(jù)某一屬性測試分成v個子集，這使得數(shù)據(jù)集S變得有序，使得數(shù)據(jù)集S的熵變小了。分組后的熵其實就是各個子集的熵的權(quán)重和。通過計算我們得到Gain(Outlook)=0.940-0.694=0.246，Gain(Windy)=0.940-0.892=0.048….可以得到第一個測試屬性是Outlook。需要注意的是，屬性測試是從數(shù)據(jù)集中包含的所有屬性組成的候選屬性中選擇出來的。對于所在節(jié)點到根節(jié)點的路徑上所包含的屬性（我們稱之為繼承屬性），其實根據(jù)公式很容易得到他們的熵增益是0，因此這些繼承屬性完全不必考慮可以從候選屬性中剔除這些屬性。到這里似乎一切都很完美，增益這個指標(biāo)非常好，但是其實增益這個指標(biāo)有一個缺點。我們來考慮play數(shù)據(jù)集中的Day這個屬性（我們假設(shè)它是一個真屬性，實際上很可能大家不會把他當(dāng)做屬性），y有個不同的值，那么y的屬性測試節(jié)點就會有個分支，很顯支其實都覆蓋了一個“純”數(shù)據(jù)集（所謂“純”，指的就是所覆蓋的數(shù)據(jù)集都屬于同一個類），那么其熵增益顯然就是最大的，那么Day就默認(rèn)得作為第一個屬性。之所以出現(xiàn)這樣Ratio-增益比。C4.5算法之信息增益率增益比率度量是用前面的增益度量Gain(S，A)和分裂信息度量SplitInformation(S，A)來共同定義的，如下所示：其中，分裂信息度量被定義為(分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻)：其中S1到Sc是c個值的屬性A分割S而形成的c個樣例子集。分裂信息實際上就是S關(guān)于屬性A的各值的熵。這與我們前面對熵的使用不同，在那里我們只考慮S關(guān)于學(xué)習(xí)到的樹要預(yù)測的目標(biāo)屬性的值的熵。通過計算我們很容易得到GainRatio(Outlook)=0.246/1.577=0.156。增益比實際上就是對增益進行了歸一化，這樣就避免了指標(biāo)偏向分支多的屬性的傾向。決策樹能夠幫助我們對新出現(xiàn)的樣本進行分類，但還有一些問題它不能很好得解決。們想知道對于最終的分類，哪個屬性的貢獻更大？能否用一種比較簡潔的規(guī)則來區(qū)分樣于哪個類？等等。算法的改進：用信息增益率來選擇屬性。在樹構(gòu)造過程中進行剪枝，在構(gòu)造決策樹的時候，那些掛著幾個元素的節(jié)點，不考慮不然容易導(dǎo)致overfitting。對非離散數(shù)據(jù)也能處理。能夠?qū)Σ煌暾麛?shù)據(jù)進行處理。決策樹的剪枝決策樹為什么要剪枝？原因就是避免決策樹“過擬合”樣本。前面的算法生成的決策樹非常的細(xì)而龐大，每個屬性都被詳細(xì)地加以考慮，決策樹的樹葉節(jié)點所覆蓋的訓(xùn)練樣本都是“純”因此用這個決策樹來對訓(xùn)練樣本進行分類的話，你會發(fā)現(xiàn)對于訓(xùn)練樣本而言，這個樹表現(xiàn)堪稱完美，它可以100%完美正確得對訓(xùn)練樣本集中的樣本進行分類（因為決策樹本身就是100%完美擬合訓(xùn)練樣本的產(chǎn)物）。但是，這會帶來一個問題，如果訓(xùn)練樣本中包含了一些錯誤，按照前面的算法，這些錯誤也會100%一點不留得被決策樹學(xué)習(xí)了，這就是“過擬合”。C4.5的締造者昆蘭教授很早就發(fā)現(xiàn)了這個問題，他作過一個試驗，在某一個數(shù)據(jù)集中，過擬合的決策樹的錯誤率比一個經(jīng)過簡化了的決策樹的錯誤率要高。那么現(xiàn)在的問題就來了，如何在原生的過擬合決策樹的基礎(chǔ)上，通過剪枝生成一個簡化了的決策樹？1、第一種方法，也是最簡單的方法，稱之為基于誤判的剪枝。這樹不是過度擬合么，我再搞一個測試數(shù)據(jù)集來糾正它。對于完全決策樹中的每一個非葉子節(jié)點的子樹，我們嘗試著把它替換成一個葉子節(jié)點，該葉子節(jié)點的類別我們用子樹所覆蓋訓(xùn)練樣本中存在最多的那個類來代替，這樣就產(chǎn)生了一個簡化決策樹，然后比較這兩個決策樹在測試數(shù)據(jù)集中的表現(xiàn)，如果簡化決策樹在測試數(shù)據(jù)集中的錯誤比較少，并且該子樹里面沒有包含另外一個具有類似特性的子樹（所謂類似的特性，指的就是把子樹替換成葉子節(jié)點后，其測試數(shù)據(jù)集誤判率降低的特性），那么該子樹就可以替換成葉子節(jié)點。該算法以bottom-up的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測試數(shù)據(jù)集的表現(xiàn)得以改進時，算法就可以終止。2、第一種方法很直接，但是需要一個額外的測試數(shù)據(jù)集，能不能不要這個額外的數(shù)據(jù)集呢？為了解決這個問題，于是就提出了悲觀剪枝。該方法剪枝的依據(jù)是訓(xùn)練樣本集中的樣本誤判率。我們知道一顆分類樹的每個節(jié)點都覆蓋了一個樣本集，根據(jù)算法這些被覆蓋的樣本集往往都有一定的誤判率，因為如果節(jié)點覆蓋的樣本集的個數(shù)小于一定的閾值，那么這個節(jié)點就會變成葉子節(jié)點，所以葉子節(jié)點會有一定的誤判率。而每個節(jié)點都會包含至少一個的葉子節(jié)點，所以每個節(jié)點也都會有一定的誤判率。悲觀剪枝就是遞歸得估算每個內(nèi)部節(jié)點所覆蓋樣本節(jié)點的誤判率。剪枝后該內(nèi)部節(jié)點會變成一個葉子節(jié)點，該葉子節(jié)點的類別為原內(nèi)部節(jié)點的最優(yōu)葉子節(jié)點所決定。然后比較剪枝前后該節(jié)點的錯誤率來決定是否進行剪枝。該方法和前面提到的第一種方法思路是一致的，不同之處在于如何估計剪枝前分類樹內(nèi)部節(jié)點的錯誤率。連續(xù)值屬性的改進相對于那些離散值屬性，分類樹算法傾向于選擇那些連續(xù)值屬性，因為連續(xù)值的分支，熵增益也最大。算法需要克服這種傾向，我們利用增益率來克服這種傾也可以用來克服連續(xù)值屬性傾向。增益率作為選擇屬性的依據(jù)克服連續(xù)值屬性傾向，這有問題的。但是如果利用增益率來選擇連續(xù)值屬性的分界點，會導(dǎo)樣本分成兩個部分，這兩個部分的樣本個數(shù)之比也會影響增益率。根據(jù)增益率公式，我們以發(fā)現(xiàn)，當(dāng)分界點能夠把樣本分成數(shù)量相等的兩個子集時（我們稱此時的分界點為點），增益率的抑制會被最大化，因此等分分界點被過分抑制了。子集樣本個數(shù)能夠影響界點，顯然不合理。因此在決定分界點是還是采用增益這個指標(biāo)，而選擇屬性的時增益率這個指標(biāo)。這個改進能夠很好得抑制連續(xù)值屬性的傾向。當(dāng)然還制這種傾向，比如MDL。處理缺失屬性如果有些訓(xùn)練樣本或者待分類樣本缺失了一些屬性值，那么該如何處理？要解決這個問題，需要考慮3個問題：當(dāng)開始決定選擇哪個屬性用來進行分支時，如果有些訓(xùn)練樣本缺失了某些屬性值時該怎么辦？一個屬性已被選擇，那么在決定分支的時候如果有些樣本缺失了該屬性該如何處理？當(dāng)決策樹已經(jīng)生成，但待分類的樣本缺失了某些屬性，這些屬性該如何處理？針對這三個問題，昆蘭提出了一系列解決的思路和方法。對于問題i),計算屬性a的增益或者增益率時，如果有些樣本沒有屬性a，那么可以有這么幾種處理方式：忽略這些缺失屬性a的樣本。給缺失屬性a的樣本賦予屬性a一個均值或者最常用的的值。計算增益或者增益率時根據(jù)缺失屬性樣本個數(shù)所占的比率對增益/增益率進行相應(yīng)的“折”。根據(jù)其他未知的屬性想辦法把這些樣本缺失的屬性補全。對于問題ii)，當(dāng)屬性a已經(jīng)被擇，該對樣本進行分支的時候，如果有些樣本缺失了屬性a,那么：忽略這些樣本。把這些樣本的屬性a賦予一個均值或者最常出現(xiàn)的值，然后再對他們進行處理。把這些屬性缺失樣本，按照具有屬性a的樣本被劃分成的子集樣本個數(shù)的相對各個子集中去。至于哪些缺失的樣本被劃分到子集1，哪些被劃分到子集2，這個沒有一定的準(zhǔn)則，可以隨機而動。(A)把屬性缺失樣本分配給所有的子集，也就是說每個子集都有這些屬性缺失樣本。單獨為屬性缺失的樣本劃分一個分支子集。對于缺失屬性a的樣本，嘗試著根據(jù)其他屬性給他分配一個屬性a的值，然后繼續(xù)處劃分到相應(yīng)對于問題iii)，對于一個缺失屬性a的待分類樣本，有這么幾種選擇：如果有單獨的確實分支，依據(jù)此分支。把待分類的樣本的屬性a值分配一個最常出現(xiàn)的a的屬性值，然后進行分支預(yù)測(3)根據(jù)其他屬性為該待分類樣本填充一個屬性a值，然后進行分支處理。在決策樹中屬性a節(jié)點的分支上，遍歷屬性a節(jié)點的所有分支，探索可能所有的分類結(jié)然后把這些分類結(jié)果結(jié)合起來一起考慮，按照概率決定一個分類。待分類樣本在到達(dá)屬性a節(jié)點時就終止分類，然后根據(jù)此時a節(jié)點所覆蓋的葉子節(jié)點類別況為其分配一個發(fā)生概率最高的類。推理規(guī)則C4.5決策樹能夠根據(jù)決策樹生成一系列規(guī)則集,我們可以把一顆決策樹看成一系列規(guī)則的組合。一個規(guī)則對應(yīng)著從根節(jié)點到葉子節(jié)點的路徑，該規(guī)則的條件是路徑上的條件，結(jié)果是葉子節(jié)點的類別。C4.5首先根據(jù)決策樹的每個葉子節(jié)點生成一個規(guī)則集，對于規(guī)則集中的每條規(guī)則，算法利用“爬山”搜索來嘗試是否有條件可以移除，由于移除一個條件和剪枝一個內(nèi)部點本質(zhì)上是一樣的，因此前面提到的悲觀剪枝算法也被用在這里進行規(guī)則簡化。MDL準(zhǔn)則在這里也可以用來衡量對規(guī)則進行編碼的信息量和對潛在的規(guī)則進行排序。簡化后的規(guī)則數(shù)目要遠(yuǎn)遠(yuǎn)小于決策樹的葉子節(jié)點數(shù)。根據(jù)簡化后的規(guī)則集是無法重構(gòu)原來的決策樹的。規(guī)則集相比決策樹而言更具有可操作性，因此在很多情況下我們需要從決策樹中推理出規(guī)則集。C4.5有個缺點就是如果數(shù)據(jù)集增大了一點，那么學(xué)習(xí)時間會有一個迅速地增長。數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解k-meansPAGE12k-meansPAGE12挖掘十大算法--K-均值聚類算法 一、相異度計算在正式討論聚類前，我們要先弄清楚一個問題：如何定量計算兩個可比較元素間用通俗的話說，相異度就是兩個東西差別有多大，例如人類與章魚的相異度明顯大于人類黑猩猩的相異度，這是能我們直觀感受到的。但是，計算機沒有這種直觀感受能力，我們須對相異度在數(shù)學(xué)上進行定量定義。設(shè)，其中X，Y是兩個元素項，各自具有n個可量特征屬性，那么X和Y的相異度定義為：，其中R為實數(shù)域。也就是說相異度是兩個元素對實映射，所映射的實數(shù)定量表示兩個元素的相異度。下面介紹不同類型變量相異度計算方法。1、標(biāo)量標(biāo)量也就是無方向意義的數(shù)字，也叫標(biāo)度變量?，F(xiàn)在先考慮元素的所有特征屬性都是量的情況。例如，計算X={2,1,102}和Y={1,3,2}的相異度。一種很自然的想法是用兩者的歐幾里得距離來作為相異度，歐幾里得距離的定義如下：其意義就是兩個元素在歐氏空間中的集合距離，因為其直觀易懂且可解釋性強，被廣泛用于標(biāo)識兩個標(biāo)量元素的相異度。將上面兩個示例數(shù)據(jù)代入公式，可得兩者的歐氏距離為：除歐氏距離外，常用作度量標(biāo)量相異度的還有曼哈頓距離和閔可夫斯基距離，兩者定義如下：曼哈頓距離：閔可夫斯基距離：皮爾遜系數(shù)(PearsonCorrelationCoefficient)兩個變量之間的皮爾遜相關(guān)系數(shù)定義為兩個變量之間的協(xié)方差和標(biāo)準(zhǔn)差的商.(其中，E為數(shù)學(xué)期望或均值，D為方差，D開根號為標(biāo)準(zhǔn)差，E{[X-ux][Y-uy]}稱為隨機變量X與Y的協(xié)方差，記為Cov(X,Y)，即Cov(X,Y)=E{[X-ux][Y-ux]}，而兩個變量之間的協(xié)方差和標(biāo)準(zhǔn)差的商則稱為隨機變量X與Y的相關(guān)系數(shù)，記為歐氏距離和曼哈頓距離可以看做是閔可夫斯基距離在p=2和p=1下的特例。另外這三種距離都可以加權(quán)，這個很容易理解。下面要說一下標(biāo)量的規(guī)格化問題。上面這樣計算相異度的方式有一點問題，就是取值范圍的屬性對距離的影響高于取值范圍小的屬性。例如上述例子中第三個屬性的取值跨度遠(yuǎn)前兩個，這樣不利于真實反映真實的相異度，為了解決這個問題，一般要對屬性值進行規(guī)化。所謂規(guī)格化就是將各個屬性值按比例映射到相同的取值區(qū)間，這樣是為了平衡各個屬性對距離的影響。通常將各個屬性均映射到[0,1]區(qū)間，映射公式為：其中max(ai)和min(ai)表示所有元素項中第i個屬性的最大值和最小值。例如，將示例中的元素規(guī)格化到[0,1]區(qū)間后，就變成了X’={1,0,1}，Y’={0,1,0}，重新計算歐氏距離約為1.732。2、二元變量所謂二元變量是只能取0和1兩種值變量，有點類似布爾值，通常用來標(biāo)識是或不是這種二屬性。對于二元變量，上一節(jié)提到的距離不能很好標(biāo)識其相異度，我們需要一種更適合的標(biāo)識。一種常用的方法是用元素相同序位同值屬性的比例來標(biāo)識其相異度。設(shè)有X={1,0,0,0,1,0,1,1}，Y={0,0,0,1,1,1,1,1}，可以看到，兩個元素第2、3、5、7和8個屬性取值相同，而第1、4和6個取值不同，那么相異度可以標(biāo)識為3/8=0.375。一般的，對于二元變量，相異度可用“取值不同的同位屬性數(shù)/單個元素的屬性位數(shù)”標(biāo)識。上面所說的相異度應(yīng)該叫做對稱二元相異度?，F(xiàn)實中還有一種情況，就是我們只關(guān)心兩取1的情況，而認(rèn)為兩者都取0的屬性并不意味著兩者更相似。例如在根據(jù)病情對病人聚類時，如果兩個人都患有肺癌，我們認(rèn)為兩個人增強了相似度，但如果兩個人都沒患肺癌，并不覺得這加強了兩人的相似性，在這種情況下，改用“取值不同的同位屬性數(shù)/(單位數(shù)-同取0的位數(shù))”來標(biāo)識相異度，這叫做非對稱二元相異度。如果用1減去非對稱二元相異度，則得到非對稱二元相似度，也叫Jaccard系數(shù)，是一個非常重要的概念。3、分類變量分類變量是二元變量的推廣，類似于程序中的枚舉變量，但各個值沒有數(shù)字或序數(shù)意義顏色、民族等等，對于分類變量，用“取值不同的同位屬性數(shù)/單個元素的全部屬性數(shù)”來標(biāo)識其相異度。4、序數(shù)變量序數(shù)變量是具有序數(shù)意義的分類變量，通?？梢园凑找欢樞蛞饬x排列，如冠軍、亞軍軍。對于序數(shù)變量，一般為每個值分配一個數(shù)，叫做這個值的秩，然后以秩代替原值當(dāng)做量屬性計算相異度。5、向量對于向量，由于它不僅有大小而且有方向，所以閔可夫斯基距離不是度量其相異度的好辦法，一種流行的做法是用兩個向量的余弦度量，其度量公式為：其中||X||表示X的歐幾里得范數(shù)。要注意，余弦度量度量的不是兩二、聚類問題所謂聚類問題，就是給定一個元素集合D，其中每個元素具有n個可觀察屬性，使用某種算法將D劃分成k個子集，要求每個子集內(nèi)部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高。其中每個子集叫做一個簇。與分類不同，分類是示例式學(xué)習(xí)，要求分類前明確各個類別，并斷言每個元素映射到一個類別，而聚類是觀察式學(xué)習(xí)，在聚類前可以不知道類別甚至不給定類別數(shù)量，是無監(jiān)督學(xué)習(xí)的一種。目前聚類廣泛應(yīng)用于統(tǒng)計學(xué)、生物學(xué)、數(shù)據(jù)庫技術(shù)和市場營銷等領(lǐng)域，相應(yīng)的算法也非常的多。本文僅介紹一種最簡單的聚類算法均值（k-ms）算法。1、算法簡介k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類算法。它是將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點，算法的主要思想是通過迭代過程把數(shù)據(jù)集劃分為不同的類別，使得評價聚類性能的準(zhǔn)則達(dá)到最優(yōu)，從而使生成的每個聚類內(nèi)緊湊，類間獨立。這一算法不適合處是對于連續(xù)型具有較好的聚類效果。2、算法描述1、為中心向量c1,c2,…,ck初始化k個種子2、分組:將樣本分配給距離其最近的中心向量由這些樣本構(gòu)造不相交（non-overlapping）的聚類3、確定中心:用各個聚類的中心向量作為新的中心4、重復(fù)分組和確定中心的步驟，直至算法收斂。3、算法k-means算法輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫。輸出：k個簇，使平方誤差準(zhǔn)則最小。算法步驟：為每個聚類確定一個初始聚類中心，這樣就有K個初始聚類中心。將樣本集中的樣本按照最小距離原則分配到最鄰近聚類使用每個聚類中的樣本均值作為新的聚類中心。重復(fù)步驟2.3直到聚類中心不再變化。結(jié)束，得到K個聚PS1、將樣本分配給距離它們最近的中心向量，并使目標(biāo)函數(shù)值減小2、更新簇平均值3、計算準(zhǔn)則函數(shù)E4、劃分聚類方法對數(shù)據(jù)集進行聚類時包括如下三個要點：選定某種距離作為數(shù)據(jù)樣本間的相似性度量上面講到，k-means聚類算法不適合處理離散型屬性，對連續(xù)型屬性比較適合。因此在計據(jù)樣本之間的距離時，可以根據(jù)實際需要選擇歐式距離、曼哈頓距離或者明考斯距離中的一種來作為算法的相似性度量，其中最常用的是歐式距離。下面我再給大家具體介紹一下歐式距離。平均值假設(shè)給定的數(shù)據(jù)集，X中的樣本用d個描述屬性A1,A2…Ad來表示，并且d個描述屬性都是連續(xù)型屬性。數(shù)據(jù)樣本xi=(xi1,xi2,…xid),xj=(xj1,xj2,…xjd)其中，xi1,xi2,…xid和xj1,xj2,…xjd分別是樣本xi和xj對應(yīng)d個描述屬性A1,A2,…Ad的具體取值。樣本xi和xj之間的相似度通常用它們之間的距離d(xi,xj)來表示，距離越小，樣本xi和xj越相似，差異度越??；距離越大，樣本xi和xj越不相似，差異度越大。歐式距離公式如下：選擇評價聚類性能的準(zhǔn)則函數(shù)k-means聚類算法使用誤差平方和準(zhǔn)則函數(shù)來評價聚類性能。給定數(shù)據(jù)集X，其中只包含描述屬性，不包含類別屬性。假設(shè)X包含k個聚類子集X1,X2,…XK；各個聚類子集中的樣本數(shù)量分別為n1，n2,…,nk;各個聚類子集的均值代表點（也稱聚類中心）分別為m1，m2,…,mk。則誤差平方和準(zhǔn)則函數(shù)公式為：相似度的計算根據(jù)一個簇中對象的平均值來進行。將所有對象隨機分配到k個非空的簇中。計算每個簇的平均值，并用該平均值代表相應(yīng)的簇。根據(jù)每個對象與各個簇中心的距離，分配給最近的簇。然后轉(zhuǎn)），重新計算每個簇的平均值。這個過程不斷重復(fù)直到滿足某個準(zhǔn)則三、聚類例子數(shù)據(jù)對象集合S見上表，作為一個聚類分析的二維樣本，要求的簇的數(shù)量k=2。選擇，為初始的簇中心，即 。對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇對O3：顯然O3，故將C2分配給對于O4:因為：所以將O4分配給C2對于O5:因為： 所以講O5分配給C1更新，得到新簇 和計算平方誤差準(zhǔn)則，單個方差為總體平均方差是：（）計算新的簇的中心。重復(fù)（）和（），得到分配給；分配給，分配給2，分配給，分C1。更新，得到新簇。中心為 ，。單個方差分別為總體平均誤差是：由上可以看出，第一次迭代后，總體平均誤差值52.25~25.65，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。PS1、k-means算法的性能分析主要優(yōu)點：是解決聚類問題的一種經(jīng)典算法，簡單、快速。對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。因為它的復(fù)雜度是0(nkt),其中,n是所有對象的數(shù)目,k是簇的數(shù)目,t是迭代的次數(shù)。通常k<<n且t<<n。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時,它的效果較好。主要缺點在簇的平均值被定義的情況下才能使用，這對于處理符號屬性的數(shù)據(jù)不適用。必須事先給出k（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導(dǎo)致不同結(jié)果。它對于“躁聲”和孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。K-Means算法對于不同的初始值，可能會導(dǎo)致不同結(jié)果。解決方法：多設(shè)置一些不同的初值，對比最后的運算結(jié)果）一直到結(jié)果趨于穩(wěn)定結(jié)束，比較耗時和浪資源很多時候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個類別才最合適。這也是K-means法的一個不足。有的算法是通過類的自動合并和分裂，得到較為合理的類K.2、k-means算法的改進方法——k-prototype算法k-Prototype算法：可以對離散與數(shù)值屬性兩種混合的數(shù)據(jù)進行聚類，在k-prototype中定義了一個對數(shù)值與離散屬性都計算的相異性度量標(biāo)準(zhǔn)。K-Prototype算法是結(jié)合K-Means與K-modes算法，針對混合屬性的，解決2個核心問題如下：度量具有混合屬性的方法是，數(shù)值屬性采用K-means方法得到P1，分類屬性采用K-modes方法P2，那么D=P1+a*P2，a是權(quán)重，如果覺得分類屬性重要，則增加a，否則減少a，a=0時即只有數(shù)值屬性更新一個簇的中心的方法，方法是結(jié)合K-Means與K-modes的更新方法。3、k-means算法的改進方法——k-中心點算法k-中心點算法：k-means算法對于孤立點是敏感的。為了解決這個問題，不采用簇中的平均值作為參照點，可以選用簇中位置最中心的對象，即中心點作為參照點。這樣是基于最小化所有對象與其參照點之間的相異度之和的原則來執(zhí)行的。數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解SVMPAGE20SVMPAGE20數(shù)據(jù)挖掘-支持向量機(SVM) 數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解PAGE21支持向量機PAGE21支持向量機最近在看斯坦福大學(xué)的機器學(xué)習(xí)的公開課，學(xué)習(xí)了支持向量機，再結(jié)合網(wǎng)上各位大神的學(xué)習(xí)經(jīng)驗總結(jié)了自己的一些關(guān)于支持向量機知識。一、什么是支持向量機(SVM)?、支持向量機（SrtcrMc，常簡稱為VM）是一種監(jiān)督式學(xué)習(xí)的方法，可廣泛地應(yīng)用于統(tǒng)計分類以及回歸分析。支持向量機屬于一般化線性分類器，這族分類器的特點是他們能夠同時最小化經(jīng)驗誤差與最大化幾何邊緣區(qū)，因此支持向量機也被稱為最大邊緣區(qū)分類器。2、支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超平面，分隔超平面使兩的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。3、假設(shè)給定一些分屬于兩類的2維點，這些點可以通過直線分割，我們要找到一條最優(yōu)的分割線，如何來界定一個超平面是不是最優(yōu)的呢?如下圖：在上面的圖中，a和b都可以作為分類超平面，但最優(yōu)超平面只有一個，最優(yōu)分類平面使間最大化那是不是某條直線比其他的更加合適呢我們可以憑直覺來定義一條評價直線的標(biāo)準(zhǔn):距離樣本太近的直線不是最優(yōu)的，因為這樣的直線對噪聲敏感度高，泛化性較差。因此我們的目標(biāo)是找到一條直線（圖中的最優(yōu)超平面），離所有點的距離最遠(yuǎn)由此SVM算法的質(zhì)是找出一個能夠?qū)⒛硞€值最大化的超平面，這個值就是超平面離所有訓(xùn)練樣本的最小距離。這個最小距離用SVM術(shù)語來說叫做間隔(margin)。二、如何計算最優(yōu)超平面?1、線性分類：我們通常希望分類的過程是一個機器學(xué)習(xí)的過程。這些數(shù)據(jù)點并不需要是中的點，而可以是任意的點（一個超平面，在二維空間中的例子就是一條直線）。我們希望能夠把這些通過一個n-1維的超平面分開，通常這個被稱為線性分類器。有很多分類器都符合這但是我們還希望找到分類最佳的平面，即使得屬于兩個不同類的數(shù)據(jù)點間隔最大的那個面，該面亦稱為最大間隔超平面。如果我們能夠找到這個面，那么這個分類器就稱為最大間隔分類器。我們從下面一個圖開始：中間那條線是wx+b=0，我們強調(diào)所有點盡可能地遠(yuǎn)離中間那條線?？紤]上面3個點A、B和C。從圖中我們可以確定A是×類別的，然而C我們是不太確定的，B還算能夠確定。這樣我可以得出結(jié)論，我們更應(yīng)該關(guān)心靠近中間分割線的點，讓他們盡可能地遠(yuǎn)離中間線，而不是在所有點上達(dá)到最優(yōu)。因為那樣的話，要使得一部分點靠近中間線來換取另外一部分點更加遠(yuǎn)離中間線。同時這個所謂的超平面的的確把這兩種不同形狀的數(shù)據(jù)點分隔開來，在超平面一邊的數(shù)據(jù)點所對應(yīng)y-1，而在另一邊1。我們可以令分類函數(shù)：顯然，f(x)=0，x是位于超平面上的點。我們不妨要求對于所有滿f(x)<0的點其對應(yīng)的y=等于1，而f(x)="">0y=1的數(shù)據(jù)點。如下圖。最優(yōu)超平面可以有無數(shù)種表達(dá)方式，即通過任意的縮放w和b。習(xí)慣上我們使用以下方式來表達(dá)最優(yōu)超平面=1式中 表示離超平面最近的那些點，也可以就可以得到支持向量的表達(dá)式為：y(x+)1，上面說了，我們令兩類的點分別為+1,-1，所以當(dāng)有一個新的點x需要預(yù)測屬于哪個分類的時候，我們用sgn(f(x))，就可以預(yù)測了，sgn表示符號函數(shù)，當(dāng)f(x)>0的時候，sgn(f(x))=+1,當(dāng)f(x)<0的時候sgn(f(x))=–1。通過幾何學(xué)的知識，我們知道點 到超平面的距離為:特別的，對于超平面,表達(dá)式中的分子為1，因此支持向量到超平面的距離是||w||的意思是w的二范數(shù)。紹了間隔(margin),這里表示為,它的取值是最近距離的2倍:M=2/||w||M=2/||w||最大化這個式子等價于最小化||w||,另外由于||w||是一個單調(diào)函數(shù)，我們可以對和前面的系數(shù)，熟悉的同學(xué)應(yīng)該很容易就看出來了，這個式子是為了方便求導(dǎo)。最后最大化轉(zhuǎn)化為在附加限制條件下最小化函數(shù)：即：這是一個拉格朗日優(yōu)化問題，可以通過拉格朗日乘數(shù)法得到最優(yōu)超平面的權(quán)重向量W和偏置b。PS1、咱們就要確定上述分類函數(shù)f(x)=w.x+b（w.x表示w與x的內(nèi)積）中的兩個參數(shù)w和b，通俗理解的話w是法向量，b是截距;2、那如何確定w和b呢？答案是尋找兩條邊界端或極端劃分直線中間的最大間隔（之所以要尋最大間隔是為了能更好的劃分不同類的點，下文你將看到：為尋最大間隔，導(dǎo)出1/2||w||^2，繼而引入拉格朗日函數(shù)和對偶變量a，化為對單一因數(shù)對偶變量a的求解，當(dāng)然，這是后話），從而確定最終的最大間隔分類超平面hyperplane和分類函數(shù)；3、進而把尋求分類函數(shù)f(x)=w.x+b的問題轉(zhuǎn)化為對w，b的最優(yōu)化問題，最終化為對偶因子的求解。數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解PAGE26拉格朗日PAGE26拉格朗日對偶支持向量機(SVM)（二）--拉格朗日對偶（Lagrangeduality） 簡介：1、在之前我們把要尋找最優(yōu)的分割超平面的問題轉(zhuǎn)化為帶有一系列不等式約束的優(yōu)化問題。這個最優(yōu)化問題被稱作原問題。我們不會直接解它，而是把它轉(zhuǎn)化為對偶問題進行解決。2、為了使問題變得易于處理，我們的方法是把目標(biāo)函數(shù)和約束全部融入一個新的函數(shù)，為使問題變得易于處理，我們的方法是把目標(biāo)函數(shù)和約束全部融入一個新的函數(shù)，即拉格朗日函數(shù)，再通過這個函數(shù)來尋找最優(yōu)點。即拉格朗日函數(shù)，再通過這個函數(shù)來尋找最優(yōu)點。3、約束條件可以分成不等式約束條件和等式約束條件，只有等式約束條件的問題我們數(shù)學(xué)課程中已經(jīng)學(xué)習(xí)過了，其解決方法是直接將等式約束加入原問題構(gòu)造出拉格朗日函數(shù)，然后求導(dǎo)即可?，F(xiàn)在考慮更加一般性的問題：帶不等式約束和等式約束的極值問題如何構(gòu)造拉格朗日函數(shù)求解。學(xué)習(xí)拉格朗日對偶原理重要的是理解構(gòu)造所得的原始問題和原函數(shù)的等價性，以及原始問題和對偶問題解得等價性?；貞浺幌轮暗玫降哪繕?biāo)函數(shù)要求解這個式子。我們可以通過求解對偶問題得到最優(yōu)解，這就是線機的對偶算法，這樣做的優(yōu)點在于：一者對偶問題函數(shù)，進而推廣到非線性分類問題。1、我們下看下面的一個式子上面是要求解的目標(biāo)函數(shù)及其條件。我們可以得到拉格朗日公式為在這里被稱為拉格朗日算子。然后分別對w和求偏導(dǎo)，使得偏導(dǎo)數(shù)等于0，然后解出；下面我們將要產(chǎn)生一個既有等式又有不等式條件限制的式子，我們可以叫做原始優(yōu)化問題，這里簡單介紹下拉格朗日對偶的原理。如下式子：上述式子有兩個條件（等式條件和不等式條件）由此我們定義一般化的拉格朗日公式這里的 和都是拉格朗日算子。不要忘了我們求解的是最小值。設(shè)如下等式：這里的P代表rm。我們設(shè)如下約束條件（rmlcsrs）：如果條件不全部滿足的話，我們總可以調(diào)整 和使最大值出現(xiàn)正無窮，即會出現(xiàn)下面況：因此我們可以得出如下式子：這樣我們原來要求的minf(w)可以轉(zhuǎn)換成求了。同時我們設(shè)將問題轉(zhuǎn)化為先求拉格朗日關(guān)于的最小值，這個時候就把 和 看做常量。之再求最大值。如下：這個問題就是原問題的對偶問題，相對于原問題只是更換了min和max的順序，而一般更換順序的結(jié)果是MaxMin(X)<=MinMax(X)。然而在這里兩者相等。由此我們可以設(shè)如下：所以在一定的條件下我們可以得到：因此我們可以解決原問題的對偶問題，但是我們還要看看條件是什么。假設(shè)f和g都是凸函數(shù)，h是仿射的(仿射的含義：存在ai,bi，使，并且還在w使得所有的i都有；有了以上的假設(shè)，那么一定會存在使得是原問題的解，是對偶問題的解。同時也滿足另外， 還滿足Krs-K-ckr（KKTcondition），如下式子：所以 如果滿足了KKT條件，那么他們就是原問題和對偶問題的解。我們從式子和式子可以看出如果那么，這個也就說明 時，w處于可行域的邊界上，這時才是起作用的約束。而其他位于可行域內(nèi)部的（）點都是不起作用的約束，其中也就是的候。這個KKT雙重補足條件會用來解釋支持向量和SMO的收斂測試。數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解PAGE30最PAGE30最優(yōu)間隔分類器支持向量機(SVM)（三）--最優(yōu)間隔分類器（optimalmarginclassifier） 在之前為了尋找最有分類器，我們提出了如下優(yōu)化問題：在這里我們可以把約束條件改寫成如下：首先我們看下面的圖示：很顯然我們可以看出實線是最大間隔超平面，假設(shè)×號的是正例，圓圈的是負(fù)例。在虛線點和在實線上面的兩個一共這三個點稱作支持向量?，F(xiàn)在我們結(jié)合KKT條件分析下這個圖。我們從式子 和式子可以看出如果那么，這個也就說明時，w處于可行域的邊界上，這時才是起作用的約束1、那我們現(xiàn)在可以構(gòu)造拉格朗日函數(shù)如下：注意到這里只有沒是因為原問題中沒有等式約束，只有不等式約束。2、接下來我們對w和b分別求偏導(dǎo)數(shù)。并得到3、將上式帶回到拉格朗日函數(shù)中得到：由于，因此簡化為在我們得到了關(guān)于w和b的可以最小化的等式，我們在聯(lián)這個參數(shù)，當(dāng)然他的條件還>=0，現(xiàn)在我們可以得到如下的二元優(yōu)化等式了：5、現(xiàn)在你還必須知道我們之前講解的條件一是 ，二是KKT條件：存在w使得對于所有的i。因此，一定存 使 是原問題的解 是對偶問的解。如果求出（也就是 ），根據(jù)即可求出w（也是 ，原問題的解）。然后即可求出b。即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。6、現(xiàn)在我們在看另外一個問題：由所這里我們將向量內(nèi) 表示現(xiàn)在可以看出我要計算等式的話就只需要計算向量的內(nèi)積就好了，同時要在支持向量上的話，那，這樣就更簡單了，因此很多的值都是0。數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解PAGE33核函數(shù)PAGE33核函數(shù)支持向量機（四）--核函數(shù) 一、核函數(shù)的引入問題：SVM顯然是線性分類器，但數(shù)據(jù)如果根本就線性不可分怎么辦？解決方案1：數(shù)據(jù)在原始空間（稱為輸入空間）線性不可分，但是映射到高維空間（稱為特征空間）后很可能就線性可分了。問題：映射到高維空間同時帶來一個問題：在高維空間上求解一個帶約束的優(yōu)化問題顯然比在低維空間上計算量要大得多，這就是所謂的“維數(shù)災(zāi)難”。解決方案：于是就引入了“核函數(shù)”，核函數(shù)的價值在于它雖然也是講特征進行從低維到高維的轉(zhuǎn)換。二、實例說明例如圖中的兩類數(shù)據(jù)，分別分布為兩個圓圈的形狀，不論是任何高級的分器，只要它是線性的，就沒法處理，SVM也不行。因為這樣的數(shù)據(jù)本身就是線性不可分的。從上圖我們可以看出一個理想的分界應(yīng)該是一個“圓圈”而不是一條線（超平面）。如果用X1和X2來表示這個二維平面的兩個坐標(biāo)的話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：a1X1+a2X21+a3X2+a4X22+a5X1X2+a6=0a1X1+a2X21+a3X2+a4X22+a5X1X2+a6=0注意上面的形式，如果我們構(gòu)造另外一個五維的空間，其中五個坐標(biāo)的值分別為Z1=X1,Z2=X21,Z3=X2,Z4=X22,Z5=X1X2，那么顯然，上面的方程在新的坐標(biāo)系下可以寫作：∑i=15aiZi+a6=0∑i=15aiZi+a6=0關(guān)于新的坐標(biāo)Z，這正是一個超平面的方程！也就是說，如果我們做一個映射?:R2→R5，將X按照上面的規(guī)則映射為Z，那么在新的空間中原來的數(shù)據(jù)將變成線性可分的，從而使用之前我們推導(dǎo)的線性分類算法就可以進行處理了。這正是Kernel方法處理非線性問題的基本思想。三、詳細(xì)分析還記得之前我們用內(nèi)積這里是二維模型，但是現(xiàn)在我們需要三維或者更高的維來表示樣本。這里我們假設(shè)是維度是三；那么首先需要將特征x擴展到三維，然后尋找特征和結(jié)果之間的模型。我們將這種征變換稱作特征映射（rem）。映射函數(shù)稱作，在這個例子中我們希望將得到的特征映射后的特征應(yīng)用于SVM分類，而不是最初的特征。這樣，我們將前面公式中的內(nèi)積從，映射到。為什么需要映射后的特征而不是最初的特征來參與計算，一個重要原因是樣例可能存在線性不可分的情況，而將特征映射到高維空間后，往往就可分了。核函數(shù)的定義：將核函數(shù)形式化定義，如果原始特征內(nèi)積是，映射后為，那么定義核函數(shù)（Kr）為現(xiàn)在有了以上的概念，我們現(xiàn)在要計算K(x,z)只要簡單的計算，然后計算，在出它們的內(nèi)積。但是現(xiàn)在有一個問題，那是計算K(x,z)的時間復(fù)雜度是提高了。即使是計算也是很復(fù)雜的。那現(xiàn)在怎么解決呢？現(xiàn)在我們假設(shè)：x，z都是n維，同時有展開發(fā)現(xiàn)我們可以只計算原始特征x和z內(nèi)積的平方（時間復(fù)雜度是()），就等價與計特征的內(nèi)積。也就是說我們不需要時間了。現(xiàn)在看一下映射函數(shù)（=時），根據(jù)上面的公式，得到也就是說核函數(shù)只能在選擇這樣的作為映射函數(shù)時才能夠等價于映射后特征內(nèi)積。再看一個核函數(shù)對應(yīng)的映射函數(shù)（=時）是更一般地，核函數(shù)對應(yīng)的映射后特征維度為 四、如何映射到核函數(shù)現(xiàn)在介紹了核函數(shù)之后那到底怎么來使用核函數(shù)到樣本了？設(shè)超平面實際的方程是這個樣子（圓心在X2軸上的一個正圓）：a1X21+a2(X2?c)2+a3=0a1X21+a2(X2?c)2+a3=0因此我只需要把它映射到Z1=X21,Z2=X22,Z3=X2這樣一個三維空間中即可，下圖是映射之后的結(jié)果，將坐標(biāo)軸經(jīng)過適當(dāng)?shù)男D(zhuǎn)，就可以很明顯地看出，數(shù)據(jù)是可以通過一個平面來分開的：現(xiàn)在讓我們SVM的情形，假設(shè)原始的數(shù)據(jù)時非線性的，我們通過?(?)射到一個高維空間中，數(shù)據(jù)變得線性可分了，這個時候，我們就可以使用原來的推導(dǎo)來進行計算，只是所有的推導(dǎo)現(xiàn)在是在新的空間，而不是原始空間中進行。我們上一次得到的最終的分類函數(shù)是這樣的：現(xiàn)在則是在映射過后的空間，即：而其中的α也是通過求解如下dual問題而得到的：回到我們之前構(gòu)造的一個五維的空間：到現(xiàn)在貌似我們還沒有用到核函數(shù)，但是現(xiàn)在我們以看出，數(shù)據(jù)映射到新空間后，因為新空間是多維的，計算量肯定是增加了不少了，現(xiàn)只能用核函數(shù)來解決了。不妨還是從最開始的簡單例子出發(fā)，設(shè)兩個向量和 ，而?(*)即是到前面說的五維空間的映射，五個坐標(biāo)的值分別為Z1=X1,Z2=X21,Z3=X2,Z4=X22,Z5=X1X2，因此映射過后的內(nèi)積為：根據(jù)我們之前簡介的核函數(shù)的實現(xiàn)，具體來說，上面這個式子的計算結(jié)果實際上映射了這樣一來計算的問題就算解決了，避開了直接在高維空間中進行計算，而結(jié)果卻是等價的。五、高斯核函數(shù)再看另外一個核函數(shù)這時，如果x和z很相近（核函數(shù)值為1，如果x和z相差很大（），那么核函數(shù)值約等于0。由于這個函數(shù)類似于高斯分布，因此稱為高斯核函數(shù)，也叫做徑向基函數(shù)(RadialBasisFunction簡稱RBF)。它能夠把原始特征映射到無窮維。既然高斯核函數(shù)能夠比較x和z的相似度，并映射到0到1，回想logistic回歸，sigmoid函數(shù)可以，因此還有sigmoid核函數(shù)等等。注意，使用核函數(shù)后，怎么分類新來的樣本呢？線性的時候我們使用SVM學(xué)習(xí)出w和b，新來樣本x的話，我們使用 來判斷，如果值大于等于1，那么是正類，小于等于是負(fù)類。兩者之間，認(rèn)為無法確定。如果使用了核函數(shù)后，就變成了，是否先要找到，然后再預(yù)測？答案肯定不是了，找很麻煩，回想我們之前說過的只需將替換成，然后值的判斷同上。總結(jié)：對于非線性的情況，SVM的處理方法是選擇一個核函數(shù)κ(*)，通過將數(shù)據(jù)映射到高維空間，來解決在原始空間中線性不可分的問題。由于核函數(shù)的優(yōu)良品質(zhì)，這樣的非線性擴展在計算量上并沒有比原來復(fù)雜多少，這一點是非常難得的。當(dāng)然，這要歸功于核方法——除了SVM之外，任何將計算表示為數(shù)據(jù)點的內(nèi)積的方法，都可以使用核方法進行非線性擴參考文檔：（主要的參考文檔來自4個地方）1、支持向量機:Kernel2、JerryLead關(guān)于核函數(shù)的講解3、支持向量機通俗導(dǎo)論（理解SVM的三層境界4、斯坦福大學(xué)機器學(xué)習(xí)的公開課。數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解SMO算法詳SMO算法詳解PAGE39支持向量機(SVM)（五）--SMO算法詳解 一、我們先回顧下SVM問題。A、線性可分問題1、SVM基本原理：SVM使用一種非線性映射，把原訓(xùn)練數(shù)據(jù)映射到較高的維。在新的維面，兩個類的數(shù)據(jù)總可以被超平面分開。2、問題的提出：3、如何選取最優(yōu)的劃分直線f(x)呢？4、求解：凸二次規(guī)劃建立拉格朗日函數(shù)：求偏導(dǎo)數(shù)：B、線性不可分問題1、核函數(shù)如下圖：橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負(fù)類.設(shè)：g(x)轉(zhuǎn)化為f(y)=g(x)=f(y)=ay在任意維度的空間中，這種形式的函數(shù)都是一個線性函數(shù)（只不過其中的a和y都是多維向量罷了），因為自變量y的次數(shù)不大于1。下圖w，x都是1000維，w’和x’分別是由w，x變換得到的2000維向量g(x)=K(w,x)+bK(w,x)被稱作核函數(shù)基本作用：接受兩個低維空間里的向量，能夠計算出經(jīng)過某個變換后在高維空間里的向量內(nèi)積值。2、松弛變量、軟間隔-SVM：C是一個由用戶指定的系數(shù)，表示對分錯的點加入多少的懲罰，當(dāng)C很大的時候，分錯的點就會更少，但是過擬合的情況可能會比較嚴(yán)重，當(dāng)C很小的時候，分錯的點可能會很多，不過能由此得到的模型也會不太正確總結(jié)：SVM算法優(yōu)點：(1)非線性映射是SVM方法的理論基礎(chǔ),SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射；(2)對特征空間劃分的最優(yōu)超平面是SVM的目標(biāo),最大化分類邊際的思想是SVM方法的核心；(3)支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類決策中起決定性作用。因此，模型需要存儲空間小，算法魯棒性（Robust）強。SVM算法缺點：SVM算法對大規(guī)模訓(xùn)練樣本難以實施由于SVM是借助二次規(guī)劃來求解支持向量，而求解二次規(guī)劃將涉及m階矩陣的計算（m為樣本的個數(shù)），當(dāng)m數(shù)目很大時該矩陣的存儲和計算將耗費大量的機器內(nèi)存和運算時間。用SVM解決多分類問題存在困難經(jīng)典的支持向量機算法只給出了二類分類的算法，而在數(shù)據(jù)挖掘的實際應(yīng)用中，一般要解決多類的分類問題?；谝陨蠁栴}，我們現(xiàn)在討論SM（SlMmlmznrm）算法。1、SMO算法的原理這一被稱為“順次最小優(yōu)化”的算法和以往的一些SVM改進算法一樣，是把整個二次規(guī)劃問題分解為很多易于處理的小問題，所不同的是，只有SMO算法把問題分解到可能達(dá)到的最小規(guī)模：每次優(yōu)化只處理兩個樣本的優(yōu)化問題，并且用解析的方法進行處理。我們將會看到，這種與不同的方法帶來了一系列不可比擬的優(yōu)勢。對SVM來說，一次至少要同時對兩個樣本進行優(yōu)化（就是優(yōu)化它們對應(yīng)的Lagrange乘子這是因為等式約束的存在使得我們不可能單獨優(yōu)化一個變量。所謂“最小優(yōu)化”的最大好處就是使得我們可以用解析的方法求解每一個最小規(guī)模的優(yōu)化問題，從而完全避免了迭代算法。當(dāng)然，這樣一次“最小優(yōu)化”不可能保證其結(jié)果就是所優(yōu)化的Lagrange乘子的最終結(jié)果，但會使目標(biāo)函數(shù)向極小值邁進一步。我們再對其它Lagrange乘子做最小優(yōu)化，直到所有乘子都符合KKT條件時，目標(biāo)函數(shù)達(dá)到最小，算法結(jié)束。這樣，SMO算法要解決兩個問題：一是怎樣解決兩個變量的優(yōu)化問題，二是怎樣決定先對哪些Lagrange乘子進行優(yōu)化。2、兩個Lagrange乘子的優(yōu)化問題我們在這里不妨設(shè)正在優(yōu)化的兩個Lagrange乘子對應(yīng)的樣本正是第一個和第二個，對兩個Lagrange乘子α1和α2，在其他乘子不改變的情況下，它們的約束條件應(yīng)表達(dá)為正方形內(nèi)的一條線段。（如圖）在這條線段上求一個函數(shù)的極值，相當(dāng)于一個一維的極值問題。我們可以把α1用α2表示，對α2求無條件極值，如果目標(biāo)函數(shù)是嚴(yán)格上凹的，最小值就一定在這一極值點（極值點在區(qū)間內(nèi)）或在區(qū)間端點（極值點在區(qū)間外）。α2確定后，α1也就確定下來了。因此我們先找到優(yōu)化區(qū)間的上下限制，再在這個區(qū)間中對α2求最小值。由圖1我們?nèi)菀椎玫溅?的上下限應(yīng)為：L=max(0,α2－α1)，H=min(C,C+α2–α1若y1與y2異號；L=max(0,α2+α1－CH=min(Cα2+α1若y1與y2同號；令s=y1y2標(biāo)志這兩個樣本是否同類，則有L=max(0α2+sα11/2(s+1)CH=min(Cα2+sα1–1/2(s－1)C)而α1和α2在本次優(yōu)化中所服從的等式約束為：α1＋sα2=α01+sα02=d下面我們推導(dǎo)求最小值點α2的公式：由于只有α1，α2兩個變量需要考慮，目標(biāo)函數(shù)可以寫成1 3i3 lil 11i 1Wolfe(α1,α2)=1/2K11α2+1/2K22α2+sK12α1α2+y1α1v1+y2α2v2－α1－α2+常數(shù)其中Kij=K(xi,xj),vi=y3α0K+…+ylα0K=ui+b0－y11 3i3 lil 11i 1上標(biāo)為0的量表示是本次優(yōu)化之前Lagrange乘子的原值。將α2用α1表示并代入目標(biāo)函數(shù)：2（α）=2K(-sα)+Kα2+sK(-sα)α+y(-sα)v–+sα+yαv－2α2+常數(shù)對α2求導(dǎo)：dWolfe(α2)/dα2=－sK11(d－sα2)+K22α2－K12α2+sK12(d－sα2)－y2v2+s+y2v2－1＝0如果Wolfe函數(shù)總是嚴(yán)格上凹的，即二階導(dǎo)數(shù)K11+K22－2K12>0,那么駐點必為極小值點，無條件的極值點就為α2＝[s(K11－K12)d+y2(v1－v2)＋1－s]/(K11＋K22－2K12)2 12 將d,v與α0,u之間關(guān)系代入，就得到用上一步的α0，u,u表示的α的無條件最2 12 2 22 12 2 1 2 2 1 22 α2＝[α0(K ＋K －2K )+y(u－u＋y－y)]/2 22 12 2 1 2 2 1 22 令η=K11＋K22－2K12為目標(biāo)函數(shù)的二階導(dǎo)數(shù)，Ei=ui－yi為第i個訓(xùn)練樣本的“誤差”，這個式子又可以寫為2 2 1 α2＝α0＋y(E－2 2 1 除非核函數(shù)K不滿足Mercer條件（也就是說不能作為核函數(shù)），η不會出現(xiàn)負(fù)值。但η=0是可以出現(xiàn)的情況。這時我們計算目標(biāo)函數(shù)在線段兩個端點上的取值，并將Lagrange乘子修正到目標(biāo)函數(shù)較小的端點上：f1=y1(E1+b)－α1K(x1,x1)－sα2K(x1,x1)f2=y2(E2+b)－sα1K(x1,x2)－α2K(x2,x2)L1=α1+s(α2－L)H1=α1+s(α2－H)11WolfeL=L1f1+Lf2+1/2L2K(x1,x1)+1/2L2K(x2,x2)+sLL1K(x1,x2)WolfeH=H1f1+Hf2+1/2H2K(x1,x1)+1/2H2K(x2,x2)+sHH1K(x1,x2)11當(dāng)兩個端點上取得相同的目標(biāo)函數(shù)值時，目標(biāo)函數(shù)在整條線段上的取值都會是一樣的（因為它是上凹的），這時不必對α1，α2作出修正。α2的無條件極值確定后，再考慮上下限的限制，最終的α2為最后，由等式約束確定α：1 1 2 α*=α+s(α－α*1 1 2 3、SMO算法、SMO算法的目的無非是找出一個函數(shù)f(x)，這個函數(shù)能讓我們把輸入的數(shù)據(jù)x進行分類將一個凸二次規(guī)劃問題轉(zhuǎn)換成下列形式（KK條件）這里的ai是拉格朗日乘子(問題通過拉格朗日乘法數(shù)來求解)對于（）的情況，表明是正常分類，在邊界內(nèi)部（我們知道正確分類的點對于（）的情況，表明了是支持向量，在邊界上對于（c）的情況，表明了是在兩條邊界之間而最優(yōu)解需要滿足KK條件，即滿足（）（）（c）條件都滿足、以下幾種情況出現(xiàn)將會出現(xiàn)不滿足：yiui<=1但是ai<C則是不滿足的,而原本ai=Cyiui>=1但是ai>0則是不滿足的而原本ai=0yiui=1但是ai=0或者ai=C則表明不滿足的，而原本應(yīng)該是0<ai<C所以要找出不滿足KKT的這些ai，并更新這些ai，但這些ai又受到另外一個約束，即通過另一個方法，即同時更新ai和aj，滿足以下等式就能保證和為0的約束。利用上面的式子消去ai得到一個關(guān)于單變量aj的一個凸二次規(guī)劃問題，不考慮其約束0<=aj<=C,可以得其解為：其中：aj表示舊值，然后考慮約束0<=aj<=C可得到a的解析解為：其中：輸入是x，是一個數(shù)組，組中每一個值表示一個特征。輸出是A類還是B類。（正類還是負(fù)類）4、SMO算法的特點和優(yōu)勢SMO算法和以往流行的SVM優(yōu)化算法如塊算法、固定工作樣本集法相比，既有共同點，又有自己的獨特之處。共同點在于它們都是把一個大的優(yōu)化問題分解為很多小問題來處理。塊算法在每一步中將新加入樣本中違反KKT條件的樣本與原有的支持向量一起組成小問題的樣本集進行優(yōu)化，優(yōu)化完畢后只保留其中的支持向量，再加進來新的樣本進入下一步。固定工作樣本集法是每一步只收集新加入樣本中“最壞”的樣本，并將原來保留的支持向量集中“較好”的替換出去，以保持樣大小不變。SMO則是把每一步的優(yōu)化問題縮減到了最小，它可以看作是固定工作樣本集法的一種特殊情況：把工作樣本集的大小固定為2，并且每一步用兩個新的Lagrange乘子替換乘子。SMO的最大特色在于它可以采用解析的方法而完全避免了二次規(guī)劃數(shù)值解法的復(fù)雜迭代過程。這不但大大節(jié)省了計算時間，而且不會牽涉到迭代法造成的誤差積累（其它一些算法中這種誤差積累帶來了很大的麻煩）。理論上SMO的每一步最小優(yōu)化都不會造成任何誤差積用雙精度數(shù)計算，舍入誤差幾乎可以忽略，于是所有的誤差只在于最后一遍檢驗時以多大的公差要求所有Lagrange乘子滿足KKT條件?？梢哉fSMO算法在速度和精度兩方面都得到了保證。SMO在內(nèi)存的節(jié)省上也頗具特色。我們看到，由于SMO不涉及二次規(guī)劃數(shù)值核函數(shù)矩陣整個存在內(nèi)存里，而數(shù)值解法每步迭代都要拿這個矩陣作運算。（個樣本的核函算法那樣成平方增長。在我們的程序中SMO算法最多占用十幾兆內(nèi)存。SMO使得存儲空間問題不再是SVM應(yīng)用中的另一個瓶頸。SMO算法對線性支持向量機最為有效，對非線性則不能發(fā)揮出全部優(yōu)勢，這是因為線性情況下每次最小優(yōu)化后的重置工作都是很簡單的運算，而非線性時有一步加權(quán)求和，占用了主要的時間。其他算法對線性和非線性區(qū)別不大，因為凡是涉及二次規(guī)劃數(shù)值解的算法都把大量時間花在求數(shù)值解的運算中了。當(dāng)大多數(shù)Lagrange乘子都在邊界上時，SMO算法的效果會更好。盡管SMO的計算時間仍比訓(xùn)練集大小增長快得多，但比起其它方法來還是增長得慢一個等級。因此SMO較適合大數(shù)量的樣本。數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解AprioriPAGE49AprioriApriori算法 一、Apriori算法概述Apriori算法是一種最有影響力的挖掘布爾關(guān)聯(lián)規(guī)則的頻繁項RakeshAgrawal和RamakrishnanSkrikant提出的。它使用一種稱作逐層搜索的迭代方法，k-項集用于探索（k+）-項集。首先，找出頻繁-項集的集合。該集合記作。1用于找頻繁-項L2，而L2用于找L2k-項Lk需要一次數(shù)據(jù)庫掃描。為提高頻繁項集逐層產(chǎn)生的效率，一種稱作Apriori性質(zhì)的重要性用于壓縮搜索空間。其運行定理在于一是頻繁項集的所有非空子集都必須也是頻繁的，二是非頻繁項集的所有父集都是非頻繁的。二、問題的引入購物籃分析：引發(fā)性例子Question：哪組商品顧客可能會在一次購物時同時購買？關(guān)聯(lián)分析Ss：：經(jīng)常同時購買的商品可以擺近一點，以便進一步刺激這些商品一起銷售。2：規(guī)劃哪些附屬商品可以降價銷售，以便刺激主體商品的捆綁銷售。三、關(guān)聯(lián)分析的基本概念1、支持度關(guān)聯(lián)規(guī)則A->B的支持度support=P(AB)，指的是事件A和事件B同時發(fā)生的概率。2、置信度置信度confidence=P(B|A)=P(AB)/P(A),指的是發(fā)生事件A的基礎(chǔ)上發(fā)生事件B的概率。比如說在規(guī)則Computer=>antivirus_software,其中support=2%,confidence=60%中，就表示的意思是所有的商品交易中有2%的顧客同時買了電腦和殺毒軟件，并且購買電腦的顧客中有60%也購買了殺毒軟件。3、k項集如果事件A中包含k個元素，那么稱這個事件A為k項集，并且事件A滿足最小支持度閾值的事件稱為頻繁k項集。4、由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則K維數(shù)據(jù)項集LK是頻繁項集的必要條件是它所有K-1維子項集也為頻繁項集，記為LK-1如果K維數(shù)據(jù)項集LK的任意一個K-1維子集Lk-1，不是頻繁項集，則K維數(shù)據(jù)項集LK不是最大數(shù)據(jù)項集。Lk是K維頻繁項集，如果所有K-1維頻繁項集合Lk-1中包含LK的K-1維子項K，則Lk不可能是K維最大頻繁數(shù)據(jù)項集。同時滿足最小支持度閥值和最小置信度閥值的規(guī)則稱為強規(guī)則。例如：用一個簡單的例子說明。表1是顧客購買記錄的數(shù)據(jù)庫D，包含6個事務(wù)。項集I={網(wǎng)球拍,網(wǎng)球,運動鞋,羽毛球}?？紤]關(guān)聯(lián)規(guī)則：網(wǎng)球拍 網(wǎng)球，事務(wù)1,2,3,4,6包含網(wǎng)球拍，事務(wù)1,2,6同時包含網(wǎng)球拍和網(wǎng)球，支持度，置信度。若給定最小支持度 ，最小置信度，關(guān)聯(lián)規(guī)則網(wǎng)球拍 網(wǎng)球是有趣的，認(rèn)為購買網(wǎng)球拍和購買網(wǎng)球之間存在強關(guān)聯(lián)。四、Apriori算法的基本思想：Apriori算法過程分為兩個步驟：第一步通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項集，即支持度不低于用戶設(shè)定的閾值的項集；第二步利用頻繁項集構(gòu)造出滿足用戶最小信任度的規(guī)則。具體做法就是：首先找出頻繁-項集，記為；然后利用來產(chǎn)生候選項集，對中的項進行判定挖掘出L2，即頻繁2-項集；不斷如此循環(huán)下去直到無法發(fā)現(xiàn)更多的頻繁k-項集為止。每挖掘一層Lk需要掃描整個數(shù)據(jù)庫一遍。算法利用了一個性質(zhì)：Apriori性質(zhì)：任一頻繁項集的所有非空子集也必須是頻繁的。意思就是說，生成一個k-itemset的候選項時，如果這個候選項有子集不在(k-1)-itemset(已經(jīng)確定是frequent的)中時，那么這個候選項就不用拿去和支持度判斷了，直接刪除。具體而言：連接步為找出Lk（所有的頻繁k項集的集合），通過將Lk-1（所有的頻繁k-1項集的集合）與自身連接產(chǎn)生候選k項集的集合。候選集合記作Ck。設(shè)l1和l2是Lk-1中的成員。記li[j]表示li中的第j項。假設(shè)Apriori算法對事務(wù)或項集中的項按字典次序排序，即對于（k-1）項集li，li[1]i</sub>[2]<……….i</sub>[k-1]。將Lk-1與自身連接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&& &&(l1[k-2]=l2[k-2])&&(l1[k-1]2</sub>[k-1])，那認(rèn)為l1和l2是可連接。連接l1和l2產(chǎn)生的結(jié)果是{l1[1],l1[2],……,l1[k-1],l2[k-1]}。剪枝步CK是LK的超集，也就是說，CK的成員可能是也可能不是頻繁的。通過掃描所有的事務(wù)（交易），確定CK中每個候選的計數(shù)，判斷是否小于最小支持度計數(shù)，如果不是，則認(rèn)為該候是頻繁的。為了壓縮Ck,可以利用Apriori性質(zhì)：任一頻繁項集的所有非空子集也必須是頻繁的，反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。五、實例說明實例一：下面以圖例的方式說明該算法的運行過程：假設(shè)有一個數(shù)據(jù)庫D，其中有4個事務(wù)記錄，分別表示為：這里預(yù)定最小支持度minSupport=2,下面用圖例說明算法運行的過程：1、掃描D，對每個候選項進行支持度計數(shù)得到表C1:、比較候選項支持度計數(shù)與最小支持度mSr，產(chǎn)生維最大項目集：、由產(chǎn)生候選項集：4、掃描D，對每個候選項集進行支持度計數(shù):、比較候選項支持度計數(shù)與最小支持度mSr，產(chǎn)生維最大項目集：、由產(chǎn)生候選項集：、比較候選項支持度計數(shù)與最小支持度mSr，產(chǎn)生維最大項目集：算法終止。實例二：下圖從整體同樣的能說明此過程：此例的分析如下：1.連接：=2={{A{B{BE}{E}}{{A{B{BE}{E}}={{AB{AE},{B,C,E}}使用Apriori性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪子集為非頻繁的選項：{A,B,C}的2項子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以刪除這個選項；{A,C,E}的2項子集是{A,C},{A,E},{C,E}，其中{A,E}不是L2的元素，所以刪除這個選項；{B,C,E}的2項子集是{B,C},{B,E},{C,E}，它的所有2－項子集都是L2的元素，因此保留這個選項。這樣，剪枝后得到C3={{B,C,E}}PS從算法的運行過程，我們可以看出該Apriori算法的優(yōu)點：簡單、易理解、數(shù)據(jù)要求低，然而我們也可以看到Apriori算法的缺點：在每一步產(chǎn)生侯選項目集時循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素;每次計算項集的支持度時，都對數(shù)據(jù)庫D中的全部記錄進行了一遍掃描比較，如果是一個大型的數(shù)據(jù)庫的話，這種掃描比較會大大增加計算機系統(tǒng)的I/O開銷。而這庫的記錄的增加呈現(xiàn)出幾何級數(shù)的增加。因此人們開始尋求更好性能的算法。六、改進Apriori算法的方法方法：基于s表的項集計數(shù)將每個項集通過相應(yīng)的hash函數(shù)映射到hash表中的不同的桶中，這樣可以通過將桶中的項集技術(shù)跟最小支持計數(shù)相比較先淘汰一部分項集。方法：事務(wù)壓縮（壓縮進一步迭代的事務(wù)數(shù)）不包含任何k-項集的事務(wù)不可能包含任何(k+1)-項集，這種事務(wù)在下一步的計算中可以加上標(biāo)記或刪除方法：劃分挖掘頻繁項集只需要兩次數(shù)據(jù)掃描D中的任何頻繁項集必須作為局部頻繁項集至少出現(xiàn)在一個部分中。第一次掃描：將數(shù)據(jù)劃分為多個部分并找到局部頻繁項集第二次掃描：評估每個候選項集的實際支持度，以確定全局頻繁項集。方法4：選樣（在給定數(shù)據(jù)的一個子集挖掘）基本思想：選擇原始數(shù)據(jù)的一個樣本，在這個樣本上用Apriori算法挖掘頻繁模式通過犧牲精確度來減少算法開銷，為了提高效率，樣本大小應(yīng)該以可以放在內(nèi)存中為宜，可以適當(dāng)降低最小支持度來減少遺漏的頻繁模式可以通過一次全局掃描來驗證從樣本中發(fā)現(xiàn)的模式可以通過第二此全局掃描來找到遺漏的模式方法：動態(tài)項集計數(shù)在掃描的不同點添加候選項集，這樣，如果一個候選項集已經(jīng)滿足最少支持度，則接將它添加到頻繁項集，而不必在這次掃描的以后對比中繼續(xù)計算。PS：Arr算法的優(yōu)化思路1、在逐層搜索循環(huán)過程的第k步中，根據(jù)k-1步生成的k-1維頻繁項目集來產(chǎn)生k維候選項目集，由于在產(chǎn)生k-1維頻繁項目集時，我們可以實現(xiàn)對該集中出現(xiàn)元素的個數(shù)進行計數(shù)處因此對某元素而言，若它的計數(shù)個數(shù)不到k-1的話，可以事先刪除該元素，從而排除由該將引起的大規(guī)格所有組合。這是因為對某一個元素要成為K維項目集的一元素的話，該元素在k-1階頻繁項目集中的計數(shù)次數(shù)必須達(dá)到K-1個，否則不可能生成K維項目集(性質(zhì)3)。2、根據(jù)以上思路得到了這個候選項目集后，可以對數(shù)據(jù)庫D的每一個事務(wù)進行掃描，若該事務(wù)中至少含有候選項目集Ck中的一員則保留該項事務(wù)，否則把該事物記錄與數(shù)據(jù)庫末端沒有作刪除標(biāo)記的事務(wù)記錄對換，并對移到數(shù)據(jù)庫末端的事務(wù)記錄作刪除標(biāo)一記，整個數(shù)據(jù)庫掃描完畢后為新的事務(wù)數(shù)據(jù)庫D’中。因此隨著K的增大，D’中事務(wù)記錄量大大地減少，對于下一次事務(wù)掃描可以大大節(jié)約I/0開銷。由于顧客一般可能一次只購買幾件商品，因此這種虛擬刪除的方法可以實現(xiàn)記錄在以后的挖掘中被剔除出來，在所剩余的不多的記錄中再作更高維的數(shù)據(jù)挖大地節(jié)約時間的。實例過程如下圖：當(dāng)然還有很多相應(yīng)的優(yōu)化算法，比如針對Apriori算法的性能瓶頸問題-需要產(chǎn)生大量候選項集和需要重復(fù)地掃描數(shù)據(jù)庫，2000年JiaweiHan等人提出了基于FP樹生成頻繁項集的FP-growth算法。該算法只進行2次數(shù)據(jù)庫掃描且它不使用侯選集，直接壓縮數(shù)據(jù)庫成一個頻繁模式樹，最后通過這棵樹生成關(guān)聯(lián)規(guī)則。研究表明它比Apriori算法大約快一個數(shù)量級。數(shù)據(jù)挖數(shù)據(jù)挖掘十大算法詳解EMPAGE57EMPAGE57數(shù)據(jù)挖掘十大算法 算法