用電負荷相關聚類演算法總結（1）
聚類演算法大致可以分為劃分聚類方法、層次聚類方法、密度聚類方法、網格聚類方法、模型聚類方法等。近年來，量子聚類方法、譜聚類方法、粒度聚類方法、概率圖聚類方法、同步聚類方法等也流行起來。
- 1.1 基於劃分的聚類演算法
基於劃分的聚類演算法通過構造一個迭代過程來優化目標函式，當優化到目標函式的最小值或極小值時，可以得到資料集的一些不相交的子集，通常認為此時得到的每個子集就是一個聚類。
多數基於劃分的聚類演算法都是非常高效的，但需要事先給定一個在聚類分析前難以確定下來的聚類數目。k-means 演算法[5]和 FCM(FuzzyC Means)演算法是該型別中最著名的兩個演算法。另外，k-中心點演算法 PAM(PartitioningAround Medoid)和 CLARA(Clustering LARgeApplications)、k-模演算法(聚類分類資料)和k-原型演算法(聚類混合資料)[25]也屬於這種型別的演算法。基於劃分的聚類演算法優點是易於實現，聚類速度快。其時間複雜度與資料點數目n、資料的維度d 及預先設定的聚類數目k 成線性關係。缺點是優化函式是個NP難問題，要搜尋到最小值，時間代價高，且易陷入區域性最小值。 - 1.2 層次聚類演算法
層次聚類方法使用一個距離矩陣作為輸入，經過聚類後得到一個反映該資料集分佈狀
況的聚類層次結構圖。層次聚類演算法通常分為兩種。第一種是凝聚的層次聚類演算法，它首先把每個資料點看作是一個聚類，然後以一種自底向上的方式通過不斷地選擇最近鄰居聚類對的合併操作，最終可以構造出一棵代表著該資料集聚類結構的層次樹。第二種是分裂的層次聚類演算法，它首先把所有的資料點看作是一個聚類，然後以一種以自頂向下的方式通過不斷地選擇最鬆散簇進行分裂操作，最終可以構造出一棵代表著該資料集聚類結構的層次樹。儘管層次聚類方法的時間代價高於劃分聚類方法，但多數層次聚類演算法並不需要事先設定一個難以確定的聚類數目這個引數，而且這類方法可以獲得一種具有多個粒度的多層次聚類結構，這是它區別於劃分聚類方法的最大優點。 - 1.3 基於密度的聚類演算法
基於密度的聚類演算法試圖通過稀疏區域來劃分高密度區域以發現明顯的聚類和孤立點，主要用於空間型資料的聚類。代表性的是DBSCAN演算法。 - 1.4 基於網格的聚類演算法
基於網格的聚類演算法是一種基於網格的具有多解析度的聚類方法。它首先將資料集的分佈空間劃分為若干個規則網格(如超矩形單元)或靈活的網格(如任意形狀的多面體)，然後通過融合相連的帶資料概要資訊的網格來獲得明顯的聚類。這類演算法的優點是處理時間與資料點的數目無關、與資料的輸入順序無關，可以處理任意型別的資料。其缺點是 處理時間與每個維度上所劃分的單元數相關，一定程度上降低了聚類的質量和準確性。代表性演算法是STING(STatistical INformation Grid)演算法。 - 1.5 基於模型的聚類演算法
基於模型的聚類演算法藉助於一些統計模型來獲得資料集的聚類分佈資訊。該方法假定資料集是由有限個概率分佈模型共同作用生成的。在這種方法中，多變數的高斯分佈混合模型應用最為廣泛。其中，COBWEB 演算法是一個常用的、簡單的增量式概念聚類方法，它採用分類樹的形式來表現層次聚類結果。 - 1.6 基於圖的聚類演算法
採用圖聚類方法進行聚類分析時，首先是建立與具體問題相適應的圖。圖的結點代表被分析資料的基層單元，圖的邊代表基層單元資料之間的相似性度量(或相異性度量)。通常，每個基層單元資料之間都會有一個度量表達，這樣可以保持資料集的區域性分佈特性。圖聚類方法是以資料集的區域性連線特徵作為聚類的主要資訊源，因而易於處理區域性資料的特性。Karypis 等提出的變色龍演算法也可看作是一種圖聚類演算法。 - 1.7 其他聚類演算法
量子聚類方法借用了量子學理論，先是從源資料中建立一個基於空間尺度的概率函式，接著使用一些分析操作來獲得一個根據極小值來確定聚類中心的勢函式，最終通過調整尺度引數來搜尋聚類結構。
譜聚類(Spectral Clustering)方法通過源資料的相似度矩陣來計算特徵值，進而可以發現明顯的聚類區域。許多譜聚類演算法都易於實現，其效果優於傳統的聚類演算法，如k-means，它們在許多應用中也都獲得了成功的實現。用於影象劃分的 Shi-Malik 演算法就是基於譜聚類方法開發出來的。
基於粒度的聚類方法，是從資訊粒度角度上發展起來的一個新的聚類研究方向。目前這種聚類方法的研究還不太成熟，尤其是對粒度計算語義的研究還比較少。
概率圖聚類方法是近年來流行起來的一種聚類方法。最著名的概率圖聚類方法要數2007 年發表在《Science》上面的 AP(AffinityPropagation)聚類演算法。
同步聚類演算法——SynC (Synchronization Clustering)演算法。該演算法不僅可以在不知道資料集的任何分佈情況下，通過動態的同步過程來發現它的內在結構，並能很好地處理孤立點，還能使用最小描述長度原理來實現自動聚類。
由於基於網格的演算法主要用於處理空間資料，而電力負荷曲線是一種時間序列，本文重點研究其他型別的聚類演算法。
二、電力負荷聚類方法
目前的電力負荷曲線聚類的方法很多，比較流行的有Kmeans 聚類、小波分析、模糊C 均值聚類演算法（FCM）、整合聚類演算法、自組織特徵對映神經網路（SOM）、極端學習機（ELM）、雲模型等，同時還有一些在這些演算法的基礎上進行改進的演算法。
-
1.1 聚類有效性
聚類有效性研究是通過建立有效性指標，評價聚類質量並確定最佳聚類數的過程。典型的聚類有效性指標有誤差平方和(sum of squared error，SSE) 、Calinski-Harabasz 指標(Calinski-HarabaszIndex，CHI)、Davies-Bouldi 指標(Davies-BouldinIndex，DBI)等。
1）SSE 指標。
誤差平方和 SSE 指標ISSE 用一個子類到所在類簇的聚類中心的歐氏距離來表示，即：
d(ci , x)為向量間的歐氏距離。隨著聚類數增多，ISSE會減小，SSE 曲線的拐點表示在該點後再增加聚類數時誤差平方和的減小幅度很小，因此可以將SSE曲線的拐點作為最佳聚類數。 2）CHI 指標。 CHI 指標綜合考慮類間的分散性(用B 表示)和類內的緊湊性(用W 表示)，其中：
式中：x 為所有物件的均值；wk,i 表示第i 個物件對第k 個類簇的隸屬關係，即：
可見，ICHI 越大表示類簇間的分散性和類簇內的緊湊性越好。 3）DBI 指標。 DBI 指標的含義與CHI 類似，計算公式為：
其中：
式中：d(Xk)和d(Xj)為矩陣內部距離；d(ck, cj)為向量間的距離。IDBI 越小表示聚類效果越好。
- 1.2指標分析
3 種聚類有效性指標都可以正確地找到最佳聚類數。CHI 和DBI 曲線的極值點比SSE 曲 線的拐點更為直觀；與CHI 相比，DBI 指標的計算公式更為簡單且變化範圍小，便於應用。因此，DBI適合作為電力負荷曲線聚類的有效性指標。
- 2、經典聚類演算法比較 表 2 對上述各類演算法進行彙總：
由圖 2 可知，劃分聚類的計算效率明顯高於其他型別的演算法。
由圖3 可知，層次聚類的效果較好且波動性較小。此外，這兩類演算法都具有需要的輸入引數較少的優點。 本文將劃分聚類高效率和層次聚類高精度的特點相結合，提出負荷曲線的整合聚類演算法。
- 3、整合聚類演算法 整合聚類演算法(ensemble clustering algorithm，EnsClust)的基本思想是：在原資料集的多個子集上重複進行劃分聚類，對得到的聚類中心用層次聚類進行組合。整合聚類演算法包括3 個步驟：bootstrap重取樣、劃分聚類、層次聚類。首先通過bootstrap 重取樣得到原資料集的多個樣本集，然後通過劃分聚類減小每個樣本集的資料規模，最後用層次聚類對劃分聚類的結果進行組合。 3.1 演算法流程如下：
1）bootstrap 重取樣。
所謂 bootstrap 重取樣就是對容量為n 的原始樣本進行有放回的隨機取樣，抽取的隨機樣本容量為n，並保證每次抽樣中各個體被抽取的概率相等。由於劃分聚類穩定性較差且可能收斂到區域性最優解，即不同的初始聚類中心或資料集的微小變動可能會導致不同的聚類結果。通過bootstrap 重取樣，在多個樣本集上進行聚類，可以降低初始聚類中心隨機因素和原始資料集中離群點的影響，從而提高演算法穩定性。
2）劃分聚類。
在整合聚類演算法中，劃分聚類可看作對層次聚類的資料預處理步驟。若直接對原始資料集進行層次聚類，則需要計算所有物件兩兩之間的歐氏距離並存儲該距離矩陣，時間和空間開銷很大。劃分聚類效率最高，用其輸出的聚類中心表徵原始資料集的結構，從而大幅縮減資料規模。和隨機抽樣相比，聚類中心包含原始資料集更多的資訊並能消除噪聲點和離群點的影響。
3）層次聚類。
在整合聚類演算法中，層次聚類可看作是對樣本集劃分聚類的輸出結果進行組合。為了解決劃分聚類容易陷入區域性最優解和受初始聚類中心影響較大的問題，採用聚類質量較好、穩定性較高的層次聚類演算法對劃分聚類輸出的聚類中心進行組合，進而得到最終的聚類結果。 - 3.2 演算法分析和實驗結果
綜合以上分析，整合聚類演算法不僅具有較高的計算效率，而且聚類質量也比傳統的劃分聚類和層次聚類演算法有所提高。
-
4、結合降維的整合聚類演算法 4.1 負荷曲線降維
當資料集規模較大時，採用整合聚類演算法的計算時間還是較長，為了進一步提升聚類效率，有必要對資料集進行降維處理。降維的目的用維數較低的向量表示負荷曲線。降維一方面可以減小資料的儲存空間，另一方面可以減少向量間歐氏距離的計算時間，提升演算法效率。常用的降維演算法包括sammon 對映、自組織對映、主成分分析等。 4.2 降維演算法分類 1）sammon 對映。 sammon 對映(sammon mapping，SM)是一種非線性對映，演算法的目標是最小化誤差函式：
式中：d(xi,xj)為原始空間中物件i 和物件j 間的距離；d(yi,yj)為投影空間中兩個物件的距離。sammon 對映用梯度下降法求解該優化問題。
2）自組織對映。
自組織對映(self-organizing map，SOM)神經網路可以實現對資料的非線性降維[20]。SOM 的輸入層節點是高維向量的屬性，輸出層節點是低維向量的屬性，輸入層屬性和輸出層屬性之間的相似性通過權向量表示。計算輸入向量x(m)與權向量w(n)間的歐氏距離d(x(m), w(n))，將與x(m)最近的輸出節點作為勝出節點，並更新其權向量：
式中η為學習率。同時更新其k 個近鄰的權向量。
3）主成分分析。
主成分分析(principal component analysis，PCA)是線性降維演算法。用原始變數的線性組合構造綜合指標，使其儘可能多地反映原始變數的資訊(用方差表達)。這些綜合指標即為主成分。
式中：X 為歸一化後的資料矩陣；cov(X)為協方差矩陣；V 的列向量為cov(X)的正交單位特徵向量。將 X 降至L 維後的資料矩陣為：
4）特徵提取。
特徵提取(feature extraction，FE)法直接計算每條負荷曲線的特性指標，本文對每條負荷曲線提取4 個基本特性指標：最大負荷、最小負荷、平均負荷、負荷標準差。
4.3 降維結果分析
ORG 表示原始資料集，SM、SOM、PCA、FE分別表示sammon 對映、自組織對映、主成分分析和特徵提取後的降維資料集。原始資料集是48 維，降維資料集是4 維。對降維資料集進行整合聚類。圖10 為各種降維方法的計算時間，包括降維時間和聚類時間兩部分。由圖 10 可見，PCA 降維方法的計算時間最小，且資料集規模越大效果越明顯。
各種降維方法的聚類結果的DBI 指標如圖11 所示。由 DBI 的箱線圖可知，主成分分析和sammon對映降維後的資料集聚類效果較好且與原始資料集的聚類效果相當，說明這兩種降維方法可以最大程度地保留負荷資料集的資訊。
綜上所述，負荷曲線PCA 降維後的整合聚類精度很高。 5、結論
本文提出了結合降維技術的電力負荷曲線整合聚類演算法。
1）聚類有效性指標SSE、CHI 和DBI 都可以正確地找到最佳聚類數。DBI 指標計算簡便、曲線直觀，適合作為負荷曲線聚類的有效性指標。
2）對於負荷曲線資料集，層次聚類演算法精度最高，劃分聚類演算法效率最高，且隨著資料集規模增大，各種演算法的效率差異顯著增大。
3）整合聚類演算法結合了劃分聚類高效率和層次聚類高精度的優點，聚類效率與劃分聚類演算法接近，聚類質量優於劃分聚類與層次聚類。
4）對於負荷曲線降維，主成分分析的計算時間(包括降維時間和聚類時間)最短；主成分分析和sammon 對映降維後的資料集聚類效果最好。
5）對於海量高維的負荷曲線，可採用主成分分析對資料集降維，在此基礎上應用整合聚類演算法聚類並用DBI 有效性指標評估聚類結果。
Ⅱ 基於改進DTW演算法的用電負荷聚類研究
一、背景知識：DTW演算法
Dynamic Time Warping（DTW 動態時間規整）是一種衡量兩個長度不同的時間序列的相似度的方法。應用也比較廣，主要是在模板匹配中，比如說用在孤立詞語音識別（識別兩段語音是否表示同一個單詞），手勢識別，資料探勘和資訊檢索等中。
在時間序列中，需要比較相似性的兩段時間序列的長度可能並不相等，在語音識別領域表現為不同人的語速不同。因為語音訊號具有相當大的隨機性，即使同一個人在不同時刻發同一個音，也不可能具有完全的時間長度。而且同一個單詞內的不同音素的發音速度也不同，比如有的人會把“A”這個音拖得很長，或者把“i”發的很短。在這些複雜情況下，使用傳統的歐幾里得距離無法有效地求的兩個時間序列之間的距離（或者相似性）。
例如上圖所示，實線和虛線分別是同一個詞“pen”的兩個語音波形（在y軸上拉開了，以便觀察）。可以看到他們整體上的波形形狀很相似，但在時間軸上卻是不對齊的。例如在第20個時間點的時候，實線波形的a點會對應於虛線波形的b’點，這樣傳統的通過比較距離來計算相似性很明顯不靠譜。因為很明顯，實線的a點對應虛線的b點才是正確的。而在下圖中，DTW就可以通過找到這兩個波形對齊的點，這樣計算它們的距離才是正確的。
也就是說，大部分情況下，兩個序列整體上具有非常相似的形狀，但是這些形狀在x軸上並不是對齊的。所以我們在比較他們的相似度之前，需要將其中一個（或者兩個）序列在時間軸下warping扭曲，以達到更好的對齊。而DTW就是實現這種warping扭曲的一種有效方法。DTW通過把時間序列進行延伸和縮短，來計算兩個時間序列性之間的相似性。
如何才知道兩個波形是對齊了呢？也就是說怎麼樣的warping才是正確的？直觀上理解，當然是warping一個序列後可以與另一個序列重合recover。這個時候兩個序列中所有對應點的距離之和是最小的。所以從直觀上理解，warping的正確性一般指“feature to feature”的對齊。
動態時間規整DTW是一個典型的優化問題，它用滿足一定條件的的時間規整函式W(n)描述測試模板和參考模板的時間對應關係，求解兩模板匹配時累計距離最小所對應的規整函式。
假設我們有兩個時間序列Q和C，他們的長度分別是n和m：（實際語音匹配運用中，一個序列為參考模板，一個序列為測試模板，序列中的每個點的值為語音序列中每一幀的特徵值。例如語音序列Q共有n幀，第i幀的特徵值（一個數或者一個向量）是qi。至於取什麼特徵，在這裡不影響DTW的討論。我們需要的是匹配這兩個語音序列的相似性，以達到識別我們的測試語音是哪個詞）
Q = q1, q2,…,qi,…, qn ; C = c1, c2,…, cj,…, cm ; 如果n=m，那麼就用不著折騰了，直接計算兩個序列的距離就好了。但如果n不等於m我們就需要對齊。最簡單的對齊方式就是線性縮放了。把短的序列線性放大到和長序列一樣的長度再比較，或者把長的線性縮短到和短序列一樣的長度再比較。但是這樣的計算沒有考慮到語音中各個段在不同情況下的持續時間會產生或長或短的變化，因此識別效果不可能最佳。因此更多的是採用動態規劃（dynamic programming）的方法。
為了對齊這兩個序列，我們需要構造一個n x m的矩陣網格，矩陣元素(i, j)表示qi和cj兩個點的距離d(qi, cj)（也就是序列Q的每一個點和C的每一個點之間的相似度，距離越小則相似度越高。這裡先不管順序），一般採用歐式距離，d(qi, cj)= (qi-cj)2（也可以理解為失真度）。每一個矩陣元素(i, j)表示點qi和cj的對齊。DP演算法可以歸結為尋找一條通過此網格中若干格點的路徑，路徑通過的格點即為兩個序列進行計算的對齊的點。
哪條路徑才是最好的呢？也就是剛才那個問題，怎麼樣的warping才是最好的。
我們把這條路徑定義為warping path規整路徑，並用W來表示，W的第k個元素定義為wk=(i,j)k，定義了序列Q和C的對映。這樣我們有：
首先，這條路徑不是隨意選擇的，需要滿足以下幾個約束：
1）邊界條件：w1=(1, 1)和wK=(m, n)。任何一種語音的發音快慢都有可能變化，但是其各部分的先後次序不可能改變，因此所選的路徑必定是從左下角出發，在右上角結束。
2）連續性：如果wk-1= (a’, b’)，那麼對於路徑的下一個點wk=(a, b)需要滿足 (a-a’) <=1和 (b-b’) <=1。也就是不可能跨過某個點去匹配，只能和自己相鄰的點對齊。這樣可以保證Q和C中的每個座標都在W中出現。 3）單調性：如果wk-1= (a’, b’)，那麼對於路徑的下一個點wk=(a, b)需要滿足0<=(a-a’)和0<= (b-b’)。這限制W上面的點必須是隨著時間單調進行的。以保證圖B中的虛線不會相交。 結合連續性和單調性約束，每一個格點的路徑就只有三個方向了。例如如果路徑已經通過了格點(i, j)，那麼下一個通過的格點只可能是下列三種情況之一：(i+1, j)，(i, j+1)或者(i+1, j+1)。
滿足上面這些約束條件的路徑可以有指數個，然後我們感興趣的是使得下面的規整代價最小的路徑：
分母中的K主要是用來對不同的長度的規整路徑做補償。我們的目的是或者說DTW的思想是把兩個時間序列進行延伸和縮短，來得到兩個時間序列性距離最短也就是最相似的那一個warping，這個最短的距離也就是這兩個時間序列的最後的距離度量。在這裡，我們要做的就是選擇一個路徑，使得最後得到的總的距離最小。 這裡我們定義一個累加距離cumulative distances。從(0, 0)點開始匹配這兩個序列Q和C，每到一個點，之前所有的點計算的距離都會累加。到達終點(n, m)後，這個累積距離就是我們上面說的最後的總的距離，也就是序列Q和C的相似度。 累積距離γ(i,j)可以按下面的方式表示，累積距離γ(i,j)為當前格點距離d(i,j)，也就是點qi和cj的歐式距離（相似性）與可以到達該點的最小的鄰近元素的累積距離之和：
最佳路徑是使得沿路徑的積累距離達到最小值這條路徑。這條路徑可以通過動態規劃（dynamic programming）演算法得到。
二、基於DTW改進演算法
1、概述
本文提出一種基於改進DTW演算法的用電負荷聚類方法，針對原DTW演算法時間複雜度高、存在惡性匹配的缺點，提出對DTW演算法的搜尋路徑進行限制，控制在矩陣對角線附近，在限制不合理點對匹配的同時大大降低了搜尋的複雜度，從O(N2)降至平均O(N)的水平；同時，引入曲線平移以在搜尋範圍內儘可能提升精度，改善時軸稍有偏移的相似曲線度量。最後選擇K-Medoids演算法進行聚類，對使用者進行劃分。
2、實現思路
動態時間規整（DTW）演算法可以用來衡量時間序列相似度，但其侷限性也非常明顯。如圖2-1所示，DTW在計算兩時間序列匹配關係時，會遍歷整個M*N矩陣尋找最優路徑，時間複雜度高達O（N2），在處理大資料量時顯得極為乏力；同時，DTW演算法存在病態匹配現象，在許多場合下，比較時間序列相似度不允許進行大量曲線伸縮，否則可能會引入額外誤差。例如對用電負荷進行聚類時，波動週期不同的使用者顯然具有不同的用電習慣，不應該通過伸縮對齊被誤聚為一類，圖2-2中的曲線會被DTW通過病態伸縮匹配，認為非常相似。
為此，論文提出了一種基於限制伸縮範圍並引入曲線平移的改進DTW演算法，實現對使用者用電負荷進行相似度分析。越相似的曲線，其匹配路徑越接近矩陣的對角線；反之通過伸縮才能對齊的曲線，其路徑波動極大。為了限制曲線的病態匹配，我們提出將搜尋範圍限制在矩陣對角線附近。對於超出搜尋範圍的部分，引入曲線平移，在不超過伸縮範圍的基礎上儘可能搜尋最相似的匹配，進一步改善計算結果。同時，由於限制了搜尋範圍，大大減少了相似度比較開銷，可以將演算法複雜度降至平均O(N)的水平。
該方法除了DTW的三個約束條件之外，還有另外兩個約束條件：
約束四：搜尋範圍約束。矩陣的搜尋範圍代表了曲線的伸縮程度，越相似的曲線匹配路徑就越貼近對角線。設路徑搜尋範圍必須在距離矩陣對角線附近Limit 範圍內，即曲線最大伸縮程度為Limit。
Pi=(xa,yb)，有|xa-yb|≤Limit
約束五：曲線平移約束。對於有明顯平移相似性的時間序列X 和Y，允許對曲線進行平移，平移後重新計算距離矩陣和匹配路徑。對於移出比較範圍的曲線起點和終點，保持它們的最優匹配關係，計入距離矩陣的初始值D[0,0]。
3、 演算法流程
4、 聚類演算法的選擇
為了對使用者用電負荷進行聚類，已經通過改良的DTW演算法衡量了用電曲線之間的距離。在此基礎上，我們選擇K-Medoids演算法對使用者進行聚類。
K-Medoids演算法與K-means演算法類似，都是通過隨機選取質心、計算點與質心的距離、更新質心的迭代過程完成聚類。不同之處在於質心的產生方法：在K-means中質心選取當前cluster中所有資料點的平均值；而在K-medoids演算法中，我們選取當前cluster 中到其他所有點距離之和最小的點作為新的質心。
L-K-Medoids演算法對髒資料和異常資料不敏感，個別用電異常的使用者不會影響整體聚類的結果；K-Medoids演算法可以得到典型用電曲線，即每一簇的質心都是一個實際使用者，可以真實反映本類使用者用電特徵，便於後續結合地理、經濟等相關資訊進行場景分析；同時，K-Medoids演算法有易於解釋的物理意義，每個向量代表著一條使用者用電曲線，每兩個向量之間的距離代表著不同使用者的用電相似度，每次迭代可以視作使用者的重新排隊，每個質心都代表著一個典型的實際使用者。
5、 實驗評估
選取輪廓係數Silhouette Coefficient、誤差平方和SSE以及Calinski-Harabaz Index作為評估指標。
輪廓係數結合內聚度和分離度因素，SI越接近1則聚類的效果越好，簇內更緊緻，簇間更分離。公式定義如下，其中a是與它同類別的其它元素的平均距離，b是與它距離最近的不同類別中樣本的平均距離。
誤差平方和SSE衡量距離定義的合理性，比較聚類結果各點距離簇中心的誤差。
Calinski-Harabaz Index則從協方差的角度評估資料，類別內部資料的協方差越小越好，類別之間的協方差越大越好，則其評分就會越高。公式定義如下：
其中m為訓練集樣本數，k為類別數，Bk為類別之間的協方差矩陣，Wk為類別內部資料的協方差矩陣，tr為矩陣的跡。
三、結論
本文提出了一種適合於衡量使用者用電模式相似度的基於限制伸縮的改進DTW演算法。引入搜尋範圍限制，規範了負荷序列的伸縮程度，避免了因惡意匹配造成的曲線週期改變，同時將運算複雜度提升至平均O（N）水平。通過引入序列平移，提升了演算法對峰值出現時刻存在差異的相似使用者的計算精度。
Canopy 演算法
K-Means 、K-Medoids演算法的一個不足之處是必須預先指定簇數K ，在許多實際應用中要設定一個合理的K值不是一件容易的事。此時，藉助Canopy 演算法可以完成簇數K 及初始簇中心的估計。Canopy 是一種聚類演算法，依據引數T 1 和T 2 實現物件的粗略劃分。下圖顯示一個典型的Canopy 聚類過程。
劃分過程如下圖：
Canopy 演算法雖然執行速度較快，但是聚類過程精度較低，因此本文使用Cannopy 演算法對資料初步並行聚類，獲取K 個簇。然後把獲得的K 個簇作為初始聚類個數利用用K-means 進行進一步聚類。也就是說Canopy 演算法主要把聚類分為兩個階段。第一階段為資料預處理階段，使用簡便計算方法將相似物件放入一個叫做Canopy 的子集中。第二階段為聚類計算階段，在各個子集中使用K-Means演算法計算同一子集中所有資料向量的距離。 其中，T1和T2的值可以用交叉校驗來確定。