層次聚類算法應(yīng)用

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 安 徽 三 聯(lián) 學(xué) 院 題目：層次聚類算法應(yīng)用 姓 名 張 翔 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí) 計(jì)一系本科2班 指導(dǎo)教師 張 林 完成日期： 2011年 11 月 16 日摘 要專心-專注-專業(yè)本文圍繞層次聚類分析算法展開研究首先根據(jù)樣本間的相似性關(guān)系定義分類后類與類間的分離性，以及同一個(gè)類別內(nèi)部的一致性，并進(jìn)行計(jì)算，從而使得計(jì)算過程得到簡(jiǎn)化利用層次聚類算法實(shí)現(xiàn)分層聚類在基于電價(jià)區(qū)域劃分的實(shí)際問題中，這里結(jié)合人類視覺感知理論，提出了獲取最優(yōu)聚類的條件，從而實(shí)現(xiàn)了最佳的分類本文的主要研究工作如下：第一章：說明了層次聚類分析的定義及研究方法，對(duì)層次聚類分析方法的有效性

2、做出了細(xì)致的研究，并提出了基于相似矩陣的有效性函數(shù)第二章：將層次聚類分析方法應(yīng)用在電價(jià)區(qū)域的空間尺度劃分問題中，進(jìn)而實(shí)現(xiàn)了電價(jià)區(qū)域的劃分關(guān)鍵詞 層次聚類分析；有效性；空間尺度目 錄2225666 2.3 基于尺度空間聚類的電價(jià)區(qū)域劃分.8 2.4 本章小結(jié).134第1章 層次聚類分析算法及其研究1.1 層次聚類分析算法層次聚類算法1，也稱為樹聚類算法，它的目標(biāo)是對(duì)于具有個(gè)樣本的集合，首先通過相似性函數(shù)計(jì)算樣本間的相似性并構(gòu)成相似性矩陣，再根據(jù)樣本間的相似性矩陣把樣本集組成一個(gè)分層結(jié)構(gòu)，產(chǎn)生一個(gè)從1到的聚類序列這個(gè)序列有著二叉樹的形式，即每個(gè)樹的結(jié)點(diǎn)有兩個(gè)分支，從而使得聚類結(jié)果構(gòu)成樣本集的系統(tǒng)樹

3、圖, 使得有或?qū)λ械亩汲闪南到y(tǒng)樹圖形成的方式來看，層次聚類算法包括2種形式：凝聚式算法和分裂式算法凝聚式算法是以“自底向上”的方式進(jìn)行的首先將每個(gè)樣本作為一個(gè)聚類，然后合并相似性最大的聚類為一個(gè)大的聚類，直到所有的聚類都被融合成一個(gè)大的聚類它以個(gè)聚類開始，以1個(gè)聚類結(jié)束，分裂式算法是以一種“自頂向下”的方式進(jìn)行的一開始它將整個(gè)樣本看做一個(gè)大的聚類，然后，在算法進(jìn)行的過程中考察所有可能的分裂方法把整個(gè)聚類分成若干個(gè)小的聚類第1步分成2類，第2步分成3類，這樣一直能夠進(jìn)行下去直到最后一步分成類在每一步中選擇一個(gè)使得相異程度最小的分裂運(yùn)用這種方法，可以得到一個(gè)相反結(jié)構(gòu)的系統(tǒng)樹圖，它以1個(gè)聚類開始

4、，以個(gè)聚類結(jié)束與分裂式算法相比，由于凝聚式算法在計(jì)算上簡(jiǎn)單、快捷，而且得到相近的最終結(jié)果，所以絕大多數(shù)層次聚類方法都是凝聚式的，它們只是在聚類的相似性度量的定義上有所不同層次聚類算法是一個(gè)非常有用的聚類算法，它在迭代的過程中直到所有的數(shù)據(jù)都屬于同一個(gè)簇才停止迭代，但是層次聚類也存在幾個(gè)缺點(diǎn)，如聚類的時(shí)空復(fù)雜度4高、聚類的簇效率底、誤差較大等1.2 層次聚類分析算法的有效性研究針對(duì)如何從層次聚類算法得到樣本集的多種聚類結(jié)果中獲得用戶最滿意的聚類結(jié)果，在深入研究聚類有效性的基礎(chǔ)上，通過模糊相似性關(guān)系刻畫聚類的類內(nèi)致密性和類間分離性，可以建立一個(gè)聚類的有效性函數(shù)在人工和實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)都表明了該有

5、效性函數(shù)具有良好的性能層次聚類算法，特別是凝聚式算法在計(jì)算上簡(jiǎn)單、快捷，而且能夠得到相近的最終結(jié)果，所以層次聚類算法的應(yīng)用較為廣泛5雖然該類算法把數(shù)據(jù)集的多種分類結(jié)果都展現(xiàn)了出來，但是從算法所得到的各類分類結(jié)果中獲得用戶最滿意的分類情況卻成了一個(gè)問題根據(jù)模糊集理論6，系統(tǒng)樹結(jié)構(gòu)的每一層是由閾值決定的因此，最優(yōu)聚類結(jié)果的選取問題就是最優(yōu)閾值的選取問題對(duì)于最優(yōu)閾值的選取問題，使用統(tǒng)計(jì)量是研究者們比較認(rèn)可的方法當(dāng)然隨著模糊數(shù)學(xué)研究的深入，近幾年來也有新的解決方法，Nasibov和Ulutagay提出了一個(gè)對(duì)于噪聲更為穩(wěn)定的FJP(fuzzy joint points)算法該算法的基本思想是根據(jù)樣本點(diǎn)

6、與樣本點(diǎn)之間的距離計(jì)算模糊關(guān)系矩陣，對(duì)于某一，建立截集和等價(jià)類此時(shí)，這些等價(jià)類決定了模糊聚類的每個(gè)截集但并非對(duì)每個(gè)都計(jì)算截集，而是只計(jì)算影響聚類個(gè)數(shù)的對(duì)應(yīng)的截集最終的截集是由取值區(qū)間上的最大值確定的FJP算法已被證明能成功檢測(cè)團(tuán)裝數(shù)據(jù)集及流形狀數(shù)據(jù)集，即使添加噪聲點(diǎn)后FJP算法也能成功識(shí)別流形狀數(shù)據(jù)集如何衡量一個(gè)聚類結(jié)果的好壞，以及如何確定最優(yōu)聚類個(gè)數(shù)，這些都是聚類有效性問題關(guān)于模糊均值算法聚類有效性問題的研究也已經(jīng)有了很豐碩的成果，從1974年開始研究者們提出了許多有效性函數(shù)這些有效性函數(shù)構(gòu)建聚類有效性指標(biāo)的定義應(yīng)當(dāng)是客觀的通常情況下，刻畫聚類有效性有2個(gè)標(biāo)準(zhǔn)：類內(nèi)致密性和類間分離性統(tǒng)計(jì)量也

7、是從類內(nèi)致密性和類間分離性2個(gè)方面考慮的對(duì)于層次聚類算法的有效性研究，很多研究者還試圖從模糊數(shù)學(xué)理論著手范九倫和吳成茂對(duì)基于模糊集合定義的若干公式在聚類有效性方面的性質(zhì)進(jìn)行了討論，并對(duì)分類性能進(jìn)行實(shí)驗(yàn)，篩選出2有應(yīng)用價(jià)值的公式這里通過樣本間的相似性關(guān)系定義類與類間的分離性以及同一個(gè)類別內(nèi)部的一致性，從而使得計(jì)算過程得到簡(jiǎn)化1.2.1 有效性函數(shù)的定義字典上將類定義為許多相似或同事物的綜合這個(gè)定義包含2層含義：第1層，在同一個(gè)類內(nèi)的樣本相互之間具有相似或相同的屬性，也就是說，聚類的致密性度量的值應(yīng)該是極小化的，否則，如果屬性不同的樣本被劃分到同一個(gè)類內(nèi)，那么這個(gè)類的類內(nèi)致密性度量的值就會(huì)較大；第

8、2層是好的聚類的各個(gè)類別間的分離性7應(yīng)該是很好的，如果本應(yīng)屬于同一個(gè)類的樣本被分到不同類別內(nèi)，那么類與類之間的重疊就會(huì)較大，也就是說，一個(gè)好的聚類結(jié)果得到的類別之間具有較大的離散性本文將通過樣本間的相似性度量給出類內(nèi)致密性度量和類間離散性7度量的定義設(shè)樣本集通過某相似性度量得到的相似性矩陣為，其通過凝聚式層次聚類算法得到的系統(tǒng)樹圖為對(duì)于此系統(tǒng)樹圖中的任何一層，設(shè)其中包含個(gè)聚類，每個(gè)聚類中含有個(gè)樣本，本文將所有樣本間的相似性的算術(shù)平均值叫做樣本集的平均相似性向量，即對(duì)于一個(gè)類，這里把類內(nèi)所有樣本間相似性的算術(shù)平均值叫做類內(nèi)平均相似性向量類是具有相似屬性樣本的集合，同一類內(nèi)樣本相互間的相似性差異相

9、對(duì)較小也就是說，每個(gè)樣本與其他樣本的相似性與類內(nèi)平均相似性向量就會(huì)相對(duì)小于是有下面的定義：定義1 (類內(nèi)致密性度量)設(shè)是樣本集的層次聚類系統(tǒng)樹圖中某一層，并設(shè)其中包含個(gè)聚類每個(gè)聚類中含有個(gè)樣本，樣本集的聚類結(jié)果的類內(nèi)致密性度量定義為： (2-1)若要類與類間的分離性較好，各類的平均相似性向量與樣本集平均相似性向量的差異必然要大由此本文通過類內(nèi)平均相似性向量與樣本集平均相似性向量的距離來定義類間離散性度量定義2 (類間離散性度量)設(shè)是樣本集X的層次聚類系統(tǒng)樹圖中某一層，并設(shè)其中包含個(gè)聚類，每個(gè)聚類中含有個(gè)樣本，樣本集的這種聚類結(jié)果的類間離散性度量定義為： (2-2)對(duì)于一個(gè)好的聚類，同一個(gè)類內(nèi)的

10、樣本越相似越好，而不同類別間的樣本相似性越小越好于是類內(nèi)致密性度量的值越小越好，而類間離散性度量的值越大越好定義3 (新的有效性指標(biāo))建立新的有效性指標(biāo)為： (2-3)聚類結(jié)果對(duì)應(yīng)的越大，聚類的結(jié)果越好1.3 本章小結(jié)層次聚類算法，也稱為樹聚類算法，它的目標(biāo)是對(duì)于具有個(gè)樣本的集合，首先通過相似性函數(shù)計(jì)算樣本間的相似性并構(gòu)成相似性矩陣，再根據(jù)樣本間的相似性矩陣把樣本集組成一個(gè)分層結(jié)構(gòu)，產(chǎn)生一個(gè)從1到的聚類序列針對(duì)如何從層次聚類算法得到樣本集的多種聚類結(jié)果中獲得用戶最滿意的聚類結(jié)果，在深入研究聚類有效性的基礎(chǔ)上，通過模糊相似性關(guān)系刻畫聚類的類內(nèi)致密性和類間分離性，可以建立一個(gè)新的聚類有效性函數(shù)層次

11、聚類算法，特別是凝聚式算法在計(jì)算上簡(jiǎn)單、快捷，而且能夠得到相近的最終結(jié)果，所以層次聚類算法的應(yīng)用較為廣泛雖然該類算法把數(shù)據(jù)集的多種分類結(jié)果都展現(xiàn)了出來，但是從算法所得到的各類分類結(jié)果中獲得用戶最滿意的分類情況卻成了一個(gè)問題因此可以建立一個(gè)新的基于相似性矩陣的有效性函數(shù)，使得聚類效果更好第2章 層次聚類算法的應(yīng)用2.1 多機(jī)系統(tǒng)分析意義在實(shí)際的電力市場(chǎng)運(yùn)營(yíng)中，準(zhǔn)確、合理地劃分電價(jià)區(qū)域是提供正確電價(jià)的前提和保證為了實(shí)現(xiàn)準(zhǔn)確的電價(jià)區(qū)域劃分，這里以節(jié)點(diǎn)注入功率對(duì)阻塞線路傳輸功率的靈敏度系數(shù)作為節(jié)點(diǎn)電價(jià)的特征量，借助模擬人類視覺系統(tǒng)的尺度空間理論，提出了一種基于尺度空間層次聚類的電價(jià)區(qū)域劃分方法，在無需

12、事先設(shè)定任何區(qū)域劃分信息的情況下實(shí)現(xiàn)了準(zhǔn)確、合理的電價(jià)區(qū)域劃分準(zhǔn)確的電價(jià)區(qū)域劃分是制定有效、簡(jiǎn)潔的區(qū)域電價(jià)的關(guān)鍵不準(zhǔn)確的電價(jià)區(qū)域劃分10將會(huì)造成市場(chǎng)電價(jià)的歪曲，導(dǎo)致阻塞發(fā)生頻率的增加目前，在實(shí)際運(yùn)行的電力市場(chǎng)中，一般都基于系統(tǒng)運(yùn)行人員的經(jīng)驗(yàn)和判斷來劃分電價(jià)區(qū)域然而由于輸電網(wǎng)絡(luò)的龐大和復(fù)雜，僅僅憑借人的經(jīng)驗(yàn)制定的電價(jià)區(qū)域劃分方案很難做到準(zhǔn)確、合理文獻(xiàn)11介紹了輸電網(wǎng)為輻射網(wǎng)絡(luò)時(shí)，以阻塞線路為區(qū)域邊界的電價(jià)區(qū)域劃分方法然而，實(shí)際的輸電網(wǎng)卻是環(huán)形網(wǎng)絡(luò)，僅以阻塞線路為邊界將無法實(shí)現(xiàn)輸電網(wǎng)絡(luò)的區(qū)域分割提出了根據(jù)節(jié)點(diǎn)間電價(jià)的相似性來劃分輸電網(wǎng)絡(luò)的思想，卻沒有給出具體的實(shí)現(xiàn)方法為了實(shí)現(xiàn)準(zhǔn)確的電價(jià)區(qū)域12劃分

13、，本文引入模擬人類視覺系統(tǒng)的尺度空間層次聚類算法，提出了一種新的電價(jià)區(qū)域劃分方法該方法通過提取節(jié)點(diǎn)注入功率對(duì)阻塞線路傳輸功率的靈敏度系數(shù)來表征節(jié)點(diǎn)電價(jià)的特征，形成節(jié)點(diǎn)的聚類樣本；借助基于尺度空間的層次聚類算法實(shí)現(xiàn)了樣本點(diǎn)集的不斷融合，結(jié)合電價(jià)區(qū)域劃分的實(shí)際問題，提出了獲取最優(yōu)聚類的條件，從而在無需事先設(shè)定任何區(qū)域劃分信息的情況下實(shí)現(xiàn)準(zhǔn)確、合理的電價(jià)區(qū)域劃分2.2 節(jié)點(diǎn)電價(jià)的特征量提取電價(jià)區(qū)域劃分的實(shí)質(zhì)是按照節(jié)點(diǎn)電價(jià)的相似程度，即以節(jié)點(diǎn)電價(jià)作為節(jié)點(diǎn)聚類的特征量來實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的匯集然而直接采用節(jié)點(diǎn)電價(jià)作為聚類的特征量卻會(huì)帶來以下問題：(1) 輸電網(wǎng)節(jié)點(diǎn)眾多，節(jié)點(diǎn)電價(jià)的計(jì)算復(fù)雜；(2) 節(jié)點(diǎn)電價(jià)隨時(shí)間

14、不斷變化的特點(diǎn)會(huì)引起電價(jià)區(qū)域劃分邊界頻繁變更，不利于市場(chǎng)的穩(wěn)定因此，直接采用節(jié)點(diǎn)電價(jià)作為聚類特征量在實(shí)際應(yīng)用中并不理想下面從節(jié)點(diǎn)電價(jià)求解的直流潮流模型出發(fā)，獲得既能映射出節(jié)點(diǎn)電價(jià)的大小，又較為穩(wěn)定(不會(huì)隨時(shí)變化)的特征量指標(biāo)基于直流潮流，系統(tǒng)調(diào)度的優(yōu)化模型如下： (4-1)式(4-1)中為維節(jié)點(diǎn)注入有功功率矢量(不包括平衡節(jié)點(diǎn))；為平衡節(jié)點(diǎn)的注入有功功率；為維矩陣，代表節(jié)點(diǎn)注入功率對(duì)線路傳輸功率的靈敏度系數(shù)，它只與輸電網(wǎng)的電納矩陣和節(jié)點(diǎn)線路關(guān)聯(lián)矩陣有關(guān)；為維全1矢量；為維線路傳輸功率限值矢量；為維節(jié)點(diǎn)成本函數(shù)矢量，為平衡節(jié)點(diǎn)的成本函數(shù)，它們可依據(jù)市場(chǎng)參與者的報(bào)價(jià)曲線推出；為輸電網(wǎng)的節(jié)點(diǎn)總數(shù)，為

15、線路總數(shù)構(gòu)建優(yōu)化問題(1)的Lagrange函數(shù)： (4-2) 由，可以獲得節(jié)點(diǎn)電價(jià)的計(jì)算公為：(4-3)式中為平衡節(jié)點(diǎn)的節(jié)點(diǎn)電價(jià)；維節(jié)點(diǎn)電價(jià)矢量(不包括平衡節(jié)點(diǎn))；為功率平衡等式約束的Lagrange乘子；維線路傳輸功率不等式約束的Lagrange乘子矢量當(dāng)線路阻塞時(shí)，線路功率的不等式約束成為有效約束，其對(duì)應(yīng)的Lagrange乘子；當(dāng)線路不處于阻塞狀態(tài)時(shí)，線路功率的不等式約束為無效約束，其對(duì)應(yīng)的Lagrange乘子由式(4-3)可以看出，節(jié)點(diǎn)電價(jià)的大小與平衡節(jié)點(diǎn)的邊際成本(即節(jié)點(diǎn)電價(jià))、阻塞線路的影子價(jià)格(即Lagrange乘子)以及節(jié)點(diǎn)注入功率對(duì)線路傳輸功率的靈敏度系數(shù)有關(guān)兩節(jié)點(diǎn)和的電價(jià)之

16、差為： (4-4)式中、分別為節(jié)點(diǎn)和的節(jié)點(diǎn)電價(jià)；代表阻塞線路集合；為矩陣的第行元素；、為矩陣的第行列和列元素從式(4-4)可見，節(jié)點(diǎn)間的電價(jià)差與節(jié)點(diǎn)注入功率對(duì)阻塞線路傳輸功率的靈敏度系數(shù)之差成比例只要節(jié)點(diǎn)間的靈敏度系數(shù)相近，則無論阻塞線路影子價(jià)格的數(shù)值大小如何，節(jié)點(diǎn)間的電價(jià)始終會(huì)相近，雖然相近的程度會(huì)隨著系統(tǒng)運(yùn)行狀態(tài)的變化及阻塞線路影子價(jià)格的不同而改變因而，采用節(jié)點(diǎn)注入功率對(duì)阻塞線路傳輸功率的靈敏度系數(shù)作為節(jié)點(diǎn)電價(jià)的特征量來進(jìn)行節(jié)點(diǎn)的聚類，可以很好地完成對(duì)電價(jià)相近節(jié)點(diǎn)的匯集而且靈敏度系數(shù)不會(huì)隨輸電網(wǎng)運(yùn)行狀態(tài)的改變而變化，只要輸電網(wǎng)的拓?fù)浣Y(jié)構(gòu)不變，靈敏度系數(shù)的數(shù)值將會(huì)保持不變因此，采用該指標(biāo)作為

17、節(jié)點(diǎn)電價(jià)的特征量來進(jìn)行節(jié)點(diǎn)的聚類，在一段時(shí)間內(nèi)可以獲得較為穩(wěn)定的電價(jià)區(qū)域邊界2.3 基于尺度空間聚類的電價(jià)區(qū)域劃分2.3.1 尺度空間理論隨著神經(jīng)生理學(xué)的發(fā)展和計(jì)算機(jī)輔助解剖學(xué)的研究，人們已經(jīng)提出了幾個(gè)相當(dāng)精確的初級(jí)視覺系統(tǒng)計(jì)算模型它們分別建模于視覺系統(tǒng)的不同層次、不同部分，尺度空間理論便是其中之一它定量地描述出由視網(wǎng)膜側(cè)向聯(lián)接所造成的圖像模糊化效應(yīng)13在人類的視覺過程中，眼睛將外部場(chǎng)景成像在視網(wǎng)膜上，大腦中形成的圖像可視為一群空間中的光點(diǎn)集合隨著尺度的增加或分辨率的下降，圖像逐漸模糊化，每個(gè)小光點(diǎn)將融合成光斑，直至當(dāng)尺度充分大時(shí)，整個(gè)圖像成為一個(gè)大光斑在不同尺度下的圖像形成了一個(gè)分層結(jié)構(gòu)，大

18、光斑由小光組成，每個(gè)光斑僅在一定的尺度范圍內(nèi)存在，當(dāng)尺度小于此范圍時(shí)，光斑分裂成數(shù)個(gè)小光斑，而當(dāng)尺度大于此范圍時(shí)，光斑將與其它光斑融合對(duì)于給定的維空間的光點(diǎn)集，數(shù)學(xué)上光點(diǎn)可由Dirac廣義函數(shù)表示，即：，(4-5)于是，由光點(diǎn)集在空間形成的圖像為： (4-6)根據(jù)視覺前端系統(tǒng)的尺度空間理論，圖像的多尺度可表示為為與高斯核的卷積，即： (4-7)式中為高斯函數(shù)，高斯函數(shù)的參數(shù)稱為尺度函數(shù)，由構(gòu)成的空間即為尺度空間在給定尺度下，光斑的中心定義為關(guān)于的一個(gè)極大值點(diǎn)，光斑則為關(guān)于梯度系統(tǒng)的吸引域，記為，即： (4-8)其中為梯度系統(tǒng)初值問題： (4-9)在給定尺度下，驗(yàn)證點(diǎn)是否屬于光斑可以通過求解上述

19、方程來完成近年來，有學(xué)者將視覺前端系統(tǒng)的尺度空間理論引入聚類算法，將樣本的聚類過程比于人眼對(duì)事物的感知方式，提出了基于尺度空間的層次聚類算法，該方法具有無需設(shè)定初始劃分，通過局部尋優(yōu)即可確定聚類中心，且能夠有效判定最優(yōu)聚類中心和類別個(gè)數(shù)等一系列的有點(diǎn)，從而避免了劃分聚類法，如均值，模糊均值聚類算法都需要設(shè)定初始劃分、尋找全局最優(yōu)聚類和難以確定聚類有效性的缺點(diǎn)，同時(shí)也克服了系統(tǒng)聚類法，如離差平法和法、最短距離法、最長(zhǎng)距離法，難以準(zhǔn)確度量樣本間的相似度和難以合理選取最優(yōu)聚類截取水平的缺點(diǎn)，為有效解決電價(jià)區(qū)域劃分問題提供了一條新的途徑2.3.2 基于尺度空間層次聚類的電價(jià)區(qū)域劃分1. 聚類樣本在劃分

20、電價(jià)區(qū)域前，根據(jù)輸電網(wǎng)的實(shí)際運(yùn)行情況，確定出在一段時(shí)間內(nèi)可能出現(xiàn)的阻塞線路(這一步驟的具體實(shí)現(xiàn)可以在考慮市場(chǎng)中各種不確定因素的情況下通過采用Mont Carlo模擬法來對(duì)輸電網(wǎng)的阻塞情況進(jìn)行概率分析，從而確定出最可能發(fā)生阻塞的線路，此處不再詳述)，將它們歸入阻塞線路集合，針對(duì)這些阻塞線路，計(jì)算出每個(gè)節(jié)點(diǎn)電價(jià)的特征量，即節(jié)點(diǎn)注入功率的靈敏系數(shù)然后，將他們映射到高位空間上，(空間位數(shù)為阻塞線路數(shù))，形成聚類的樣本點(diǎn)集通過對(duì)樣本點(diǎn)的聚類，便可以按照節(jié)點(diǎn)電價(jià)的相似度，實(shí)現(xiàn)節(jié)點(diǎn)的匯集，從而完成電價(jià)區(qū)域的劃分2. 基于尺度空間的區(qū)域劃分將尺度空間理論引入到輸電網(wǎng)節(jié)點(diǎn)的聚類之中，需要聚類的每個(gè)樣本被視作空間

21、中的一個(gè)光點(diǎn)，即光點(diǎn)集式中，為節(jié)點(diǎn)的注入功率對(duì)阻塞線路傳輸功率的靈敏度系數(shù)，為阻塞線路總數(shù)隨著尺度的增加，光點(diǎn)逐漸融合成光斑，每個(gè)光斑被視為一個(gè)樣本的聚類，它由落在該光斑內(nèi)的所有光點(diǎn)構(gòu)成，并由相應(yīng)的光斑中心表示光斑逐漸融合的過程可類比為樣本相互聚集融合，直到最后全部歸并為一個(gè)大光斑，即所有的樣本聚合成一個(gè)類，于是形成了隨尺度空間變化的層次聚類樹光斑中心或聚類中心為光點(diǎn)集關(guān)于臺(tái)的極大值點(diǎn)，它可以通過求解微分方程(4-9)來獲得運(yùn)用Euler數(shù)值微分方法來求解，并且微分方程(4-9)的解在各時(shí)刻(為步長(zhǎng)，, )處的值形成了序列, 采用對(duì)數(shù)坐標(biāo)，于是聚類中心求取的迭代公式為： (4-10)式中一般取

22、0.2，以便迭代過程可以獲得較好的收斂特性綜合上述樣本的融合過程，基于尺度空間層次聚類的具體步驟如下：1) 置迭代次數(shù)，設(shè)定充分小的初始尺度，使每個(gè)樣本成為一個(gè)聚類，它為該類的中心；2) 對(duì)于尺度下的每個(gè)聚類中心，通過式(4-10)的迭代計(jì)算，求出尺度下新的聚類中心當(dāng)兩個(gè)類的聚類中心相同時(shí)，兩個(gè)類便融合為一個(gè)新的類，兩個(gè)類中的樣本便歸并到新的類中；3) 當(dāng)存在兩個(gè)及以上的類時(shí)，以一定的比例改變尺度大小，即，設(shè)，重復(fù)步驟2)；4) 直到只有一個(gè)類為止，生成完整的聚類樹3. 聚類的有效性在樣本點(diǎn)集的層次聚類過程中，生成了完整的聚類樹在不同尺度上，出現(xiàn)了不同的聚類，獲得了不同大小的電價(jià)區(qū)域在這眾多的

23、電價(jià)區(qū)域中，哪些電價(jià)區(qū)域是最優(yōu)的，即節(jié)點(diǎn)聚類的有效性問題，將借助尺度空間層次聚類算法中的聚類有效性標(biāo)準(zhǔn)，并結(jié)合電價(jià)區(qū)域劃分的特點(diǎn)來解決 存活時(shí)間每個(gè)類都是在一定的尺度范圍內(nèi)才會(huì)存在當(dāng)尺度超出此范圍時(shí)，該類分裂或融合成其它類依據(jù)Witkin的心理實(shí)驗(yàn)結(jié)果，即在人的視覺系統(tǒng)中，那些在較大尺度范圍內(nèi)可觀察的物體結(jié)構(gòu)較之那些在較小尺度范圍內(nèi)可觀察到的物體結(jié)構(gòu)更容易被感知，故可以得出聚類的一個(gè)有效性檢驗(yàn)標(biāo)準(zhǔn)：存活時(shí)間，存活時(shí)間長(zhǎng)的類優(yōu)于存活時(shí)間短的類類的存活時(shí)間是指類從產(chǎn)生到消亡的對(duì)數(shù)尺度范圍，即： (4-11)式中為該類產(chǎn)生的尺度，為該類消亡的尺度(即該類與其它類融合為新類的尺度) 緊湊程度和孤立程度

24、直觀上講，同類樣本間的距離越小，類與類的樣本間距離越大，則聚類效果越好基于此，提出了兩個(gè)有效性檢驗(yàn)標(biāo)準(zhǔn)：緊湊程度和孤立程度對(duì)于某一個(gè)類來說，緊湊程度和孤立程度的定義如下： (4-12) (4-13)式(4-12)和(4-13)中為類的聚類中心；為樣本點(diǎn)；表示在尺度樣本點(diǎn)與所有聚類中心之間的距離；表示在尺度下所有樣本點(diǎn)與第個(gè)聚類中心之間的距離對(duì)于一個(gè)好的聚類來說，類的緊湊程度和孤立程度應(yīng)該接近于1采用上面給出的3個(gè)聚類有效性標(biāo)準(zhǔn)，結(jié)合電價(jià)區(qū)域劃分問題，完成最優(yōu)聚類的選取，從而獲得輸電網(wǎng)的電價(jià)區(qū)域最優(yōu)聚類的選取步驟如下：第1步 選取滿足一定要求的聚類，形成有效聚類點(diǎn)集從聚類樹的頂結(jié)點(diǎn)開始向下搜索，將具有以下條件的結(jié)點(diǎn)形成聚類點(diǎn)集1) 類的緊湊程度和孤立程度大于一定閾值；2) 類中樣本點(diǎn)(或節(jié)點(diǎn)數(shù))多于一定個(gè)數(shù)；3) 類中樣本點(diǎn)之間的距離小于一定數(shù)值，或類中節(jié)點(diǎn)間的電價(jià)差小于一定閾值，即： (4-13)式中為阻塞線路影子價(jià)格的期望值；為