數(shù)據(jù)挖掘技術(shù)在控制器局域網(wǎng)總線中的應(yīng)用研究

程文靜 臧麗萍

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

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

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

1.1 CAN總線

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

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

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

2實(shí)驗(yàn)

2.1 實(shí)驗(yàn)原理

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

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

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

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

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

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

2.3 實(shí)驗(yàn)步驟

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

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

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

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

2.4 實(shí)驗(yàn)結(jié)果

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

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

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

3結(jié)論

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

[參考文獻(xiàn)]

[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.