分類算法在手機(jī)取證中的應(yīng)用

肖程望，盧軍，余力耕

（武漢郵電科學(xué)研究院湖北武漢430074）

分類算法在手機(jī)取證中的應(yīng)用

肖程望，盧軍，余力耕

（武漢郵電科學(xué)研究院湖北武漢430074）

在當(dāng)今社會(huì)，手機(jī)犯罪越來(lái)越引起人們的重視，對(duì)研究人員來(lái)說(shuō)需要馬上研究相應(yīng)的對(duì)策加以應(yīng)對(duì)，智能手機(jī)的使用率越來(lái)越高也促使了手機(jī)取證技術(shù)的研究發(fā)展。同時(shí)采用Android系統(tǒng)的智能手機(jī)越來(lái)越多，針對(duì)Android系統(tǒng)手機(jī)取證的電子證據(jù)進(jìn)行相應(yīng)的數(shù)據(jù)分析，能更方便和直觀的發(fā)現(xiàn)手機(jī)信息中的重點(diǎn)與需要關(guān)注的目標(biāo)對(duì)象。在本文中應(yīng)用了樸素貝葉斯分類算法對(duì)數(shù)據(jù)中各聯(lián)系人進(jìn)行分類，而樸素貝葉斯分類算法的條件獨(dú)立性假設(shè)是非?？量痰?，很難在正常情況下滿足，本文中提出了一種基于變異系數(shù)法的加權(quán)樸素貝葉斯分類模型，克服這個(gè)問(wèn)題關(guān)鍵在于利用各項(xiàng)指標(biāo)間所包含的信息的差異，通過(guò)計(jì)算得到指標(biāo)的權(quán)重。有效地提高了樸素貝葉斯算法的分類性能，并且也繼承了貝葉斯分類算法的簡(jiǎn)單性，本文首先對(duì)算法原理進(jìn)行了分析與證明，然后描述了相應(yīng)的算法，在最后給出了基于變異系數(shù)法的屬性權(quán)值求解方法。

手機(jī)取證；取證方法；分類算法；樸素貝葉斯；變異系數(shù)

手機(jī)等各類電子產(chǎn)品中的電子證據(jù)，包括：短信、通訊錄、通話記錄和瀏覽記錄等逐漸成為新的訴訟證據(jù)之一，例如通過(guò)短信和通話記錄可以了解嫌疑人與外界的聯(lián)系，查看嫌疑人的手機(jī)GPS記錄來(lái)確定嫌疑人的活動(dòng)軌跡，而且QQ聊天記錄、郵件、上網(wǎng)記錄等都有很大的可能記錄著犯罪份子的犯罪行為[1]。手機(jī)的取證對(duì)于一個(gè)案件的偵破有著十分重大的意義，手機(jī)取證這一概念也隨之提出。

同時(shí)，最近三年中使用Android系統(tǒng)的手機(jī)所占市場(chǎng)份額正在快速上升，通過(guò)市場(chǎng)調(diào)查機(jī)構(gòu)報(bào)告顯示，在全球手機(jī)智能操作系統(tǒng)中所占份額最高的是Android，達(dá)到了72.1%，IOS排第二，占據(jù)了24.4%的份額，剩下的就是WP等等其他操作系統(tǒng)了。Android操作系統(tǒng)已經(jīng)成為當(dāng)今全球第一大操作系統(tǒng)，并且其增長(zhǎng)沒(méi)有任何衰減的趨勢(shì)[2]。大量利用手機(jī)進(jìn)行誹謗、詐騙等的犯罪活動(dòng)也在最近兩發(fā)頻頻發(fā)生，這與Android系統(tǒng)手機(jī)的迅猛發(fā)展不無(wú)關(guān)系。面對(duì)這種情況，對(duì)智能手機(jī)，包括使用Android系統(tǒng)的，進(jìn)行取證技術(shù)與分析方面的相關(guān)研究必須要盡快發(fā)展起來(lái)。

對(duì)提取數(shù)據(jù)的分析與分類也顯得更加的重要，本文提出了一種貝葉斯分類優(yōu)化算法，基于變異系數(shù)，介紹了算法詳情、原理與相應(yīng)的實(shí)現(xiàn)步驟。

1 取證信息分析

手機(jī)取證是一個(gè)對(duì)目標(biāo)手機(jī)中的與案件有關(guān)的數(shù)據(jù)進(jìn)行提取的過(guò)程。通過(guò)一些技術(shù)分析，確保原始手機(jī)未被損壞、篡改，并且收集的數(shù)據(jù)不可被修改，并且最終獲得具有法律效力的證據(jù)能夠幫助公安機(jī)關(guān)人員破案[3]。

重要證據(jù)源主要保存在Android系統(tǒng)手機(jī)中的手機(jī)內(nèi)存和sim卡中。提取出的信息大致有聯(lián)系人、短信息、通話記錄、瀏覽歷史記錄、多媒體信息、GPS信息、目標(biāo)手機(jī)上的app內(nèi)信息等[4]，具體如圖1所示。

2 手機(jī)取證分析

通過(guò)分析從數(shù)據(jù)庫(kù)中提取出的位置信息和時(shí)間，可以得知手機(jī)使用者的行為與活動(dòng)規(guī)律。通過(guò)分析通訊錄與短信數(shù)據(jù)庫(kù)中的信息，可以分析出使用者與某個(gè)人或某幾人聯(lián)系比較密切[5]。同時(shí)，通過(guò)查看瀏覽器歷史記，可以看到使用者的愛好與興趣。

同時(shí)在分析和監(jiān)控團(tuán)伙的各個(gè)手機(jī)時(shí)，使用基于Apriori算法的信息歸納總結(jié)，通過(guò)分析提取出的通訊錄和短信數(shù)據(jù)來(lái)分析出團(tuán)伙中的主要人物或關(guān)鍵人物。各個(gè)手機(jī)使用者之間的關(guān)系和它們之間的相互影響能夠很快的求出。在經(jīng)過(guò)了這么多年的研究后，只是把數(shù)據(jù)從手機(jī)中取出并不是一個(gè)十分困難的事情，現(xiàn)在主要是要對(duì)取出數(shù)據(jù)進(jìn)行分析和歸類。在眾多分類方法和理論中，樸素貝葉斯（na?ve Bayes，NB）由于精確度高、計(jì)算高效、算法不復(fù)雜并且計(jì)算原理簡(jiǎn)單易懂，而且具有堅(jiān)實(shí)的理論基礎(chǔ)，使得它在不同領(lǐng)域得到了廣泛應(yīng)用[5]。然而樸素貝葉斯分類有一個(gè)前提就是：屬性值之間是相互獨(dú)立的在給定分類特征條件下。通常情況下，這種基于獨(dú)立性的假設(shè)是很難滿足的。樸素的貝葉斯分類最大的缺陷是它無(wú)法處理特征符合所產(chǎn)生的變化（即前面提到過(guò)的實(shí)際上難以滿足的相互獨(dú)立）[6]。

本文就是在提取出數(shù)據(jù)的基礎(chǔ)上，利用樸素貝葉斯算法對(duì)信息進(jìn)行分類，并針對(duì)樸素貝葉斯算法中的不足之處進(jìn)行了優(yōu)化與研究。引入了變異系數(shù)來(lái)對(duì)不同特征的屬性進(jìn)行權(quán)重分析，以獲得更加客觀和精確的分類結(jié)果。

表1 提取信息表

3 算法分析

3.1 基本介紹

數(shù)據(jù)分類主要分為兩個(gè)階段：學(xué)習(xí)階段（構(gòu)造分類模型）、分類階段（使用模型預(yù)測(cè)給定數(shù)據(jù)的類標(biāo)號(hào)）。而其中的的關(guān)鍵是構(gòu)造分類器。其中樸素貝葉斯分類模型（NBC）已被廣泛使用，主要是因?yàn)樗兄鴪?jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率[7]。樸素貝葉斯模型有以下幾大優(yōu)點(diǎn)：所需參數(shù)少、算法也比較簡(jiǎn)單、缺失數(shù)據(jù)不太敏感。

同時(shí)還有一種貝葉斯分類器也有很多人在進(jìn)行研究，那就是貝葉斯網(wǎng)絡(luò)（BayesNet），它是一個(gè)有向的無(wú)環(huán)圖，上面帶有概率注釋，并且沒(méi)一個(gè)節(jié)點(diǎn)表示了一個(gè)隨機(jī)變量，并且可以在其上進(jìn)行學(xué)習(xí)[8]。而經(jīng)過(guò)研究學(xué)習(xí)后發(fā)現(xiàn)這會(huì)增加貝葉斯算法的復(fù)雜性，這主要是因?yàn)樘卣髦抵g的相互依賴。因此，當(dāng)應(yīng)用于實(shí)踐，它往往需要被簡(jiǎn)化。這就給我們提出了一個(gè)問(wèn)題：如何來(lái)提高其分類性能而又不會(huì)增加計(jì)算的復(fù)雜性呢。閱讀各種文獻(xiàn)資料后，發(fā)現(xiàn)了有基于信息增益和利用爬山算法等方法、還有提出了采用粗糙集技術(shù)來(lái)確定屬性權(quán)值的方法[9]。然而經(jīng)過(guò)實(shí)驗(yàn)后，我們發(fā)現(xiàn)在上述方法中雖然有一定的提高，但是在分析手機(jī)取證提取出的數(shù)據(jù)時(shí)改進(jìn)的效果并不是十分理想。

變異系數(shù)法（Coefficient of variation method）是一種客觀賦權(quán)的方法，在很多場(chǎng)合也有利用，它是直接利用各個(gè)特征項(xiàng)所包含的信息大小，來(lái)決定各個(gè)特征項(xiàng)的權(quán)重值[10]。這主要是因?yàn)樵谠u(píng)價(jià)一類事物時(shí)，相互間差別越大的特征項(xiàng)越能表達(dá)這些事物的不同之處，更能反映相互之間的差距。因此本文利用變異系數(shù)對(duì)貝葉斯分類模型進(jìn)行了優(yōu)化，并對(duì)算法的原理進(jìn)行了說(shuō)明。

3.2 加權(quán)樸素貝葉斯分類模型

3.2.1 樸素貝葉斯分類

P（A|B）表示了在B發(fā)生的前提下，A發(fā)生的概率。這是個(gè)條件概率。然而在實(shí)際生活中，我們可以很輕易的知道P（A|B），但是P（B|A）卻很難知道，而貝葉斯定律就是幫助我們獲得P（B|A）的。首先給出貝葉斯定理[11]。

貝葉斯分類在所有分類算法中是十分簡(jiǎn)單的主要有以下幾步組成[12]：

1）設(shè)一個(gè)待分類項(xiàng)為X=[a1，a2，…，an]表示，分別描述在n個(gè)屬性A1，A2，…，An上的值；

2）假定有m個(gè)類，用C=[b1，b2，…，bn]表示；

3）計(jì) 算 出P（C1|x），P（C2|x），P（C3|x），…，P（Cn|x）；

4）如果P（Ck|x）是所有概率中最大的，那么這個(gè)待分類項(xiàng)就屬于Ck類。其中先驗(yàn)概率p(x1|Ci)，p(x2|Ci)，…，p(xn|Ci)可以從之前收集的數(shù)據(jù)中求得。

3.2.2 加權(quán)樸素貝葉斯分類

樸素貝葉斯模型（NBC）認(rèn)為所有條件都是互不影響并且對(duì)分類結(jié)果的權(quán)重都是1，然而并非如此，在同一個(gè)問(wèn)題中時(shí)，據(jù)常理所知，有的條件可能更重要些，而有的對(duì)結(jié)果可能影響較小。為了解決這個(gè)問(wèn)題，需要給不容的條件附上不同的權(quán)重值，則可以得到經(jīng)過(guò)了加權(quán)的樸素貝葉斯模型為：

其中，wk代表了屬性Ai的權(quán)重值。對(duì)應(yīng)的屬性的權(quán)值越大，那么它對(duì)分類結(jié)果的影響就越大。而如何確定不同屬性的權(quán)值，那又產(chǎn)生了一個(gè)新的問(wèn)題了。

3.3 變異系數(shù)

將各屬性視為隨機(jī)變量Mi，任一隨機(jī)變量Mi的標(biāo)準(zhǔn)差與平均數(shù)的比值稱為其對(duì)應(yīng)的變異系數(shù)，記為CVi。把所有的屬性對(duì)應(yīng)的變異系數(shù)相加后，對(duì)各個(gè)變異系數(shù)進(jìn)行歸一化處理后就可以得到對(duì)應(yīng)的權(quán)重了[13]。在評(píng)價(jià)手機(jī)聯(lián)系人的親密度關(guān)系時(shí)，有多種評(píng)價(jià)標(biāo)準(zhǔn)，例如：通話次數(shù)、通話時(shí)長(zhǎng)、短信次數(shù)、短信中關(guān)鍵字詞的出現(xiàn)頻率、郵件聯(lián)系次數(shù)等等。而由于各個(gè)指標(biāo)的量綱不同，自然是不能直接拿來(lái)比較的，還需要進(jìn)行歸一化和利用到變異系數(shù)來(lái)進(jìn)行處理，然后才能得到各個(gè)指標(biāo)的權(quán)重系數(shù)。

下面來(lái)進(jìn)行一個(gè)實(shí)例分析：用變異系數(shù)法去計(jì)算手機(jī)中各個(gè)指標(biāo)對(duì)親密度關(guān)系的權(quán)重大小。下列數(shù)據(jù)是調(diào)查了10余部手機(jī)中的所有相關(guān)數(shù)據(jù)，計(jì)算出各個(gè)對(duì)應(yīng)指標(biāo)的變異系數(shù)，這些指標(biāo)所對(duì)應(yīng)的權(quán)重系數(shù)反應(yīng)出了對(duì)親密度分類結(jié)果的影響大小，并作為確定各項(xiàng)指標(biāo)權(quán)重的依據(jù)。具體計(jì)算數(shù)據(jù)見表2：

表2 各指標(biāo)的權(quán)重

計(jì)算過(guò)程如下：

1）分別計(jì)算這些數(shù)據(jù)的平均數(shù)和標(biāo)準(zhǔn)差，這主要依靠之前提取的各個(gè)數(shù)據(jù)；

2）計(jì)算出變異系數(shù)（均值與標(biāo)準(zhǔn)差的比值）；

3）將每一個(gè)指標(biāo)所對(duì)應(yīng)的變異系數(shù)相加求出總和；

4）計(jì)算出每一個(gè)指標(biāo)所對(duì)應(yīng)的權(quán)重。

上面求出的權(quán)重系數(shù)表明了不同指標(biāo)對(duì)最后分類結(jié)果的影響大小，所以是可作權(quán)重系數(shù)應(yīng)用在加權(quán)貝葉斯分類模型中的。

3.4 算法實(shí)現(xiàn)

基于變異系數(shù)的加權(quán)樸素貝葉斯分類算法的實(shí)現(xiàn)關(guān)鍵在于求解各條件屬性的變異系數(shù)，并確定各條件屬性的權(quán)重值，具體算法如下：

1）提取數(shù)據(jù)處理：將提取出的數(shù)據(jù)和預(yù)先準(zhǔn)備的數(shù)據(jù)進(jìn)行相應(yīng)的處理，例如一些缺失數(shù)據(jù)的補(bǔ)充和數(shù)據(jù)之間的離散處理；

2）判斷：如果是分類任務(wù)，則到（6），如果是訓(xùn)練任務(wù)則到（3）；

3）概率表學(xué)習(xí)（構(gòu)造分類模型）：按照預(yù)先準(zhǔn)備的練習(xí)數(shù)據(jù)，針對(duì)每一個(gè)屬性Ai的屬性值xik，每個(gè)分類的類別Ci、以及各個(gè)Ci的出現(xiàn)概率，計(jì)算在Ci發(fā)生的前提下，aik的出現(xiàn)概率p(xki|Ci)[14]；

4）變異系數(shù)計(jì)算：計(jì)算出變異系數(shù)=對(duì)應(yīng)的均值/對(duì)應(yīng)的標(biāo)準(zhǔn)差，然后經(jīng)過(guò)歸一化處理后得出對(duì)應(yīng)的權(quán)重系數(shù)；

5）生成經(jīng)過(guò)了加權(quán)的樸素貝葉斯分類器，并且吧加權(quán)樸素貝葉斯概率表已經(jīng)各個(gè)對(duì)應(yīng)屬性權(quán)值表保存下來(lái)以供分類使用；

6）分類：利用保存了的概率表以及屬性權(quán)值列表，并且使用之前生成的樸素貝葉斯分類器，得出分類結(jié)果。

4 實(shí)驗(yàn)測(cè)試

在提取了10部手機(jī)內(nèi)的信息進(jìn)行了加權(quán)貝葉斯分類算法的概率表和變異系數(shù)的學(xué)習(xí)后，對(duì)新取得的手機(jī)內(nèi)信息進(jìn)行分類后可知道手機(jī)內(nèi)聯(lián)系人與此人的親密度關(guān)系。下表列出了集合名稱、各個(gè)屬性名稱以及分類結(jié)果。

圖1 加權(quán)貝葉斯分類結(jié)果

同時(shí)，利用樸素貝葉斯算法對(duì)相同數(shù)據(jù)進(jìn)行處理后，可以發(fā)現(xiàn)加上由變異系數(shù)得出的權(quán)重之后，能更準(zhǔn)確吧手機(jī)使用者內(nèi)的聯(lián)系人進(jìn)行親密度分類。原因在于權(quán)重計(jì)算考慮到了特征項(xiàng)在類間的分布，類間的分布的越不均勻，對(duì)類的貢獻(xiàn)能力越大，同時(shí)對(duì)分類結(jié)果的影響也就越大，因此它的權(quán)重就越大。

5 結(jié) 論

現(xiàn)今，有很多犯罪分子通過(guò)手機(jī)進(jìn)行交流、預(yù)謀犯罪等等行為，所以對(duì)手機(jī)提取數(shù)據(jù)的分析與提取數(shù)據(jù)的分類也顯得更加的重要，本文提出了一種基于變異系數(shù)的貝葉斯分類算法，并給出了相應(yīng)的算法實(shí)現(xiàn)步驟。并提取了某部手機(jī)中的測(cè)試數(shù)據(jù)，通過(guò)實(shí)驗(yàn)比較了樸素貝葉斯分類與基于變異系數(shù)的貝葉斯分類的效果，實(shí)驗(yàn)表明本算法在分類性能上有一定的優(yōu)越性。

樸素貝葉斯分類的分類能力受到了特征項(xiàng)間獨(dú)立性這一假設(shè)的很大影響。本文提出的這樣一種新的分類方法，引入了權(quán)重的計(jì)算來(lái)克服這一問(wèn)題，生成了更加精確并且有效的條件屬性權(quán)重，考慮到在類內(nèi)分布越均勻、類間分布越不均勻的特征項(xiàng)，權(quán)重越大，對(duì)分類結(jié)果的影響越大，對(duì)獲得更精確地分類結(jié)果十分有利[15]。同時(shí)，可以利用本文提出的方法和更多別的方法進(jìn)行組合來(lái)繼續(xù)優(yōu)化本算法。同時(shí)可以考慮新的變異系數(shù)的度量方法以便更進(jìn)一步的提高分類性能，以及是否還要考慮各屬性的其他特征以及各屬性間的相關(guān)性是下一步的研究方向。

[1]杜江，褚?guī)?智能手機(jī)取證研究[J].電腦知識(shí)與技術(shù)，2011（9）:2120-2121.

[2]Y Yao，Y Zhao.Attribute reduction in decisiontheoretic rough set models[J].Information Sciences，2013.

[3]LS Huang，A Moshchuk，HJ Wang.Clickjacking:attacks and defenses[J].Usenix Conference on Security Symposium，2012.

[4]賈嫻，劉培玉，公偉.基于改進(jìn)屬性加權(quán)的樸素貝葉斯入侵取證研究[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（7）:81-84.

[5]劉磊，陳興蜀，尹學(xué)淵，等.基于特征加權(quán)樸素貝葉斯分類算法的網(wǎng)絡(luò)用戶識(shí)別[J].計(jì)算機(jī)應(yīng)用，2011，31（12）:3268-3270.

[6]王行甫，杜婷.基于屬性選擇的改進(jìn)加權(quán)樸素貝葉斯分類算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2015，24（8）:149-154.

[7]寧榮.基于粗糙集貝葉斯分類的供應(yīng)商評(píng)價(jià)研究[J].物流科技，2013，36（5）:124-126.

[8]徐光美，劉宏哲等.基于特征加權(quán)的多關(guān)系樸素貝葉斯分類模型[J].計(jì)算機(jī)科學(xué)，2014，41（10）:283-285.

[9]梁天超，荊曉遠(yuǎn).基于加權(quán)RFE-Bayes方法的軟件缺陷預(yù)測(cè)模型[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015（10）:131-134.

[10]饒麗麗，劉雄輝，張東站.基于特征相關(guān)的改進(jìn)加權(quán)樸素貝葉斯分類算法[J].廈門大學(xué)學(xué)報(bào):自然科學(xué)版，2012，51（4）:682-685.

[11]李翔，程玉勝.基于粗糙集理論的貝葉斯網(wǎng)絡(luò)分類算法[J].安慶師范學(xué)院學(xué)報(bào):自然科學(xué)版，2014（1）:36-40.

[12]夏燕，徐娜，舒健等.加權(quán)樸素貝葉斯模型在高校學(xué)科評(píng)價(jià)中的應(yīng)用[J].微型電腦應(yīng)用，2016，32（1）:15-18.

[13]楊敏.基于貝葉斯方法的空間數(shù)據(jù)分析及應(yīng)用[D].西安：西安工程大學(xué)，2012.

[14]王小麗，遠(yuǎn)俊紅.基于加權(quán)樸素貝葉斯分類法的成績(jī)預(yù)測(cè)模型[J].電子技術(shù)與軟件工程，2013（19）:225-226.

[15]劉牛.基于屬性加權(quán)的樸素貝葉斯分類算法改進(jìn)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2011（6）：72-74.

Application and optimization of algorithm in mobile phone forensics

XIAO Cheng?wang，LU Jun，YU Li?geng
（Wuhan Research Institute of Posts and Telecommunications，Wuhan430074，China）

In modern society，mobile phone crime phenomenon as a high?technology crime，need to study and the corresponding counter?measures to deal with，the popularity of intelligent mobile phone make the mobile phone on evidence research to a new height，wherein more and more intelligent mobile phone use Android system.this paper mainly introduces the Android system mobile phone forensics elec?tronic sources of evidence and forensic analysis method，finally puts forward using Android system should solve the problem of mobile phone forensics.Naive Bayes is based on an assumption of conditional independence and the assumption can scarcely be satisfied.A weighted naive Bayes classification algorithm based on Coefficient of Variation is proposed.By computing Coefficient of Variation between condition attributes and decision attribute，different condition attributes are weighted differently.With a new method offered first to solve the weights of attributes on the basis of Coefficient of Variation discusses the operation principle of the algorithm，as well as its implementation.

mobile phone forensics；method of forensics；classification algorithm；Na?ve Bayes；coefficient of variation

TP301

A

1674-6236（2017）22-0049-05

2016-09-13稿件編號(hào)：201609138

肖程望（1992—），男，湖南岳陽(yáng)人，碩士。研究方向：通信與信息系統(tǒng)。