程文靜 臧麗萍

摘要：提出了數(shù)據(jù)挖掘技術在汽車控制器局域網(wǎng)(CAN)總線通信數(shù)據(jù)中的應用。汽車中的各種電子控制系統(tǒng)通過CAN總線相互連接通信，其中產(chǎn)生的大量報文被存儲在日志文件中。首先對CAN總線日志文件的中大量通信數(shù)據(jù)做預處理，再擴展使用關聯(lián)分析、分類及聚類分析等方法對處理過的數(shù)據(jù)進行挖掘，從而找到各條報文之間及報文內(nèi)部各位或字節(jié)之間可能存在的新規(guī)律或者關系，為進一步研究CAN總線系統(tǒng)連接的各個控制系統(tǒng)之間的通信提供了幫助。

關鍵詞：控制器局域網(wǎng)總線；報文；數(shù)據(jù)挖掘Application of Data mining in Controller Area Network System

Cheng Wen-JingLiu Yan-Mei(Department of Computer Science and Application,

Zhengzhou Institute of Aeronautical Industry Management,Zhengzhou 450000,China)

Abstract:This report presents application of data mining in the controller area networks(CAN) bus of real automotive systems. A set of analysis tools are applied in the experiment. The association rules are utilized to describe the relationship between different message IDs, classification method to find important bits or bytes from content of each message and clustering method to check whether these bits or bytes are important or not. Because of the lack of domain experts in the CAN bus field, the results do not refer to semantic meaning about message IDs and messages from different devices, but they only focus on interesting relationship or rules between different messages.

Key words:CAN bus; message;data mining;association rules;classification; clustering汽車包含一系列電子控制單元，它們通過控制器局域網(wǎng)（CAN）總線系統(tǒng)彼此相連接并通信，通信數(shù)據(jù)包則可以記錄在相應的日志文件中。本實驗使用的源數(shù)據(jù)為模擬汽車CAN總線系統(tǒng)中獲取的四個子網(wǎng)日志文件。為了研究這些通信，不只可以用傳統(tǒng)的統(tǒng)計學方法來分析這些文件，還可以考慮用一些經(jīng)典的數(shù)據(jù)挖掘方法來尋找重要的新規(guī)律或者特征。目前，數(shù)據(jù)挖掘工作大概被分為兩類：一是預測性的工作，另一種是描述性的工作。在本文中，涉及的是后者。描述性的工作的目的在于發(fā)現(xiàn)潛在的令人感興趣的模式，比如關聯(lián)度,趨勢,聚類等等。為了實現(xiàn)描述性的功能，本實驗使用了關聯(lián)規(guī)則來發(fā)現(xiàn)不同報文標示符（ID）之間的關系，分類方法用來尋找每條報文中重要的位或字節(jié)，聚類方法用來檢測找到的位或字節(jié)重要的準確度。鑒于實驗中缺乏CAN總線領域的專業(yè)知識，實驗結(jié)果不討論報文和其ID的實際含義，而只關注報文之間及報文內(nèi)部的位（字節(jié)）之間的關系。本文以舒適性（Comfort）子網(wǎng)中的數(shù)據(jù)為例說明我們的實驗。

1CAN總線及數(shù)據(jù)挖掘的基本介紹

1.1 CAN總線

CAN是控制器局域網(wǎng)絡(Controller Area Network)的簡稱，是國際上應用最廣泛的現(xiàn)場總線之一[1]。在北美和西歐，CAN總線協(xié)議已經(jīng)成為汽車計算機控制系統(tǒng)和嵌入式工業(yè)控制局域網(wǎng)的標準總線。在協(xié)議的各個版本中，報文通信無論采用哪種幀格式，都有四種不同的幀類型：數(shù)據(jù)幀、遠程幀、錯誤幀和過載幀。在此研究的是CAN總線日志文件中記錄的數(shù)據(jù)幀，它由數(shù)據(jù)域和其他的6個控制位組成。由于實驗研究的是對數(shù)據(jù)域的數(shù)據(jù)挖掘，因此在研究過程中，報文的結(jié)構(gòu)被精簡為：報文標識符(ID)和報文內(nèi)容數(shù)據(jù)(Data）。

1.2 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘一般是指從大量的數(shù)據(jù)中通過算法搜索隱藏于其中信息的過程。數(shù)據(jù)挖掘的任務主要有關聯(lián)分析、聚類分析、分類分析等[2]。關聯(lián)分析是尋找數(shù)據(jù)中頻繁一起出現(xiàn)的項集模式。在本實驗中，研究的是哪些報文ID經(jīng)常同時出現(xiàn)。分類是首先從數(shù)據(jù)中選出已經(jīng)分好類的訓練集，在該訓練集上運用數(shù)據(jù)挖掘分類的技術，建立分類模型，對于沒有分類的數(shù)據(jù)進行分類。在本實驗中，報文ID被作為類別標志，報文數(shù)據(jù)項的8個字節(jié)或者64個位被作為屬性進行分類。事實上，在此并不訓練分類模型來做預測，而只是借用信息增益（Information Gain）的概念在建造決定樹分類模型的過程中來選擇最優(yōu)的屬性來和其他屬性做區(qū)分。而聚類分析是根據(jù)“各聚集內(nèi)部數(shù)據(jù)對象間的相似度最大化，而各聚集對象間相似度最小化”的基本聚類分析原則，將聚類分析的數(shù)據(jù)對象劃分為若干組，因此一個組中數(shù)據(jù)對象間的相似度要比不同組數(shù)據(jù)對象間的相似度要大[3]。

2實驗

2.1 實驗原理

鑒于CAN總線日志文件中的原始數(shù)據(jù)包含了大量其他信息，所以為了方便分析和數(shù)據(jù)挖掘，首先要對文件數(shù)據(jù)進行預處理，也就是從中抽取出報文ID和報文內(nèi)容。圖1顯示了從原始數(shù)據(jù)中抽取出兩列可測量數(shù)據(jù)的基本思想：

接下來尋找數(shù)據(jù)中有用的規(guī)律。首先考慮不同報文ID之間可能存在的關聯(lián)規(guī)則。受經(jīng)典的關聯(lián)分析方法啟發(fā)，可以用“超市購物籃”問題來描述本實驗中的問題，即把數(shù)據(jù)集分別放入不同的“籃子”中，進一步說，把報文ID看做“單品”放入不同的“購物籃”，每一個購物籃就是一組。那么不同ID之間的關系分析就像超市購物籃中不同單品之間關系的分析了。對數(shù)據(jù)的分組在此采用兩種形式：按照固定的報文ID號分組或者固定的時間間隔分組。針對前者，把出現(xiàn)頻率最高的ID號作為分割線，每兩個該ID之間出現(xiàn)的報文ID被分在一組；針對后者，每0.1秒之內(nèi)出現(xiàn)的所有報文ID被分在一組。

下一步工作是尋找報文數(shù)據(jù)中重要的位或者字節(jié)。如果可以根據(jù)一個或者一些位（字節(jié)）的不同值來區(qū)分某部分或全部報文ID，就認為這些位（字節(jié)）是重要的。傳統(tǒng)統(tǒng)計學方法可以很容易地為一個報文ID找到重要的位或字節(jié)。但是對日志文件中大量的報文ID卻并不適用。為此采用決策樹分類的信息增益方法來實現(xiàn)這個想法[4]?！靶畔⒃鲆妗笔怯脕砗饬恳粋€屬性區(qū)分以上數(shù)據(jù)樣本的能力。每個位（字節(jié)）被作為一個屬性，其對應的報文ID號為最終的類別。

最后進行聚類分析的工作，目的是為了驗證上一步的結(jié)果。一方面根據(jù)已找到的重要的位（字節(jié)）把數(shù)據(jù)記錄分組，另一方面根據(jù)所有的位（字節(jié)）對數(shù)據(jù)記錄分組。鑒于總線方面專業(yè)知識的缺乏，單純的分析結(jié)果本身沒有意義，但是在此可以通過比較兩個結(jié)果集合的相似度來驗證重要位（字節(jié)）的準確度。

2.2 運行環(huán)境和工具

對數(shù)據(jù)預處理的工作由Java編寫程序?qū)崿F(xiàn)。然后選擇Spss Clementine[5]作為數(shù)據(jù)挖掘工具，對處理過的數(shù)據(jù)進行分析。Clementine是一個數(shù)據(jù)挖掘工具平臺，它有著更好的圖形用戶界面，能夠高效地進行數(shù)據(jù)統(tǒng)計和分析。

2.3 實驗步驟

⑴數(shù)據(jù)預處理：預處理的目的是把原始日志文件中雜亂的數(shù)據(jù)轉(zhuǎn)化為可處理的數(shù)據(jù)。如上文所述，抽取出每條報文的ID號和8字節(jié)的數(shù)據(jù)內(nèi)容，把8字節(jié)再轉(zhuǎn)化位64位，選擇出現(xiàn)頻率最高的ID號531作為標記把整個數(shù)據(jù)集分組以及按時間間隔0.1秒把數(shù)據(jù)集分組。

⑵數(shù)據(jù)挖掘：針對上一步中根據(jù)兩種方式得到的數(shù)據(jù)集分組進行關聯(lián)規(guī)則分析。在Clementine上運用apriori算法，得到兩組結(jié)果。圖2顯示了按0.1秒時間間隔分組的實驗結(jié)果。

接下來根據(jù)報文記錄中的8個字節(jié)和64個位分別建立決策樹模型，通過尋找能把報文ID進行最細化分類的最小屬性集合，得到的位（字節(jié)）即為重要的位（字節(jié)）。圖3展示了尋找重要字節(jié)的實驗結(jié)果。

最后進行聚類分析。隨著日志文件的增大，報文ID的數(shù)量也隨之增加，因此在建立決策樹模型的過程中最終的類別標記也會隨之增加，就會需要越來越多的的位或者字節(jié)來區(qū)分報文內(nèi)容，最終會覆蓋所有的位或者字節(jié)。在這樣的情況下聚類分析就沒有意義了。因此在本實驗中只把報文記錄分入五個聚類。圖4展示了根據(jù)重要字節(jié)聚類以及根據(jù)所有字節(jié)聚類分析的比較。

2.4 實驗結(jié)果

對關聯(lián)分析，通常用支持度和信任度來描述結(jié)果。本實驗只查看了支持度高于10%和信任度高于50%的結(jié)果，一共有43條關聯(lián)記錄。如結(jié)果記錄35B->531，470，373，3E1表示在所有的分組中，這五個ID同時出現(xiàn)的概率超過10%，而當ID35B出現(xiàn)的時候，531、470、373和3E1同時出現(xiàn)的概率高于50%。用戶可以根據(jù)自己的需求得到不同支持度和信任度的報文ID。

對分類分析，根據(jù)模型計算，報文中的第1、2、4、5、6字節(jié)和第1、2、3、4、5、6、7、8、11、16、17、18、19、20、25、42位比較重要。

對聚類分析，按照上一步驟選擇的五個重要字節(jié)一共可以把3386條記錄分入五個聚類；按照所有的字節(jié)一共可以把3555條記錄分入五個聚類，所以得到按字節(jié)聚類的準確率為3386/3555=95.25%。通過類似的分析可以得到按位聚類的準確率為1158/3495=33.13%。此結(jié)果說明，本實驗通過建模分析選擇的重要字節(jié)準確性較高，而選擇的重要位意義不大。

3結(jié)論

本文展示了如何運用數(shù)據(jù)挖掘技術從原始的CAN總線日志文件中尋找規(guī)律的過程。首先通過編寫預處理功能來轉(zhuǎn)化數(shù)據(jù)格式，然后把一些經(jīng)典的數(shù)據(jù)挖掘算法擴展到實驗中，運用關聯(lián)規(guī)則、分類分析和聚類分析找到不同的報文ID之間的關系以及不同的位（字節(jié)）對報文的重要性影響，最后對實驗結(jié)果根據(jù)不同需求做出總結(jié)評估。對今后的工作可以有如下兩方面的改進：一是使用更復雜的數(shù)據(jù)挖掘方法，比如對動態(tài)的數(shù)據(jù)集進行實時分析或者根據(jù)時間序列尋找文件中的序列模式；二是可以在了解總線專業(yè)知識的基礎上對實驗結(jié)果做出具有實際意義的解釋。

[參考文獻]

[1]Robert Bosch GmbH.CAN Specification Version 2.0[Z].1991. http://download.csdn.net/download/lc841004/920494.

[2]J.Han,M.Kamber.Data Mining: Concepts and Techniques[M]. San Francisco:Morgan Kaufmann Publishers,2001:20-25.

[3]I.H.Witten,E.Frank.Data Mining: Practical Machine Learning Tools and Technique(2nd Edition.)[M].San Francisco:Morgan Kaufmann Publishers,2007:112-120.

[4]P.N.Tan,M.Steinbach,V.Kumar.數(shù)據(jù)挖掘?qū)д揫M].北京：人民郵電出版社,2006：32-39.P.N.Tan,M.Steinbach,V.Kumar.Introduction to Data Mining[M].Beijing:Posts&Telecom Press,2006:32-39.

[5]The Predictive Analytics Company. Spss Clementine 11.1 for Windows[Z].2007.http://download.csdn.net/download/open_567/1239185.