王保義, 胡 恒, 張少敏

(華北電力大學(xué)控制與計算機(jī)工程學(xué)院, 河北省保定市 071003)

0 引言

智能電表的逐漸普及使用戶用電數(shù)據(jù)收集變得簡單易行。海量用電數(shù)據(jù)使電力大數(shù)據(jù)分析技術(shù)[1]精確分析用戶用電行為成為了可能。精確的用電行為分析能為短期負(fù)荷預(yù)測、電價調(diào)節(jié)、提供個性化的用電服務(wù)等提供可靠的依據(jù)。因此用戶用電行為分析一直是研究熱點(diǎn)。文獻(xiàn)[2]利用云平臺和并行K-means算法對用戶用電行為進(jìn)行分析,最終把小區(qū)內(nèi)600名用戶分成了5類用戶。文獻(xiàn)[3]提出一種以數(shù)據(jù)對象密度稠密程度作為初始聚類中心選取標(biāo)準(zhǔn),并把簇間距離和類簇內(nèi)對象分散程度作為聚類數(shù)目選擇的標(biāo)準(zhǔn)的K-means算法,同時結(jié)合了MapReduce技術(shù)提高計算效率。該算法被應(yīng)用于用戶行為分析達(dá)到了預(yù)期的效果。文獻(xiàn)[4]用兩次聚類的方法對用戶用電行為進(jìn)行分析,該文首先利用K-means算法對用電數(shù)據(jù)進(jìn)行一次聚類,然后再次用聚類算法對之前聚類結(jié)果進(jìn)行聚類。

然而,智能電表收集的用戶用電信息中包括了很多用戶敏感信息。目前世界一些地方已出現(xiàn)了反對智能電表的聲音。2010年,美國斯科茨谷發(fā)起“Stop Smart Meter”的游行,使人們對智能電表的不信任達(dá)到了高潮。而大數(shù)據(jù)背景下對用戶的用電數(shù)據(jù)的精確分析對于改善用電服務(wù)、預(yù)測地區(qū)負(fù)荷、合理配電及減少網(wǎng)損等都是必不可少的。因此如何在對用戶用電數(shù)據(jù)快速、精確分析的同時保護(hù)用戶隱私不被泄露成為一個亟待解決的問題。

目前防止用戶隱私泄露的方法主要有面向智能電表和數(shù)據(jù)分析技術(shù)兩個方面。面向智能電表的隱私保護(hù)技術(shù)主要包括智能電表身份隱私保護(hù)技術(shù)和智能電表數(shù)據(jù)隱私保護(hù)技術(shù)[5]。文獻(xiàn)[6]把可鏈接直接匿名認(rèn)證技術(shù)和Pedersen承諾技術(shù)應(yīng)用于智能電表的實(shí)時發(fā)送數(shù)據(jù)階段和記賬階段,從而構(gòu)造一個完整的智能電表用戶完整隱私保護(hù)系統(tǒng)。文獻(xiàn)[7]提出了一種基于電池儲放電差分隱私保護(hù)模型,保護(hù)用戶的隱私不被智能電表泄露。智能電表端進(jìn)行隱私保護(hù),首先設(shè)計比較復(fù)雜,可能需要增加硬件開銷,給用戶帶來不好的體驗(yàn)。其次在大數(shù)據(jù)時代,匿名等傳統(tǒng)的隱私保護(hù)技術(shù)無法抵御完全背景知識攻擊。而且對用戶用電數(shù)據(jù)進(jìn)行挖掘分析,優(yōu)化電力公司對用戶的各項(xiàng)服務(wù)是獲取用電數(shù)據(jù)的目的。目前利用隱私保護(hù)數(shù)據(jù)挖掘[8]方法分析用戶用電信息的相關(guān)研究還比較少。

為此,本文提出了一種在數(shù)據(jù)分析階段對用戶隱私保護(hù)的方法——差分隱私保護(hù)下的用戶用電數(shù)據(jù)聚類分析方法。該方法利用差分隱私技術(shù)和兩階段聚類[9-11]在保證用戶隱私不被泄露的同時也能對用戶用電行為進(jìn)行快速、可靠的分析。

1 相關(guān)技術(shù)

1.1 差分隱私保護(hù)基礎(chǔ)

差分隱私保護(hù)[12-14]是通過向數(shù)據(jù)添加噪聲實(shí)現(xiàn)對敏感數(shù)據(jù)的保護(hù),同時又不影響數(shù)據(jù)自身的統(tǒng)計特征。差分隱私保護(hù)相較于其他隱私保護(hù)方法擁有堅實(shí)的數(shù)學(xué)基礎(chǔ)、可量化的隱私保護(hù)水平、能抵御最大背景知識攻擊等優(yōu)點(diǎn)。

差分隱私保護(hù)噪聲添加的機(jī)制主要有Laplace機(jī)制和指數(shù)機(jī)制。本文選用的是Laplace機(jī)制[15]。差分隱私保護(hù)是用敏感度[12]控制噪聲的大小。敏感度只與函數(shù)本身及計算方式有關(guān),與數(shù)據(jù)集大小無關(guān)。這為差分隱私保護(hù)用于局部用電數(shù)據(jù)動態(tài)聚類分析提供了支持。

1.2 聚類分析技術(shù)

聚類分析技術(shù)是一種無監(jiān)督學(xué)習(xí)技術(shù),根據(jù)聚類思想的不同被分為基于劃分、密度、層次等聚類算法。基于劃分的聚類算法中,K-means算法相較于其他聚類算法而言聚類速度較快,且簡單易實(shí)現(xiàn)。

密度聚類算法是通過過濾低密度區(qū)域發(fā)現(xiàn)稠密區(qū)域。本文密度聚類采用的是改進(jìn)的快速密度峰值聚類(CFSFDP)算法[16]。CFSFDP的核心思想是首先計算所有數(shù)據(jù)對象兩兩之間的距離和每一個數(shù)據(jù)對象的密度ρ并對其進(jìn)行降序排列,然后依次計算每個數(shù)據(jù)對象的δ,δ是該樣本點(diǎn)到比它的ρ大的所有樣本點(diǎn)的最小距離。根據(jù)ρ和δ生成決策圖,人為在決策圖選擇出聚類中心。最后對所有點(diǎn)進(jìn)行聚類。其在同類密度聚類算法具有只需要一次聚類計算就可以完成聚類且聚類質(zhì)量較高的特點(diǎn)。

層次聚類算法是通過某種層次架構(gòu),不斷地對數(shù)據(jù)進(jìn)行合并或者分裂,直到滿足停止條件。本文引用并改進(jìn)了Chameleon算法[17]合并子類簇時的思想。算法用圖劃分的方法把K-近鄰圖劃分成兩個大小相似的子圖。然后把每個子圖當(dāng)做初始圖重復(fù)上述過程,直到滿足停止條件。最后算法根據(jù)子類簇相似度的程度對子類簇進(jìn)行合并。相似度是從相對互連性(RI)和相對鄰近度(RC)兩個方面考慮的,即把RI與RC的乘積很高的兩個子類簇合并。相對于其他聚類算法的合并它考慮了簇與簇間的RI,RC,并能對子類簇進(jìn)行動態(tài)合并,最終的合并效果較好。

2 隱私保護(hù)下用電數(shù)據(jù)聚類分析算法設(shè)計

2.1 計算模型設(shè)計

智能電表對用戶用電信息的采集達(dá)到了30 min甚至15 min采集一次的頻率。對于這些超大規(guī)模、分布廣泛的數(shù)據(jù),傳統(tǒng)的數(shù)據(jù)挖掘方法已不能滿足大數(shù)據(jù)分析需求。

智能電網(wǎng)通過智能電表獲取用戶用電數(shù)據(jù),智能電表分布于各個家庭,其采集的用電數(shù)據(jù)是通過遠(yuǎn)程或本地通信信道完成系統(tǒng)各層之間的數(shù)據(jù)傳輸,由此可見用戶用電數(shù)據(jù)采用分布式采集和存儲。

分布式聚類[18-19]計算模型的核心思想首先是把利用智能電表獲取的用戶數(shù)據(jù)匯集到地區(qū)分站點(diǎn),對數(shù)據(jù)進(jìn)行清洗、預(yù)處理,構(gòu)建局部聚類模型進(jìn)行初次聚類。然后把初次聚類的結(jié)果傳輸?shù)娇倲?shù)據(jù)中心,在數(shù)據(jù)中心內(nèi)對初次聚類結(jié)果進(jìn)行二次優(yōu)化精確聚類得到全局聚類結(jié)果。最終根據(jù)得到的全局聚類結(jié)果進(jìn)行負(fù)荷特性分析。

分布式技術(shù)用于電力系統(tǒng)信息采集領(lǐng)域的大規(guī)模分散數(shù)據(jù)源[1],可以緩解各個站點(diǎn)與數(shù)據(jù)中心之間的通信壓力及減輕數(shù)據(jù)集中處理的負(fù)擔(dān),節(jié)約計算資源。

2.2 算法設(shè)計思想

用戶用電數(shù)據(jù)隱私保護(hù)聚類分析分為兩個階段:①局部聚類階段,運(yùn)用基于差分隱私保護(hù)技術(shù)的改進(jìn)K-means算法對海量原始用電數(shù)據(jù)聚類;②全局聚類階段,設(shè)計了一種基于密度層次聚類算法對局部聚類結(jié)果進(jìn)行二次優(yōu)化聚類。最后得到用戶用電行為習(xí)慣模型。

2.2.1局部聚類

局部聚類的目的是利用分布式的思想對分布廣、體量大的用電數(shù)據(jù)進(jìn)行初次聚類,計算出各個節(jié)點(diǎn)數(shù)據(jù)集的代表性負(fù)荷曲線,為二次聚類提供數(shù)據(jù)。在眾多聚類算法中K-means算法是聚類速度較快的算法之一,但它初始中心需人為設(shè)定,對聚類結(jié)果影響大,且在聚類過程中易泄露隱私,為此,本文設(shè)計了差分隱私保護(hù)自適應(yīng)K-means(DPAK)算法。該算法利用基于二叉樹結(jié)構(gòu)K-means算法對用電數(shù)據(jù)在分布式節(jié)點(diǎn)進(jìn)行初次聚類,在聚類過程中對其實(shí)施差分隱私保護(hù)。

2.2.2全局聚類

全局聚類的目的是對局部聚類的結(jié)果進(jìn)行優(yōu)化聚類,相對于原始數(shù)據(jù)量,全局聚類輸入數(shù)據(jù)量要小得多,因此相較于聚類速度,全局聚類更注重聚類質(zhì)量。本文設(shè)計了一種基于密度和層次聚類(CDH)的算法。CDH的主要思想:首先利用基于圖結(jié)構(gòu)密度聚類算法對數(shù)據(jù)集進(jìn)行聚類,得到若干高質(zhì)量的子類簇,然后引用并改進(jìn)Chameleon算法的合并子類簇的思想,對子類簇進(jìn)行動態(tài)合并。CDH算法可以對任意形態(tài)的數(shù)據(jù)集進(jìn)行聚類且聚類質(zhì)量高。

2.3 用電數(shù)據(jù)局部聚類算法設(shè)計

2.3.1自適應(yīng)K-means算法設(shè)計

自適應(yīng)K-means(AK)算法是利用二叉樹結(jié)構(gòu)進(jìn)行的動態(tài)聚類[20]。首先把整體數(shù)據(jù)集看作根結(jié)點(diǎn),隨機(jī)從根結(jié)點(diǎn)數(shù)據(jù)集中選擇兩個數(shù)據(jù)對象作為初始聚類中心,在結(jié)點(diǎn)上進(jìn)行t次迭代得到兩個類簇Ck(k=1,2),分別計算這兩個類簇的均方差EMSEk,然后把EMSEk與閾值T進(jìn)行比較,若EMSEk≤T,則停止。否則Ck繼續(xù)二分,直到滿足條件,最終得到葉結(jié)點(diǎn)即為每個最終類簇。

2.3.2DPAK算法設(shè)計

目前采用隱私保護(hù)分析技術(shù)在用戶用電數(shù)據(jù)挖掘階段對用戶隱私進(jìn)行保護(hù)的文獻(xiàn)還很少。而對用戶用電原始數(shù)據(jù)采用傳統(tǒng)隱私保護(hù)技術(shù)進(jìn)行發(fā)布,因原始數(shù)據(jù)體量大,故發(fā)布所消耗的資源大,且在分析階段會造成信息的丟失,從而影響分析的精度。在數(shù)據(jù)分析階段對其進(jìn)行隱私保護(hù)可有效避免以上問題。文獻(xiàn)[21]分析對比了目前主要的隱私保護(hù)技術(shù)得出差分隱私保護(hù)比較適合于數(shù)據(jù)挖掘技術(shù)。

差分隱私保護(hù)技術(shù)在數(shù)據(jù)挖掘上的研究多集中于頻繁模式挖掘和分類挖掘。在聚類算法上的研究還處于初級階段[22]。文獻(xiàn)[23]把差分隱私保護(hù)思想引入到K-means算法中;文獻(xiàn)[15]進(jìn)一步給出了K-means算法中添加噪聲的兩種方案,已知迭代次數(shù)為N的情況下,噪聲信號服從Laplace分布L((d+1)N/ε),其中d為數(shù)據(jù)維度,ε為隱秘保護(hù)水平。未知迭代次數(shù)情況時采用每次隱私預(yù)算減半的方法。文獻(xiàn)[24]提出并實(shí)現(xiàn)了差分隱私保護(hù)K-means算法,其與DPAK算法的不同之處在于對K-means算法初始聚類中心的選擇。DPAK算法描述如下:首先,從數(shù)據(jù)集隨機(jī)選取兩個數(shù)據(jù)對象C1,C2,作為待聚類數(shù)據(jù)中心點(diǎn),并對C1,C2進(jìn)行隱私保護(hù);然后,計算兩個類簇的EMSEk,并判斷EMSEk是否小于等于T,若否則對類簇繼續(xù)二分,執(zhí)行隨機(jī)選取數(shù)據(jù)中心直到滿足停止條件,若是則停止。在DPAK算法中每次僅選擇兩個初始中心點(diǎn)且迭代次數(shù)較小,這就大大降低了隱私泄露的風(fēng)險。

2.3.3局部隱私聚類算法有效性驗(yàn)證

為驗(yàn)證AK算法的有效性,本文選用UCI Machine Learning Repository的iris數(shù)據(jù)集對AK算法進(jìn)行驗(yàn)證,并把聚類結(jié)果與iris標(biāo)準(zhǔn)結(jié)果進(jìn)行了對比。

表1 AK算法聚類準(zhǔn)確度Table 1 Clustering accuracy of AK algorithm

從表1中可以得到AK算法聚類準(zhǔn)確度,此處用F-measure值評價聚類,AK算法的F=0.896 7。

DPAK算法在ε=1時對類簇1、類簇2、類簇3進(jìn)行的10次聚類結(jié)果的平均值分別為46.4,52.7,50.9。可知,DPAK算法在保護(hù)數(shù)據(jù)隱私的同時也有可能提高了聚類精確度。這種結(jié)果是可能的,因?yàn)樵肼暤奶砑硬⒉皇墙^對的負(fù)向影響聚類結(jié)果,對結(jié)果的影響也可能是正向[25]。

2.4 用電數(shù)據(jù)全局聚類算法設(shè)計

2.4.1CDH算法設(shè)計

局部聚類對智能電表采集的、存放于各分布節(jié)點(diǎn)的用戶用電數(shù)據(jù)進(jìn)行隱私聚類,計算出總體數(shù)據(jù)集的代表負(fù)荷曲線傳回數(shù)據(jù)中心。為二次優(yōu)化聚類代表負(fù)荷曲線,本文設(shè)計了基于CDH算法實(shí)現(xiàn)全局聚類。其所需的聚類數(shù)據(jù)是由DPAK算法所產(chǎn)生的能夠代表全局?jǐn)?shù)據(jù)的負(fù)荷曲線,這些代表性的負(fù)荷曲線所代表的每個類簇的總負(fù)荷曲線是不同的,所以它們在二次聚類中的地位、對二次聚類的影響也是不同的。為表現(xiàn)不同代表負(fù)荷曲線對二次聚類的影響,本文引入了負(fù)荷權(quán)重ωi,為類簇i中的數(shù)據(jù)對象數(shù)目與總數(shù)據(jù)對象數(shù)目的比值。

CFSFDP算法是一種密度聚類算法,它僅需一次計算便可實(shí)現(xiàn)對數(shù)據(jù)聚類,是目前較高效的聚類算法之一,但它也有不能自動選擇聚類中心、對多密度數(shù)據(jù)集聚類效果不佳、不能適用于大數(shù)據(jù)等缺點(diǎn)。為此本文提出了一種改進(jìn)的CFSFDP算法。改進(jìn)算法首先把整體數(shù)據(jù)看作是一個無向連通圖,計算鄰接矩陣D,路徑權(quán)值表示兩點(diǎn)間距離;其次確定截斷距離dc,把D中所有大于dc的路徑截斷;然后把每個數(shù)據(jù)對象Vi當(dāng)作圖心,統(tǒng)計所有可達(dá)Vi的對象Vj個數(shù)ρ,ρ稱之為Vi的負(fù)荷密度;最后對Vi按ρ降序排列。ρ越大,對應(yīng)的Vi越可能是類簇中心。若Vi成為聚類中心,還需要判斷Vi與Vh之間的距離,Vh屬于所有ρ大于Vi的ρ的數(shù)據(jù)對象集合,若二者不可達(dá)則Vh為新的類簇中心,否則Vh∈Vi。

聚類中dc的值是較難確定的,當(dāng)dc值大時,聚類數(shù)量少;反之,聚類數(shù)量多。本文為了便于后續(xù)數(shù)據(jù)分析,把dc值設(shè)的稍小些,這樣可以通過最終的類簇合并,得到最終聚類結(jié)果。

為了實(shí)現(xiàn)類簇合并,本文提出了內(nèi)部互連度的概念,即類內(nèi)所有點(diǎn)之間的相似度之和。內(nèi)部互連度用來測量這個類整體的緊密程度,內(nèi)部互連度大說明這兩個類融合的好。

從CDH算法第一階段生成的子類簇中選取K個最小距離,則內(nèi)部互連度EC(Ci)表示Ci類內(nèi)數(shù)據(jù)點(diǎn)之間的相似度之和。類間互連度ρi′表示Ci,Cj類之間最小的K個連接的相似度之和。

相對互連度RI(Ci,Cj)表示類間互連性相對于Ci,Cj兩個類的內(nèi)部互連性的規(guī)范化[17]。

(1)

類內(nèi)相似度AC(Ci)表示Ci類內(nèi)數(shù)據(jù)點(diǎn)之間的相似度之和的平均值。

類間相似度AC(Ci,Cj)表示Ci,Cj類之間最小的K個連接相似度之和的平均值。

相對相似度RC(Ci,Cj)表示類間相似度相對于Ci,Cj兩個類的類內(nèi)相似度的規(guī)范化。

RC(Ci,Cj)=

(2)

式中:|Ci|和|Cj|分別為類Ci和類Cj中數(shù)據(jù)點(diǎn)的個數(shù)。

(3)

(4)

(5)

在合并階段選擇RC(Ci,Cj)RI(Ci,Cj)值較大的兩類進(jìn)行合并。算法在迭代計算RC與RI乘積的過程中不需重新計算RI,RC值,而只需比較被合并的兩個子類簇的RI,RC值,選擇其中較大的值作為新類簇的RI,RC值。這也是此合并算法優(yōu)點(diǎn)之一。若未滿足合并停止條件(聚類個數(shù)或RI,RC閾值法),則算法繼續(xù)計算RC與RI的乘積。若滿足合并終止條件時,聚類結(jié)束。

數(shù)據(jù)通過密度層次聚類歸類到各個不同的類簇,因最終需要的是每個類簇的代表性負(fù)荷曲線,所以CDH算法最后是對每個類簇求均值得到均值負(fù)荷曲線。CDH算法具體步驟如下。

步驟1:計算數(shù)據(jù)對象間距離矩陣。

步驟2:計算各點(diǎn)負(fù)荷密度ρi,并排序。

步驟4:計算γ=ρδ及相鄰之間的差值,確定最終聚類個數(shù)。

步驟5:對非聚類中心數(shù)據(jù)對象進(jìn)行歸類。

步驟6:計算類簇間RI和 RC值。

步驟7:選取RC與RI的乘積值最大的兩個類進(jìn)行合并。

步驟8:判斷是否滿足停止條件,是則停止合并,否則返回步驟6。

步驟9:計算每個類均值負(fù)荷曲線。

2.4.2全局聚類有效性驗(yàn)證

本文采用判斷γ值拐點(diǎn)的方法確定CDH算法的最終聚類個數(shù)。

首先計算γ=ρδ,并降序排列γ值,然后通過檢測γ值的鄰差值確定拐點(diǎn)。取拐點(diǎn)上方的對象數(shù)目Nc為聚類類簇個數(shù)。該方法在iris數(shù)據(jù)集上計算的前8個候選中心點(diǎn)的鄰差值結(jié)果分別為0.494 4,0.418 4,0.006 6,0.007 7,0.006 6,0.007 9,0.000 5。從鄰差值結(jié)果中可以看出第2,3鄰差值相差很大,鄰差值在此處發(fā)生了躍變,而這個點(diǎn)是γ中第三點(diǎn),即為聚類拐點(diǎn)。

傳統(tǒng)聚類算法對于凹凸鑲嵌且?guī)в写罅吭肼暤亩嗝芏葮O值數(shù)據(jù)集聚類質(zhì)量不佳,即使部分算法能夠?qū)崿F(xiàn)滿足要求的聚類,但聚類算法往往過于復(fù)雜。本文提出的CDH算法能夠?qū)崿F(xiàn)對任意形狀數(shù)據(jù)集的簡潔、高效聚類,且抗噪聲干擾效果好。為了驗(yàn)證CDH算法的聚類效果及優(yōu)勢,本文對比了CFSFDP,K-means, CDH算法在數(shù)據(jù)集t48k[17]的實(shí)驗(yàn)結(jié)果,如圖1所示。圖中，不同的顏色表示不同的類簇。從圖1可以很清晰地看出本文所提CDH算法的聚類結(jié)果準(zhǔn)確度明顯優(yōu)于另外兩種算法。

3 算例分析

3.1 數(shù)據(jù)來源及數(shù)據(jù)預(yù)處理

為驗(yàn)證所提出算法的有效性及效率,本文所用數(shù)據(jù)為由The Research Perspective Ltd于2012年3月12日發(fā)布的愛爾蘭智能電表對某地區(qū)居民用電的監(jiān)測數(shù)據(jù),實(shí)現(xiàn)對用戶用電行為的分析。原始數(shù)據(jù)包含6個壓縮文件,前5個文件每個文件包含1 000個用戶,第6個文件包含1 445個用戶。它提

圖1 各算法在數(shù)據(jù)集t48k上的聚類結(jié)果Fig.1 Clustering results of each algorithm on datasets t48k

供用戶24天用電數(shù)據(jù)(第195至218天)但并不是所有用戶都提供了24天數(shù)據(jù),部分用戶不滿24天甚至沒有數(shù)據(jù)。每天采集48次,每隔30 min采集一次。

首先對數(shù)據(jù)進(jìn)行清洗,剔除其中的異常數(shù)據(jù)和某個時間段內(nèi)沒有數(shù)據(jù)的某天全部數(shù)據(jù),然后把數(shù)據(jù)轉(zhuǎn)化為每天48維的數(shù)據(jù)。最后利用式(6)對數(shù)據(jù)x進(jìn)行歸一化,使數(shù)據(jù)映射到[0,1]區(qū)間。

(6)

式中:xmax和xmin分別為數(shù)據(jù)集中的最大、最小值。

經(jīng)過處理后的數(shù)據(jù)最終得到了100 408條負(fù)荷曲線。

3.2 用電數(shù)據(jù)AK聚類算法T值的選擇

對AK算法復(fù)雜度進(jìn)行分析,因?yàn)锳K運(yùn)用二叉樹思想,所以在每個節(jié)點(diǎn)上的計算復(fù)雜度為O(2nt),其中n為數(shù)據(jù)集大小。最壞情況下,樹停止生長時為滿二叉樹,設(shè)樹最終高度為h,滿二叉樹每層節(jié)點(diǎn)為2h-1個,每個節(jié)點(diǎn)中數(shù)據(jù)的大小為n/2h-1,復(fù)雜度O=2tn/(2h-12h-1h);則AK算法最終復(fù)雜度為O(2nth)。由此可見AK算法復(fù)雜度由t,h決定。t決定著每個節(jié)點(diǎn)的均方差,t值越大,均方差越小,越是能很快滿足樹停止生長的條件,所以t與h呈負(fù)相關(guān)關(guān)系,一般情況下t值取很小值。設(shè)f=2nt,f的值幾乎固定,那么復(fù)雜度O(fh)主要取決于h,經(jīng)分析可知閾值T是影響h值的另一重要因素。當(dāng)T值越大時樹的高度越低,即h越小。所以取得恰當(dāng)?shù)拈撝礣對降低AK算法的復(fù)雜度很有意義。

在AK算法中T值決定著初次聚類的個數(shù),雖然整體算法對初次聚類要求不是十分精確,T值的選擇可以很靈活,但是一個較好的T值,可以在保證精度的同時提高整體的算法效率。本文的局部聚類采用的是分布式思想聚類方法,為模擬分布式計算,本文把數(shù)據(jù)分割成了10份,每份約10 000條負(fù)荷曲線。確定T值:首先從每一份數(shù)據(jù)中選取1 000條負(fù)荷曲線,然后在不同的T值下用AK算法對這些小規(guī)模數(shù)據(jù)進(jìn)行聚類,結(jié)果如圖2所示。

圖2 不同T值A(chǔ)K算法下對應(yīng)的代表性中心負(fù)荷曲線Fig.2 Central load curves produced by AK with different T

從圖2中可以看出,聚類中心負(fù)荷曲線個數(shù)隨著閾值T的增加而減少。在圖2中負(fù)荷曲線的減少并不是均勻的,而是在負(fù)荷曲線曲率最大點(diǎn)處曲線下降速率出現(xiàn)突變,越過此點(diǎn)下降速率開始變緩。本文稱此處為閾值拐點(diǎn)。

3.3 用戶用電算例分析

本文在對整體用電數(shù)據(jù)分析時把總負(fù)荷曲線分成了10份,每份10 000條負(fù)荷曲線(最后一份有10 408條負(fù)荷曲線),分別把這10份數(shù)據(jù)提交給不同的分布式節(jié)點(diǎn)進(jìn)行局部聚類。然后把每份數(shù)據(jù)在各節(jié)點(diǎn)計算出的代表性的負(fù)荷曲線匯集到中心節(jié)點(diǎn),在中心處用CDH算法對進(jìn)行全局二次聚類,最終聚類結(jié)果如圖3所示。

圖3(a)是用電數(shù)據(jù)經(jīng)本文所提算法聚類分析后得到的4種居民用電模型。從圖3中可以分析出每種居民不同的用電習(xí)慣。用電模型1在早上、晚上用電負(fù)荷較高,白天用電負(fù)荷低,整體負(fù)荷波動大。用電模型2用電比較平穩(wěn),整體用電負(fù)荷都比較高。用電模型3白天負(fù)荷低、晚上負(fù)荷高。用電模型4的用電高峰會出現(xiàn)在早上和晚上,但整體負(fù)荷波動不是太大。以上只是以一天為單位對居民用電行為進(jìn)行分析,當(dāng)數(shù)據(jù)量足夠大時還可以一周為單位對居民一周內(nèi)的用電習(xí)慣進(jìn)行分析預(yù)測,以季度、年為單位進(jìn)行分析,可以了解當(dāng)?shù)氐木用裆钏降母淖儭夂虻淖兓取?/p>

采用相同的數(shù)據(jù),用經(jīng)典K-means算法對該用電數(shù)據(jù)進(jìn)行聚類,其結(jié)果如圖3(b)所示,并將其作為新算法聚類結(jié)果的參考。

圖3 用戶用電行為聚類結(jié)果Fig.3 Clustering results of electricity consumption behavior

1)聚類結(jié)果有效性驗(yàn)證

對比圖3(a)和(b)中的負(fù)荷特性曲線可知,雖然兩圖中采用的負(fù)荷聚類算法不同,但其聚類特性曲線趨勢是相似的,文獻(xiàn)[2-3]證明了K-means聚類算法的有效性,這也說明本文所提算法是有效的。

2)聚類效率驗(yàn)證

已存在的用電聚類算法往往只是實(shí)現(xiàn)聚類分析。本文所提算法為了實(shí)現(xiàn)用電數(shù)據(jù)的隱私保護(hù),將算法分成兩部分。在第一步中通過對用電數(shù)據(jù)添加噪聲來實(shí)現(xiàn)隱私保護(hù),這一過程中肯定會帶來時間開銷。為了使算法的整體效率不降低,本文算法在局部聚類階段經(jīng)過DPAK算法對10萬余條原始數(shù)據(jù)聚類后產(chǎn)生了948組子類簇,而這個過程是在分布式計算節(jié)點(diǎn)完成的,這相較于K-means算法直接聚類原始數(shù)據(jù),本文算法的第二步聚類時數(shù)據(jù)量減少100多倍。這就顯著減少了全局聚類階段的負(fù)擔(dān)。本文算法整體聚類共耗時16.469 s。而K-means算法共耗時長為34.115 s,本文算法比經(jīng)典K-means算法快出一倍有余。而使用CFSFDP算法、Chameleon算法聚類用電數(shù)據(jù)所需時間均大于1 min。由此可見本文算法不僅實(shí)現(xiàn)了隱私保護(hù),而且在保證聚類精度的同時提高了整體聚類效率。

本文實(shí)驗(yàn)所用的用電數(shù)據(jù)量不是很大,當(dāng)用戶增多、使數(shù)據(jù)量增大時,分布式計算節(jié)點(diǎn)也會增加,可以通過增加聚類層數(shù)的方法提高運(yùn)行效率,以滿足時效性要求。

4 結(jié)語

針對智能電表獲得的用戶用電數(shù)據(jù)量大、分布廣及分析過程易泄露用戶隱私的問題,提出了一種差分隱私保護(hù)下面向海量用戶的用電數(shù)據(jù)聚類分析方法。該方法采用分布式思想,通過局部和全局聚類兩部分最終得到用戶用電行為模型,相關(guān)實(shí)驗(yàn)結(jié)果證明了其有效性。本文方法適用于處理海量用戶數(shù)據(jù),此時,通過增加分布式計算節(jié)點(diǎn)、增加聚類的層數(shù),以滿足時效上的要求。但這些方法可能使聚類結(jié)果準(zhǔn)確性變差,如何平衡分布式計算節(jié)點(diǎn)數(shù)量、聚類層數(shù)與聚類準(zhǔn)確性還有待進(jìn)一步研究。

[1] 彭小圣,鄧迪元,程時杰,等.面向智能電網(wǎng)應(yīng)用的電力大數(shù)據(jù)關(guān)鍵技術(shù)[J].中國電機(jī)工程學(xué)報,2015,35(3):503-511.

PENG Xiaosheng, DENG Diyuan, CHENG Shijie, et al. Key technologies of electric power big data and its application prospects in smart grid[J]. Proceedings of the CSEE, 2015, 35(3): 503-511.

[2] 張素香,劉建明,趙丙鎮(zhèn),等.基于云計算的居民用電行為分析模型研究[J].電網(wǎng)技術(shù),2013,37(6):1542-1546.

ZHANG Suxiang, LIU Jianming, ZHAO Bingzhen, et al. Cloud computing-based analysis on residential electricity consumption behavior[J]. Power System Technology, 2013, 37(6): 1542-1546.

[3] 趙莉,候興哲,胡君,等.基于改進(jìn)k-means算法的海量智能用電數(shù)據(jù)分析[J].電網(wǎng)技術(shù),2014,38(10):2715-2720.

ZHAO Li, HOU Xingzhe, HU Jun, et al. Improvedk-means algorithm based analysis on massive data of intelligent power utilization[J]. Power System Technology, 2014, 38(10): 2715-2720.

[4] 朱文俊,王毅,羅敏,等.面向海量用戶用電特性感知的分布式聚類算法[J].電力系統(tǒng)自動化,2016,40(12):21-27.DOI:10.7500/AEPS20160316007.

ZHU Wenjun, WANG Yi, LUO Min, et al. Distributed clustering algorithm for awareness of electricity consumption characteristics of massive consumers[J]. Automation of Electric Power Systems, 2016, 40(12): 21-27. DOI: 10.7500/AEPS20160316007.

[5] 田秀霞,李麗莎,孫超超,等.面向智能電表的隱私保護(hù)技術(shù)綜述[J].華東師范大學(xué)學(xué)報(自然科學(xué)版),2015(5):46-60.

TIAN Xiuxia, LI Lisha, SUN Chaochao, et al. Review on privacy protection approaches in smart meter[J]. Journal of East China Normal University (Natural Science), 2015(5): 46-60.

[6] 刁鳳,張方國.智能電表的完整隱私保護(hù)系統(tǒng)[J].密碼學(xué)報,2014,1(4):400-409.

DIAO Feng, ZHANG Fangguo. Full privacy preserving smart metering system[J]. Journal of Cryptologic Reseatch, 2014, 1(4): 400-409.

[7] ZHANG Zijian, QIN Zhan, ZHU Liehuang, et al. Cost-friendly differential privacy for smart meters: exploiting the dual roles of the noise[J]. IEEE Transactions on Smart Grid, 2017, 8(2): 619-626.

[8] AGRAWAL R, SRIKANT R. Privacy-preserving data mining[R]. 2000.

[9] TSEKOURAS G J, HATZIARGYRIOU N D, DIALYNAS E N. Two-stage pattern recognition of load curves for classification of electricity customers[J]. IEEE Transactions on Power Systems, 2007, 22(3): 1120-1128.

[10] BHATIA S K. Adaptivek-means clustering[C]// Proceedings of the Seventeenth International Florida Artificial Intelligence Research Society Conference, May 12-14, 2004, Miami Beach, Florida, USA.

[11] KWAC J, FLORA J, RAJAGOPAL R. Household energy consumption segmentation using hourly data[J]. IEEE Transactions on Smart Grid, 2014, 5(1): 420-430.

[12] DWORK C. Differential privacy[R]. 2006.

[13] 熊平,朱天清,王曉峰.差分隱私保護(hù)及其應(yīng)用[J].計算機(jī)學(xué)報,2014,37(1):101-122.

XIONG Ping, ZHU Tianqing, WANG Xiaofeng. A survey on differential privacy and applications[J]. Chinese Journal of Computers, 2014, 37(1): 101-122.

[14] DWORK C. A firm foundation for private data analysis[J]. Communications of the ACM, 2011, 54(1): 86-95.

[15] DWORK C, MCSHERRY F, NISSIM K. Calibrating noise to sensitivity in private data analysis[C]// Proceedings of Third Theory of Cryptography Conference, March 4-7, 2006, New York, NY, USA: 265-284.

[16] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.

[17] KARYPIS G, HAN E H, KUMAR V. Chameleon: hierarchical clustering using dynamic modeling[J]. Computer, 1999, 32 (8): 68-75.

[18] WANG Yi, CHEN Qixin, KANG Chongqing, et al. Clustering of electricity consumption behavior dynamics toward big data applications[J]. IEEE Transactions on Smart Grid, 2016, 7(5): 2437-2447.

[19] 倪巍偉,陳耿,吳英杰,等.一種基于局部密度的分布式聚類挖掘算法[J].軟件學(xué)報,2008,19(9):2339-2348.

NI Weiwei, CHEN Geng, WU Yingjie, et al. Local density based distributed clustering algorithm[J]. Journal of Software, 2008, 19(9): 2339-2348.

[20] 陳平華,陳傳瑜.基于滿二叉樹的二分K-means聚類并行推薦算法[J].計算機(jī)工程與科學(xué),2015,37(8):1450-1457.

CHEN Pinghua, CHEN Chuanyu. A bisectingK-means clustering parallel recommendation algorithm based on full binary tree[J]. Computer Engineering and Science, 2015, 37(8): 1450-1457.

[21] CLIFTON C, TASSA T. On syntactic anonymity and differential privacy[J]. Transactions on Data Privacy, 2013, 6(2): 161-183.

[22] 康海燕,馬躍雷.差分隱私保護(hù)在數(shù)據(jù)挖掘中應(yīng)用綜述[J].山東大學(xué)學(xué)報(理學(xué)版),2017,52(3):16-23.

KANG Haiyan, MA Yuelei. Survey on application of data mining via differential privacy[J]. Journal of Shandong University (Natural Science), 2017, 52(3): 16-23.

[23] BLUM A, LIGETT K, ROTH A. A learning theory approach to non-interactive database privacy[J]. Journal of the ACM, 2011, 60(2): 1-25.

[24] 李楊,郝志峰,溫雯,等.差分隱私保護(hù)k-means聚類方法研究[J].計算機(jī)科學(xué),2013,40(3):287-290.

LI Yang, HAO Zhifeng, WEN Wen, et al. Research on differential privacy preservingk-means clustering[J]. Computer Science, 2013, 40(3): 287-290.

[25] DWORK C, FELDMAN V, HARDT M, et al. The reusable holdout: preserving validity in adaptive data analysis[J]. Science, 2015, 349(6248): 636-638.