數據挖掘基本算法

數據挖掘基本算法第一頁，共一百二十二頁，編輯于2023年，星期六數據倉庫與數據挖掘第一章數據倉庫與數據挖掘概述第二章數據倉庫的分析第三章數據倉庫的設計與實施第四章信息分析的基本技術第五章數據挖掘過程第六章數據挖掘基本算法第七章非結構化數據挖掘第八章離群數據挖掘第九章數據挖掘語言與工具的選擇第十章知識管理與知識管理系統第二頁，共一百二十二頁，編輯于2023年，星期六第六章數據挖掘基本算法6.1分類規(guī)則挖掘6.2預測分析與趨勢分析規(guī)則6.3數據挖掘的關聯算法6.4數據挖掘的聚類算法6.5數據挖掘的統計分析算法6.6數據挖掘的品種優(yōu)化算法6.7數據挖掘的進化算法第三頁，共一百二十二頁，編輯于2023年，星期六6.4數據挖掘的聚類算法聚類分析是對群體及成員進行分類的遞歸過程。一個簇是一組數據對象的集合，在同一簇中的對象彼此類似，而不同簇中的對象彼此相異。將一組物理或抽象對象分組成由類似對象組成的多個簇的過程被稱為聚類。聚類就是將數據對象分組成多個類或簇，在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。距離是經常采用的度量方式。第四頁，共一百二十二頁，編輯于2023年，星期六6.4數據挖掘的聚類算法聚類分析的應用：市場或客戶分割、模式識別、生物學研究、空間數據分析、Web文檔分類等。聚類分析可以用作獨立的數據挖掘式工具，來獲得對數據分布的了解，也可以作為其他數據挖掘算法的預處理步驟。聚類的質量是基于對象相異度來評估的。相異度是描述對象的屬性值來計算的。相異度可以對多種類型的數據來計算，包括區(qū)間標度變量、二元變量、標稱變量、序數型變量和比例度型變量類型的組合。第五頁，共一百二十二頁，編輯于2023年，星期六6.4數據挖掘的聚類算法聚類分析的算法可以分為：劃分方法：首先得到初始的K個劃分的集合。如K-平均、K-中心點、CLARANS以及對它們的改進。層次方法：創(chuàng)建給定數據對象集合的一個層次性的分解。根據層次分解的過程可以分為凝聚（自底向上）或分裂（自頂向下）?；诿芏鹊姆椒ǎ焊鶕芏鹊母拍顏砭垲悓ο?，如DBSCAN、DENCLUE、OPTICS。基于網格的方法：首先將對象空間量化為有限數目的單元，形成網格結構，然后在網格結構上進行聚類，如STING、CLIQUE、WaveCluster?；谀Ｐ偷姆椒ǎ簽槊總€簇假設一個模型，發(fā)現數據對模型的最好匹配，如COBWEB、CLASSIT和AutoClass。第六頁，共一百二十二頁，編輯于2023年，星期六6.4數據挖掘的聚類算法類別算法分裂/劃分方法K-MEANS（K-平均）、K-MEDOIDS算法（K-中心點）、CLARANS算法（基于選擇的方法）層次法BIRCH算法（平衡迭代規(guī)約和聚類）、CURE算法（代表聚類）、CHAMELEON算法（動態(tài)模型）基于密度的方法DBSCAN算法（基于高密度連接區(qū)域）、OPTICS算法（對象排序識別）、DENCURE算法（密度分布函數）基于網格的方法STING算法（統計信息網格）、CLIQUE算法（聚類高維空間）、WAVE-CLUSTER算法（小波變換）基于模型的方法統計學方法、神經網絡方法表6.9主要的聚類算法的分類第七頁，共一百二十二頁，編輯于2023年，星期六6.4數據挖掘的聚類算法6.4.1聚類分析的概念6.4.2聚類分析中兩個對象之間的相異度計算方法6.4.3劃分方法6.4.4層次方法*6.4.5基于密度的方法*6.4.6基于網格的方法*6.4.7基于模型的聚類方法*6.4.8模糊聚類算法*第八頁，共一百二十二頁，編輯于2023年，星期六6.4.1聚類分析的概念聚類就是按照事物的某些屬性，把事物聚集成類，使類間的相似性盡可能小，類內相似性盡可能大。聚類是一個無監(jiān)督學習的過程，它與分類的根本區(qū)別在于，分類是需要事先知道所依據的數據特征，而聚類是要找到這個數據特征。因此在很多應用中，聚類分析作為一種數據預處理過程，是進一步分析和處理數據的基礎。聚類是一種對具有共同趨勢和模式的數據元組進行分組的方法，試圖找出數據集中的共性和差異并將具有共性的元組聚合在相應的類或段中。第九頁，共一百二十二頁，編輯于2023年，星期六6.4.1聚類分析的概念數據挖掘對聚類的典型要求如下：1）可伸縮性：算法能夠處理海量的數據庫對象。2）處理不同類型屬性的能力3）發(fā)現具有任意形狀的聚類的能力4）輸入參數對領域知識的弱依賴性5）處理噪聲數據或離群數據的能力6）結果對于輸入記錄順序的無關性7）處理高維度數據的能力8）結果的可解釋性和可用性9）基于約束的聚類分析能力第十頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法基于內存的聚類算法多選擇如下兩種有代表性的數據結構：（1）數據矩陣（datamatrix）數據矩陣用m個變量（也稱屬性）來表現n個對象，這種數據結構是關系表的形式，或nm維（n個對象m

個屬性）的矩陣。(6-12)第十一頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法（2）相異度矩陣（dissimilatorymatrix）存儲n個對象兩兩之間的近似性，通常用一個nn維的矩陣表示。其中d(i,j)是對象i和對象j之間的測量差或相異度，通常它是一個非負的數值。對象i和j之間越相似，其值越接近0；兩個對象越不同，其值越大。由于d(i,j)=d(j,i)；且d(i,i)=0，可以得到（6-13）。(6-13)第十二頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法數據矩陣的行和列代表不同的實體，也被稱為二模矩陣。相異度矩陣的行和列代表相同的實體，也被稱為單模矩陣。許多聚類算法都是以相異度矩陣為數據源運行的，如果數據是用數據矩陣的形式存儲的，在使用聚類算法之前要將其轉化為相異度矩陣。第十三頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法計算相異度的常用方法有：區(qū)間標度變量計算方法，二元變量計算方法，標稱、序數和比例標度計算方法，或這些變量類型的組合來描述對象的相異度計算方法。第十四頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法（1）區(qū)間標度變量計算方法區(qū)間標度變量是一個粗略線性標度的連續(xù)度量。度量單位的選用將直接影響聚類分析的結果。一般而言，所用的度量單位越小，變量可能的值域就越大，這樣對聚類的結果影響就越大。因此為了避免對度量單位選擇的依賴，應該對數據進行標準化。標準化度量值試圖給所有的變量相等的權重，當沒有關于數據的先驗知識時，這樣做是十分有效的。第十五頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法為了實現度量值的標準化，一種方法是將原來的度量值轉化為無單位的值。給定一個變量f的變量值，可以進行如下的變換。其中，x1f,x2f,…,xnf是f的n個度量值，mf是f的平均值，即1）計算均值絕對偏差sf第十六頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法均值絕對偏差sf比標準的偏差f對于孤立點具有更好的魯棒性。在計算均值絕對值偏差時，度量值與平均值的偏差沒有被平方，因此孤立點的影響在一點程度上減小了。采用均值絕對偏差的優(yōu)點在于孤立點的z-score值不會太小，因此孤立點仍可別發(fā)現。2）計算標準化的度量值第十七頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法標準化后，或者在某些應用中不需要標準化，區(qū)間標度變量描述的對象間的相異度（或相似度）通?；趯ο箝g的距離來計算。常用的距離度量方法如下：1）歐幾里德距離其中，是兩個n維的數據對象。第十八頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法2）曼哈頓距離3）明考斯基距離是歐幾里德距離和曼哈頓距離的推廣。其中，p是一個正整數。p=1時，它表示曼哈頓距離；p=2時，它表示歐幾里德距離。第十九頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法如果對每個變量根據其重要性賦予一個權重，加權的歐幾里德距離可以計算如下：同理，加權也可以用于曼哈頓距離和明考斯基距離。第二十頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法例6.7x1=(2,9)和x2=(4,6)表示兩個對象，計算x1和x2的歐幾里德距離和曼哈頓距離。x1和x2的歐幾里德距離x1和x2的曼哈頓距離第二十一頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法（2）二元變量計算方法一個二元變量只有兩個狀態(tài)：0或1，其中0表示該變量為空，1表示該變量存在。如果所有的二元變量具有相同的權重，可以得到一個兩行兩列的可能性如表6.10所示。第二十二頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法表6.10中，q表示對象i和對象j的值都為1的變量的數目；r表示在對象i中值為1，但在該對象j中值為0的變量的數目；s表示在對象i中值為0，但在該對象j中值為1的變量的數目；t表示對象i和對象j的值都為0的變量的數目。變量的總數是p，p=q+r+s+t。對象j10求和對象i1qrq+r0sts+t求和q+sr+tp=q+r+s+t表6.10二元變量的相依表第二十三頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法評價兩個對象i和j之間的相異度標準如下。（1）簡單匹配系數（2）Jaccard系數（3）Rao系數第二十四頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法例6.8二元變量之間的相異度使用實例假設一個病人記錄表（表6.11）包含屬性姓名、性別、發(fā)燒、咳嗽、test-1、test-2、test-3和test-4，其中姓名是對象標識，屬性都是二元變量。值Y和P被置為1，值N被置為0。求病人間患病的相似情況。表6.11二元屬性的關系變量姓名性別發(fā)燒咳嗽test-1test-2test-3test-4ZhangMYNPNNNLiFYNPNPNWangMYNNNNP……………………第二十五頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法根據Jaccard系數公式，三個病人Zhang，Li和Wang兩兩之間的相異度如下：d(Zhang,Li)=(0+1)/(2+0+1)=0.33d(Zhang,Wang)=(1+1)/(1+1+1)=0.67d(Li,Wang)=(1+2)/(1+1+2)=0.75因此，Wang和Li患有相似的疾病可能性較低，因為他們有著最高的相異度，而Zhang和Li最可能有類似的疾病。第二十六頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法（3）標稱型、序數型和比例標度型變量計算方法1）標稱變量標稱變量是二元變量的推廣，它可以具有多于兩個狀態(tài)的值。假設一個標稱變量的狀態(tài)數目是M。這些狀態(tài)可以用字母、符號，或者一組整數來表示（注意：這些整數只是用于數據處理，并不代表任何特定的順序）。兩個對象i和j之間的相異度可以用簡單匹配方法來計算：這里m是匹配的數目，即對i和j取值相同的變量的數目；而p是全部變量的數目。可以通過賦權重來增加m的影響，或者賦給有較多狀態(tài)的變量的匹配更大的權重。第二十七頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法2）序數型變量一個離散的序數型變量類似于標稱變量，不同在于序數型變量的M個狀態(tài)是以有意義的序列排序的。序數型變量對記錄那些難以客觀度量的主觀評價是非常有用的。一個連續(xù)的序數型變量看起來像一個未知刻度的的連續(xù)數據的集合，即值的相對順序是必要的，而其實際的大小則不重要。將區(qū)間標度變量的值域劃分為有限個區(qū)間，從而將其值離散化，可以得到序數型變量。一個序數型變量的值可以映射為排序。例如，一個變量f有Mf個狀態(tài)，這些有序的狀態(tài)定義了一個序列1,…,Mf。第二十八頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法處理序數型變量：在計算對象的相異度時，序數型變量的處理與區(qū)間標度變量的處理方法類似。假設f是用于描述n個對象的一組序數型變量之一，關于f的相異度計算步驟如下：Step1第i個對象的f值為xif，變量f有Mf個有序的狀態(tài)，對應于序列1,…,Mf

。用對應的秩rif代替xif，rif

{1,…,Mf}。Step2既然每個序數變量可以有不同數目的狀態(tài)，必須經常將每個變量的值域映射到[0.0,1.0]上，以便每個變量都有相同的權重。這一點可以通過zif代替rif來實現。(6-14)第二十九頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法Step3相異度的計算可以采用任意一種距離度量方法，采用zif作為第i個對象的f值。第三十頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法3）比例標度型變量比例標度型變量在非線性的標度取正的度量值，例如指數標度，近似地遵循AeBT。計算用比例標度型變量描述的對象之間的相異度，目前有三種方法：采用與處理區(qū)間標度變量同樣的方法。缺點：標度可能被扭曲。對比例標度型變量進行對數變換。變換得到的值可用區(qū)間標度方法計算，對于比例標度型變量可以采用log-log或者其他形式的變換，具體做法取決于定義和應用。將xif看作連續(xù)的序數型數據，將其秩作為區(qū)間標度的值來對待。第三十一頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法（4）混合類型的變量計算方法一個數據庫可能包含區(qū)間標度量、對稱二元變量、不對稱二元變量、標稱變量、序數型變量或者比例標度變量。第一種方法：計算用混合類型變量描述的對象之間的相異度方法是將變量按類型分組，對每種類型的變量進行單獨的聚類分析。如果這些分析得到兼容的結果，這種做法是可行的。但在實際應用中，這種情況是不大可能的。第二種方法：將所有變量一起處理，只進行一次聚類分析。將不同類型的變量組合在單個的相異度矩陣中，把所有有意義的變量轉換到共同的值域區(qū)間[0.0,1.0]上。第三十二頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法假設數據集包含p不個同類型的變量，對象i和對象j之間相異度d(i,j)定義為：(6-15)其中，如果xif或者xjf缺失，或者xif=xjf=0，且變量f是不對稱的二元變量，則指示項，否則。第三十三頁，共一百二十二頁，編輯于2023年，星期六6.4.2聚類分析中兩個對象之間的相異度計算方法變量f對i和j之間相異度的計算方式與其具體類型有關。1）如果f是二元變量或標稱變量：2）如果f是區(qū)間標度變量：3）如果f是序數型或者比例標度型變量：第三十四頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法給定一個包含n個數據對象的數據庫，以及要生成的簇的數目k，一個劃分類的算法將數據對象組織為k個劃分（k≤n），其中每個劃分代表一個簇。通常會采用一個劃分準則（相似度函數）以便在同一個簇中的對象是“相似的”，而不同簇中的對象是“相異的”。第三十五頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法（1）典型的劃分方法：k-平均和k-中心點最著名與最常用的劃分方法是k-平均、k-中心點和它們的變種。1）基于簇的重心技術：k-平均方法k-means算法是基于質心的算法。k-means算法以k為參數，把n個對象分為k個簇，以使簇內具有較高的相似度，而簇間的相似度最低。相似度的計算根據一個簇中對象的平均值（被看作簇的重心）來進行。第三十六頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法k-means聚類算法的具體流程：Step1從數據集中任意選擇k個對象C1,C2,…,Ck作為初始的簇中心；Step2把每個對象分配到與之最相似的聚合。每個聚合用其中所有對象的均值來代表，“最相似”就是指距離最小。對于每個點Vi，找出一個質心Cj，使它們之間的距離d(Vi,Cj)最小，并把Vi分到第j組。Step3把所有的點分配到相應的簇之后，重新計算每個組的質心Cj

。Step4循環(huán)執(zhí)行Step2和Step3，直到數據的劃分不再發(fā)生變化。第三十七頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法通常采用的準則函數是平方誤差準則函數，其定義如下：(6-16)其中，E是數據庫中所有對象的平方誤差的總和；p是空間中的點，表示給定的數據對象；mi是簇Ci的平均值（p和mi都是多維的）。也就是說，對于每個簇中的每個對象，求對象到其簇中心距離的平方，然后求和。這個準則試圖使生成的結果簇盡可能地緊湊和獨立。第三十八頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法輸入：k：簇的數目n：數據庫對象的個數輸出：k個簇，使平方誤差最小方法：隨機選擇k個對象作為初始的代表對象；repeat；根據與每個中心的距離，將每個對象賦給最近的簇；重新計算每個簇的平均值；until不再發(fā)生變化。第三十九頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法例6.9k-means算法使用實例設數據對象集合如表6.12所示。簇數目k=2，采用k-means算法對其進行聚類。表6.12pxy11121.21.230.81.240.90.751.30.9611.473383.12.893.23.4102.73.3112.62.9第四十頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法第一次迭代：選擇p3(0.8,1.2)，p8(3.1,2.8)為簇C1，C2的初始簇代表。所以，將p1分配給p3所屬的類C1，同理，將p2、p3、p4、p5、p6分配給p3所屬的類C1，將p7、p8、p9、p10、p11分配給p8所屬的類C2。第四十一頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法第二次迭代，用m1(1.033,1.067)，m2(2.92,3.08)作為簇C1，C2的簇中心，重新對數據進行劃分。將p1、p2

、p3

、p4

、p5

、p6分類C1，將p7

、p8

、p9

、p10

、p11分配給類C2

。m1=(1.033,1.067)，m2=(2.92,3.08)，E=1.023第四十二頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法由于在兩次迭代過程中，2個簇中心都不變，所以停止迭代過程。得到的兩個聚類分別為：C1={p1,p2,p3,p4,p5,p6}C2={p7,p8,p9,p10,p11}第四十三頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法k-means聚類算法嘗試找出使平方誤差函數值最小的k個劃分。當結果簇是密集的，而簇與簇之間區(qū)別明顯時，它的效果較好。對處理大數據集，該算法是相對可伸縮的和高效率的，復雜度是O(nkt)，n是所有對象的數目，k是簇的數目，t是迭代的次數。第四十四頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法不足：k-means算法只有在簇的平均值被定義的情況下才能使用。k-means算法的不足之處在于它要多次掃描數據庫。k-means算法只能找出球形的類，而不能發(fā)現任意形狀的類。初始質心的選擇對聚類結果有較大的影響。k-means算法對于噪聲和孤立點數據是敏感的，少量的該類數據能夠對平均值產生極大的影響。k-平均算法的變種：k-模方法、EM算法等第四十五頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法2）基于有代表性的對象的技術：k-中心點法為了避免k-means算法對孤立點的敏感性，不采用簇中對象的平均值作為參照點，可以選用簇中位置最中心的對象，即medoid。這樣的劃分方法仍然是基于最小化所有對象與其參照點之間的相異度之和的原則來執(zhí)行的。這是k-medoids方法的基礎。通常采用的準則函數是絕對誤差準則函數，其定義如下：(6-17)其中，E是數據庫中所有對象的絕對誤差的總和；p是空間中的點，表示給定的數據對象；oi是簇Ci中的代表對象。第四十六頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法k-medoids算法的基本策略：首先隨機選擇k個對象，每個對象代表一個簇，把其余的對象分別分配給最相似的簇。然后，反復地嘗試把每個中心分別用其他非中心來代替，檢查聚類的質量是否有所提高。若是，則保留該替換，重復上述過程，直到不再發(fā)生變化。為了判定一個非代表對象Orandom是否是當前一個代表對象Oj的好的替代，對于每一個非中心點對象，考慮下面的四種情況：第一種情況：p當前隸屬于中心點對象Oj。如果Orandom代替Oj作為一個中心點，且p離Oi最近，i≠j，那么p被重新分配給Oi

。第四十七頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法第二種情況：p當前隸屬于中心點對象Oj。如果Orandom代替Oj作為一個中心點，且p離Orandom最近，那么p被重新分配給Orandom

。第三種情況：p當前隸屬于中心點對象Oi，i≠j

。如果Orandom代替Oj作為一個中心點，且p離Oi最近，那么對象的隸屬不發(fā)生變化。第四種情況：p當前隸屬于中心點對象Oi，i≠j

。如果Orandom代替Oj作為一個中心點，且p離Orandom最近，那么p被重新分配給Orandom

。第四十八頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法每當重新分配時，平方-誤差E所產生的差別對代價函數有影響。因此，如果一個當前的中心點對象被非中心點所代替，就通過代價函數計算平方-誤差值所產生的差別。替換的總代價是所有非中心點對象所產生的代價之和。如果總代價是負的，那么實際的平方-誤差將會減少，Oj可以被Orandom代替。如果總代價是正的，則當前的中心點Oj被認為是可接受的，在本次迭代中沒有變化發(fā)生。第四十九頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法輸入：k：簇的數目n：數據庫對象的個數輸出：k個簇，使所有對象與其最近代表對象的相異度總和最小方法：隨機選擇k個對象作為初始的代表對象；repeat；指派每個剩余的對象給離它最近的代表對象所代表的簇；隨意地選擇一個非代表對象Orandom；計算用Orandom代替Oj的總代價S；如果S<0，則用Orandom替換Oj

，形成新的k個代表對象的集合；

until不發(fā)生變化。第五十頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法k-medoids算法的過程和k-means算法的不同之處在于：k-medoids算法用類中最靠近中心的一個對象來代表聚類，而k-means算法用質心來代表聚類。k-means算法對噪聲非常敏感，因為一個極大的值會對質心的計算帶來很大的影響，而k-medoids算法中，通常用中心來代替質心，可以有效地消除該影響。第五十一頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法PAM（partitioningaroundmedoid,圍繞中心點的劃分）是最早提出的k-中心點算法之一。它試圖對n個對象給出k個劃分。最初隨機選擇k個中心點后，該算法反復地進行，試圖找出更好的中心點：對所有可能的對象進行分析，每兩個對象的一個對象被看作是中心點，而另一個不是；對可能的各種組合，計算聚類結果的質量。一個對象Oj被可以產生最大平方-誤差值減少的對象代替，使在一次迭代中產生的最佳對象的集合為下次迭代的中心點。第五十二頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法（2）大型數據庫中的劃分方法：基于選擇的k-中心點CLARANS方法典型的k-中心點劃分算法PAM方法，對小的數據集合非常有效，由于沒有良好的可伸縮性，所以不適合答的數據集合。為了處理較大的數據集合，可以采用一個基于選擇的方法CLARA（clusteringlargeapplications,CLARA）。CLARA的基本思想是：不考慮整個數據集合，選擇實際數據的一小部分作為數據的樣本。然后用PAM方法從樣本中選擇中心點。如果樣本是以非隨機方式選取，它應當足以代表原來的數據集合。第五十三頁，共一百二十二頁，編輯于2023年，星期六6.4.3劃分方法改進CLARA的聚類質量和可伸縮性是將CLARANS（clusteringlargeapplicationsbaseduponrandomizedsearch,CLARANS）的采樣技術和PAM結合起來。與CLARA不同，CLARANS沒有在任一給定時間內局限于任一樣本，即不同于CLARA在搜索的每個階段都有一個固定的樣本，CLARANS在搜索的每一步帶一定隨機性地抽取一個樣本。6.5數據挖掘的統計分析算法第五十四頁，共一百二十二頁，編輯于2023年，星期六6.4.4層次方法一個層次的聚類方法將數據對象組成一棵聚類的樹。根據層次分解是自底向上，還是自頂向下形成，層次的聚類方法可以進一步分為凝聚和分裂層次聚類。一個純粹的層次聚類方法的聚類質量受限于如下特點：一個合并或分裂一旦執(zhí)行，就不能修正。（1）凝聚的和分裂的層次聚類（2）BIRCH：平衡迭代歸約和聚類（3）ROCK：分類屬性層次聚類算法（4）CURE：使用代表點聚類方法（5）Chameleon：動態(tài)建模層次聚類第五十五頁，共一百二十二頁，編輯于2023年，星期六（1）凝聚的和分裂的層次聚類1）凝聚的方法首先將每個對象作為單獨的一個原子簇然后相繼地合并相近的對象或原子簇直到所有的原子簇合并為一個（層次的最上層），或者達到一個終止條件2）分裂的方法首先將所有的對象置于一個簇中在迭代的每一步中，一個簇被分裂為更小的簇，直到最終每個對象在單獨的一個簇中，或者達到一個終止條件第五十六頁，共一百二十二頁，編輯于2023年，星期六（1）凝聚的和分裂的層次聚類四個常用的簇間距離度量方法如下：最小距離：最大距離：平均值的距離：平均距離：(6-18)(6-19)(6-20)(6-21)其中，|p-p’|是兩個對象p和p’之間的距離，mi是簇Ci的平均值，而ni是簇Ci中對象的數目。第五十七頁，共一百二十二頁，編輯于2023年，星期六（2）BIRCH：平衡迭代歸約和聚類利用層次方法的平衡迭代規(guī)約和聚類（BalancedIterativeReducingandClusteringusingHierarchies,BIRCH）用于歐幾里德向量空間數據，即平均值有意義的數據。該算法通過聚類特征（ClusteringFeature,CF）對簇的信息進行匯總描述，然后對簇進行分類。假設某個簇中包含N個d維的數據點或者數據對象{oi}，則該簇的聚類特征定義如下：(6-22)其中，N是簇中數據對象的數目，是N個對象的線性和，即SS是對象的平方和，即，它記錄了計算聚類和有效利用存儲的關鍵度量。第五十八頁，共一百二十二頁，編輯于2023年，星期六（2）BIRCH：平衡迭代歸約和聚類BIRCH算法的主要目標是使I/O時間盡可能小，原因在于大型數據集通常不能完全裝入內存中。BIRCH算法通過把聚類分為多個階段來達到此目的。首先通過構建CF-樹對原數據集進行預聚類，在前面預聚類的基礎上進行聚類。CF1CF2……CFnCF11CF12……CF1n根層第一層…………………………圖6.10CF樹的結構第五十九頁，共一百二十二頁，編輯于2023年，星期六（2）BIRCH：平衡迭代歸約和聚類BIRCH共包含四個階段：預聚類階段：掃描整個數據庫，構建初始聚類特征樹，該樹保存在內存中，用簡潔的匯總信息或者葉子節(jié)點中的子聚類來代表數據點的密集區(qū)域。（可選階段）重新掃描葉子節(jié)點項，來構建一個更小的CF-樹。采用別的聚類算法，對CF-tree的葉子節(jié)點進行聚類。（可選階段）把前一個階段中找到的聚類的質心，用作種子來創(chuàng)建最終的聚類。其它數據點根據到這些種子所代表聚類的遠近來重新分配到各個聚類中。第六十頁，共一百二十二頁，編輯于2023年，星期六（2）BIRCH：平衡迭代歸約和聚類BIRCH算法的主要缺點之一就是在初始掃描完成之后，它使用基于質心的方法來形成聚類，當聚類的形狀不同或大小各異的情況下，就容易出現問題。BIRCH算法采用直徑作為控制參數，所以當類的形狀非球形或不同大小的類時，聚類效果不佳。BIRCH算法對數據的輸入順序很敏感，還需要用戶手工設置一些參數。第六十一頁，共一百二十二頁，編輯于2023年，星期六（3）ROCK：分類屬性層次聚類算法分類屬性的層次聚類算法（RobustClusteringusinglinKs），針對具有分類屬性的數據使用了鏈接（指兩個對象共同的近鄰數目）的概念。對于聚類包含布爾或分類屬性的數據，傳統聚類算法使用距離函數，然而實驗表明對分類數據聚類時，這些距離度量不能產生高質量的簇。大多數聚類算法在進行聚類時只估計點與點之間的相似度；也就是說，在每一步中那些最相似的點合并到一個簇中。這種局部方法很容易導致錯誤。第六十二頁，共一百二十二頁，編輯于2023年，星期六（3）ROCK：分類屬性層次聚類算法ROCK算法采用一種比較全局的觀點，通過考慮成對點的鄰域情況進行聚類。如果兩個相似的點同時具有相似的鄰域，那么這兩個點可能屬于同一個簇而合并。ROCK算法使用一個相似度閾值和共享鄰域的概念從一個給定的數據相似度矩陣中首先構建一個稀疏圖，然后在這個稀疏圖上執(zhí)行凝聚層次聚類。使用一個優(yōu)度度量評價聚類。采用隨機抽樣處理大規(guī)模的數據集。ROCK算法在最壞情況下的時間復雜度為O(n2+nmmma+n2logn)，其中mm和ma分別是近鄰數目的最大值和平均值，n是對象的個數。第六十三頁，共一百二十二頁，編輯于2023年，星期六（4）CURE：使用代表點聚類方法使用代表點的聚類方法（ClusteringUsingRepresentative,CURE）解決了偏好球形和相似大小的問題，在處理孤立點上也更加健壯。CURE選擇了位于基于質心和基于代表對象方法之間的中間策略，它不用單個質心或對象來代表一個簇，而是選擇數據空間中固定數目的具有代表性的點。一個簇的代表點通過如下方式產生：首先選擇簇中分散的對象然后根據一個特定的分數或收縮因子向簇中心收縮或移動它們在算法的每一步，有最近距離的代表點對（每個點來自于一個不同的簇）的兩個簇被合并第六十四頁，共一百二十二頁，編輯于2023年，星期六（4）CURE：使用代表點聚類方法每個簇有多于一個的代表點使得CURE算法可以適應非球形的幾何形狀。簇的收縮或凝聚可以有助于控制孤立點的影響。因此，CURE算法對于孤立點的處理更加健壯，而且能夠識別非球形和大小變化較大的簇。對于大規(guī)模數據庫，它也具有良好的伸縮性，而且沒有犧牲聚類質量。第六十五頁，共一百二十二頁，編輯于2023年，星期六（4）CURE：使用代表點聚類方法針對大型數據庫，CURE算法采用隨機取樣和劃分兩種方法的組合：一個隨機樣本首先被劃分，每個劃分在被部分聚類；然后這些聚類結果簇被聚類產生希望的結果。該算法的具體過程如下。Step1源數據對象中抽取一個隨機樣本S；Step2將樣本S分割為一組劃分；Step3對每個劃分局部地聚類；Step4通過隨機取樣剔除孤立點。如果一個簇增長的太慢，就去掉它；Step5對局部的簇進行聚類。落在每個新形成的簇中的代表點根據用戶定義的一個收縮因子α收縮或向簇中心移動。這些點代表了簇的形狀；Step6用相應的簇標簽來標記數據。第六十六頁，共一百二十二頁，編輯于2023年，星期六（4）CURE：使用代表點聚類方法CURE算法特點：CURE算法可以適應非球形的幾何形狀算法對孤立點的處理更加健壯能夠識別非球形和大小變化較大的簇；CURE算法的復雜性為O(n)。CURE從源數據對象中抽取一個隨機樣本S，基于對此樣本的劃分進行聚類，如果抽取的樣本發(fā)生傾斜，則會嚴重影響聚類結果。第六十七頁，共一百二十二頁，編輯于2023年，星期六（5）Chameleon：動態(tài)建模層次聚類Chameleon是一個在層次聚類中利用動態(tài)模型的層次聚類算法，屬于凝聚聚類技術。在聚類過程中，如果兩個簇之間的互連性和近似度與簇內部對象間的互連性和近似度高度相關，則合并這兩個簇?；趧討B(tài)模型的合并過程有利于自然的和相似的聚類的發(fā)現，而且只要定義了相似度函數就可以應用于所有類型的數據。第六十八頁，共一百二十二頁，編輯于2023年，星期六（5）Chameleon：動態(tài)建模層次聚類Chameleon通過兩個簇的相對互連度RI(Ci,Cj)和相對接近度RC(Ci,Cj)來決定簇之間的相似度。相對互連度是被簇的內部互聯度規(guī)范化的兩個簇的絕對互連度，如果結果簇中的點之間連接幾乎和原來的每個簇一樣強，兩個簇合并，數學表述為：其中，EC{Ci,Cj}是連接簇Ci和Cj的邊之和；類似地，ECCi（或ECCj

）是二分簇Ci（或Cj）的割邊最小和。(6-23)第六十九頁，共一百二十二頁，編輯于2023年，星期六（5）Chameleon：動態(tài)建模層次聚類相對接近度是被簇的內部互聯度規(guī)范化的兩個簇的絕對接近度，兩個簇合并，僅當結果簇中的點之間的接近程度幾乎與原來的每個簇一樣。數學表述為：其中，|Ci|和|Cj|分別是簇Ci和Cj的大?。?6-24)是連接Ci和Cj節(jié)點的邊的平均權值；是二分簇Ci（或Cj）的邊的平均權值；EC表示割邊。第七十頁，共一百二十二頁，編輯于2023年，星期六（5）Chameleon：動態(tài)建模層次聚類Chameleon算法的思想是：首先通過一個圖劃分算法將數據對象聚類為大量相對較小的子聚類，然后用一個凝聚的層次聚類算法通過反復地合并子類來找到真正的結果簇。Chameleon既考慮了互連性，又考慮了簇間的近似度，特別是簇內部的特征，來確定最相似的子簇。它不依賴于一個靜態(tài)的，用戶提供的模型，能夠自動地適應被合并的簇的內部特征。第七十一頁，共一百二十二頁，編輯于2023年，星期六（5）Chameleon：動態(tài)建模層次聚類與CURE和DBSCAN相比：Chameleon在發(fā)現高質量的任意形狀的聚類方面有更強的能力但是在最壞的情況下，高維數據的處理代價可能對n個對象需要O(n2)的時間第七十二頁，共一百二十二頁，編輯于2023年，星期六6.4.5基于密度的聚類方法基于密度的聚類方法將簇看作數據空間中由低密度區(qū)域分隔開的高密度對象區(qū)域。主要思想：只要臨近區(qū)域的密度（對象或數據點的數目）超過某個閾值，就繼續(xù)聚類，即對給定類中的每個數據點，在一個給定范圍的區(qū)域中必須至少包含某個數目的點。基于密度的聚類方法可以用來過濾噪聲孤立點數據，發(fā)現任意形狀的簇。（1）DBSCAN：基于高密度連通區(qū)域聚類（2）OPTICS：通過點排序識別聚類結構（3）DENCLUE：基于密度分布函數的聚類第七十三頁，共一百二十二頁，編輯于2023年，星期六（1）DBSCAN：基于高密度連通區(qū)域聚類基于高密度連通區(qū)域的聚類（Density-BasedSpatialClusteringofApplicationwithNoise,DBSCAN）將具有足夠高密度的區(qū)域劃分為簇，并可以在帶有噪聲的空間數據庫中發(fā)現任意形狀的聚類。它定義簇為密度相連的點的最大集合。定義：一個給定對象周圍半徑內的區(qū)域稱為該對象的鄰域。如果一個對象的鄰域至少包含最小數目MinPts的對象，那么該對象稱為核心對象。給定一個對象集合D，如果p是在q的鄰域內，而q是一個核心對象，我們說對象p從對象q出發(fā)是直接密度可達的。第七十四頁，共一百二十二頁，編輯于2023年，星期六（1）DBSCAN：基于高密度連通區(qū)域聚類如果存在一個對象鏈p1,p2,…,pn，p1=q，pn=p，對piD，1in，pi+1是從pi關于和MinPts直接密度可達的，則對象p是從對象q關于和MinPts密度可達的。如果對象集合D中存在一個對象o，使得對象p和q是從o關于和MinPts密度相連的。密度可達性是直接密度可達性的傳遞閉包，這種關系式非對稱的。只有核心對象之間是相互密度可達的?；诿芏鹊拇厥腔诿芏瓤蛇_性的最大的密度相連對象的集合，不包含在任何簇中的對象認為是噪聲。第七十五頁，共一百二十二頁，編輯于2023年，星期六（1）DBSCAN：基于高密度連通區(qū)域聚類DBSCAN算法通過檢查數據庫中每個點的ε-鄰域來尋找聚類。如果一個點p的ε鄰域包含多于MinPts個點，則創(chuàng)建一個以p作為核心對象的新簇。然后，DBSCAN算法迭代地尋找從這些核心對象直接密度可達的對象，這個過程可能涉及一些密度可達簇的合并。當沒有新的點可以被添加到任何簇時，該過程結束。第七十六頁，共一百二十二頁，編輯于2023年，星期六（1）DBSCAN：基于高密度連通區(qū)域聚類算法：DBSCAN輸入：D：數據對象集合Eps：鄰域或稱為半徑MinPts：密度閾值輸出：k個簇，使平方誤差最小方法：Step1

讀取D中任意一個未分類的對象p；Step2

檢索出與p的距離不大于Eps的所有對象Neps(p)；Step3

如果|Neps(p)|<MinPts（即p為非核心對象），則將p標記為噪聲，并執(zhí)行Step1；第七十七頁，共一百二十二頁，編輯于2023年，星期六（1）DBSCAN：基于高密度連通區(qū)域聚類Step4

否則（即p為核心對象），給Neps(p)中的所有對象打上一個新的類標簽newid，然后將這些對象壓入堆棧的Seeds中；Step5

讓CurrentObject=Seeds.top；然后檢索屬于Neps(CurrentObject)的所有對象；如果|Neps(CurrentObject)|>MinPts，則剔除已經打上標記的對象，將余下的未分類對象打上類標簽newid，然后壓入堆棧；Step6

Seeds.pop，判斷Seeds是否為空，是，則執(zhí)行Step1

，否則執(zhí)行Step5。第七十八頁，共一百二十二頁，編輯于2023年，星期六（1）DBSCAN：基于高密度連通區(qū)域聚類DBSCAN算法不僅可以發(fā)現任意形狀的聚類，對數據輸入順序不敏感，并且具有處理異常數據（噪聲）的能力。DBSCAN算法對用戶定義的參數是敏感的，而參數的恰當選擇是需要有相關經驗的。第七十九頁，共一百二十二頁，編輯于2023年，星期六（2）OPTICS：通過點排序識別聚類結構對于真實的，高維的數據集合而言，參數的設置通常是依靠經驗，難以確定。絕大多數算法對參數值是非常敏感的：設置的細微不同可能導致差別很大的聚類結果。OPTICS算法通過對象排序識別聚類結構。OPTICS沒有顯式地產生一個數據集合簇，它為自動和交互的聚類分析計算一個簇排序。這個次序代表了數據的基于密度的聚類結構。第八十頁，共一百二十二頁，編輯于2023年，星期六（3）DENCLUE：基于密度分布函數的聚類DENCLUE是對k-means聚類算法的一個推廣：DENCLUE算法得到的是全局最優(yōu)劃分。DENCLUE主要基于：每個數據點的影響可以用一個數學函數來形式化地模擬，它描述了一個數據點在鄰域內的影響，被稱為影響函數；數據空間的整體密度可以被模型化為所有數據點的影響函數的總和；然后聚類可以通過確定密度吸引點來得到，這里的密度吸引點是全局密度函數的局部最大。第八十一頁，共一百二十二頁，編輯于2023年，星期六（3）DENCLUE：基于密度分布函數的聚類DENCLUE算法步驟：Step1對數據點占據的空間推導密度函數；Step2識別局部最大點；Step3通過沿密度增長最大的方向移動，將每個點關聯到一個密度吸引點；Step4定義與特定的密度吸引點相關聯的點構成的簇；Step5丟棄密度吸引點的密度小于用戶指定閾值ξ的簇；Step6合并通過密度大于等于ξ的點路徑連接的簇。第八十二頁，共一百二十二頁，編輯于2023年，星期六6.4.6基于網格的聚類方法基于網格的方法把對象空間量化為有限數目的單元，形成了一個網格結構。所有的聚類操作都在這個網格結構（即量化的空間）上進行。這種方法的主要優(yōu)點是處理速度快，其處理時間獨立于數據對象的數目，僅依賴于量化空間中每一維上的單元數目。（1）STING：統計信息網格聚類（2）WaveCluster：利用小波變換聚類第八十三頁，共一百二十二頁，編輯于2023年，星期六（1）STING：統計信息網格聚類STING是一種基于網格的多分辨率聚類技術，它將空間區(qū)域劃分為矩形單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結構：高層的每個單元被劃分為多個低一層的單元。關于每個網格單元屬性的統計信息（例如平均值、最大值和最小值）被預先計算和存儲。這些統計信息用于回答查詢。第八十四頁，共一百二十二頁，編輯于2023年，星期六（1）STING：統計信息網格聚類優(yōu)點：計算是獨立于查詢的；有利于并行處理和增量更新；效率很高。第八十五頁，共一百二十二頁，編輯于2023年，星期六（1）STING：統計信息網格聚類缺點如果粒度比較細，處理的代價會顯著增加；但是，如果網格結構最低層的粒度太粗，將會降低聚類分析的質量；在構建一個父親單元時沒有考慮孩子單元和其相鄰單元之間的關系，因此，結果簇的形狀是isothetic，即所有的聚類邊界或者是水平的，或者是豎直的，沒有對角的邊界。盡管該技術有快速的處理速度，但可能降低簇的質量和精確性。第八十六頁，共一百二十二頁，編輯于2023年，星期六（2）WaveCluster：利用小波變換聚類WaveCluster是一種多分辨率的聚類算法，首先通過在數據空間上加一個多維網格結構來匯總數據，然后采用一種小波變換來變換原特征空間，在變換后的空間中找到密集區(qū)域。在該方法中，每個網格單元匯總了一組映射到該單元中的點的信息。這種匯總信息適合于在內存中進行多分辨率小波變換和隨后的聚類分析使用。第八十七頁，共一百二十二頁，編輯于2023年，星期六（2）WaveCluster：利用小波變換聚類強調點密集的區(qū)域，而忽視在密集區(qū)域外的較弱的信息。在原始特征空間中的密集區(qū)域成為了附近點的吸引點，距離較遠的點成為抑制點。能夠自動地排除孤立點。有助于發(fā)現不同精度的聚類。聚類速度很快?？梢圆⑿谢?。第八十八頁，共一百二十二頁，編輯于2023年，星期六6.4.7基于模型的聚類方法（1）統計學方法COBWEB（2）神經網絡方法SOMs（3）高維數據聚類方法第八十九頁，共一百二十二頁，編輯于2023年，星期六（1）統計學方法COBWEB

COBWEB算法將對象增量地加入到分類樹中。

COBWEB算法沿著一條適當的路徑向下，修改計數，尋找可以分類該對象的最好節(jié)點。

COBWEB算法也計算為給定對象創(chuàng)建一個新的節(jié)點所產生的分類效用。它與基于現存節(jié)點的計算相比較。根據產生最高分類效用的劃分，對象被置于一個已存在的類，或者為它創(chuàng)建一個新類。COBWEB算法可以自動修正劃分中類的數目。它不需要用戶提供這樣的輸入參數。第九十頁，共一百二十二頁，編輯于2023年，星期六（1）統計學方法COBWEB

CORWEB算法的優(yōu)點：它不需要用戶輸入參數來確定分類的個數，它可以自動修正劃分中類的數目。缺點：首先，它基于這樣一個假設：在每個屬性上的概率分布是彼此獨立的。由于屬性間經常是相關的，這個假設并不總是成立。此外，聚類的概率分布表示使得更新和存儲類相當昂貴。因為時間和空間復雜度不只依賴于屬性的數目，而且取決于每個屬性的值的數目，所以當屬性有大量的取值時情況尤其嚴重。第九十一頁，共一百二十二頁，編輯于2023年，星期六（2）神經網絡方法SOMs算法步驟：Step1隨機選取一組輸入層神經元到輸出層神經元之間的權值；Step2選取輸出神經元j的鄰接神經元集合Sj。Sj(0)是初始時刻為0的神經元集合形狀，Sj(t)則為t

時刻的形狀；Step3輸入一個新樣本X；Step4計算歐式距離dj，即輸入樣本與每個輸入神經元j之間的距離；Step5修正輸出神經元j*及其鄰近神經元的權值；Step6重復Step3-Step5的學習過程。第九十二頁，共一百二十二頁，編輯于2023年，星期六（3）高維數據聚類方法1）CLIQUE：維增長子空間聚類方法2）PROCLUS：維歸約子空間聚類方法第九十三頁，共一百二十二頁，編輯于2023年，星期六1）CLIQUE：維增長子空間聚類方法算法步驟：Step1找出對應于每個屬性的一維空間中的所有稠密區(qū)域；Step22k；Step3repeat；Step4由稠密的k-1維單元產生所有的候選稠密k維單元；Step5刪除點數少于ξ的單元；Step6kk+1

；Step7until不存在候選稠密k維單元；Step8通過取所有鄰接的、高密度的單元并發(fā)現簇；Step9使用一小組描述簇中單元的屬性值閾的不等式概括每一個簇。第九十四頁，共一百二十二頁，編輯于2023年，星期六1）CLIQUE：維增長子空間聚類方法缺點：CLIQUE算法容易破壞密集區(qū)域的邊緣，降低最終結果的準確性。不能自動去除數據集中的孤立點，增加了計算復雜性。可能會剪掉一些密集單元，對最終的聚類結果質量造成影響。算法的多步驟都采用近似算法，聚類結果的精確性可能因此降低。第九十五頁，共一百二十二頁，編輯于2023年，星期六2）PROCLUS：維歸約子空間聚類方法投影聚類（PROjectedCLUstering,PROCLUS）是一種典型的維規(guī)約子空間聚類方法，即它不是從單維空間開始，而是從高維的屬性空間中尋找簇的初始近似開始。對每組各簇賦值一個權值，并且在下一輪迭代中使用這些更新的權重產生簇。這導致在某期望維度的所有子空間中檢測稠密區(qū)域，并且避免在較低維度的投影維產生大量重疊的維。第九十六頁，共一百二十二頁，編輯于2023年，星期六6.4.8模糊聚類FCM由于模糊聚類得到了樣本屬于各個類別的不確定性程度，表達了樣本類屬的中介性，因此更能客觀地反映現實世界。第九十七頁，共一百二十二頁，編輯于2023年，星期六第六章數據挖掘基本算法6.1分類規(guī)則挖掘6.2預測分析與趨勢分析規(guī)則6.3數據挖掘的關聯算法6.4數據挖掘的聚類算法6.5數據挖掘的統計分析算法6.6數據挖掘的品種優(yōu)化算法6.7數據挖掘的進化算法第九十八頁，共一百二十二頁，編輯于2023年，星期六6.5數據挖掘的統計分析算法6.5.1辨別分析6.5.2回歸建模6.5.3優(yōu)點和缺點第九十九頁，共一百二十二頁，編輯于2023年，星期六6.5.1辨別分析辯別分析找出一系列數或權重描述性分類函數，該函數能最大限度地劃分變量類別。辨別分析在發(fā)現變量的相似集合方面很流行，進行顧客市場細分時此技術很有用。閾值決定是否將對象歸入一個組，如果對象大于等于閾值，則屬于該組；對象小于閾值，則屬于另一組。權重被稱之為辨別系數，聚類的數據挖掘過程與此相似。第一百頁，共一百二十二頁，編輯于2023年，星期六6.5.2回歸建?；貧w方程用一組獨立變量和常量估計一因變量，因此分類研究可以用傳統統計回歸技術構建。線性回歸模型致力于實現許多數據挖掘工具的功能，如預測顧客對直接郵寄廣告活動的反應。引入條件概率技術后，回歸技術可用于預測，預測反應所用的回歸模型有時叫做線性概率模型。Logit模型就是回歸模型的一種，其中所有獨立變量都是分類的；logisticregression模型與logit模型相似，但是此模型中還可有連續(xù)變量。第一百零一頁，共一百二十二頁，編輯于2023年，星期六6.5.3優(yōu)點和缺點優(yōu)點精確、易理解且已廣泛使用。缺點統計學受到的最大批判是很難有效使用，許多商業(yè)人員更容易掌握數據挖掘而無法搞清楚統計術語，因此統計學家與想利用預測模型的商業(yè)人員總是存在隔閡。IBM，SPSS和SAS公司一直在努力將標準的統計模型與神經元網絡、決策樹及其他與數據挖掘有關的技術結合在一起。第一百零二頁，共一百二十二頁，編輯于2023年，星期六第六章數據挖掘基本算法6.1分類規(guī)則挖掘6.2預測分析與趨勢分析規(guī)則6.3數據挖掘的關聯算法6.4數據挖掘的聚類算法6.5數據挖掘的統計分析算法6.6數據挖掘的品種優(yōu)化算法6.7數據挖掘的進化算法第一百零三頁，共一百二十二頁，編輯于2023年，星期六6.6數據挖掘的品種優(yōu)化算法6.6.1品種優(yōu)化6.6.2品種優(yōu)化的算法第一百零四頁，共一百二十二頁，編輯于2023年，星期六6.6.1品種優(yōu)化品種優(yōu)化是選擇恰當的產品組合以高質量地完成零售商預定商業(yè)目標的過程。這些目標可以是短期利潤、也可以是長期市場占有率，還可以構建長期客戶群及其綜合率等。一般品種優(yōu)化包括檢查現有類別產品的品種和決定是否增加或剔除有關產品。品種優(yōu)化過程可分成兩部分：第一部分要解決的問題是當我們從現有的品種減少或往其中增加若干產品時銷量如何變化；第二部分考慮品種的變化如何影響成本。第一百零五頁，共一百二十二頁，編輯于2023年，星期六6.6.1品種優(yōu)化（1）銷量銷量具有多樣性和替換性。當我們從某一類的產品中去掉一種產品后，去掉產品的部分銷量會轉嫁到剩余產品中，而另一部分銷量則會消失。當我們向某一類產品中添加一種產品，那么這種產品的銷量部分是由原有產品調撥過來的，而其余銷量則來自從來沒有買過此類產品的新客戶或那些來購買此產品的同時附帶購買其他產品的客戶。每一類別中產品的多樣性和替換性之間就呈現出競爭的趨勢。第一百零六頁，共一百二十二頁，編輯于2023年，星期六6.6.1品種優(yōu)化某一類別所包含的產品越多，該類產品的銷量就可能越高。然而由于產品的替換性，某一產品類別包含的品種越多，每一附加產品對銷量的邊際影響就越小，所以隨著產品類別中品種數的增加，銷量的邊際回報反而減少。由于產品的相似性和可替換性，客戶對某一產品的需求可能轉移到本類產品中的其他產品；同樣，客戶對某一產品的需求也可能來自本類產品中的其他產品。對需求轉移進行評估的一個簡單方法就是采用變化曲線。第一百零七頁，共一百二十二頁，編輯于2023年，星期六6.6.1品種優(yōu)化（2）成本當一個品種中產品數量增加到某一水平時，銷量不再增加。品種數量在不斷地增加，因此成本總是在增加的。這兩種趨勢的結果是，隨著品種的增加，利潤會持續(xù)增加到某一最大值，然后開始減少。因此，存在著一種能獲得最大利潤的最優(yōu)的品種數。品種優(yōu)化問題與兩種成本密切相關：可避免成本和機會成本。第一百零八頁，共一百二十二頁，編輯于2023年，星期六6.6.1品種優(yōu)化可避免成本是指通過改變品種可以免除的成本。機會成本是改變品種時損失的利益。第一百零九頁，共一百二十二頁，編輯于2023年，星期六6.6.2品種優(yōu)化的算法