基于混沌關(guān)聯(lián)維與決策樹(shù)的運(yùn)動(dòng)數(shù)據(jù)分類研究

鄭 貞，鄒俊穎

(1. 成都中醫(yī)藥大學(xué)體育學(xué)院，四川 成都 610101；2. 四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610101)

1 引言

通過(guò)對(duì)運(yùn)動(dòng)數(shù)據(jù)挖掘，可以得到其中包含的特征信息，這對(duì)于運(yùn)動(dòng)分析與管理有著重要意義[1]。運(yùn)動(dòng)數(shù)據(jù)通常具有明顯的波動(dòng)性，同時(shí)也具有某種程度上的關(guān)聯(lián)性，隨著移動(dòng)互聯(lián)與大數(shù)據(jù)的發(fā)展，運(yùn)動(dòng)數(shù)據(jù)變得混沌、龐大且不平衡[2]，使得數(shù)據(jù)分類變得愈加困難。為了能夠更好的實(shí)現(xiàn)運(yùn)動(dòng)數(shù)據(jù)分類，增強(qiáng)運(yùn)動(dòng)數(shù)據(jù)的利用價(jià)值，相關(guān)領(lǐng)域的專家學(xué)者已經(jīng)取得了一些研究成果。文獻(xiàn)[3]首先針對(duì)數(shù)據(jù)邊緣做濾波處理，然后引入小波識(shí)別數(shù)據(jù)特征，最后根據(jù)RBF完成數(shù)據(jù)分類。該方法復(fù)雜度過(guò)高，不適用于大規(guī)模非規(guī)則運(yùn)動(dòng)數(shù)據(jù)的處理。文獻(xiàn)[4]針對(duì)波動(dòng)的運(yùn)動(dòng)數(shù)據(jù)，引入了關(guān)聯(lián)維積分算法，對(duì)于隨時(shí)間波動(dòng)的非規(guī)則數(shù)據(jù)具有較好的估測(cè)效果。文獻(xiàn)[5]針對(duì)運(yùn)動(dòng)數(shù)據(jù)引入圖模型，通過(guò)關(guān)聯(lián)維搜索數(shù)據(jù)特征，根據(jù)特征分布生成決策樹(shù)，從而完成數(shù)據(jù)分類。雖然該方法能夠較好的利用關(guān)聯(lián)信息，但是沒(méi)有考慮關(guān)聯(lián)維參數(shù)的影響，以及決策樹(shù)構(gòu)建的優(yōu)化。

由于不同數(shù)據(jù)間的分類方法通用性較差，加上運(yùn)動(dòng)數(shù)據(jù)獨(dú)有的一些特征，使得其它領(lǐng)域中的分類方法移植過(guò)來(lái)難以獲得理想的效果。目前的研究成果中，關(guān)聯(lián)維能夠較好的克服運(yùn)動(dòng)數(shù)據(jù)非規(guī)則和非確定性[6-7]，提高數(shù)據(jù)特征提取的準(zhǔn)確度，于是，本文也利用關(guān)聯(lián)維提取運(yùn)動(dòng)數(shù)據(jù)特征。同時(shí)，本文結(jié)合混沌時(shí)間序列，充分考慮了相空間的關(guān)鍵參數(shù)影響，并設(shè)計(jì)了關(guān)鍵參數(shù)最優(yōu)值的確定方法，根據(jù)相空間內(nèi)關(guān)聯(lián)相點(diǎn)對(duì)數(shù)量計(jì)算得到關(guān)聯(lián)積，實(shí)現(xiàn)運(yùn)動(dòng)數(shù)據(jù)特征提取。針對(duì)提取后的高維特征，考慮到解釋能力與多屬性組合，決定構(gòu)造多參決策樹(shù)?；趥鹘y(tǒng)決策樹(shù)在分裂次數(shù)與學(xué)習(xí)方面的性能問(wèn)題[8-9]，設(shè)計(jì)了基于信息增益與增益率評(píng)價(jià)的分裂規(guī)則，避免樹(shù)生長(zhǎng)出現(xiàn)偏向性，使決策樹(shù)生成更加純凈高效。利用剪枝策略降低決策樹(shù)的冗余度和復(fù)雜度，并采取輪廓相似性實(shí)現(xiàn)數(shù)據(jù)類型判斷。

2 混沌關(guān)聯(lián)維算法

由于采集過(guò)程存在多方面差異，運(yùn)動(dòng)數(shù)據(jù)一般具有多源、不規(guī)則，以及扭曲等特性?；谶\(yùn)動(dòng)數(shù)據(jù)所表現(xiàn)出的混沌性質(zhì)，可以將其在相空間進(jìn)行重構(gòu)，并通過(guò)關(guān)聯(lián)維來(lái)提取其特征。

在對(duì)運(yùn)動(dòng)數(shù)據(jù)采取重構(gòu)時(shí)，會(huì)構(gòu)造線性與非線性兩種序列。根據(jù)運(yùn)動(dòng)數(shù)據(jù)的特征，兩種序列分別代表時(shí)間與數(shù)據(jù)。假定時(shí)間序列表示為{y1，y2，…，yt}，將其與多維空間結(jié)合，可以對(duì)混沌時(shí)間進(jìn)行估計(jì)。于是，運(yùn)動(dòng)數(shù)據(jù)在相空間中的重構(gòu)表示如下

(1)

式中，m=t-(n-1)δ；m代表嵌入維度；δ代表混沌延時(shí)。這里m與δ是影響重構(gòu)性能的關(guān)鍵參數(shù)。

針對(duì)運(yùn)動(dòng)數(shù)據(jù)建立分布曲線。數(shù)據(jù)范圍內(nèi)，假定y(τ)位于分布曲線i上的概率是pi，y(τ+δ)表示y(τ)對(duì)應(yīng)的δ混沌延時(shí)，y(τ+δ)位于分布曲線j上的概率是pj。則根據(jù)y(τ)及其延遲y(τ+δ)可得聯(lián)合概率pij(δ)。由此，計(jì)算得到混沌時(shí)間互信息如下

(2)

雖然y(τ+δ)與y(τ)存在δ混沌延時(shí)，但是y(τ+δ)與y(τ)各自獨(dú)立，而且互信息M(δ)的值越小，說(shuō)明y(τ+δ)與y(τ)獨(dú)立程度越高。當(dāng)互信息M(δ)的值為零時(shí)，y(τ+δ)無(wú)法估算。此時(shí)，可以通過(guò)計(jì)算τ+δ時(shí)間的自相關(guān)程度來(lái)確定最優(yōu)δ。自相關(guān)程度的計(jì)算公式如下

(3)

Ym={ym，y(m+δ)，…，y(m+(n-1)δ)}

(4)

當(dāng)m取最小時(shí)，還能夠保證重構(gòu)滿足如下約束，則Y(m)可看成是Ym的虛假臨界點(diǎn)

(5)

式中，Th表示閾值。至此，利用虛假臨界點(diǎn)的條件約束，可以確定最優(yōu)m。結(jié)合最優(yōu)δ，便可以完成相空間的合理重構(gòu)。

在經(jīng)過(guò)重構(gòu)之后的相空間內(nèi)，如果yi與yj相距在d范圍以內(nèi)，則表示yi與yj存在關(guān)聯(lián)。除去數(shù)據(jù)yi，與yj相距在d以內(nèi)的數(shù)據(jù)集合表示為

(6)

(7)

由于I(d)也表示運(yùn)動(dòng)數(shù)據(jù)混沌特征，因此，通過(guò)求解I(d)實(shí)現(xiàn)了特征提取。

3 決策樹(shù)分類

在執(zhí)行第一步驟的過(guò)程時(shí)，利用屬性組合構(gòu)成評(píng)判規(guī)則

(8)

式中，k表示數(shù)據(jù)的屬性數(shù)量；Xi表示數(shù)據(jù)的第i個(gè)特征屬性；wi表示Xi的加權(quán)；TX表示門(mén)限。為增強(qiáng)葉子的純凈度，在屬性組合基礎(chǔ)上引入信息增益

G(Z|X)=Hs(Y)-E(Hs(Y|X))

(9)

G(Z|X)即為分裂過(guò)程信息增益，用來(lái)衡量屬性區(qū)分的訓(xùn)練性能。式中，E(Hs(Y|X))為計(jì)算Hs(Y|X)的期望；Hs(·)為香農(nóng)熵，計(jì)算公式表示為

(10)

當(dāng)G(Z|X)具有最大值時(shí)，分裂得到葉子分類的純凈度最高。但是在G(Z|X)取得最大值時(shí)，可能是某些原因引起的G(Z|X)假性升高，從而引發(fā)分裂的偏向性。為此，采用信息增益率評(píng)價(jià)來(lái)抑制G(Z|X)可能受到的干擾，其公式表示為

R(Z|X)=G(Z|X)/U(Y)

(11)

式中，U(Y)為葉子分布熵。葉子越多，U(Y)值越大，如果葉子增多使得數(shù)據(jù)平衡性變差，利用U(Y)的波動(dòng)就能夠調(diào)整傾斜，從而有效控制G(Z|X)免受干擾。

求解信息增益的過(guò)程中，熵期望E(Hs(Y|X))的計(jì)算表示為

E(Hs(Y|X))=W(X>Xi)Hs(Y|X>Xi)

+W(X

(12)

圖1 數(shù)據(jù)分布交叉區(qū)

圖1描述了數(shù)據(jù)分布情況，其中[Xi，Yi]是紅藍(lán)兩類數(shù)據(jù)交叉區(qū)。如果分裂點(diǎn)選擇Xi，那么有Hs(Y|X

E(Hs(Y|Xi))=W(X>Xi)Hs(X>Xi)

(13)

如果分裂點(diǎn)選擇Xj，則Hs(Y|X>Xj)=0，此時(shí)期望描述為

E(Hs(Y|Xj))=W(X

(14)

對(duì)于數(shù)據(jù)交叉區(qū)[Xi，Yj]，根據(jù)兩類數(shù)據(jù)的多少可判斷出E(Hs(Y|Xi))與E(Hs(Y|Xj))的大小，從而確定Xi與Xj哪個(gè)作為分裂點(diǎn)更合適。如果最終選擇Xi作為分裂點(diǎn)，則可將XXi的數(shù)據(jù)在決策樹(shù)中。如果最終選擇Xj作為分裂點(diǎn)，則可將X>Xj的所有數(shù)據(jù)刪除，只保留X

(15)

式中，關(guān)于faj、Qj和Pj參量的計(jì)算方式分別描述如下

(16)

(17)

(18)

4 仿真與結(jié)果分析

實(shí)驗(yàn)平臺(tái)JDK版本為JDK1.8.65，Python開(kāi)發(fā)環(huán)境為Eclipse，數(shù)據(jù)通過(guò)Python在網(wǎng)絡(luò)中爬取得到，總共包含18869條運(yùn)動(dòng)數(shù)據(jù)。利用WEKA進(jìn)行分類實(shí)驗(yàn)，該平臺(tái)可以用于數(shù)據(jù)挖掘，采取其自帶的J48實(shí)現(xiàn)決策樹(shù)。

采用準(zhǔn)確度來(lái)衡量運(yùn)動(dòng)數(shù)據(jù)的分類準(zhǔn)確性，其公式表示如下

Accuracy=countture/counttotal

(19)

countture是被正確分類的正樣本數(shù)量；counttotal是全部數(shù)據(jù)集中的數(shù)據(jù)數(shù)量。

實(shí)驗(yàn)過(guò)程中，隨機(jī)選擇1000條數(shù)據(jù)作為測(cè)試樣本，利用PrintBolt輸出運(yùn)動(dòng)數(shù)據(jù)分類的準(zhǔn)確度，10次實(shí)驗(yàn)得出的結(jié)果如表1所示。通過(guò)結(jié)果對(duì)比分析可知，所提算法對(duì)運(yùn)動(dòng)數(shù)據(jù)的分類準(zhǔn)確度高于其它方法，10次實(shí)驗(yàn)的準(zhǔn)確度平均值分別高于其它方法3.85%和1.17%。并且算法性能更加穩(wěn)定，準(zhǔn)確度波動(dòng)范圍保持在12.43%。

表1 分類準(zhǔn)確度結(jié)果(%)

為了更加合理的衡量分類方法的有效性，采用靈敏度指標(biāo)進(jìn)行補(bǔ)充評(píng)價(jià)，其公式如下

Recall=countture/(countture+countfalse)

(20)

式中，countfalse是被錯(cuò)誤分類的正樣本數(shù)量。Recall能夠描述某個(gè)正確分類和實(shí)際分類的數(shù)據(jù)量比例關(guān)系，Recall值越大表示分類性能越好。

通過(guò)10次實(shí)驗(yàn)得出Recall指標(biāo)的平均值，以及決策樹(shù)相關(guān)參數(shù)(文獻(xiàn)[4]方法不包含決策樹(shù))，結(jié)果如表2所示。根據(jù)Recall指標(biāo)比較可知，本文方法較其它方法具有更好的召回率，能夠降低數(shù)據(jù)錯(cuò)誤分類的概率。另外，通過(guò)決策樹(shù)規(guī)模和節(jié)點(diǎn)的比較可知，本文方法的分類計(jì)算復(fù)雜度明顯低于文獻(xiàn)[5]方法，有助于分類速度的提升。

表2 Recall指標(biāo)與決策樹(shù)相關(guān)參數(shù)

選擇不合度指標(biāo)來(lái)進(jìn)一步衡量運(yùn)動(dòng)數(shù)據(jù)的分類性能。其公式如下

(21)

針對(duì)10個(gè)相鄰數(shù)據(jù)分類，仿真得到它們與其它類的不合度，結(jié)果如圖2所示。根據(jù)不合度比較可知，對(duì)于10個(gè)相鄰數(shù)據(jù)分類，本文方法的不合度顯然更加穩(wěn)定，沒(méi)有在某個(gè)分類上出現(xiàn)明顯較大的不合度。并且平均不合度僅為19.46%，分別比其它方法低6.98%和3.37%，較其它方法顯然更好。

圖2 不合度結(jié)果對(duì)比

將原始數(shù)據(jù)循環(huán)輸入分類算法模型，得到對(duì)應(yīng)的吞吐量曲線，如圖3所示。根據(jù)曲線分析可知，因?yàn)樵缙跀?shù)據(jù)量的增長(zhǎng)未超過(guò)決策樹(shù)構(gòu)建需求，所以吞吐量都不高，且都處于緩慢增長(zhǎng)趨勢(shì)。到了中后期，數(shù)據(jù)量增長(zhǎng)達(dá)到?jīng)Q策樹(shù)構(gòu)建需求，吞吐量開(kāi)始快速增加，表明方法具有更好的數(shù)據(jù)分類速度。本文算法在分裂過(guò)程中，多參決策樹(shù)和剪枝操作表現(xiàn)出明顯優(yōu)勢(shì)，決策樹(shù)相關(guān)參數(shù)得到有效優(yōu)化，分類效率增長(zhǎng)明顯。

圖3 吞吐量結(jié)果對(duì)比

5 結(jié)束語(yǔ)

本文根據(jù)時(shí)間序列構(gòu)造運(yùn)動(dòng)數(shù)據(jù)的相空間，結(jié)合混沌軌跡提取數(shù)據(jù)特征。對(duì)關(guān)聯(lián)維提取出的特征變量，構(gòu)建多參決策樹(shù)，利用決策樹(shù)的可解釋性實(shí)現(xiàn)數(shù)據(jù)分類。為驗(yàn)證所提方法對(duì)運(yùn)動(dòng)數(shù)據(jù)分類的實(shí)際效果，基于WEKA數(shù)據(jù)挖掘環(huán)境進(jìn)行仿真，得到方法的準(zhǔn)確度為81.47%，靈敏度為83.92%，不合度為19.46%，結(jié)果充分說(shuō)明方法具有良好的分類性能。同時(shí)吞吐量結(jié)果也說(shuō)明方法具有良好的數(shù)據(jù)處理效率。