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

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

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

0 引言

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

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

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

1 Hash原理

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

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

y=H(k)。

(1)

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

2 算法設計

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

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

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

① 遍歷第i天采集的數據，并對出現次數大于等于th1的IMSI進行標記；

② 重復步驟①直至N天數據都被處理并生成IMSIs；

③ 遍歷IMSIs中所有IMSI，生成每個IMSI對應的AppearFlags；

④ 構造FlagsLib，保留其中長度大于等于th2的字段；

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

算法框圖如圖1所示。

圖1 算法框圖

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

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

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

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

構造存放居民IMSI的Hash索引變量ResidentIMSIs

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

在數據預處理階段，IMSIs構造過程簡化如下：

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

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

long tempCount = MongoCollection.count(… ,eq("imsi",IMSI),…); ∥統計當前IMSI在集合中出現的次數

if (tempCount >=th1) ∥出現次數大于等于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構造過程簡化如下：

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映射函數H(k)為：

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

(2)

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

3 實驗結果及分析

3.1 仿真數據分析

首先利用仿真數據對構造的判別特征FlagsLib及算法有效性進行驗證分析，以“5天內IMSI在每天出現次數大于等于2次且連續出現2天及以上”為居民判定準則。此種情況下生成的判別特征庫FlagsLib為{12,123,1 234,12 345,23,234,2 345,34,345,45}，可以看到構造的FlagsLib每一字段長度都大于等于2并且具有連續性。

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

表1 IMSI分布規律

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

利用算法對上述仿真數據進行分析，運行時間為213 ms，結果如圖2所示。可以看到4位有效居民都被正確分析出，并且AppearFlags統計的其出現規律也完全符合表1；另一方面，IMSI為460 022 444 635 725和460 013 216 186 295的非居民出現規律也被正確統計出，但是由于二者的出現不具有連續性，因此并沒有被判定為合法居民。實驗結果表明通過FlagsLib有效挖掘了數據之間的關聯性，同時也驗證了算法的有效性。

圖2 仿真數據分析結果

3.2 真實數據分析

對設備在一個高速路口實采的數據進行分析，總共包含51 231條數據記錄，此種情況下當IMSI“7天內每天出現次數大于等于2次且連續出現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}，同樣可以看到構造的FlagsLib每一字段長度都大于等于3并且具有連續性。算法運行269 028 ms，結果如圖3所示。

圖3 真實數據分析結果

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

4 結束語

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

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

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

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

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

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

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

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

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

[8] 張艷磊.關聯規則和決策樹理論在影視傳播分析中的研究與應用[D].蘭州:西北民族大學,2015.

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

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

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

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

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

[14] 嚴蔚敏,吳偉民.數據結構[M].北京:清華大學出版社,2014.