差分隱私保護(hù)下面向海量用戶的用電數(shù)據(jù)聚類分析

王保義, 胡 恒, 張少敏

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

0 引言

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

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

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

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

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

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

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

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

1.2 聚類分析技術(shù)

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

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

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

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

2.1 計(jì)算模型設(shè)計(jì)

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

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

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

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

2.2 算法設(shè)計(jì)思想

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

2.2.1局部聚類

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

2.2.2全局聚類

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

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

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

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

2.3.2DPAK算法設(shè)計(jì)

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

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

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

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

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

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

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

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

2.4.1CDH算法設(shè)計(jì)

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

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

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

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

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

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

(1)

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

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

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

RC(Ci,Cj)=

(2)

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

(3)

(4)

(5)

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

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

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

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

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

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

步驟6:計(jì)算類簇間RI和 RC值。

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

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

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

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

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

首先計(jì)算γ=ρδ,并降序排列γ值,然后通過(guò)檢測(cè)γ值的鄰差值確定拐點(diǎn)。取拐點(diǎn)上方的對(duì)象數(shù)目Nc為聚類類簇個(gè)數(shù)。該方法在iris數(shù)據(jù)集上計(jì)算的前8個(gè)候選中心點(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ā)生了躍變,而這個(gè)點(diǎn)是γ中第三點(diǎn),即為聚類拐點(diǎn)。

傳統(tǒng)聚類算法對(duì)于凹凸鑲嵌且?guī)в写罅吭肼暤亩嗝芏葮O值數(shù)據(jù)集聚類質(zhì)量不佳,即使部分算法能夠?qū)崿F(xiàn)滿足要求的聚類,但聚類算法往往過(guò)于復(fù)雜。本文提出的CDH算法能夠?qū)崿F(xiàn)對(duì)任意形狀數(shù)據(jù)集的簡(jiǎn)潔、高效聚類,且抗噪聲干擾效果好。為了驗(yàn)證CDH算法的聚類效果及優(yōu)勢(shì),本文對(duì)比了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ù)來(lái)源及數(shù)據(jù)預(yù)處理

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

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

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

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

(6)

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

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

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

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

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

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

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

3.3 用戶用電算例分析

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

[1] 彭小圣,鄧迪元,程時(shí)杰,等.面向智能電網(wǎng)應(yīng)用的電力大數(shù)據(jù)關(guān)鍵技術(shù)[J].中國(guó)電機(jī)工程學(xué)報(bào),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ì)算的居民用電行為分析模型研究[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)自動(dò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é)報(bào)(自然科學(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] 刁鳳,張方國(guó).智能電表的完整隱私保護(hù)系統(tǒng)[J].密碼學(xué)報(bào),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ì)算機(jī)學(xué)報(bào),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é)報(bào),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] 陳平華,陳傳瑜.基于滿二叉樹(shù)的二分K-means聚類并行推薦算法[J].計(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é)報(bào)(理學(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ì)算機(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.