一種基于粗糙集和歐式距離的手機故障案例匹配算法?

唐瑞春， 張肖南， 郭雙樂， 邱 悅， 丁香乾

(1.中國海洋大學信息科學與工程學院，山東 青島 266100；2.武漢東方賽思軟件有限公司，湖北 武漢；3.濱州學院信息工程系，山東 濱州 256600；4.北京三快在線科技有限公司，北京 朝陽區 100000)

?

一種基于粗糙集和歐式距離的手機故障案例匹配算法?

唐瑞春1， 張肖南2， 郭雙樂3， 邱 悅4， 丁香乾1

(1.中國海洋大學信息科學與工程學院，山東 青島 266100；2.武漢東方賽思軟件有限公司，湖北 武漢；3.濱州學院信息工程系，山東 濱州 256600；4.北京三快在線科技有限公司，北京 朝陽區 100000)

本文研究在云環境中手機故障案例檢索時的案例匹配問題，提出了一種基于粗糙集和歐式距離的案例相似度匹配算法CMARE(Case Matching Algorithm based on Rough sets and Euclidean distance)。首先云計算平臺收集手機故障參數，根據參數構建粗糙集信息表，利用粗糙集求出信息表里各案例特征參數的屬性客觀權重值并結合專家經驗給出綜合的屬性權重值，最后利用此權重值和歐式距離計算案例間的相似度,找出案例庫中與新案例最相似的案例。該算法的創新之處在于確定案例屬性權重值時基于數據本身和人工經驗，避免了過分依靠人工經驗知識設定屬性權重的不足；與規則推理方式不同，本文使用案例推理的方式。仿真實例說明了算法的有效性。

手機故障檢索；粗糙集；歐式距離；信息表

隨著相關技術的發展，手機的結構越來越復雜，功能越來越完善，智能化程度也越來越高。手機在使用過程中也會出現各種故障，當前，人工智能領域中沒有專門針對手機的故障診斷方法，手機故障點的查找都是依靠人工查找，往往會出現誤診或者漏診，其準確性有待進一步提高。

隨著移動互聯網和云計算的發展，手機可以與云計算平臺更好的交互，從而可以利用云計算平臺輔助手機故障的診斷。利用云計算環境收集手機運行時的參數，在云平臺上與已有的故障案例進行相似度的計算，依據相似度的高低對新故障進行推理，從而能夠在故障發生時進行有效的分析和處理，這對于故障點的確定有著重要的意義。

基于案例的推理即CBR(Case Based Reasoning)，核心思想是使用過去人們解決問題的經驗解決新問題，它需要研究以往的案例庫，如果無法在案例庫中找到與當前案例相同的案例，則需要找到一個與當前情況最相似的案例。CBR由4個基本過程組成—4R循環：Retrieve、Reuse、Revise、Retain，分別對應著案例的檢索、重用、改編和保存(學習)[1]。

CBR在故障推理和預測工作中有著廣泛的應用。文獻[2]提出了使用云計算平臺云景，通過CBR推理的方式來預測大型風力發電機故障；文獻[3]將CBR推理應用到了飛機故障預測系統中，同時結合了故障樹的方式，逐步完善數據庫，提高了案例庫的準確度。事例的檢索和選擇是CBR系統的一個關鍵步驟，也是CBR系統技術實現研究的一個熱點問題。文獻[4]研究了在進行相似度檢索時使用最近相鄰法來進行案例檢索，利用海明距離(Hamming Distance)來計算相似度；文獻[5]中在使用CBR進行故障推理時使用歐式距離(Euclidean Distance)來計算相似度。以上各文獻在確定故障案例中各特征的屬性權重時都是根據人工經驗直接指定，從而引入了人為因素，導致案例檢索準確性不夠。

為解決上述問題，本文提出了基于知識粒度粗糙集的屬性權重計算方法，在結合歐式距離的基礎上以知識粒度粗糙集來計算案例中各屬性的客觀權重值，結合人工經驗給出最終的屬性權重值，將其應用到手機故障案例匹配中能夠提高案例匹配的精確度。云計算平臺收集手機運行時的狀態參數，提取故障參數并創建新案例，云平臺根據故障參數構建決策表，利用決策表計算各參數代表的屬性權重值，之后結合人工經驗給出最終的屬性權重值；在計算相似度時利用歐式距離求案例的相似度，并結合決策表求出的屬性權重值，從而得到更準確的相似度結果。

1 相關研究

1.1 研究環境

如圖1所示，手機故障案例的檢索主要在云計算平臺上完成，手機運行時的故障特征參數作為輸入。在服務器端，收集到手機運行時的參數并保存，權重計算模塊會根據故障特征參數，從云存儲的案例庫中選出相關的案例集，組成信息表并進行權重計算，之后進行案例的匹配計算。

圖1 基于粗糙集和歐式距離的相似度檢索算法應用環境

1.2 基于粗糙集和歐式距離的CBR模型

CBR模型廣泛應用在案例推理與故障預測中，模型如圖2所示，CBR是模擬人腦類比學習的過程。常見的CBR模型有高斯案例推理預測模型和貝葉斯案例推理模型等。

圖2 基于粗糙集和歐式距離的CBR模型

基于粗糙集與歐式距離的CBR案例匹配過程為：對新出現的故障案例，首先在案例庫中查找到相關的案例構建決策表，利用知識粒度粗糙集求出決策表中的客觀屬性權重值并結合專家經驗給出最終權重值，利用歐式距離求出新產生的案例與案例庫中的案例最為匹配的案例，最后將檢索到的結果返回。

2 CMARE算法

2.1 基于粗糙集的屬性權重確定

對于手機而言，故障工作狀態參數包括由其操作系統讀取的當前工作狀態下系統中各項設備的運行狀態及特征信號。手機故障征兆指以一定形式表現出來的狀態信息，如供電端電壓過高或者過低，電容失效等。除了故障工作狀態參數和故障征兆外，手機其他信息還包括一些設備及運行信息，如手機型號、CPU處理器型號、運行狀態等。手機的這些工作參數通過云計算平臺收集起來用于創建新的故障案例。在計算新案例與已有案例的相似度時，各屬性的權重值直接影響到相似度的值，獲得準確的屬性權重值至關重要，因此，計算出權重值是相似度計算的前提。屬性的權重將根據案例庫中的已有案例計算得出。

手機故障案例庫S′可由一個四元組來描述：

S′=(U′,A′,V′,f′)。

(1)

其中：U′為所有的故障案例的集合；A′是案例中所有的故障特征即故障屬性的集合；V′是A′中所有屬性值的集合；f′是指定U′中每個案例對象屬性值的信息函數，f′:U′×A′→V′。

知識粒度粗糙集理論框架，主要研究一個由對象集和屬性集構成的信息系統S[6]：

定義1 定義一個知識系統：

S=(U,A,V,f)。

(2)

(1)故障案例集U′對應粗糙集理論中的論域U。

(2)故障特征屬性A′對應粗糙集理論中的屬性集合A。

(3)案例屬性值域V′對應粗糙集理論中的值域集合V。

(4)案例與屬性之間的關系函數f′對應粗糙集中的關系函數f。

因此，案例庫中屬性求權重問題可以轉換成粗糙集理論中的屬性權重值求解問題。在粗糙集中，存在著由關系函數f確定的“屬性—值”的二維表，即信息表，案例庫中的信息表對應于粗糙集中的決策表。通過求出決策表中各條件屬性對應于決策屬性的權重值，進而得到不同故障特征對應于故障結果的重要程度。具體在粗糙集中求解如下：

(3)

表1 故障集信息系統

屬性重要程度：依據知識粒度粗糙集模型，設X?A是一屬性子集，x∈A為一屬性，記x對X的屬性重要度為Wx，其定義為[7]：

(4)

(5)

(6)

(7)

歸一化之后Wi就作為每個屬性的客觀權重。

在信息系統S=(U,A,V,f)中，條件屬性C?A中每個屬性對于決策屬性取值的影響是不同的，應該賦予它們不同的權重。該文給出的最終權重結果有兩部分權重組成，一是由大量歷史數據體現，并通過知識粒度粗糙集理論處理而得到的客觀權重W，二是由專家經驗知識直接確定的主觀權重P：

(8)

I=?W+(1-?)P0≤?≤1。

(9)

其中：?為經驗因子，0≤?≤1反映了決策過程中決策者f對客觀權重和主觀權重的偏好程度：?越大，表明決策者越重視客觀權重；?越小，表明決策者越重視專家的經驗知識。特別地，若?=1，則決策者只考慮客觀權重；若?=0則決策者只考慮專家的經驗知識。在得到綜合權重之后，對綜合權重再進行歸一化處理，即可得到各個屬性的最終權重值。

依據信息表求出的各屬性權重值，其結果比較客觀，再結合專家經驗直接給出權重值，求出屬性權重值后將權重值帶入相似度計算公式，即可以得到案例的相似度結果。

基于粗糙集的屬性權重計算過程：

Step1 根據新案例特征屬性ai1到ain確定信息表；

Step4 根據公式(4)計算屬性aij的客觀權重；

Step5 若j

Step6 結合公式(8)設定的權重利用公式(9)計算最終的屬性權重值I。

2.2 基于知識粒度粗糙集和歐式距離的案例匹配

(10)

其中d為案例Ci和C0中對應屬性的歐式距離，兩案例在各屬性上的對應分量相同，則其歐式距離為0，其相似度為最高1[8]。

(11)

其中表示案例庫中案例的屬性值，a0j表示新產生的案例中的屬性值，Iaj表示對應屬性由粗糙集求出的綜合權重值。

案例匹配是在案例庫中尋找與當前案例相同或者最相似案例的過程，在收集到新的故障案例時，云平臺先去查找案例庫中是否存在完全相同的案例，如有直接返回案例結果，如不存在，則利用基于歐式距離的檢索算法進行檢索計算。本文基于粗糙集和歐式距離的相似度匹配算法過程如下：

Step1 提取手機故障征兆并創建新故障案例；

Step2 根據故障屬性提取故障庫案例，并構建信息表；

Step3 根據基于粗糙集的屬性權重計算算法計算屬性權重；

Step4 按式(10)計算當前案例與案例庫中案例各條件屬性的歐式距離；

Step5 通過對各條件屬性的歐式距離進行加權求案例間的整體相似度，其中權重為Ia1,Ia2,,…,Ian，由Step3求出，相似度計算依據式(11)。在求出新案例與案例庫中的案例相似度以后，按照相似度由大到小的順序排列，設定閾值，將閾值以上相似度最高的結果返回。若結果中沒有閾值以上的結果，則認為是案例庫中不存在的新故障，將新案例加入案例庫，因本文重點在于案例的相似度計算和案例匹配，新案例如何加入案例庫部分不再贅述。

先由粗糙集理論來確定屬性的權重值，之后利用歐式距離來求兩案例的相似度，避免了人工設定權重值主觀性，可以使檢索結果更具有客觀性，也更加準確。

3 仿真實驗

為了驗證CMARE算法的有效性，本文選擇某手機廠商測試數據為研究目標，使用VC++6.0搭建仿真環境實現算法，利用測試數據中手機運行故障參數和已量化的案例庫作為輸入，評估CMARE手機故障案例匹配算法的性能。

將手機中常出現的3種故障主板故障、電源故障、軟件故障作為研究的對象進行量化：決策屬性為1代表手機主板故障，決策屬性為2代表電源故障，決策屬性為3代表軟件故障，其伴隨的征兆集合即故障現象量化如表2。

表2 征兆集合列表

表3 手機故障案例決策表

本文選取其中的8種屬性進行決策，如果某項征兆出現，則對應的屬性我們量化為1，反之量化為0。從手機的測試數據庫中選取60組數據作為案例庫數據，則手機的故障案例決策表可量化表示如表3。

新案例依據相同的方式進行量化，量化后為一維數組，之后將量化的結果輸入查詢匹配，并將結果返回。

首先，案例匹配檢索的準確性是衡量預測算法成功與否的一個因素。因此，用成功率(Successrate)表示當前系統在同樣給定的案例庫時，僅僅基于專家設定權重值參數的CS算法和利用粗糙集獲取權重值參數的CMARE的正確率(見圖3)。

圖3 案例檢索的準確率

圖中CMARE表示基于粗糙集和歐式距離的檢索算法，CS表示由專家設定權重值的預測算法，圖中縱坐標表示推理預測的準確率，橫坐標表示案例庫中的案例的個數，由于實驗條件限制，本文案例庫選擇了60組案例，由圖可以看出來，隨著數據庫中的案例個數的增加，推理預測的準確性會越來越高，同時，可以看出CMARE準確率剛開始和CS的準確率高相差不大，但隨著案例數目的增加，CMARE算法的準確率不斷提高并超過CS的準確率，這是因為隨著案例庫中案例的增加，各屬性的權重值越接近客觀均值，從而在計算相似度時使準確率更高。

其次從誤報率的角度考慮，仿真實驗仍然采用上面給出的案例庫，新案例采用與案例庫中案例差別較大的案例，統計其誤報率,如圖4。

圖中縱坐標表示案例檢索的誤報率，橫坐標表示案例庫中的案例的個數，由圖可以看出來，隨著數據庫中的案例個數的增加，CRE案例檢索算法的誤報率會越來越低，說明基于粗糙集案例匹配算法的有效性。

圖4 案例檢索的誤報率

4 結語

本文研究在云計算環境中手機故障預測算法，提出了一種基于粗糙集的CMARE檢索算法。目前專門針對手機故障診斷的方法較少，本文將基于案例推理的故障診斷方法引入手機的故障診斷中，同時為了提高故障案例的匹配準確度，利用粗糙集計算屬性權重值，結合專家系統給出最終的權重值，使用歐式距離來計算案例的相似度。該算法在確定屬性權重值時基于數據本身和專家經驗，避免了僅僅依靠專家經驗設定屬性權重值的不足，仿真結果說明了該算法的有效性。

[1]TomásdelaRosa,AngelGarcía-Olaya,DanielBorrajo.Acaseba-sedapproachtoheuristicplanning[J].AppliedIntelligence, 2013, 39(1): 184-201.

[2]ArshdeepBahga,VijayK.Madisetti.AnalyzingmassivemachinemaintenanceDatainacomputingcloud[J].IEEETransactionsonParallelandDistributedSystems, 2012, 23(10): 1831-1843.

[3]ZhouYilin,LiHongning.Aircraftfaultdiagnosisbasedonc-ase-Basedreasoningandfaulttreeanalysisintegrated[C]//2011InternationalConferenceonElectronics,CommunicationsandControl,Ningbo,China：IEEEComputerSociety, 2011: 703-706.

[4] 王曉亮, 劉西拉. 基于事例推理系統中的模糊檢索[J]. 上海交通大學學報, 2007, 41(11): 1783-1787.

[5] 董磊, 任章, 李清東. 基于模型和案例推理的混合故障診斷方法[J]. 系統工程與電子技術, 2012, 34(11): 2339-2343.

[6]JuanM.Alberola,AnaGarcia-Fornes.Usingacase-basedreas-oningapproachfortradinginsportsbettingmarkets[J].App-liedIntelligence, 2012, 38(3): 465-477.

[7] 王洪凱, 姚炳學, 胡海清. 基于粗集理論的權重確定方法[J]. 計算機工程與應用, 2003, 40(36): 20-21.

[8]BohaiHong,RuichunTang，YiliZhai.AResourcesAllocationAlgorithmbasedonMediaTaskQoSinCloudComputing[C].Beijing：Proceedingsof2013IEEE4thInternationalConferenceonSo-ftwareEngineeringandServiceScience, 2013: 841-844.

責任編輯 陳呈超

A Failure Case Matching Algorithm Based on Euclidean Distance and Rough Sets

TANG Rui-Chun1, ZHANG Xiao-Nan2, GUO Shuang-Le3, QIU Yue4， DING Xiang-Qian1

(1.College of Information Science and Engineering, Ocean University of China, Qingdao 266100,China；2.East Science software Co.of Wuhan, Wuhan 43000,China;3.College of Information Engineering,Bin Zhou University,Bin Zhou 256600,China;4.Peking Science and Technology Co.,Three Fast Anliml,Beijing 100000,China)

Study the mobile phone fault case retrieval in a cloud environment when matching cases, we propose a similarity matching algorithm CMARE (Case Matching Algorithms based on Rough sets and Euclidean distance).First, cloud computing platform collects mobile phone fault parameters, and then it builds a Rough sets information table according to these parameters. Second, property weight is computed based on objective weight of feature parameters of each case in the table calculated by Rough sets as well as in the light of expertise. Finally, with the weight and Euclidean distance, the degree of similarity between cases are figured out and then the most similar one from the case base is chased down. This algorithm is based on the date and experience, avoiding the disadvantage of being overly dependent on artificial expertise. This algorithm is based on the date and experience, avoiding the disadvantage of being overly dependent on artificial expertise. The simulation shows the effectiveness of the algorithm.

the mobile phone fault case retrieve; rough sets; euclidean distance; information table

國家科技支撐計劃項目(2012BAH15F01)資助

2014-04-26;

2014-11-20

唐瑞春(1968-)，女，教授。研究方向：網絡流媒體。E-mail:tangruichun@ouc.edu.cn

O241.6

A

1672-5174(2015)12-125-06

10.16441/j.cnki.hdxb.20140030