雙重聚類的協同過濾算法在智能家居中的應用

胡 磊，蔡紅霞，俞 濤

(上海大學 機電工程與自動化學院，上海 200072)

雙重聚類的協同過濾算法在智能家居中的應用

胡 磊，蔡紅霞，俞 濤

(上海大學 機電工程與自動化學院，上海 200072)

針對智能家居系統中用戶獲取有效信息困難的問題，提出基于用戶和環境雙重聚類的協同過濾推薦算法。利用K-means算法分別對智能家居系統中的用戶和環境進行聚類，找出目標用戶和所處家居環境的最近鄰居。使用歐氏距離為度量計算目標用戶和系統其他用戶之間、目標用戶所處家居環境和系統其他家居環境之間的綜合相似度。從最近鄰居之間選出與目標用戶最相似的前K個推薦給目標用戶，實現對推薦算法的優化。實驗結果表明，與傳統的協同過濾算法，以及基于用戶或環境單一變量的協同過濾算法相比，文中采用的算法推薦精度更高，實時性和可擴展性更好。

智能家居；K-means；聚類；最近鄰居；協同過濾

0 引 言

智能家居，就是使用當前先進的并且處于持續發展階段的計算機技術，以及網絡通訊等技術，以家庭住宅作為平臺，將各種與家居生活相關的功能性子系統，結合成一套高效的家居系統。在這套系統中，運用控制平臺進行統籌管理，使得家居生活更加安全、高效、舒適。智能家居系統中最重要的組成成分就是用戶和家居環境。通過智能家居系統，用戶不但可以控制各種家居環境，如遠程控制家用電器開關，設置家居溫度、濕度等，而且管理員可以管理所有用戶的家居信息，如各種家居設備狀態信息詳情，各個季節時間段不同用戶的家居環境偏好信息等，因此智能家居系統中的數據具有數據量龐大、數據異構等特點。隨著系統中用戶的不斷增長，用戶和家居環境等信息數據也在成倍增長，同時，信息質量良莠不齊，導致許多有效信息被埋藏在茫茫的信息海洋中，也給用戶獲取到想要的信息造成了巨大的困難[1]。智能推薦服務技術能為用戶提供便利，通過分析用戶的某些相關信息，主動地向用戶反饋滿足其需求的內容。這種方式可以更加高效地為用戶提供其所需信息，使用戶設置自己喜歡的家居環境，從而有效解決用戶信息獲取困難的問題。

1 推薦算法及其相關技術

國內外針對智能推薦服務展開了廣泛的研究與應用，目前最常見的推薦算法是協同過濾推薦：協同過濾算法[2-4]。根據用戶的歷史操作，首先分析用戶間存在的相似性，再根據這種相似性尋找目標用戶的相鄰集合，之后根據相鄰集合測算出這些目標群體會為他們沒有評分過的項目使用怎樣的評分，以此得到推薦結果。協同過濾正迅速成為一項受歡迎的技術，具有不需要領域知識、推薦準確度隨時間推移性能提高、推薦個性化高等優點。算法描述的應用情景也最適合智能家居系統推薦功能。

“協同過濾”這一術語是由GlodBerg等在開發推薦系統Tapestry[5]時提出的，該技術以其廣闊的應用價值受到越來越多的關注。

傳統的協同過濾算法可分為基于全局的過濾算法(Memory-basedalgorithm)和基于模型的過濾算法(Model-basedalgorithm)。其中，基于全局的過濾算法又可分為基于用戶(User-Based)的全局算法和基于項目(Item-Based)的全局算法。基于用戶的全局算法是最原始的，更好的解決辦法是構建以項目為基礎的推薦模型[5]，也就是一種基于項目的協同過濾算法。使用這種算法時，速度要比基于用戶的全局算法快很多,能夠很快地得到推薦結果[6]。但是基于用戶的全局算法適用于用戶數目變化不大而項目數量遠遠超過用戶的情況，而基于項目的全局算法卻適合用戶數量多但項目數并不多的情況[7]，同時相比基于用戶的方法，該算法擁有更好的可擴展性，但是還不能有效解決實時性和可擴展性問題?；谀Ｐ偷倪^濾算法在一定程度上可以解決可擴展性問題，如SarwarB等[8]提出一種增量式的基于矩陣奇異值分解法(SingularValueDecomposition，SVD)的協同過濾算法，從而降低了重復進行矩陣分解的代價，提高了推薦系統的可擴展性。此外，也可以使用主成分分析(PrincipalComponentAnalysis)[9]和(LatentSemanticIndexing，LSI)[10]對用戶協同過濾進行降維。若使用基于SVD的降維法，雖然能夠解決可擴展性問題，但要進行矩陣分解。為了提高可擴展性，Miyahara等[11]采用基于貝葉斯方法的協同過濾算法，但是貝葉斯網絡模型需要定期維護，加上模型訓練時間成本較高，所以只適用于數據變化不頻發的場景。

文中在智能家居系統中運用協同過濾算法實現智能推薦之前，采用基于用戶和環境的雙重聚類算法對用戶和環境進行聚類。聚類算法采用K-means，因為K-means算法非常適合對大型數據集進行分類[12]?？紤]到智能家居用戶對不同家居環境偏好信息，使用K-means算法把自身屬性和偏好相似的用戶劃分到相同的用戶簇中，另外，再把用戶所處的相似家居環境劃分到相同的環境簇中，這樣可以縮小活動用戶的最近鄰居查詢范圍。并且這些聚類操作可以在離線的環境下進行，不僅實現了對推薦系統實時性、可擴展性問題的緩解，同時保證了推薦的有效性。

2 基于用戶和環境雙重聚類的協同過濾算法流程

文中提出的協同過濾算法，在對智能家居系統進行用戶和環境雙聚類的同時，分別基于這兩方面的協同過濾方法，實現優質推薦，并且克服了原有協同過濾算法中關于可擴展性的缺陷。算法流程如圖1所示。

圖1 基于用戶和環境雙重聚類的協同過濾算法流程圖

算法具體描述如下：

(1)構建用戶屬性和偏好矩陣和用戶環境矩陣。

(2)用戶聚類和環境聚類：對所有系統用戶及家居環境，按照預先制定好的聚類準則，分別進行聚類。

(3)確定最近鄰居的用戶集合和環境集合：首先找到目標用戶及其所處環境，并找到這個環境所在的一個或幾個簇，然后再在簇中找到其最近鄰居集合。

(4)預測推薦：計算出目標用戶和目標用戶所處的環境的前N個相似度高的推薦方案。

(5)綜合推薦：獲取用戶聚類和環境聚類的推薦結果，將二者進行綜合計算，運用加權平均的方式獲取前K個方案推薦給目標用戶。

3 基于用戶和環境雙重聚類的綜合過濾算法的實現

3.1 用戶和環境的基礎數據庫構建

通過對用戶的自身屬性和智能家居系統中用戶的環境偏好分析，構建的用戶數據庫表的字段有性別、年齡、體重、溫度偏好、濕度偏好、水溫偏好等m個屬性。假設有n個用戶，則表示為用戶屬性和偏好矩陣就是Xi(n1,n2,…,nm),每一個用戶都可以用一個一行m列的數組表示，用戶信息表的設計如表1所示。

表1 用戶屬性和偏好表(Users)

通過分析用戶所處的智能家居環境，構建環境數據表。表中字段主要有當前溫度、溫度變化、當前濕度、濕度變化、空氣質量、空氣質量指數、用戶居家模式等k個屬性，同樣具有n個用戶。環境信息表的設計如表2所示。

表2 用戶家居環境表(Environment)

前面提到，用戶和用戶所有的屬性可以表示為一個1行m列矩陣，那么用戶可以用一個n行m列矩陣表示，Xn表示第n個用戶。同理，n個用戶和環境所有屬性也可表示為一個n行m列矩陣。

數據庫各個字段，若是數值類型，可直接計算；若是文字描述，則要將其先化為數值的形式。舉個例子，用戶性別是Boolean類型，女為true，男為false，可以用數字[1,0]表示。若無法枚舉，則要轉換成數值類型，通過去模糊化的方式。

3.2 用戶、環境聚類

由于用戶和環境聚類原理是一樣的，只是m個屬性值不一樣，所以只對用戶聚類進行描述。

對用戶進行聚類，運用的是K-means算法。如果用戶屬性與偏好值相似，就將他們放到同一用戶簇。例如，用戶i和用戶j的聚類相似度量采用歐氏距離相似度求得。聚類的用戶數為n，用戶屬性和偏好是m，則對用戶聚類的步驟如下：

(1)從用戶中隨機選取K個(u1,u2,…,uk)作為初始聚類簇，將K個用戶的m個屬性和偏好L(ui,j),i={1,2,…,k},j={1,2,…,m}作為初始聚類中心。

(2)以聚類中心為中心，算出其與剩余的每個用戶i屬性的歐氏距離，并算出偏好值與其的歐氏距離，比較二者相似度，根據相似度，將其放置到最相似的簇Cm中。

(3)重調各個簇的聚類中心。這種做法是基于分組后各簇中的用戶集。再選擇新的聚類中心，如何選擇則是根據各簇中存在的所有用戶屬性與偏好值的均值。

(4)經過上一步的調整，進行判斷，若新的聚類中心與上一次的一致，或者在一定的誤差范圍內，就結束聚類；否則重新回到步驟(2)。

另外，設置一個參數—最大迭代次數，以避免因不滿足第四步條件而進入無限循環的情形。算法偽代碼如下：

(1)從所有用戶集N中選擇K個用戶，用戶的屬性值和偏好值作為初始的聚類中心，記為集合CC={cc1,cc2,…,cck}；K個聚類簇初始化為空，記為集合c={c1,c2,…,ck}。

(2)repeat

Foreachuserui∈U

Foreachclustercenterccj∈cc

計算其他用戶i屬性和偏好與聚類中心ccj的歐氏距離相似度d(i,ccj)；

Endfor

d(i,ccj)=max{d(ui,cc1),d(ui,ccj),…,d(ui,cck)};

聚類cm=cm∪ui;

Endfor

Foreachclusterci∈c//對聚類中心進行調整

計算聚類ci中所有用戶屬性和偏好平均值，生成新的聚類中心cci

Endfor

Until所有聚類中心與上次循環的聚類中心相同(或者誤差Jc的值小于一定的閾值)

Return

3.3 最近鄰居查找和推薦生成

對用戶和環境進行聚類分簇以后，確定與目標用戶相似度最高的簇，獲取最近鄰居集合(在簇中與目標用戶擁有最高相似度的前K個用戶組成)。在最近鄰居查詢過程中，獲取用戶間的相似度需要通過如下步驟：

(1)用戶基于屬性和偏好的相似度。

相比距離度量，相似度計算更加注重兩個向量在方向上的差異。由于用戶屬性值和偏好值可以因用戶個人變化幅度很大，所以用戶屬性和偏好組成的向量在方向上的差異很大，故選用皮爾森相關性系數，求出用戶基于屬性和偏好的相似度simu(u,v)：

(1)

(2)用戶基于環境的相似度。

由于用戶在同一季節所處的環境屬性變化不會特別大，所以數據差異不會很大，則環境屬性組成的向量不會很大。如果用皮爾森相關性系數，那么計算出的環境之間的相似度差異會很小。假如任意兩個用戶所處的環境的相似度值都達到0.9以上，那么會影響推薦的準確性，所以選用基于歐氏距離相似度計算公式求出用戶基于環境的相似度sime(u,v)，計算公式為：

(2)

(3)

(3)綜合相似度。

通過對前兩步加權，計算綜合相似度：

sim(u,v)=αsimu(u,v)+(1-α)sime(u,v)(4)

為提高推薦算法質量，可以選擇適當的α值，結合兩種方式進行相似度計算。

(4)選取目標用戶的最近鄰居數為N的集合。

(5)在目標用戶的最近鄰居集合中選取綜合相似度最大的K個推薦給目標用戶。

3.4 計算實例

在用K-means算法對用戶和環境進行聚類，選取目標用戶的最近鄰居數為K個前提下，以某智能家居公司的數據樣本作為實驗對象進行分析。用戶屬性包括性別、年齡、體重、溫度偏好、濕度偏好、水溫偏好等，使用m1,m2,…,m6描述用戶的屬性和偏好，性別上取0為男，1為女；環境屬性包括當前溫度、當前濕度等屬性，用n1,n2,…,n6描述，用戶居家模式、運動模式和休息模式等分別用[1,2,3]等數字表示。具體用戶信息為:[性別:男,年齡:26,體重:65kg,溫度偏好:26 ℃,濕度偏好:48RH,水溫偏好:60 ℃],具體環境信息為[當前溫度:31 ℃,溫度變化:14 ℃,當前濕度:55RH,濕度變化:11RH,空氣質量:78,居家模式:居家模式],對用戶詳細信息和環境詳細信息進行數學建模后得到用戶信息:[m1:0,m2:26，m3:65,m4:26，m5:48，m6:60]，環境信息：[n1:31，n2:14，n3:55，n4:11，n5:78，n6:1](文中涉及到的計算用表均為建模處理后的數據)。

3.4.1 用戶相似度計算

由于用戶屬性和偏好采用的單位是不同的，數值的差異也很大，所以計算前要對用戶信息數字進行歸一化處理，則對用戶數據處理后的信息用矩陣表示(由于數據量大，所以只列出一部分)。

令X1為目標用戶，歸一化處理后的用戶信息如表3所示。

表3 用戶信息矩陣

針對上述矩陣，利用皮爾森相關系數公式計算的X1與任意數據庫中的用戶數組[X2,X3,X4,X5,X6，…]之間的相似度數組分別為[0.975,0.934,0.801,0.733,0.660,…]。

從該數組可以看出，目標用戶X1與用戶X4的相似度最大，但是僅僅計算用戶之間的相似度是不夠的。

3.4.2 環境相似度計算

下面來計算環境相似度。具體歸一化處理后的環境信息如表4所示。

表4 環境信息矩陣

針對上述矩陣，利用皮爾森相關系數公式計算目標用戶所處的當前環境Y1與數據庫中任意用戶之間的所處環境數組[Y2,Y3,Y4,Y5,Y6,…]的相似度數組為[0.916,0.521,0.497,0.441,0.534,…]。

3.4.3 綜合相似度計算

計算出用戶相似度和環境相似度后，再根據式(4)計算出基于用戶和環境的綜合相似度sim(u,v)。當α取0.6時，推薦精度最高的目標用戶和所處環境Z1的最近鄰居用戶簇和環境簇數組[Z2,Z3,Z4,Z5,Z6,…]的綜合相似度數組為[0.951,0.769,0.689,0.616,0.610,…]。

3.4.4 產生推薦

最后選取目標用戶最近的鄰居集合，例如選取綜合相似度最大的前10個用戶集合作為最近鄰居集合，然后在最近鄰居集合中選取綜合相似度最大的前3個用戶偏好和所處家居環境設置方案推薦給目標用戶。

4 實驗設計和結果分析

4.1 推薦質量的度量標準

為了驗證文中描述算法的可行性和準確性，使用了一個度量標準，那就是平均絕對誤差，即(Mean Absolute Error,MAE)[13]。由于這種標準的計算方式，是獲取預測值與實際值二者間的差值，并以此度量準確性，故這個偏差值越小，就意味著預測精度越高。設預測結果用矩陣[p1,p2,…,pn]表示,對應的實際結果用矩陣[q1,q2,…,qn]表示，則

(5)

這里的預測值可以表示系統通過計算得到的推薦給用戶的家居環境方案，而準確值可以表示用戶在這種環境下自己手動設置的家居環境方案。例如，用戶X1處在Y1的家居環境中，由于目前的環境參數與他的偏好不相符，所以系統通過計算給他提供推薦方案，但是他可以選擇不使用系統的推薦方案而自己設置，這樣就形成了兩個方案的對比，通過計算這兩種方案的MAE值，再和傳統的協同過濾推薦方案的MAE值進行比較，來判斷算法的有效性。

4.2 聚類算法的有效性驗證

為了驗證智能家居中基于用戶和環境K-means聚類算法的有效性，從某智能家居公司中隨機抽取1 500位用戶和3 000個用戶所處的歷史環境并通過Matlab對其進行分析。在用戶和環境集合中分別隨機選取7個中心，以×表示，通過計算點與點之間的歐氏距離，得到的聚類結果如圖2和圖3所示。由圖可知，在智能家居系統中，對用戶和環境進行聚類時，采取K-means算法是有效的。

圖2 1 500用戶聚類結果

圖3 3 000個環境數據聚類結果

4.3 權重系數α取值

式(4)中，權重系數α對推薦精度有很大影響，所以必須確定α的最佳取值來盡可能減小它對推薦精度的影響。α和1-α分別表示基于用戶聚類的相似度和基于環境聚類的相似度系數。將α從0.1變動到1，變動幅度為0.1每次，在不同α取值的情況下，觀察其對基于用戶和環境雙重聚類的協同過濾算法的推薦性能影響，從而確定最佳的權重值。α與MAE的曲線圖如圖4所示。

圖4 α與MAE曲線圖

由圖可知，α=0.6為最佳權重值，推薦誤差最小。

5 結束語

智能家居正不斷發展[14-17]，智能推薦已成為智能家居功能擴展中一個重要的趨勢，利用智能推薦功能為用戶提供定制信息服務將成為智能家居未來的主流。提出了一種基于用戶和環境雙重聚類的協同過濾算法并運用到智能家居系統中，該方法采用數據庫設計思想構建用戶庫和環境庫，從數據庫發現目標用戶最近鄰居集合，從中選取綜合相似度最大的前N個最佳方案推薦給用戶。理論分析和實踐結果均表明，相比現有的傳統個性化推薦技術，該技術的性能更加優越。

[1] 李 寧.2012年，哪些技術最火？[N].光明日報，2012-04-10(12).

[2]ResnickP,IacovouN,SuchakM,etal.GroupLens:anopenarchitectureforcollaborativefilteringofnetnews[C]//ACMconferenceoncomputersupportedcooperativework.[s.l.]:ACM,1994:172-190.

[3]SchaferJ.Collaborativefilteringrecommendersystems[M].Germany:[s.n.],2007.

[4]HuangZ,ZengD,ChenHC.Acomparisonofcollaborative-filteringrecommendationalgorithmsfore-commerce[J].IEEEIntelligentSystems,2007,22(5):68-78.

[5]GoldbergD,NicholsD,OkiBM,etal.Usingcollaborativefilteringtoweaveaninformationtapestry[J].CommunicationsoftheACM,1992,35(12):61-70.

[6] 郭艷紅.推薦系統的協同過濾算法與應用研究[D].大連:大連理工大學,2008.

[7] 張雪文.智能推薦系統中協同過濾算法的研究[D].上海:上海交通大學,2008.

[8]SarwarB，KarypisG,KonstanJ，etal.Incrementalsingularvaluedecompositionalgorithmsforhighlyscalablerecommendersystems[C]//Proceedingsoffifthinternationalconferenceoncomputerandinformationscience.[s.l.]:[s.n.],2002:27-28.

[9]GoldbergK,RoederT,GuptaD,etal.Eigentaste:aconstanttimecollaborativefilteringalgorithm[J].InformationRetrieval,2001,4(2):133-151.

[10]SoboroffI,NicholasC.Combiningcontentandcollaborationintextfiltering[C]//Proceedingsoftheinternationaljointconferencesonartificialintelligenceworkshop:machinelearningforinformationfiltering.Stockholm:[s.n.],1999:86-91.

[11]MiyaharaK,PazzaniMJ.ImprovementofcollaborativefilteringwiththesimpleBayesianclassifier[J].IPSJJournal,2002,43:3429-3437.

[12]HuangZ.Afastclusteringalgorithmtoclusterverylargecategoricaldatasetsindatamining[C]//ProceedingsoftheSIGMODworkshoponresearchissuesondataminingandknowledgediscovery.Tucson:[s.n.],1997:146-151.

[13]HerlockerJL,KonstanJA,TerveenLG,etal.Evaluatingcollaborativefilteringrecommendersystem[J].ACMTransactionsonInformationSystems,2004,22(1):5-53.

[14] 鄧中祚.智能家居控制系統設計與實現[D].哈爾濱:哈爾濱工業大學,2015.

[15] 彭洪明.智能家居的體系結構及關鍵技術研究[D].北京:北京交通大學,2012.

[16] 呂 莉,羅 杰.智能家居及其發展趨勢[J].計算機與現代化,2007(11):18-20.

[17] 高小平.中國智能家居的現狀及發展趨勢[J].低壓電器,2005(4):18-21.

Application of Collaborative Filtering Recommendation Based on Double Clustering in Smart Home System

HU Lei,CAI Hong-xia,YU Tao

(School of Mechatronics Engineering and Automation,Shanghai University, Shanghai 200072,China)

To deal with the difficulty of acquiring effective information in smart home system for users,a collaborative filtering recommendation based on users and environment double clustering is proposed.It appliesK-meansmethodtoclustertheusersandenvironmentandfindoutthenearestneighborsoftargetuserandhomeenvironment.Thencomputesthecomprehensivesimilaritybetweentargetuserandotherusers,homeenvironmentoftargetuserandotherhomeenvironmentinsystem.ChoosesthefirstKrecommendationinthenearestneighborstotargetusers,realizingtheoptimizationofrecommendation.Experimentalresultsdemonstratethatthealgorithmcanimprovetheaccuracyofrecommendationcomparedwiththetraditionaloneandtheonebasedonuserorenvironment,withbetterreal-timeandscalability.

smart home;K-means;clustering;thenearestneighbors;collaborativefiltering

2016-01-11

2016-06-02

時間：2017-01-10

上海市科技重點攻關項目(15111102202)

胡 磊(1991-)，男，碩士研究生，研究方向為智能家居系統；蔡紅霞，碩士研究生導師，副教授，研究方向為工業信息化、計算機集成制造等；俞 濤，博士研究生導師，教授，研究方向為工業信息化等。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.0941.014.html

TP

A

1673-629X(2017)02-0100-06

10.3969/j.issn.1673-629X.2017.02.23