一種基于Hash索引的居民信息挖掘算法

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

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

0 引言

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

國外在數(shù)據(jù)挖掘方面的研究較早，出現(xiàn)了大量的數(shù)據(jù)挖掘工具[1-2]。大致可以分為兩類：基于統(tǒng)計分析方向的軟件，如社會科學(xué)統(tǒng)計軟件包 (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等軟件。國內(nèi)對于數(shù)據(jù)挖掘的研究起步相對較晚，但是，當(dāng)前國內(nèi)研究所和高等院校數(shù)據(jù)挖掘基礎(chǔ)理論以及應(yīng)用的研究已經(jīng)進入一個成熟階段，如清華大學(xué)、中科院計算機研究所等[11]。

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

1 Hash原理

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

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

y=H(k)。

(1)

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

2 算法設(shè)計

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

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

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

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

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

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

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

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

算法框圖如圖1所示。

圖1 算法框圖

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

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

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)造過程簡化如下：

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

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

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

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

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

IMSIs.add(tempImsi);

}

}

判別字段AppearFlags生成過程簡化如下：

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); ∥更新字段

}

}

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

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) ∥長度大于等于th2

{FlagsLib.add(tempFlagsLib);

}

j=j+1;

}

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

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

(2)

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

3 實驗結(jié)果及分析

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

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

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

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

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

對設(shè)備在一個高速路口實采的數(shù)據(jù)進行分析，總共包含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每一字段長度都大于等于3并且具有連續(xù)性。算法運行269 028 ms，結(jié)果如圖3所示。

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

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

4 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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