一种基于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.