一、層次聚類

1、層次聚類的原理及分類

1)層次法(Hierarchicalmethods)先計(jì)算樣本之間的距離。每次將距離最近的點(diǎn)合并到同一個(gè)類。然后，再計(jì)算類與類之間的距離，將距離最近的類合并為一個(gè)大類。不停的合并，直到合成了一個(gè)類。其中類與類的距離的計(jì)算方法有：最短距離法，最長距離法，中間距離法，類平均法等。比如最短距離法，將類與類的距離定義為類與類之間樣本的最短距離。

層次聚類算法根據(jù)層次分解的順序分為：自下底向上和自上向下，即凝聚的層次聚類算法和分裂的層次聚類算法(agglomerative和divisive)，也可以理解為自下而上法(bottom-up)和自上而下法(top-down)。自下而上法就是一開始每個(gè)個(gè)體(object)都是一個(gè)類，然后根據(jù)linkage尋找同類，最后形成一個(gè)“類”。自上而下法就是反過來，一開始所有個(gè)體都屬于一個(gè)“類”，然后根據(jù)linkage排除異己，最后每個(gè)個(gè)體都成為一個(gè)“類”。這兩種路方法沒有孰優(yōu)孰劣之分，只是在實(shí)際應(yīng)用的時(shí)候要根據(jù)數(shù)據(jù)特點(diǎn)以及你想要的“類”的個(gè)數(shù)，來考慮是自上而下更快還是自下而上更快。至于根據(jù)Linkage判斷“類”的方法就是最短距離法、最長距離法、中間距離法、類平均法等等(其中類平均法往往被認(rèn)為是最常用也最好用的方法，一方面因?yàn)槠淞己玫膯握{(diào)性，另一方面因?yàn)槠淇臻g擴(kuò)張/濃縮的程度適中)。為彌補(bǔ)分解與合并的不足，層次合并經(jīng)常要與其它聚類方法相結(jié)合，如循環(huán)定位。

2)Hierarchicalmethods中比較新的算法有BIRCH(BalancedIterativeReducingandClusteringUsingHierarchies利用層次方法的平衡迭代規(guī)約和聚類)主要是在數(shù)據(jù)量很大的時(shí)候使用，而且數(shù)據(jù)類型是numerical。首先利用樹的結(jié)構(gòu)對對象集進(jìn)行劃分，然后再利用其它聚類方法對這些聚類進(jìn)行優(yōu)化;ROCK(AHierarchicalClusteringAlgorithmforCategoricalAttributes)主要用在categorical的數(shù)據(jù)類型上;Chameleon(AHierarchicalClusteringAlgorithmUsingDynamicModeling)里用到的linkage是kNN(k-nearest-neighbor)算法，并以此構(gòu)建一個(gè)graph，Chameleon的聚類效果被認(rèn)為非常強(qiáng)大，比BIRCH好用，但運(yùn)算復(fù)雜度很高，O(n^2)。

2、層次聚類的流程

凝聚型層次聚類的策略是先將每個(gè)對象作為一個(gè)簇，然后合并這些原子簇為越來越大的簇，直到所有對象都在一個(gè)簇中，或者某個(gè)終結(jié)條件被滿足。絕大多數(shù)層次聚類屬于凝聚型層次聚類，它們只是在簇間相似度的定義上有所不同。

這里給出采用最小距離的凝聚層次聚類算法流程：

(1)將每個(gè)對象看作一類，計(jì)算兩兩之間的最小距離;

(2)將距離最小的兩個(gè)類合并成一個(gè)新類;

(3)重新計(jì)算新類與所有類之間的距離;

(4)重復(fù)(2)、(3)，直到所有類最后合并成一類。

聚類的效果如下圖，黑色是噪音點(diǎn)：

另外我們可以看出凝聚的層次聚類并沒有類似基本K均值的全局目標(biāo)函數(shù)，沒有局部極小問題或是很難選擇初始點(diǎn)的問題。合并的操作往往是最終的，一旦合并兩個(gè)簇之后就不會撤銷。當(dāng)然其計(jì)算存儲的代價(jià)是昂貴的。

3、層次聚類的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：1，距離和規(guī)則的相似度容易定義，限制少;2，不需要預(yù)先制定聚類數(shù);3，可以發(fā)現(xiàn)類的層次關(guān)系;4，可以聚類成其它形狀

缺點(diǎn)：1，計(jì)算復(fù)雜度太高;2，奇異值也能產(chǎn)生很大影響;3，算法很可能聚類成鏈狀

r語言中使用hclust(d,method=“complete“,members=NULL)：進(jìn)行層次聚類。d為距離矩陣;method表示類的合并方法，single最短距離法，complete最長距離法，median中間距離法，mcquitty相似法，average類平均法，centroid重心法，ward離差平方和法;members為NULL或d長度的矢量。

二、劃分聚類法k-means

基于劃分的方法(Partition-basedmethods)：其原理簡單來說就是，想象你有一堆散點(diǎn)需要聚類，想要的聚類效果就是“類內(nèi)的點(diǎn)都足夠近，類間的點(diǎn)都足夠遠(yuǎn)”。首先你要確定這堆散點(diǎn)最后聚成幾類，然后挑選幾個(gè)點(diǎn)作為初始中心點(diǎn)，再然后依據(jù)預(yù)先定好的啟發(fā)式算法(heuristicalgorithms)給數(shù)據(jù)點(diǎn)做迭代重置(iterativerelocation)，直到最后到達(dá)“類內(nèi)的點(diǎn)都足夠近，類間的點(diǎn)都足夠遠(yuǎn)”的目標(biāo)效果。

Partition-basedmethods聚類多適用于中等體量的數(shù)據(jù)集，但我們也不知道“中等”到底有多“中”，所以不妨理解成，數(shù)據(jù)集越大，越有可能陷入局部最小。

1、Kmeans算法的原理

k-means算法以k為參數(shù)，把n個(gè)對象分成k個(gè)簇，使簇內(nèi)具有較高的相似度，而簇間的相似度較低。k-means算法的處理過程如下：首先，隨機(jī)地選擇k個(gè)對象，每個(gè)對象初始地代表了一個(gè)簇的平均值或中心，即選擇K個(gè)初始質(zhì)心;對剩余的每個(gè)對象，根據(jù)其與各簇中心的距離，將它賦給最近的簇;然后重新計(jì)算每個(gè)簇的平均值。

這個(gè)過程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂，直到質(zhì)心不發(fā)生明顯的變化。通常，采用平方誤差準(zhǔn)則，誤差的平方和SSE作為全局的目標(biāo)函數(shù)，即最小化每個(gè)點(diǎn)到最近質(zhì)心的歐幾里得距離的平方和。此時(shí)，簇的質(zhì)心就是該簇內(nèi)所有數(shù)據(jù)點(diǎn)的平均值。

選擇K個(gè)點(diǎn)作為初始質(zhì)心

repeat將每個(gè)點(diǎn)指派到最近的質(zhì)心，形成K個(gè)簇

重新計(jì)算每個(gè)簇的質(zhì)心

until簇不發(fā)生變化或達(dá)到最大迭代次數(shù)

時(shí)間復(fù)雜度：O(tKmn)，其中，t為迭代次數(shù)，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)

空間復(fù)雜度：O((m+K)n)，其中，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)

K-Means算法的詳細(xì)過程

從上圖中，我們可以看到，A,B,C,D,E

是五個(gè)在圖中點(diǎn)。而灰色的點(diǎn)是我們的種子點(diǎn)，也就是我們用來找點(diǎn)群的點(diǎn)。有兩個(gè)種子點(diǎn)，所以K=2。

然后，K-Means的算法如下：

①隨機(jī)在圖中取K(這里K=2)個(gè)種子點(diǎn)。

②然后對圖中的所有點(diǎn)求到這K個(gè)種子點(diǎn)的距離，假如點(diǎn)Pi離種子點(diǎn)Si最近，那么Pi屬于Si點(diǎn)群。(我們可以看到A,B屬于上面的種子點(diǎn)，C,D,E屬于下面中部的種子點(diǎn))

③接下來，我們要移動種子點(diǎn)到屬于他的“點(diǎn)群”的中心。(見圖上的第三步)

④然后重復(fù)第2)和第3)步，直到，種子點(diǎn)沒有移動(我們可以看到圖中的第四步上面的種子點(diǎn)聚合了A,B,C，下面的種子點(diǎn)聚合了D，E)。

聚類的效果如下圖，折線是歷次循環(huán)時(shí)3個(gè)簇的質(zhì)心的更新軌跡，黑點(diǎn)是初始質(zhì)心：

我們查看基本K均值算法實(shí)現(xiàn)步驟及上面的聚類效果可以發(fā)現(xiàn)，該聚類算法將所有數(shù)據(jù)點(diǎn)都進(jìn)行了指派，不識別噪音點(diǎn)。另外選擇適當(dāng)?shù)某踉囐|(zhì)心是基本K均值過程的關(guān)鍵。

2、k均值的優(yōu)缺點(diǎn)及分類

優(yōu)點(diǎn)：1，簡單，易于理解和實(shí)現(xiàn);2，時(shí)間復(fù)雜度低

缺點(diǎn)：

1)kmeans要手工輸入類數(shù)目，對初始值的設(shè)置很敏感;所以有了k-means++、intelligentk-means、genetick-means;

2)k-means對噪聲和離群值非常敏感，所以有了k-medoids和k-medians;

3)k-means只用于numerical類型數(shù)據(jù)，不適用于categorical類型數(shù)據(jù)，所以k-modes;

4)k-means不能解決非凸(non-convex)數(shù)據(jù)，所以有了kernelk-means。

5)k-means主要發(fā)現(xiàn)圓形或者球形簇，不能識別非球形的簇。

3、k-means與DBSCAN的區(qū)別

k-means聚類算法的初始點(diǎn)選擇不穩(wěn)定，是隨機(jī)選取的，這就引起聚類結(jié)果的不穩(wěn)定。k-means屬于動態(tài)聚類，往往聚出來的類有點(diǎn)圓形或者橢圓形。kmeans對于圓形區(qū)域聚類效果較好，dbscan基于密度，對于集中區(qū)域效果較好。對于不規(guī)則形狀，kmeans完全無法用，dbscan可以起到很好的效果。

4、k-means注意問題

1)K如何確定

kmenas算法首先選擇K個(gè)初始質(zhì)心，其中K是用戶指定的參數(shù)，即所期望的簇的個(gè)數(shù)。這樣做的前提是我們已經(jīng)知道數(shù)據(jù)集中包含多少個(gè)簇，但很多情況下，我們并不知道數(shù)據(jù)的分布情況，實(shí)際上聚類就是我們發(fā)現(xiàn)數(shù)據(jù)分布的一種手段。如何有效的確定K值，這里大致提供幾種方法：

①與層次聚類結(jié)合[2]

經(jīng)常會產(chǎn)生較好的聚類結(jié)果的一個(gè)有趣策略是，首先采用層次凝聚算法決定結(jié)果粗的數(shù)目，并找到一個(gè)初始聚類，然后用迭代重定位來改進(jìn)該聚類。

②穩(wěn)定性方法[3]

穩(wěn)定性方法對一個(gè)數(shù)據(jù)集進(jìn)行2次重采樣產(chǎn)生2個(gè)數(shù)據(jù)子集，再用相同的聚類算法對2個(gè)數(shù)據(jù)子集進(jìn)行聚類，產(chǎn)生2個(gè)具有k個(gè)聚類的聚類結(jié)果，計(jì)算2個(gè)聚類結(jié)果的相似度的分布情況。2個(gè)聚類結(jié)果具有高的相似度說明k個(gè)聚類反映了穩(wěn)定的聚類結(jié)構(gòu)，其相似度可以用來估計(jì)聚類個(gè)數(shù)。采用次方法試探多個(gè)k，找到合適的k值。

③系統(tǒng)演化方法[3]

系統(tǒng)演化方法將一個(gè)數(shù)據(jù)集視為偽熱力學(xué)系統(tǒng)，當(dāng)數(shù)據(jù)集被劃分為K個(gè)聚類時(shí)稱系統(tǒng)處于狀態(tài)K。系統(tǒng)由初始狀態(tài)K=1出發(fā)，經(jīng)過分裂過程和合并過程，系統(tǒng)將演化到它的穩(wěn)定平衡狀態(tài)Ki，所對應(yīng)的聚類結(jié)構(gòu)決定了最優(yōu)類數(shù)Ki。系統(tǒng)演化方法能提供關(guān)于所有聚類之間的相對邊界距離或可分程度，適用于明顯分離的聚類結(jié)構(gòu)和輕微重疊的聚類結(jié)構(gòu)。

④使用canopy算法進(jìn)行初始劃分[4]

基于CanopyMethod的聚類算法將聚類過程分為兩個(gè)階段

Stage1、聚類最耗費(fèi)計(jì)算的地方是計(jì)算對象相似性的時(shí)候，CanopyMethod在第一階段選擇簡單、計(jì)算代價(jià)較低的方法計(jì)算對象相似性，將相似的對象放在一個(gè)子集中，這個(gè)子集被叫做Canopy，通過一系列計(jì)算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個(gè)對象不屬于任何Canopy的情況，可以把這一階段看做數(shù)據(jù)預(yù)處理;

Stage2、在各個(gè)Canopy內(nèi)使用傳統(tǒng)的聚類方法(如K-means)，不屬于同一Canopy的對象之間不進(jìn)行相似性計(jì)算。

從這個(gè)方法起碼可以看出兩點(diǎn)好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會大大減少后續(xù)需要計(jì)算相似性的對象的個(gè)數(shù);其次，類似于K-means這樣的聚類方法是需要人為指出K的值的，通過Stage1得到的Canopy個(gè)數(shù)完全可以作為這個(gè)K值，一定程度上減少了選擇K的盲目性。

其他方法如貝葉斯信息準(zhǔn)則方法(BIC)可參看文獻(xiàn)[5]。

2)初始質(zhì)心的選取

選擇適當(dāng)?shù)某跏假|(zhì)心是基本kmeans算法的關(guān)鍵步驟。常見的方法是隨機(jī)的選取初始質(zhì)心，但是這樣簇的質(zhì)量常常很差。處理選取初始質(zhì)心問題的一種常用技術(shù)是：多次運(yùn)行，每次使用一組不同的隨機(jī)初始質(zhì)心，然后選取具有最小SSE(誤差的平方和)的簇集。這種策略簡單，但是效果可能不好，這取決于數(shù)據(jù)集和尋找的簇的個(gè)數(shù)。

第二種有效的方法是，取一個(gè)樣本，并使用層次聚類技術(shù)對它聚類。從層次聚類中提取K個(gè)簇，并用這些簇的質(zhì)心作為初始質(zhì)心。該方法通常很有效，但僅對下列情況有效：(1)樣本相對較小，例如數(shù)百到數(shù)千(層次聚類開銷較大);(2)K相對于樣本大小較小

第三種選擇初始質(zhì)心的方法，隨機(jī)地選擇第一個(gè)點(diǎn)，或取所有點(diǎn)的質(zhì)心作為第一個(gè)點(diǎn)。然后，對于每個(gè)后繼初始質(zhì)心，選擇離已經(jīng)選取過的初始質(zhì)心最遠(yuǎn)的點(diǎn)。使用這種方法，確保了選擇的初始質(zhì)心不僅是隨機(jī)的，而且是散開的。但是，這種方法可能選中離群點(diǎn)。此外，求離當(dāng)前初始質(zhì)心集最遠(yuǎn)的點(diǎn)開銷也非常大。為了克服這個(gè)問題，通常該方法用于點(diǎn)樣本。由于離群點(diǎn)很少(多了就不是離群點(diǎn)了)，它們多半不會在隨機(jī)樣本中出現(xiàn)。計(jì)算量也大幅減少。

第四種方法就是上面提到的canopy算法。

3)距離的度量

常用的距離度量方法包括：歐幾里得距離和余弦相似度。兩者都是評定個(gè)體間差異的大小的。歐幾里得距離度量會受指標(biāo)不同單位刻度的影響，所以一般需要先進(jìn)行標(biāo)準(zhǔn)化，同時(shí)距離越大，個(gè)體間差異越大;空間向量余弦夾角的相似度度量不會受指標(biāo)刻度的影響，余弦值落于區(qū)間[-1,1]，值越大，差異越小。但是針對具體應(yīng)用，什么情況下使用歐氏距離，什么情況下使用余弦相似度?

從幾何意義上來說，n維向量空間的一條線段作為底邊和原點(diǎn)組成的三角形，其頂角大小是不確定的。也就是說對于兩條空間向量，即使兩點(diǎn)距離一定，他們的夾角余弦值也可以隨意變化。感性的認(rèn)識，當(dāng)兩用戶評分趨勢一致時(shí)，但是評分值差距很大，余弦相似度傾向給出更優(yōu)解。舉個(gè)極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認(rèn)知其實(shí)是一樣的，但是歐式距離給出的解顯然沒有余弦值合理。

4)質(zhì)心的計(jì)算

對于距離度量不管是采用歐式距離還是采用余弦相似度，簇的質(zhì)心都是其均值，即向量各維取平均即可。

5)算法停止條件

一般是目標(biāo)函數(shù)達(dá)到最優(yōu)或者達(dá)到最大的迭代次數(shù)即可終止。對于不同的距離度量，目標(biāo)函數(shù)往往不同。當(dāng)采用歐式距離時(shí)，目標(biāo)函數(shù)一般為最小化對象到其簇質(zhì)心的距離的平方和。

當(dāng)采用余弦相似度時(shí)，目標(biāo)函數(shù)一般為最大化對象到其簇質(zhì)心的余弦相似度和。

6)空聚類的處理

如果所有的點(diǎn)在指派步驟都未分配到某個(gè)簇，就會得到空簇。如果這種情況發(fā)生，則需要某種策略來選擇一個(gè)替補(bǔ)質(zhì)心，否則的話，平方誤差將會偏大。一種方法是選擇一個(gè)距離當(dāng)前任何質(zhì)心最遠(yuǎn)的點(diǎn)。這將消除當(dāng)前對總平方誤差影響最大的點(diǎn)。另一種方法是從具有最大SSE的簇中選擇一個(gè)替補(bǔ)的質(zhì)心。這將分裂簇并降低聚類的總SSE。如果有多個(gè)空簇，則該過程重復(fù)多次。另外，編程實(shí)現(xiàn)時(shí)，要注意空簇可能導(dǎo)致的程序bug。

三、基于密度的聚類

基于密度的方法(Density-basedmethods)：k-means解決不了不規(guī)則形狀的聚類。于是就有了Density-basedmethods來系統(tǒng)解決這個(gè)問題。該方法同時(shí)也對噪聲數(shù)據(jù)的處理比較好。基于密度聚類的思想：思路就是定一個(gè)距離半徑，最少有多少個(gè)點(diǎn)，然后把可以到達(dá)的點(diǎn)都連起來，判定為同類。其原理簡單說畫圈兒，其中要定義兩個(gè)參數(shù)，一個(gè)是圈兒的最大半徑，一個(gè)是一個(gè)圈兒里最少應(yīng)容納幾個(gè)點(diǎn)。最后在一個(gè)圈里的，就是一個(gè)類。DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)就是其中的典型，可惜參數(shù)設(shè)置也是個(gè)問題，對這兩個(gè)參數(shù)的設(shè)置非常敏感。DBSCAN的擴(kuò)展叫OPTICS(OrderingPointsToIdentifyClusteringStructure)通過優(yōu)先對高密度(highdensity)進(jìn)行搜索，然后根據(jù)高密度的特點(diǎn)設(shè)置參數(shù)，改善了DBSCAN的不足。

1、DBSCAN的概念

dbscan基于密度，對于集中區(qū)域效果較好，為了發(fā)現(xiàn)任意形狀的簇，這類方法將簇看做是數(shù)據(jù)空間中被低密度區(qū)域分割開的稠密對象區(qū)域;一種基于高密度連通區(qū)域的基于密度的聚類方法，該算法將具有足夠高密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)中發(fā)現(xiàn)任意形狀的簇。

DBSCAN中的幾個(gè)定義：

Ε鄰域：給定對象半徑為Ε內(nèi)的區(qū)域稱為該對象的Ε鄰域;

核心對象：如果給定對象Ε領(lǐng)域內(nèi)的樣本點(diǎn)數(shù)大于等于MinPts，則稱該對象為核心對象;

直接密度可達(dá)：對于樣本集合D，如果樣本點(diǎn)q在p的Ε領(lǐng)域內(nèi)，并且p為核心對象，那么對象q從對象p直接密度可達(dá)。

密度可達(dá)：對于樣本集合D，給定一串樣本點(diǎn)p1,p2….pn，p=p1,q=pn,假如對象pi從pi-1直接密度可達(dá)，那么對象q從對象p密度可達(dá)。注意：密度可達(dá)是單向的，密度可達(dá)即可容納同一類。

密度相連：存在樣本集合D中的一點(diǎn)o，如果對象o到對象p和對象q都是密度可達(dá)的，那么p和q密度相聯(lián)。

密度可達(dá)是直接密度可達(dá)的傳遞閉包，并且這種關(guān)系是非對稱的。密度相連是對稱關(guān)系。DBSCAN目的是找到密度相連對象的最大集合。

有了以上的概念接下來就是算法描述了：DBSCAN通過檢查數(shù)據(jù)庫中每點(diǎn)的r鄰域來搜索簇。如果點(diǎn)p的r鄰域包含的點(diǎn)多于MinPts個(gè)，則創(chuàng)建一個(gè)以p為核心對象的新簇。然后，DBSCAN迭代的聚集從這些核心對象直接密度可達(dá)的對象，這個(gè)過程可能涉及一些密度可達(dá)簇的合并。當(dāng)沒有新的點(diǎn)可以添加到任何簇時(shí)，該過程結(jié)束。

例如：Eg:

假設(shè)半徑Ε=3，MinPts=3，點(diǎn)p的E領(lǐng)域中有點(diǎn){m,p,p1,p2,o},點(diǎn)m的E領(lǐng)域中有點(diǎn){m,q,p,m1,m2},點(diǎn)q的E領(lǐng)域中有點(diǎn){q,m},點(diǎn)o的E領(lǐng)域中有點(diǎn){o,p,s},點(diǎn)s的E領(lǐng)域中有點(diǎn){o,s,s1}.

那么核心對象有p,m,o,s(q不是核心對象，因?yàn)樗鼘?yīng)的E領(lǐng)域中點(diǎn)數(shù)量等于2，小于MinPts=3);

點(diǎn)m從點(diǎn)p直接密度可達(dá)，因?yàn)閙在p的E領(lǐng)域內(nèi)，并且p為核心對象;

點(diǎn)q從點(diǎn)p密度可達(dá)，因?yàn)辄c(diǎn)q從點(diǎn)m直接密度可達(dá)，并且點(diǎn)m從點(diǎn)p直接密度可達(dá);

點(diǎn)q到點(diǎn)s密度相連，因?yàn)辄c(diǎn)q從點(diǎn)p密度可達(dá)，并且s從點(diǎn)p密度可達(dá)。

2、簇的生成原理及過程

1)DBSCAN聚類算法原理的基本要點(diǎn)：確定半徑eps的值

①DBSCAN算法需要選擇一種距離度量，對于待聚類的數(shù)據(jù)集中，任意兩個(gè)點(diǎn)之間的距離，反映了點(diǎn)之間的密度，說明了點(diǎn)與點(diǎn)是否能夠聚到同一類中。由于DBSCAN算法對高維數(shù)據(jù)定義密度很困難，所以對于二維空間中的點(diǎn)，可以使用歐幾里德距離來進(jìn)行度量。

②DBSCAN算法需要用戶輸入2個(gè)參數(shù)：一個(gè)參數(shù)是半徑(Eps)，表示以給定點(diǎn)P為中心的圓形鄰域的范圍;另一個(gè)參數(shù)是以點(diǎn)P為中心的鄰域內(nèi)最少點(diǎn)的數(shù)量(MinPts)。如果滿足：以點(diǎn)P為中心、半徑為Eps的鄰域內(nèi)的點(diǎn)的個(gè)數(shù)不少于MinPts，則稱點(diǎn)P為核心點(diǎn)。

③DBSCAN聚類使用到一個(gè)k-距離的概念，k-距離是指：給定數(shù)據(jù)集P={p(i);

i=0,1,…n}，對于任意點(diǎn)P(i)，計(jì)算點(diǎn)P(i)到集合D的子集S={p(1),p(2),…,p(i-1),p(i+1),…,p(n)}中所有點(diǎn)之間的距離，距離按照從小到大的順序排序，假設(shè)排序后的距離集合為D={d(1),d(2),…,d(k-1),d(k),d(k+1),…,d(n)}，則d(k)就被稱為k-距離。也就是說，k-距離是點(diǎn)p(i)到所有點(diǎn)(除了p(i)點(diǎn))之間距離第k近的距離。對待聚類集合中每個(gè)點(diǎn)p(i)都計(jì)算k-距離，最后得到所有點(diǎn)的k-距離集合E={e(1),e(2),…,e(n)}。

④根據(jù)經(jīng)驗(yàn)計(jì)算半徑Eps：根據(jù)得到的所有點(diǎn)的k-距離集合E，對集合E進(jìn)行升序排序后得到k-距離集合E’，需要擬合一條排序后的E’集合中k-距離的變化曲線圖，然后繪出曲線，通過觀察，將急劇發(fā)生變化的位置所對應(yīng)的k-距離的值，確定為半徑Eps的值。

⑤根據(jù)經(jīng)驗(yàn)計(jì)算最少點(diǎn)的數(shù)量MinPts：確定MinPts的大小，實(shí)際上也是確定k-距離中k的值，DBSCAN算法取k=4，則MinPts=4。

⑥另外，如果覺得經(jīng)驗(yàn)值聚類的結(jié)果不滿意，可以適當(dāng)調(diào)整Eps和MinPts的值，經(jīng)過多次迭代計(jì)算對比，選擇最合適的參數(shù)值。可以看出，如果MinPts不變，Eps取得值過大，會導(dǎo)致大多數(shù)點(diǎn)都聚到同一個(gè)簇中，Eps過小，會導(dǎo)致一個(gè)簇的分裂;如果Eps不變，MinPts的值取得過大，會導(dǎo)致同一個(gè)簇中點(diǎn)被標(biāo)記為噪聲點(diǎn)，MinPts過小，會導(dǎo)致發(fā)現(xiàn)大量的核心點(diǎn)。

我們需要知道的是，DBSCAN算法，需要輸入2個(gè)參數(shù)，這兩個(gè)參數(shù)的計(jì)算都來自經(jīng)驗(yàn)知識。半徑Eps的計(jì)算依賴于計(jì)算k-距離，DBSCAN取k=4，也就是設(shè)置MinPts=4，然后需要根據(jù)k-距離曲線，根據(jù)經(jīng)驗(yàn)觀察找到合適的半徑Eps的值。

2)連通核心點(diǎn)生成簇

核心點(diǎn)能夠連通(有些書籍中稱為：“密度可達(dá)”)，它們構(gòu)成的以Eps長度為半徑的圓形鄰域相互連接或重疊，這些連通的核心點(diǎn)及其所處的鄰域內(nèi)的全部點(diǎn)構(gòu)成一個(gè)簇。假設(shè)MinPts=4，則連通的核心點(diǎn)示例，如下圖所示：

計(jì)算連通的核心點(diǎn)的思路是，基于廣度遍歷與深度遍歷集合的方式：從核心點(diǎn)集合S中取出一個(gè)點(diǎn)p，計(jì)算點(diǎn)p與S集合中每個(gè)點(diǎn)(除了p點(diǎn))是否連通，可能會得到一個(gè)連通核心點(diǎn)的集合C1，然后從集合S中刪除點(diǎn)p和C1集合中的點(diǎn)，得到核心點(diǎn)集合S1;再從S1中取出一個(gè)點(diǎn)p1，計(jì)算p1與核心點(diǎn)集合S1集中每個(gè)點(diǎn)(除了p1點(diǎn))是否連通，可能得到一個(gè)連通核心點(diǎn)集合C2，再從集合S1中刪除點(diǎn)p1和C2集合中所有點(diǎn)，得到核心點(diǎn)集合S2，……最后得到p、p1、p2、……，以及C1、C2、……就構(gòu)成一個(gè)簇的核心點(diǎn)。最終將核心點(diǎn)集合S中的點(diǎn)都遍歷完成，得到所有的簇。

參數(shù)eps的設(shè)置，如果eps設(shè)置過大，則所有的點(diǎn)都會歸為一個(gè)簇，如果設(shè)置過小，那么簇的數(shù)目會過多。如果MinPts設(shè)置過大的話，很多點(diǎn)將被視為噪聲點(diǎn)。

3、根據(jù)數(shù)據(jù)點(diǎn)的密度分為三類點(diǎn)：

(1)核心點(diǎn)：該點(diǎn)在鄰域內(nèi)的密度超過給定的閥值MinPs。

(2)邊界點(diǎn)：該點(diǎn)不是核心點(diǎn)，但是其鄰域內(nèi)包含至少一個(gè)核心點(diǎn)。

(3)噪音點(diǎn)：不是核心點(diǎn)，也不是邊界點(diǎn)。

有了以上對數(shù)據(jù)點(diǎn)的劃分，聚合可以這樣進(jìn)行：各個(gè)核心點(diǎn)與其鄰域內(nèi)的所有核心點(diǎn)放在同一個(gè)簇中，把邊界點(diǎn)跟其鄰域內(nèi)的某個(gè)核心點(diǎn)放在同一個(gè)簇中。

聚類的效果如下圖，黑色是噪音點(diǎn)：初識聚類算法:

因?yàn)镈BSCAN使用簇的基于密度的定義，因此它是相對抗噪音的，并且能處理任意形狀和大小的簇。但是如果簇的密度變化很大，例如ABCD四個(gè)簇，AB的密度大大大于CD，而且AB附近噪音的密度與簇CD的密度相當(dāng)，這是當(dāng)MinPs較大時(shí)，無法識別簇CD，簇CD和AB附近的噪音都被認(rèn)為是噪音;當(dāng)MinPs較小時(shí)，能識別簇CD，但AB跟其周圍的噪音被識別為一個(gè)簇。這個(gè)問題可以基于共享最近鄰(SNN)的聚類結(jié)局。

4、DBSCAN的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

1.與K-means方法相比，DBSCAN不需要事先知道要形成的簇類的數(shù)量。

2.與K-means方法相比，DBSCAN可以發(fā)現(xiàn)任意形狀的簇類。

3.同時(shí)，DBSCAN能夠識別出噪聲點(diǎn)。

4.DBSCAN對于數(shù)據(jù)庫中樣本的順序不敏感，即Pattern的輸入順序?qū)Y(jié)果的影響不大。但是，對于處于簇類之間邊界樣本，可能會根據(jù)哪個(gè)簇類優(yōu)先被探測到而其歸屬有所擺動。

缺點(diǎn)：

1.DBScan不能很好反映高尺寸數(shù)據(jù)。

2.DBScan不能很好反映數(shù)據(jù)集變化的密度。

3.對于高維數(shù)據(jù)，點(diǎn)之間極為稀疏，密度就很難定義了。

篇2:算理與算法并重促進(jìn)學(xué)生計(jì)算能力培養(yǎng)

算理與算法并重促進(jìn)學(xué)生計(jì)算能力培養(yǎng)

教師在計(jì)算教學(xué)時(shí)常常容易忽略學(xué)生對于算理的有效理解與表達(dá),而認(rèn)為學(xué)生只要是掌握好了算法,能夠正確的計(jì)算有關(guān)題目就達(dá)到教學(xué)目標(biāo)了,其實(shí)學(xué)生能很好掌握最優(yōu)化的算法往往是有較清晰的算理的支持,一些計(jì)算能力強(qiáng)的學(xué)生,算理比一般同學(xué)更加清晰化,不但知道如何進(jìn)行計(jì)算,還知道這樣計(jì)算的理由是什么?如：我在教學(xué)一年級(下)〈〈兩位數(shù)減一位數(shù)或整十?dāng)?shù)〉〉時(shí)，先讓學(xué)生從大屏幕出示的情境圖中得到了算式64-33，誰能說說64-33等于多少?學(xué)生：64-33=31，老師：算得對。那么同學(xué)們能利用擺小棒的方法，來擺一擺計(jì)算過程嗎?擺好后跟同桌交流一下你是怎么擺的?學(xué)生擺一擺后，請學(xué)生上臺邊擺邊說你是怎么擺的?老師：剛才我們是通過擺小棒的方法擺出了計(jì)算過程?現(xiàn)在誰能結(jié)合算式用先算什么，再算什么來說一說你是怎么算的?學(xué)生：先算60-30=30，再算4-3=1，最后算30+1=31。另一個(gè)學(xué)生：先算4-3=1，再算60-30=30，最后算30+1=31，從這個(gè)片斷中我利用一年級學(xué)生思維的直觀性，先讓學(xué)生利用小捧來擺一擺，借助實(shí)物更直觀的把64-33的算理擺了出來，再引導(dǎo)學(xué)生脫離算式利用先算什么，再算什么來說出計(jì)算的過程，學(xué)生在教師有效引導(dǎo)下能較快的理清算理，掌握口算方法。

篇3:倡算法多樣化數(shù)學(xué)教學(xué)心得體會

倡算法多樣化數(shù)學(xué)教學(xué)心得體會

《數(shù)學(xué)課程標(biāo)準(zhǔn)》指出：數(shù)學(xué)教學(xué)活動必須建立在學(xué)生認(rèn)識發(fā)展水平和已有知識經(jīng)驗(yàn)的基礎(chǔ)之上。“提倡算法多樣化”、“鼓勵算法多樣化”是《數(shù)學(xué)課程標(biāo)準(zhǔn)》中關(guān)于計(jì)算教學(xué)改革的一個(gè)亮點(diǎn)，它有利于調(diào)動學(xué)生已有的計(jì)算經(jīng)驗(yàn)，探尋不同的算法，使“不同的人在數(shù)學(xué)上得到不同的發(fā)展”。但是，在課堂教學(xué)的實(shí)踐中，到底應(yīng)該如何體現(xiàn)算法多樣化的教學(xué)呢？下面是我在教學(xué)中的幾點(diǎn)體會：

1、為學(xué)生創(chuàng)設(shè)算法多樣化的機(jī)會。

給學(xué)生提供的學(xué)習(xí)內(nèi)容應(yīng)該是能夠緊密聯(lián)系他們生活實(shí)際，發(fā)生在他們身邊的現(xiàn)象或問題。而且這些現(xiàn)象與問題中含有數(shù)學(xué)價(jià)值，學(xué)生能從中發(fā)現(xiàn)客觀規(guī)律、積累數(shù)學(xué)活動經(jīng)驗(yàn)。教科書在編寫時(shí)作了許多努力，教師的任務(wù)是把教科書中的學(xué)習(xí)材料用生動、有趣的方式呈現(xiàn)給學(xué)生。我們可以從三個(gè)方面來考慮，一是學(xué)生感不感興趣、想不想學(xué)習(xí)、愿不愿探究；二是學(xué)生有沒有回憶起相關(guān)的舊知識和已有的經(jīng)驗(yàn)與方法；三是學(xué)生是不是有了初步的解決方法與打算。

例如：有這樣一道題：5×25×8要求用簡便方法計(jì)算，學(xué)生的方法很多，(1)先算5×25=125再算125×8=1000（2）把8拆成2×4，先算5×2=10、25×4=100，再算10×100=1000（3）先算25×8=200再算200×5=1000（4）先算5×8=40再算40×25=1000這樣的題目為學(xué)生提供了廣闊的思維空間，有效的調(diào)動了學(xué)生思維的積極性，為算法多樣化創(chuàng)造了機(jī)會。

2、為學(xué)生提供算法多樣化的平臺。

不同的算法展示了學(xué)生的不同認(rèn)知方式。面對問題，教師應(yīng)該不是告訴他們可以（應(yīng)該）怎樣算，而是應(yīng)讓學(xué)生進(jìn)行自主探索，以“做”而非“聽或看”的方式介入學(xué)習(xí)活動。在這樣的活動中，學(xué)生不僅能理解所學(xué)的知識，掌握正確的算法，而且提高了自己從事數(shù)學(xué)活動的能力，增強(qiáng)了學(xué)習(xí)數(shù)學(xué)的信心，促進(jìn)自身的整體發(fā)展。

學(xué)生在解決問題的時(shí)候總是會有一些自己的獨(dú)特的想法，我們應(yīng)該讓他們按照自己的設(shè)想去試一試，用自己的策略去嘗試解決。教師只要注意：一是留給學(xué)生比較充裕的時(shí)間，保障每一名學(xué)生都有獨(dú)立探索的機(jī)會；二是鼓勵學(xué)生勇于克服困難，盡力尋找問題的答案；三是在學(xué)生遇到困難是及時(shí)給予合理化的建議。3、讓學(xué)生在交流中提升算法多樣化的品位。

學(xué)生通過自己的實(shí)踐活動得到了問題的答案，找到了解決問題的方法，這就為交流創(chuàng)造條件，他們既有交流的愿望，也有交流的內(nèi)容。教師要引導(dǎo)全體學(xué)生都參與交流，交流的組織形式應(yīng)是靈活多樣的。同桌學(xué)生之間或?qū)W習(xí)小組內(nèi)部的交流頻率高、機(jī)會多、參與面廣，可以在此基礎(chǔ)上再組織班集體的交流，展示不同的計(jì)算方法，讓每個(gè)學(xué)生都發(fā)表自己的不同觀點(diǎn)，傾聽別人的想法，有利于學(xué)生感受解決問題策略的多樣性與靈活性，從中受到啟發(fā)，學(xué)會理解他人，欣賞他人。

4、讓學(xué)生在自主探究中升華算法多樣化的內(nèi)涵。

學(xué)生通過自己動手實(shí)踐，自主探索找到的解決方法只要是正確的，就都是好方法，要允許學(xué)生用自己的方法解決問題。這些方法是學(xué)生的創(chuàng)造，是他們的學(xué)習(xí)成果，其中既包含著數(shù)學(xué)知識，還包含了寶貴的精神和態(tài)度。

教師應(yīng)“允許學(xué)生以他們喜歡的方式學(xué)習(xí)數(shù)學(xué)”。如果把學(xué)生自已喜歡的算法看做“基本算法”的話，每個(gè)人心中的基本方法是不同的，在不同的階段，基本方法也在發(fā)生變化。因此教師要讓學(xué)生自已選擇“基本算法”，并應(yīng)予以肯定和鼓勵。但是強(qiáng)調(diào)個(gè)體的“基本算法”并非到此為止，還需引導(dǎo)探索、“多中選優(yōu)”。

總之，算法多樣化是數(shù)學(xué)課程標(biāo)準(zhǔn)中的一個(gè)重要思想，是指尊重學(xué)生的獨(dú)立思考，鼓勵學(xué)生探索不同的方法，它打破了原來的教學(xué)模式（教師教給方法，學(xué)生嘗試，練習(xí)鞏固提高），使數(shù)學(xué)教學(xué)更符合學(xué)生的實(shí)際，使每個(gè)學(xué)生“學(xué)到自己需要的數(shù)學(xué)”。教學(xué)中，教師應(yīng)適時(shí)地引導(dǎo)學(xué)生選擇適合于自己的方法達(dá)到算法最優(yōu)化。在算法多樣化到算法最優(yōu)化的過程中，學(xué)生學(xué)到的不僅是解題的方法，更在算法多樣的過程中彰顯了自己的個(gè)性，在數(shù)學(xué)上獲得了不同的發(fā)展。