數(shù)據(jù)挖掘基本算法

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

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

。用對(duì)應(yīng)的秩rif代替xif，rif

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

。Step4循環(huán)執(zhí)行Step2和Step3，直到數(shù)據(jù)的劃分不再發(fā)生變化。第37頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法通常采用的準(zhǔn)則函數(shù)是平方誤差準(zhǔn)則函數(shù)，其定義如下：(6-16)其中，E是數(shù)據(jù)庫(kù)中所有對(duì)象的平方誤差的總和；p是空間中的點(diǎn)，表示給定的數(shù)據(jù)對(duì)象；mi是簇Ci的平均值（p和mi都是多維的）。也就是說，對(duì)于每個(gè)簇中的每個(gè)對(duì)象，求對(duì)象到其簇中心距離的平方，然后求和。這個(gè)準(zhǔn)則試圖使生成的結(jié)果簇盡可能地緊湊和獨(dú)立。第38頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法輸入：k：簇的數(shù)目n：數(shù)據(jù)庫(kù)對(duì)象的個(gè)數(shù)輸出：k個(gè)簇，使平方誤差最小方法：隨機(jī)選擇k個(gè)對(duì)象作為初始的代表對(duì)象；repeat；根據(jù)與每個(gè)中心的距離，將每個(gè)對(duì)象賦給最近的簇；重新計(jì)算每個(gè)簇的平均值；until不再發(fā)生變化。第39頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法例6.9k-means算法使用實(shí)例設(shè)數(shù)據(jù)對(duì)象集合如表6.12所示。簇?cái)?shù)目k=2，采用k-means算法對(duì)其進(jìn)行聚類。表6.12pxy11121.21.230.81.240.90.751.30.9611.473383.12.893.23.4102.73.3112.62.9第40頁(yè)，共122頁(yè)，2023年，2月20日，星期五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。第41頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法第二次迭代，用m1(1.033,1.067)，m2(2.92,3.08)作為簇C1，C2的簇中心，重新對(duì)數(shù)據(jù)進(jìn)行劃分。將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第42頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法由于在兩次迭代過程中，2個(gè)簇中心都不變，所以停止迭代過程。得到的兩個(gè)聚類分別為：C1={p1,p2,p3,p4,p5,p6}C2={p7,p8,p9,p10,p11}第43頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法k-means聚類算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí)，它的效果較好。對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮的和高效率的，復(fù)雜度是O(nkt)，n是所有對(duì)象的數(shù)目，k是簇的數(shù)目，t是迭代的次數(shù)。第44頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法不足：k-means算法只有在簇的平均值被定義的情況下才能使用。k-means算法的不足之處在于它要多次掃描數(shù)據(jù)庫(kù)。k-means算法只能找出球形的類，而不能發(fā)現(xiàn)任意形狀的類。初始質(zhì)心的選擇對(duì)聚類結(jié)果有較大的影響。k-means算法對(duì)于噪聲和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。k-平均算法的變種：k-模方法、EM算法等第45頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法2）基于有代表性的對(duì)象的技術(shù)：k-中心點(diǎn)法為了避免k-means算法對(duì)孤立點(diǎn)的敏感性，不采用簇中對(duì)象的平均值作為參照點(diǎn)，可以選用簇中位置最中心的對(duì)象，即medoid。這樣的劃分方法仍然是基于最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和的原則來執(zhí)行的。這是k-medoids方法的基礎(chǔ)。通常采用的準(zhǔn)則函數(shù)是絕對(duì)誤差準(zhǔn)則函數(shù)，其定義如下：(6-17)其中，E是數(shù)據(jù)庫(kù)中所有對(duì)象的絕對(duì)誤差的總和；p是空間中的點(diǎn)，表示給定的數(shù)據(jù)對(duì)象；oi是簇Ci中的代表對(duì)象。第46頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法k-medoids算法的基本策略：首先隨機(jī)選擇k個(gè)對(duì)象，每個(gè)對(duì)象代表一個(gè)簇，把其余的對(duì)象分別分配給最相似的簇。然后，反復(fù)地嘗試把每個(gè)中心分別用其他非中心來代替，檢查聚類的質(zhì)量是否有所提高。若是，則保留該替換，重復(fù)上述過程，直到不再發(fā)生變化。為了判定一個(gè)非代表對(duì)象Orandom是否是當(dāng)前一個(gè)代表對(duì)象Oj的好的替代，對(duì)于每一個(gè)非中心點(diǎn)對(duì)象，考慮下面的四種情況：第一種情況：p當(dāng)前隸屬于中心點(diǎn)對(duì)象Oj。如果Orandom代替Oj作為一個(gè)中心點(diǎn)，且p離Oi最近，i≠j，那么p被重新分配給Oi

。第47頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法第二種情況：p當(dāng)前隸屬于中心點(diǎn)對(duì)象Oj。如果Orandom代替Oj作為一個(gè)中心點(diǎn)，且p離Orandom最近，那么p被重新分配給Orandom

。第三種情況：p當(dāng)前隸屬于中心點(diǎn)對(duì)象Oi，i≠j

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

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

。第48頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法每當(dāng)重新分配時(shí)，平方-誤差E所產(chǎn)生的差別對(duì)代價(jià)函數(shù)有影響。因此，如果一個(gè)當(dāng)前的中心點(diǎn)對(duì)象被非中心點(diǎn)所代替，就通過代價(jià)函數(shù)計(jì)算平方-誤差值所產(chǎn)生的差別。替換的總代價(jià)是所有非中心點(diǎn)對(duì)象所產(chǎn)生的代價(jià)之和。如果總代價(jià)是負(fù)的，那么實(shí)際的平方-誤差將會(huì)減少，Oj可以被Orandom代替。如果總代價(jià)是正的，則當(dāng)前的中心點(diǎn)Oj被認(rèn)為是可接受的，在本次迭代中沒有變化發(fā)生。第49頁(yè)，共122頁(yè)，2023年，2月20日，星期五6.4.3劃分方法輸入：k：簇的數(shù)目n：數(shù)據(jù)庫(kù)對(duì)象的個(gè)數(shù)輸出：k個(gè)簇，使所有對(duì)象與其最近代表對(duì)象的相異度總和最小方法：隨機(jī)選擇k個(gè)對(duì)象作為初始的代表對(duì)象；repeat；指派每個(gè)剩余的對(duì)象給離它最近的代表對(duì)象所代表的簇；隨意地選擇一個(gè)非代表對(duì)象Orandom；計(jì)算用Orandom代替Oj的總代價(jià)S；如果S<0，則用Orandom替換Oj

，形成新的k個(gè)代表對(duì)象的集合；

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

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

讀取D中任意一個(gè)未分類的對(duì)象p；Step2

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

如果|Neps(p)|<MinPts（即p為非核心對(duì)象），則將p標(biāo)記為噪聲，并執(zhí)行Step1；第77頁(yè)，共122頁(yè)，2023年，2月20日，星期五（1）DBSCAN：基于高密度連通區(qū)域聚類Step4

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

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

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

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

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

COBWEB算法沿著一條適當(dāng)?shù)穆窂较蛳?，修改?jì)數(shù)，尋找可以分類該對(duì)象的最好節(jié)點(diǎn)。

COBWEB算法也計(jì)算為給定對(duì)象創(chuàng)建一個(gè)新的節(jié)點(diǎn)所產(chǎn)生的分類效用。它與基于現(xiàn)存節(jié)點(diǎn)的計(jì)算相比較。根據(jù)產(chǎn)生最高分類效用的劃分，對(duì)象被置于一個(gè)已存在的類，或者為它創(chuàng)建一個(gè)新類。COBWEB算法可以自動(dòng)修正劃分中類的數(shù)目。它不需要用戶提供這樣的輸入?yún)?shù)。第90頁(yè)，共122頁(yè)，2023年，2月20日，星期五（1）統(tǒng)計(jì)學(xué)方法COBWEB

CORWEB算法的優(yōu)點(diǎn)：它不需要用戶輸入?yún)?shù)來確定分類的個(gè)數(shù)，它可以自動(dòng)修正劃分中類的數(shù)目。缺點(diǎn)：首先，它基于這樣一個(gè)假設(shè)：在每個(gè)屬性上的概率分布是彼此獨(dú)立的。由于屬性間經(jīng)常是相關(guān)的，這個(gè)假設(shè)并不總是成立。此外，聚類的概率分布表示使得更新和存儲(chǔ)類相當(dāng)昂貴。因?yàn)闀r(shí)間和空間復(fù)雜度不只依賴于屬性的數(shù)目，而且取決于每個(gè)屬性的值的數(shù)目，所以當(dāng)屬性有大量的取值時(shí)情況尤其嚴(yán)重。第91頁(yè)，共122頁(yè)，2023年，2月20日，星期五（2）神經(jīng)網(wǎng)絡(luò)方法SOMs算法步驟：Step1隨機(jī)選取一組輸入層神經(jīng)元到輸出層神經(jīng)元之間的權(quán)值；Step2選取輸出神經(jīng)元j的鄰接神經(jīng)元集合Sj。Sj(0)是初始時(shí)刻為0的神經(jīng)元集合形狀，Sj(t)則為t

時(shí)刻的形狀；Step3輸入一個(gè)新樣本X；Step4計(jì)算歐式距離dj，即輸入樣本與每個(gè)輸入神經(jīng)元j之間的距離；Step5修正輸出神經(jīng)元j*及其鄰近神經(jīng)元的權(quán)值；Step6重復(fù)Step3-Step5的學(xué)習(xí)過程。第92頁(yè)，共122頁(yè)，2023年，2月20日，星期五（3）高維數(shù)據(jù)聚類方法1）CLIQUE：維增長(zhǎng)子空間聚類方法2）PROCLUS：維歸約子空間聚類方法第93頁(yè)，共122頁(yè)，2023年，2月20日，星期五1）CLIQUE：維增長(zhǎng)子空間聚類方法算法步驟：Step1找出對(duì)應(yīng)于每個(gè)屬性的一維空間中的所有稠密區(qū)域；Step22k；Step3repeat；Step4由稠密的k-1維單元產(chǎn)生所有的候選稠密k維單元；Step5刪除點(diǎn)數(shù)少于ξ的單元；Step6kk+1

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