戎凱旋，韓新力，高 杰，霍麗娜

(1.中國(guó)電子科技集團(tuán)公司第五十四研究所,河北 石家莊 050081;2.中國(guó)電子科技集團(tuán)公司第二十二研究所，山東 青島 266000;3.河北師范大學(xué),河北 石家莊 050024)

0 引言

隨著科學(xué)技術(shù)飛速發(fā)展，人類經(jīng)濟(jì)和社會(huì)都取得了巨大進(jìn)步，伴隨計(jì)算機(jī)應(yīng)用系統(tǒng)的不斷發(fā)展和完善，在各個(gè)領(lǐng)域產(chǎn)生了海量的歷史數(shù)據(jù)。如何從這些海量無(wú)序數(shù)據(jù)中自動(dòng)、智能地提取出潛在、有價(jià)值的知識(shí)和信息是進(jìn)一步提高數(shù)據(jù)利用率的關(guān)鍵。

國(guó)外在數(shù)據(jù)挖掘方面的研究較早，出現(xiàn)了大量的數(shù)據(jù)挖掘工具[1-2]。大致可以分為兩類：基于統(tǒng)計(jì)分析方向的軟件，如社會(huì)科學(xué)統(tǒng)計(jì)軟件包 (Statistical Package for the Social Sciences，SPSS)[3-4]等；應(yīng)用與新技術(shù)方向的軟件，包括人工神經(jīng)網(wǎng)絡(luò)[5-6]、模糊邏輯[7]、決策樹理論[8-10]的工具，如Neural network Browser、Fuzzy TECH for business及Aria等軟件。國(guó)內(nèi)對(duì)于數(shù)據(jù)挖掘的研究起步相對(duì)較晚，但是，當(dāng)前國(guó)內(nèi)研究所和高等院校數(shù)據(jù)挖掘基礎(chǔ)理論以及應(yīng)用的研究已經(jīng)進(jìn)入一個(gè)成熟階段，如清華大學(xué)、中科院計(jì)算機(jī)研究所等[11]。

針對(duì)電子圍欄設(shè)備采集的海量數(shù)據(jù)，本文旨在設(shè)計(jì)相關(guān)數(shù)據(jù)挖掘算法用以將采集的潛在居民信息篩選出來(lái)，以達(dá)到挖掘數(shù)據(jù)中有價(jià)值信息，提高數(shù)據(jù)利用率的目的。由于IMSI具有唯一性，本文將其作為與居民身份關(guān)聯(lián)的特征。利用Hash存儲(chǔ)數(shù)據(jù)的優(yōu)勢(shì)[12-13]，首先對(duì)IMSI碼進(jìn)行預(yù)處理生成判別字段；然后結(jié)合實(shí)際問題，設(shè)計(jì)并構(gòu)造判別特征庫(kù)；最后通過判別字段和判別特征庫(kù)挖掘數(shù)據(jù)關(guān)聯(lián)性，以獲取潛在的居民信息。

1 Hash原理

Hash是一種重要的存儲(chǔ)和查找方法，其主要利用計(jì)算機(jī)對(duì)漢明距離計(jì)算速度快、存儲(chǔ)方便以及節(jié)約內(nèi)存空間的特點(diǎn)，將歐氏空間中的數(shù)據(jù)點(diǎn)映射到漢明空間直接進(jìn)行處理，從而提高了計(jì)算速度、減小了內(nèi)存消耗。在海量高維數(shù)據(jù)檢索任務(wù)中，其在計(jì)算速度和存儲(chǔ)空間兩方面具有明顯的優(yōu)勢(shì)。

Hash基本原理為：以關(guān)鍵字k為自變量，通過某一確定函數(shù)H，計(jì)算其對(duì)應(yīng)的函數(shù)值H(k):

y=H(k)。

(1)

H(k)為關(guān)鍵字k的存儲(chǔ)地址，或稱索引值，所有索引值構(gòu)成一張Hash表，也稱索引。查找時(shí)，根據(jù)要查找的關(guān)鍵字k用同樣的函數(shù)H計(jì)算地址，并到相應(yīng)存儲(chǔ)單元取出要查找的結(jié)點(diǎn)。理想情況下，不同關(guān)鍵字的索引值都不相同，實(shí)際中由于很難找到這樣一個(gè)H函數(shù)，因此可能存在不同關(guān)鍵字被映射在同一地址上的“沖突”?？梢允褂镁€性探測(cè)法、二次探測(cè)法、偽隨機(jī)探測(cè)法和鏈地址法等來(lái)處理產(chǎn)生的“沖突”[14]。

2 算法設(shè)計(jì)

針對(duì)海量電子圍欄數(shù)據(jù)，結(jié)合Hash在數(shù)據(jù)存儲(chǔ)和查找兩方面的優(yōu)勢(shì)，根據(jù)用戶需求，利用Hash設(shè)計(jì)算法從海量電子圍欄數(shù)據(jù)中挖掘居民信息。

由于IMSI碼的唯一性，將其作為與居民身份關(guān)聯(lián)的特征。實(shí)際中考慮到居民同一天會(huì)在同一地點(diǎn)出現(xiàn)多次，并且連續(xù)多天出現(xiàn)。為了挖掘IMSI數(shù)據(jù)之間的關(guān)聯(lián)性以對(duì)其是否連續(xù)出現(xiàn)做出正確研判，本文提出并設(shè)計(jì)了一種判別特征。同時(shí)引入閾值參數(shù)th1和th2，其中th1表示IMSI每天出現(xiàn)的次數(shù)，th2表示IMSI在N天內(nèi)連續(xù)出現(xiàn)的天數(shù)。

首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，即當(dāng)某IMSI在某一天出現(xiàn)次數(shù)大于等于th1時(shí)對(duì)其標(biāo)記。同時(shí)循環(huán)遍歷N天所有數(shù)據(jù)，對(duì)滿足此條件的所有IMSI進(jìn)行標(biāo)記，生成每天出現(xiàn)次數(shù)大于等于th1的IMSI庫(kù)IMSIs。隨后對(duì)IMSI碼在IMSIs中檢索，生成判別字段AppearFlags，同時(shí)設(shè)計(jì)并構(gòu)造判別特征庫(kù)FlagsLib以挖掘IMSI之間的關(guān)聯(lián)性。最后將AppearFlags與FlagsLib中所有字段進(jìn)行匹配，挖掘出潛在的居民。算法詳細(xì)步驟如下：

① 遍歷第i天采集的數(shù)據(jù)，并對(duì)出現(xiàn)次數(shù)大于等于th1的IMSI進(jìn)行標(biāo)記；

② 重復(fù)步驟①直至N天數(shù)據(jù)都被處理并生成IMSIs；

③ 遍歷IMSIs中所有IMSI，生成每個(gè)IMSI對(duì)應(yīng)的AppearFlags；

④ 構(gòu)造FlagsLib，保留其中長(zhǎng)度大于等于th2的字段；

⑤ 將AppearFlags在FlagsLib中匹配，若匹配成功則表明相應(yīng)的IMSI為居民。

算法框圖如圖1所示。

圖1 算法框圖

其中，左虛線框部分篩選滿足條件的IMSI用以構(gòu)造IMSIs，扮演數(shù)據(jù)預(yù)處理的作用；右虛線框部分利用IMSIs和FlagsLib對(duì)數(shù)據(jù)進(jìn)行挖掘，并得到居民IMSI信息。

針對(duì)數(shù)據(jù)的海量性，在步驟②和④中分別對(duì)IMSIs和FlagsLib作如下初始化，構(gòu)造Hash索引變量，以便于數(shù)據(jù)的存儲(chǔ)和查找。

Set IMSIs = new HashSet<>(); ∥初始化IMSIs

SetFlagsLib = new HashSet<>(); ∥初始化FlagsLib

構(gòu)造存放居民IMSI的Hash索引變量ResidentIMSIs

Set Residents = new HashSet<>(); ∥居民IMSI

在數(shù)據(jù)預(yù)處理階段，IMSIs構(gòu)造過程簡(jiǎn)化如下：

for (int i=1; i <= N; i++)

{String IMSI = MongoDocument.getString("imsi");

long tempCount = MongoCollection.count(… ,eq("imsi",IMSI),…); ∥統(tǒng)計(jì)當(dāng)前IMSI在集合中出現(xiàn)的次數(shù)

if (tempCount >=th1) ∥出現(xiàn)次數(shù)大于等于th1

{String tempImsi = IMSI + Integer.toString(i);

IMSIs.add(tempImsi);

}

}

判別字段AppearFlags生成過程簡(jiǎn)化如下：

subImsi= IMSIsString.substring("imsi"); ∥從IMSIs中取出IMSI碼

for (int i = 1; i <= N; i++)

{String tempImsi = subImsi + Integer.toString(i);

if (IMSIs.contains(tempImsi))

{AppearFlags = AppearFlags + Integer.toString(i); ∥更新字段

}

}

判別特征庫(kù)FlagsLib構(gòu)造過程簡(jiǎn)化如下：

for (int i=1; i <= N; i++)

{String tempFlagsLib = ""; ∥初始化

for (int j=i,h=i; h <= N; h++)

{tempFlagsLib = tempFlagsLib + Integer.toString(j); ∥更新

}

if (tempFlagsLib.length() >= th2) ∥長(zhǎng)度大于等于th2

{FlagsLib.add(tempFlagsLib);

}

j=j+1;

}

本問題中Hash映射函數(shù)H(k)為：

H(k)={k^ ((k>>>20) ^ (k>>> 12));
k^(k>>> 7)^(k>>>4)}，

(2)

式中，^為按位異或，>>>為二進(jìn)制右移位。利用哈希值H(k)再進(jìn)一步經(jīng)過 H(k)&(length-1) 運(yùn)算就可以得到k在哈希表中對(duì)應(yīng)的索引位置。其中，&表示按位與，length為哈希表長(zhǎng)度。對(duì)于本問題中構(gòu)造的三個(gè)hash變量(IMSIs、FlagsLib和Residents)，k分別對(duì)應(yīng)tempImsi、tempFlagsLib以及居民IMSI。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 仿真數(shù)據(jù)分析

首先利用仿真數(shù)據(jù)對(duì)構(gòu)造的判別特征FlagsLib及算法有效性進(jìn)行驗(yàn)證分析，以“5天內(nèi)IMSI在每天出現(xiàn)次數(shù)大于等于2次且連續(xù)出現(xiàn)2天及以上”為居民判定準(zhǔn)則。此種情況下生成的判別特征庫(kù)FlagsLib為{12,123,1 234,12 345,23,234,2 345,34,345,45}，可以看到構(gòu)造的FlagsLib每一字段長(zhǎng)度都大于等于2并且具有連續(xù)性。

5天仿真數(shù)據(jù)共1 237條數(shù)據(jù)記錄，其中包含四位有效居民及兩位出現(xiàn)兩天的非居民，其IMSI分布規(guī)律如表1所示。表1中數(shù)字“2”表示當(dāng)前IMSI在當(dāng)天出現(xiàn)兩次，“0”表示當(dāng)前IMSI在當(dāng)天沒有出現(xiàn)。通過表1可以得知，IMSI為460 071 357 028 025的居民在第二和第三天連續(xù)出現(xiàn)，IMSI為460 072 039 660 263的居民在第一、第二和第三天連續(xù)出現(xiàn)，IMSI為460 013 829 542 865的居民在第三、第四和第五天連續(xù)出現(xiàn)，IMSI為460 004 507 584 843的居民在五天內(nèi)全部出現(xiàn)，IMSI為460 013 216 186 295的非居民在第一和第四天出現(xiàn)，IMSI為460 022 444 635 725的非居民在第一和第三天出現(xiàn)。

表1 IMSI分布規(guī)律

IMSI第一天第二天第三天第四天第五天460 071 357 028 02502200460 072 039 660 26322200460 013 829 542 86500222460 004 507 584 84322222460 013 216 186 29520020460 022 444 635 72520200

利用算法對(duì)上述仿真數(shù)據(jù)進(jìn)行分析，運(yùn)行時(shí)間為213 ms，結(jié)果如圖2所示?？梢钥吹?位有效居民都被正確分析出，并且AppearFlags統(tǒng)計(jì)的其出現(xiàn)規(guī)律也完全符合表1；另一方面，IMSI為460 022 444 635 725和460 013 216 186 295的非居民出現(xiàn)規(guī)律也被正確統(tǒng)計(jì)出，但是由于二者的出現(xiàn)不具有連續(xù)性，因此并沒有被判定為合法居民。實(shí)驗(yàn)結(jié)果表明通過FlagsLib有效挖掘了數(shù)據(jù)之間的關(guān)聯(lián)性，同時(shí)也驗(yàn)證了算法的有效性。

圖2 仿真數(shù)據(jù)分析結(jié)果

3.2 真實(shí)數(shù)據(jù)分析

對(duì)設(shè)備在一個(gè)高速路口實(shí)采的數(shù)據(jù)進(jìn)行分析，總共包含51 231條數(shù)據(jù)記錄，此種情況下當(dāng)IMSI“7天內(nèi)每天出現(xiàn)次數(shù)大于等于2次且連續(xù)出現(xiàn)3天及以上”即判定為居民。生成的FlagsLib為{123,1234,12 345,123 456,1 234 567,234,2 345,23 456,234 567,345,3 456,34 567,456,4 567,567}，同樣可以看到構(gòu)造的FlagsLib每一字段長(zhǎng)度都大于等于3并且具有連續(xù)性。算法運(yùn)行269 028 ms，結(jié)果如圖3所示。

圖3 真實(shí)數(shù)據(jù)分析結(jié)果

圖3中Residents完整信息包括[460021330722742,460023754093405,460027300708738,460028318409995,460002003361642,460022338242227,460078339059427,460021888818523,460000042313928,460028320880948,460027320240889,460021310303155,460023750301512]，共13個(gè)IMSI碼。可以看到，由于高速路口經(jīng)過的人員流動(dòng)性大，從而利用算法得到的有效居民數(shù)量也很少。

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

結(jié)合Hash對(duì)數(shù)據(jù)的存取優(yōu)勢(shì)，根據(jù)IMSI唯一性，通過設(shè)計(jì)構(gòu)造連續(xù)性判別特征庫(kù)FlagsLib，提出了一種基于Hash索引的居民信息挖掘算法。首先通過數(shù)據(jù)預(yù)處理篩選出滿足條件的IMSI并構(gòu)造相應(yīng)的判別字段AppearFlags。其次創(chuàng)建FlagsLib，并通過AppearFlags和FlagsLib挖掘數(shù)據(jù)之間的關(guān)聯(lián)性，以進(jìn)一步對(duì)居民身份進(jìn)行研判。實(shí)驗(yàn)結(jié)果表明數(shù)據(jù)關(guān)聯(lián)性可以有效被挖掘出，同時(shí)也驗(yàn)證了本文算法的有效性。將其部署在系統(tǒng)后臺(tái)，進(jìn)一步表明了算法的可靠性及與系統(tǒng)整體的協(xié)調(diào)一致性。

雖然本文通過仿真數(shù)據(jù)和真實(shí)數(shù)據(jù)都充分驗(yàn)證了FlagsLib及算法的有效性，但是可以看到隨著數(shù)據(jù)量增加，算法運(yùn)行時(shí)間在顯著增加。為有效解決這一問題，未來(lái)可以結(jié)合大數(shù)據(jù)分析技術(shù)，利用Hadoop存儲(chǔ)架構(gòu)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)，同時(shí)采用Spark技術(shù)架構(gòu)在內(nèi)存層面完成數(shù)據(jù)的分析任務(wù)以有效降低時(shí)間消耗。

[1] 王夢(mèng)雪.數(shù)據(jù)挖掘綜述[J].軟件導(dǎo)刊,2013,12(10):135-137.

[2] 吉根林,趙斌.面向大數(shù)據(jù)的時(shí)空數(shù)據(jù)挖掘綜述[J].南京師大學(xué)報(bào)(自然科學(xué)版),2014,37(1):1-7.

[3] 周瑤,方全偉.淺談SPSS 在醫(yī)藥科研設(shè)計(jì)與數(shù)理統(tǒng)計(jì)中的應(yīng)用[J].數(shù)字技術(shù)與應(yīng)用,2012(7):201-202.

[4] 王偉賓,劉霽煒.大數(shù)據(jù)視角下的大學(xué)英語(yǔ)四級(jí)成績(jī)影響因素研究[J].北方工業(yè)大學(xué)學(xué)報(bào),2015(2):74-79.

[5] 尹廣畢,楊承志.人工神經(jīng)網(wǎng)絡(luò)的專家系統(tǒng)的研究及應(yīng)用[J].機(jī)械制造與自動(dòng)化,2007,36(5):51-53.

[6] 袁金秋,劉雅莉,楊克虎.基于人工神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)挖掘技術(shù)在臨床中應(yīng)用進(jìn)展[J].圖書與情報(bào),2010(3):95-98.

[7] 朱方啟.基于模糊邏輯控制的目標(biāo)識(shí)別技術(shù)研究[D].成都:電子科技大學(xué),2016.

[8] 張艷磊.關(guān)聯(lián)規(guī)則和決策樹理論在影視傳播分析中的研究與應(yīng)用[D].蘭州:西北民族大學(xué),2015.

[9] 薛紅軍,陳廣交,李鑫民,等.基于決策樹理論的交通流參數(shù)短時(shí)預(yù)測(cè)[J].交通信息與安全,2016,34(3):64-71.

[10] 史英杰,魯曉麗.基于決策樹理論的學(xué)生成績(jī)分析系統(tǒng)模型構(gòu)建[J].科技展望,2015,25(29):290.

[11] 何元.基于云計(jì)算的海量數(shù)據(jù)挖掘分類算法研究[D].成都:電子科技大學(xué),2011.

[12] 丁羽,韋韜.安全hash的攻與防[J].計(jì)算機(jī)與網(wǎng)絡(luò),2017,43(16):56-61.

[13] 李淵,阮軍洲.基于Hash和Radix樹的路由查找算法研究[J].計(jì)算機(jī)與網(wǎng)絡(luò),2015,41(11):42-44.

[14] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2014.