第 ２８ 卷第 ３ 期 ２０１１ 年 ３ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ 基 于 实 体 关 系 的 犯 罪 网 络 识 别 机 制 １， 林鸿飞 １， 罗文华 ２ 周利娟 Ｖｏｌ．２８ Ｎｏ．３ Ｍａｒ．２０１１ 倡 （１．大连理工大学 计算机科学与技术学院， 辽宁 大连 １１６０２４； ２．中国刑 警学 院 计 算 机 犯 罪 侦 查 系， 沈 阳 １１０８５４） 摘　要： 实体关系抽取是数据挖掘和信息检索的重要研究内容，抽取的目标是发现数据集中两个不同实体之间 的语义关系；犯罪网络是个小型的社会，具有社会化网络的特征，因此采用社会化网络的方法来分析犯罪网络中 人物之间的关系。 首先定义实体、实体关系以及关系描述词等概念，并引入了关系模型，用关系树的方法抽取案 情信息中的实体关系，在此基础上提出发掘犯罪网络核心人物的 ＣＮＣＤ 算法，最后设计并实现了犯罪网络挖掘 系统。 通过实验验证和用户反馈，本系统能在很大程度上提高公安人员办案效率，具有很高的实用价值。 关键词： 实体关系抽取； 关系模型； 网络挖掘； 网络可视化 中图分类号： ＴＰ３９１．７　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２０１１）０３唱０９９８唱０５ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．０３．０５８ Ｃｒｉｍｉｎａｌ ｎｅｔｗｏｒｋ ｒｅｃｏｇｎｉｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｂａｓｅｄ ｏｎ ｅｎｔｉｔｙ ｒｅｌａｔｉｏｎｓｈｉｐ ＺＨＯＵ Ｌｉ唱ｊｕａｎ１， ＬＩＮ Ｈｏｎｇ唱ｆｅｉ１， ＬＵＯ Ｗｅｎ唱ｈｕａ２ （１．School of Computer Science ＆ Technology， Dalian University of Technology， Dalian Liaoning １１６０２４， China； ２．Dept．of Computer Crimi唱 nal Detection， China Criminal Police University， Shenyang １１０８５４， China） Abstract： Ｅｎｔｉｔｙ ｒｅｌａｔｉｏｎｓｈｉｐ ｅｘｔｒａｃｔｉｏｎ， ｔｈｅ ｇｏａｌ ｏｆ ｗｈｉｃｈ ｗａｓ ｔｏ ｄｉｓｃｏｖｅｒ ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｏｆ ｔｗｏ ｏｒ ｍｏｒｅ ｅｎｔｉｔｉｅｓ ｉｎ ｔｈｅ ｄａｔａ唱 ｓｅｔ， ｗａｓ ａ ｃｒｕｃｉａｌ ｃｏｍｐｏｎｅｎｔ ｉｎ ｄａｔａ ｍｉｎｉｎｇ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ ｄｏｍａｉｎ．Ｃｒｉｍｉｎａｌ ｎｅｔｗｏｒｋ ｗｉｔｈ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｗａｓ ａｎ ｅｐｉｔｏｍｅ ｏｆ ｔｈｅ ｗｈｏｌｅ ｓｏｃｉｅｔｙ， ｔｈｕｓ ｕｓｉｎｇ ｔｈｅ ｍｅｔｈｏｄｓ ａｎｄ ｔｅｃｈｎｏｌｏｇｉｅｓ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ａｎａｌｙｓｉｓ ｔｏ ａｎａｌｙｚｅ ｃｒｉｍｉｎａｌ ｎｅｔｗｏｒｋ ｃｏｕｌｄ ｍａｋｅ ｍｉｒａｃｌｅｓ ｉｎ ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ ｆｉｅｌｄ．Ｔｈｉｓ ｐａｐｅｒ ｄｅｆｉｎｉｔｅｄ ８ ｋｉｎｄｓ ｏｆ ｒｅｌａｔｉｏｎ， ｒｅｌａｔｉｏｎ唱ｄｅ唱 ｓｃｒｉｐｔｏｒｓ ａｎｄ ｒｅｌａｔｉｏｎ ｍｏｄｅｌｓ ｆｉｒｓｔ ａｎｄ ｔｈｅｎ ｄｅｓｃｒｉｂｅｄ ｔｈｅ ｐｒｏｃｅｓｓ ｈｏｗ ｅｘｔｒａｃｔｅｄ ｒｅｌａｔｉｏｎｓｈｉｐ ａｎｄ ｆｉｎａｌｌｙ ｐｒｏｐｏｓｅｄ ＣＮＣＤ ａｌｇｏ唱 ｒｉｔｈｍ ｔｏ ｄｉｓｃｏｖｅｒ ｃｏｒｅ ｆｉｇｕｒｅｓ ｉｎ ｔｈｅ ｎｅｔｗｏｒｋ．Ｉｔ ａｌｓｏ ｄｅｖｅｌｏｐｅｄ ａ ｐｒａｃｔｉｃａｌ ｖｉｓｕａｌｉｚａｔｉｏｎ ｔｏｏｌ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｐｕｂｌｉｃ ｓｅｃｕｒｉｔｙ ｄｅｐａｒｔｍｅｎｔ．Ａｓ ｅｘｐｅｒｉｍｅｎｔｓ ａｎｄ ｆｅｅｄｂａｃｋ ｓｈｏｗ， ｔｈｉｓ ｓｙｓｔｅｍ ｃａｎ ｂｅ ｂｅｎｅｆｉｃｉａｌ ｔｏ ｓｅｃｕｒｉｔｙ ｄｅｐａｒｔｍｅｎｔｓ ｔｏ ａ ｃｅｒｔａｉｎ ｅｘ唱 ｔｅｎｔ． Key words： ｅｎｔｉｔｉｅｓ ｒｅｌａｔｉｏｎ ｅｘｔｒａｃｔｉｏｎ； ｒｅｌａｔｉｏｎ ｍｏｄｅｌ； ｎｅｔｗｏｒｋ ｍｉｎｉｎｇ； ｎｅｔｗｏｒｋ ｖｉｓｕａｌｉｚａｔｉｏｎ 对网络实施的犯罪 法以及多种模型相结合的方法等 网络信息传播的便捷与迅速使得网络成为犯罪分子犯罪 0　引言 中国互联网的不断发展和网民数量的不断增加，使犯罪分 子利用网络犯罪与日俱增，其受害人之广、时空无界、社会危害 性强等特点都使我国很多网民的人身财产安全受到严重威胁。 的重要手段。 网络犯罪主要是指利用网络实施的犯罪， 包括 传统的犯罪使用网络这种形式、手段予以实施， 也包括直接针 ［１］。 电子证据是以数字的形式保存在计算 机存储器或外部存储介质中， 能够证明案件真实情况的数据 或信息， 包括电子合同、电子信件、电子签名、ＱＱ 聊天记录、来 往电子邮件等。 电子证据的存在为公安人员办理此类案件提 供了可能，但是通常电子证据数据量庞大，格式丰富，人工查看 和分析这些电子证据将消耗大量的人力、物力。 在这种需求之 下，本文考虑利用文本挖掘和知识发现的方法来获取海量电子 证据中的实体以及实体之间的关系。 规定，传 统的实体主要是文本中的专有名称，包括人名、地名、机构名以 及时间表达式和数字表达式。 本文考虑网络犯罪的实际特点， 将实体的概念进行扩展，不仅包括传统的实体信息，还包括网 络中的网名、昵称、代号、网址、虚拟社区、邮箱、电话号码、ＩＰ、 银行卡号等。 目前，命名实体识别有基于规则的方法、基于语 料库的方法、基于统计语言模型（ 包括 Ｎ 元模型、隐马尔可夫 模型（ＨＭＭ）、最大熵模型（ＭＥ）、条件随机域（ＣＲＦ） 等） 的方 ［４］，考虑到公安数据的领域 特点，本文综合采用基于规则的方法和基于语料库的方法。 大多数应用通常需要在识别实体之后抽取实体间的关系， 即实体关系抽取。 实体关系的类型需要预先定义，如亲属关 系、师生关系等 ［２，５］。 实体关系抽取是信息抽取的重要组成部 分，目的在于发现用户需要的信息 ［６］。 最开始人们采用知识 库的方法来抽取关系，为了克服构建知识库困难的问题，很多 研究人员尝试研究机器学习的方法，主要包括基于特征向量和 ［７，８］。 核函数的方法不需要构造特征向量， 直接使用字符串的原始形式作为处理对象，分析和预测时间复 　　收稿日期： ２０１０唱０７唱２２； 修回日期： ２０１０唱０９唱０９　　基金项目： 国家自然科学基金资助项目（６０６７３０３９，６０９７３０６８）；国家社科基金资助项目 （０８ＢＴＱ０２５）；国家“８６３” 高科技计划资助项目（２００６ＡＡ０１Ｚ１５１）；高等学校博士学科点专项科研基金资助项目（２００９００４１１１０００２）；公安部应用创新 计划项目（２００７ＹＹＣＸＸＪＸＹ１０６） 　　作者简介：周利娟（１９８７唱），女，安徽安庆人，硕士，主要研究方向为文本挖掘和移动检索（ｚｈｏｕｌｉｊｕａｎ＠ｍａｉｌ．ｄｌｕｔ．ｅｄｕ．ｃｎ）；林鸿飞（１９６２唱），男， 教授，博导，博士，主要研究方向为搜索引擎、文本挖掘、情感计算和自然语言理解；罗文华（１９７７唱），男，副教授，主要研究方向为计算机犯罪侦查． ＭＵＣ（Ｍｅｓｓａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ） 会议 基于核函数的方法 ［２，３］ 

周利娟，等：基于实体关系的犯罪网络识别机制 ·９９９· 　　　 词作为替代词来消解指示代词。 在此基础上，本文根据词在句 子中的位置（句法结构） 抽取出名词和数词，若相连的词之间 有关系（如“辽宁省”和“大连市”），便将前后两个实体合并。 表 １　实体类型和规则描述 等 的 用 以关系作为基本分析单位的社会化网络分析方法今天已 第 ３ 期 杂度高。 本文结合了知识库和基于特征的机器学习方法，并用 关系描述词的概念扩展传统的二元关系，提出关系树的概念和 方法来抽取实体关系。 经在社会 学、 教 育 学、 经 济 学 等 诸 多 领 域 得 到 了 广 泛 的 应 ［９］。 由犯罪团伙组成的人物关系网络构成小的社会团体， 犯罪团伙的组织结构决定了犯罪的手段、规模、危险度等，可以 用社会化网络的研究方法来研究和挖掘犯罪作案手段、作案方 式等。 为了构建和分析犯罪网络，本文借助于社会网络 ［９，１０］ 分析方法来解决案情数据中犯罪网络挖掘的问题，提出了挖掘 犯罪子网和核心人物的 ＣＮＣＤ（ｃｒｉｍｉｎａｌ ｎｅｔｗｏｒｋ ｃｏｒｅ唱ｆｉｇｕｒｅ ｄｉｓ唱 ｃｏｖｅｒｙ）算法。 其主要思想是：构建带有边权重的人物关系图， 利用层次聚类的方法分析得到犯罪子网，根据人物的联系度、 中介度和紧密度计算核心度，识别出核心人物。 1　关键技术 1畅1　实体识别 为了分析数据集中隐含的实体关系，在对原始数据进行预 处理（格式分类、分词等） 之后，需要进行命名实体识别任务， 主要是识别出文本中出现的专有名称和有意义的数量短语，并 加以归类。 所谓的命名实体主要包括实体（ 组织名、人名、地 名）、时间表达式（ 日期、时间）、数字表达式（ 货币值、百分数） ［１１］。 最初人们采用基于规则的方法，这种方法由于需要人 工定义规则，费时费力，一方面规则的完备性受到质疑，另一方 面规则之间的差异性很难界定，这些因素使得该方法不适用于 信息量庞大的关系抽取领域。 基于语料库和统计语言模型是 经典的机器学习方法，特殊领域准确率和召回率能达到 ９０％ 以上。 在本文中，考虑到数据的特点，采用基于规则的方法来 识别有效的实体，如人名（代号、ＩＤ 等）、地名（ 包括机构名）、 时间、数量词等信息。 在实体识别的过程中，本文的实验过程中也遇到过很多的 问题： ａ）不规范的人名很难识别，特别是有些网民，如“ 大卡路 里”“Ｌｏｖｅ倡倡”等； ｂ）特殊的人名和地名很难区分，特别是缩略语； ｃ）机构名或地名由于层次较多，多属于复合名词，很难准 确确定范围； ｄ）未登录词问题较为严重。 对于上述问题，本文通过定义详细的规则来解决，但由于 分析犯罪网络的实际需要以及公安部门的建议，本文舍弃了一 些不必要的实体类型（如“心情” 等），精选出的具体规则定义 如表１ 所示。 在定义上述抽取规则的基础上，本文针对公安部门实际给 出的五个具体案情实例数据进行分析和抽取，结果如表２ 所示。 由上面的统计可知，不同类型的案件对应的主要实体类别 不同。 在网络走私案件中，由于存在交易，需要银行账号、电子 邮箱、手机等信息；而在网络聚集性案件中，由于以犯案人员在 网上传播不良信息、煽动网民情绪等内容为主，涉及到较多的 人、机构。 为了准确识别实体关系，本文实现了指代消解过程，正确 处理指代消解的问题是精确识别出实体间隐含关系的关键。 因此，针对本文实际语料的具体情况，根据性、数和人称的一致 性规则，选择与当前指代词性、数和人称一致、距离最近的先行 类型 人名 地名 机构名 时间 专有名词 手机或固话 邮箱 银行账号 ＩＰ 地址 数字 规则 汉字或英文字母的自由组合 含有［ 省｜市｜县｜镇｜乡｜村｜区｜路｜街｜湾｜沟｜屯｜城］ 和 ［ 楼｜单元｜巷｜胡同｜号｜室］ 的规则表达 含有［ 公司｜学校｜所｜院｜局｜部］ 含有［ 年｜月｜日］ 或“ －” ／“．” 的规则表达 蚁力神等 １１ 位数字或者是数字之间有“ －” 标志的 “．” 和“＠” 的规则组合 １９ 位数字 含有 ３ 个“．” 且 ４ 个数字都在 ０ ～２５５ 含有［ 亿｜千万｜百万｜十万｜万｜千｜百｜十］ 的规则表达以及非 时间、身份证号、银行账号、手机或固定电话号的数字组合 表 ２　实体类型定义和统计结果 类型 描述 出现总次数 实例 大卡路里、郑志勇 数字 ８７ ５６ ２４ ２８３ １４ １６ １２ ５ ２ ３４５ 邮箱 银行账号 蚁力神 专有名词 机构名 时间 人名 地名 手机或电话号 辽宁蚁力神公司 沈阳医药贸易大厦 １３１９００００８９１ ２００１ 年 １ 月 ３ 日 ２０２ ．１１８．６６．６ 八万／８００００／８ 万 ｚｈｅｎｇｚｈｉｙｏｎｇ７６５４＠２１ｃｎ．ｃｏｍ ０７３０４９９９８０１３００１４５１０ ＰＥＲ ＡＤＤＲ ＯＲＧ ＴＩＭ ＳＰＥ ＴＥＬ ＭＡＩＬ ＣＮＴ ＩＰ ＩＰ 地址 ＮＵＭ 1畅2　实体关系模型 ［７，１２］；Ｃｈｒｉｓｔｉｎａ 等人 提出基于核的关系抽取方法，能抽取人 物、地点、犯罪组织、通信方式四种实体之间的七种关系；Ｌｉ 等 利用实体位置特征定义中文实体关系抽取模型。 与前三 ［１３］ 者不同的是，本文首先根据网络犯罪的实际特点，拓展了实体类 型定义，包括人物特征属性、银行账号等信息；然后考虑实体之 间的位置关系，构建关系树，并利用关系指示词确定具体的关系 类型。 为保证分析的准确性、合理性和可操作性，关系模型的定 义必须考虑实际案情信息的特点，抽取共性特征。 由此本文在 拓展的实体类型的基础上定义了八种类型的关系，将实体主要 分为与个人的关系以及与组织的关系，如表３ 所示。 实践证明 这种关系类型定义符合公安部门查案要求。 表 ３　关系类别定义和描述 目前应用较多的关系分类方法将实体分为个人和组织两大 类 人 ［７］ 关系 Ｒｌ１ Ｒｌ２ Ｒｌ３ Ｒｌ４ Ｒｌ５ Ｒｌ６ Ｒｌ７ Ｒｌ８ 描述 个人带有某些性质 个人认识另一个人 个人受雇于组织 个人的联系方式是 个人出现在某地 组织与组织合作 组织位于地址 组织的联系方式是 表示 Ｐｅｒ唱ｗｉｔｈ唱Ｐｒｏｐ Ｐｅｒ唱ｋｎｏｗｓ唱Ｐｅｒ Ｐｅｒ唱ｅｍｐｌｏｙ唱Ｃｏｒｐ Ｐｅｒ唱Ｃｏｍｍ Ｐｅｒ唱Ａｄｄｒ Ｃｏｒｐ唱Ｃｏｒｐ Ｃｏｒｐ唱Ａｄｄｒ Ｃｏｒｐ唱Ｃｏｍｍ 实例 去找 Ｐｅｒ１，他会穿黑色夹克 Ｐｅｒ２ 和 Ｐｅｒ３ 在一起吃饭 Ｐｅｒ４ 公司的 Ｐｅｒ５ 你可以打 Ｔｅｌ１ 找 Ｐｅｒ６ 大卡现在在成达公司 成达公司和美林公司在这个 成达公司地址：… 拨打电话 １３ 找成达老总 

计 算 机 应 用 研 究 　 ｏｌｄ ｄｏ ·０００１· 1畅3　实体关系抽取 提 ［８］ ［７，８］ ［２，１３］ 即基于特征向量 的方法和基于核 提出了基于树核的动态扩张树的语义关系抽取 出了利用核函数来抽取调查数据中的实体关系 目前关系抽取的方法大多采用分类的方法，主要有两种， 的学习算法。 基于 特征的方法最早由 Ｖａｐｎｉｋ 提出，主要是将分类对象表示成所 有特征构成的高维空间中的一个向量，该向量表示这个对象所 有的性质，这种方法避免了传统方法构建知识库的过程，提高 了效率。 基于核的学习算法最早在支持向量机（ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ，ＳＶＭ）方法中被引用，在自然语言处理领域很多学者 尝试用这种方法来改进现有的算法。 例如，Ｃｈｒｉｓｔｉｎａ 等人 ［７］ ［７］，苏州大学 的 Ｑｉａｎ 等人 新方法。 为抽取实体关系，本文首先定义关系树的概念。 关系树是 一种二叉树树形结构，树的叶子是具体的实体，中间节点是关 系的具体类型。 例如，对于给定的一句话“陈登立，我是郑志勇，请把我的 工资汇到０７３０４９９９８０１３００１４５１０”，本文提出的方法构造的关系 树如图１ 所示。 在关系树概念的基础上，采用如下算法构建关系树并抽取 实体之间的关系： ｉｎｐｕｔ： ｓｅｑｕｅｎｃｅｓ ｏｆ ｅｎｔｉｔｉｅｓ ａｎｄ ｒｅｌａｔｉｏｎｓｈｉｐ ｄｉｓｃｒｉｐｔｏｒｓ； ａ）ｗｈｉｌｅ ａｔ ｌｅａｓｔ ｏｎｅ ｐｉｅｃｅ ｏｆ ｔｅｘｔ ｉｓ ｌｅｆｔ ｄｏ； ｂ）ｉｆ ｎｕｍｂｅｒ ｏｆ ｐａｓｓａｇｅｓ ｃａｎ ｂｅ ｄｉｖｉｄｅｄ ｂｙ １０ ｔｈｅｎ ｓａｖｅ； ｃ）ｅｌｓｅ Ｓｅｇｍｅｎｔａｔｉｏｎ（），ＡｎａｐｈｏｒａＲｅｓｏｌｕｔｅ（），ｇｅｔ ｓｅｔ ｏｆ ｅｎｔｉｔｉｅｓ Ａ ＝ ｄ）ｃｏｎｓｔｒｕｃｔ ｒｅｌａｔｉｏｎｓｈｉｐ ｔｒｅｅ（）： 　　　ｗｈｉｌｅ ａｔ ｌｅａｓｔ ｏｎｅ ｗｏｒｄ ｌｅｆｔ ｄｏ 　　　ｇｅｔ ｔｈｅ ｔｙｐｅ ｏｆ ｔｈｅ ｗｏｒｄ； 　　　ｉｆ（ｅｎｔｉｔｙ） ｔｈｅｎ ｍｅｒｇｅ ｅｎｔｉｔｉｅｓ； 　　　ｅｌｓｅ ｉｆ（ｒｅｌａｔｉｏｎ ｉｎｄｉｃａｔｏｒ）ｓａｖｅ； 　　　ｉｆ（ａ ｔｒｉｐｌｅ （ｅｎｔｉｔｙ１，ｅｎｔｉｔｙ２， ｒｅｌａｔｉｏｎ ｉｎｄｉｃａｔｏｒ） ｉｓ ｆｏｕｎｄ） ｔｈｅｎ ｅ）ｅｎｄ ｗｈｉｌｅ； ｏｕｔｐｕｔ； ａｄｄ ｉｎｔｏ ｔｈｅ ｒｅｌａｔｉｏｎ ｔｒｅｅ； ｛ａ１，ａ２，…，ａＮ，｝； 本文采用的实体关系抽取方法避免了滑动窗口抽取过程 以关系作为基本分析单位的社会网络分析方法目前在很 给定的方法能准确地识别出任意两个不同实体之间关系的具 中的高时耗低效率的局限性，能更有效地抽取出实体之间存在 的关系。 通过预先定义的关系类型以及关系指示词词典，本文 体类型。 1畅4　犯罪网络识别 多领域都得到了很好的应用，如人文社科学、经济学、心理学、 政治学等。 系统科学认为结构决定功能，一个复杂系统的拓扑 结构通常决定了该系统所具有的功能和语义特征。 关系图能 很好地表示犯罪网络的拓扑结构，能很清楚地揭示图中实体之 间的关系模式，通过对图中数据进行社会网络分析和发现，能 够挖掘出网络中的核心团体（犯罪子网）和核心人物。 通常犯 罪网络发现采用概念空间、层次聚类、社会化网络分析等方 ［１２，１４］，本文在原有方法的基础上进行改进并提出识别犯罪 子网和核心人物更加有效的方法。 1畅4畅1　犯罪子网发现 为了有效地研究犯罪网络中个体的特性和职责，调查人员 需要分析犯罪网络中的子网，每个子网的组成通常是为了完成 某个特定的任务，这就需要子网成员之间频繁地通信，这为侦 查案件提供了宝贵的材料。 同样，犯罪子网之间通常也需要频 繁地通信，其中暗含某些关系模式，识别出这些关系模式也能 法 ［１５ ～１７］。 聚类分析能有效地找出用相同方法作案的嫌疑犯或识别 第 ２８ 卷 为杜绝网络犯罪提供很好的支持。 目前识别犯罪子网的方法 主要有矩阵置换法和层次聚类法，由于矩阵置换是 ＮＰ 困难问 题，目前多采用层次聚类的方法来挖掘子网结构 出不同的犯罪组织。 层次聚类无须预先设定需要聚类的类别 数，并能够输出层次结构化的聚类结果。 本文研究的犯罪案情 通常包括一个或多个犯罪网络，因此层次聚类方法在分析此类 数据时具有很高的适用性。 层次聚类包括自顶向下和自底向 ［１５］，考虑到在分析犯罪网络过程中需要由犯罪个 体推出整体（犯罪网络） 特性，本文采用自底向上的分析方法 进行聚类。 的关系强度，或关系权重，本文以两点之间的关系强度作为聚 类依据，关系强度（共现次数） 越大，两点之间的距离越小。 具 体的层次聚类过程为： 两个实体节点以某种关系共现的次数被认为是两者之间 上两种方法 ｉｎｉｔｉａｌｉｚｅ： ｃｒｅａｔｅ ａ ｃｌｕｓｔｅｒ ｆｏｒ ｅａｃｈ ｎｏｄｅ ｗｈｉｌｅ ｔｈｅｒｅ ａｒｅ ｔｗｏ ｃｌｕｓｔｅｒｓ， ｔｈｅ ｄｉｓｔａｎｃｅ ｏｆ ｗｈｉｃｈ ｉｓ ｌｅｓｓ ｔｈａｎ ａ ｔｈｒｅｓｈ唱 ｃｕｒｒｅｎｔＣｌｕｓｔｅｒ ＝ａ ｃｌｕｓｔｅｒ； ｆｏｕｎｄ ＝ｆａｌｓｅ； 　ｗｈｉｌｅ ｆｏｕｎｄ ＝＝ｆａｌｓｅ ｄｏ 　ｆｉｎｄ ｔｈｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ Ｎ ｔｏ ｔｈｅ ｃｕｒｒｅｎｔＣｌｕｓｔｅｒ； 　ｉｆ ｉｓ ＮＮ（Ｎ， ｃｕｒｒｅｎｔＣｌｕｓｔｅｒ） ｔｈｅｎ ｍｅｒｇｅ Ｎ ａｎｄ ｃｕｒｒｅｎｔＣｌｕｓｔｅｒ； 　　ｆｏｕｎｄ ＝ｔｒｕｅ； 　ｅｌｓｅ ｃｕｒｒｅｎｔＣｌｕｓｔｅｒ ＝Ｎ： 　ｅｎｄ ｗｈｉｌｅ ｅｎｄ ｗｈｉｌｅ 算法执行的时间复杂度和空间复杂度均为 O（N２），计算 六度分割定理描述了社会网络的连通性质 最近邻采用全连接的方式。 1畅4畅2　六度分割定理和最短路径 ［９，１４］：社会中任 何两个人之间只需要４ 个中介即可建立联系。 换言之，两个地 球人之间５ 跳即达。 该定理是理想假设条件下得出的，研究者 作了大量社会实验，验证了这一定理的普适性。 考虑到犯罪网 络也属于社会化网络，本文设定任意两个犯罪嫌疑人之间最多 有４ 个中介进行联系，即任何两个犯罪嫌疑人之间最短路径长 度不超过５，这个规定有助于提高分析的效率。 在本文中，由于要监视任意两个犯罪嫌疑人之间的联系过 程，等同于网络中任意两个节点之间的最短路径，故采用 Ｆｌｏｙｄ 算法计算网络中任意两点（嫌疑人） 之间的最短距离，该算法 的时间复杂度为 O（N３）。 1畅4畅3　关系分析 关系分析重点在于发现网络节点之间的关系和交互行为， 常被用来识别网络核心人物和子网。 设有一个社会网络 SN， 节点集合 V ＝｛A１，A２，…，An｝，定义如下网络属性： （１） 式（１）表示节点（实体）Ak 的联系度（ｄｅｇｒｅｅ）。 联系度反映点 的活跃程度，n 是网络中的总点数，a（i，k） ＝１ 表示节点 i 和 k ［１５］。 之间直接相连；a（i，k） ＝０ 表示两者之间没有直接相连 CD（k） ＝∑n i ＝１a（i，k） j i ∑n gij（k） CB（k） ＝∑n （２） 通过 Ak 的最短路径数称为 Ak 的绝对中介度（ｂｅｔｗｅｅｎ唱 ｎｅｓｓ），记为 CB（k），描述了节点作为中介联系其他成员的能 力，即节点在网络中与其他节点之间的联系程度。 式（２） 定义 了中介度，其中，gij（k） ＝１ 表示 Ai 和 Aj 之间的最短路径经过 

第 ３ 期 ［１５］。 Ａk 周利娟，等：基于实体关系的犯罪网络识别机制 i ＝１l（i，k） CC（k） ＝∑n －）２／Ｄｅｖ（CD） ＋（CB －CB 基于六度分割定理和最短路径方法 －）２／Ｄｅｖ（CB） ＋ｅ －（Cc －Cc （３） Ak 与网络中所有节点之间的最短路径长度之和称为 Ak 的绝对紧密度（ｃｌｏｓｅｎｅｓｓ），描述该节点控制以自己为中心的小 集团的紧密程度。 －）２／Ｄｅｖ（CD）（４） ｃｏｒｅ ＝ ｅ （CD －CD 本文提出用式（４） 综合考虑三种度的重要性，以此来度量 － 表示节点联系度的平均值；Ｄｅｖ（CD） ＝ 节点的核心度。 其中：CD 表示联系度的平滑系数，对 CB 和 CC 同理。 ∑n i ＝１（CDi －CD）２ 根据式（１） ～（４）的计算内容，得到每个节点的属性值，再 计算各节点的核心度。 1畅4畅4　核心人物识别方法 ＣＮＣＤ 社会化分析方法最初用在社会学研究中，用来分析社会中 因子之间的关系以及交互模式，从而发现潜在的社会结构。 六 度分割理论认为，一个正常有效运转的社会团体，任何两个个 体之间一般不会用多于４ 个中介进行通信；因此，在计算节点 的绝对中介度时，只考虑长度最长为５ 的最短路径而忽略长度 大于５ 的所有路径。 基于六度分割理论的最短路径算法，本文 提出了发现犯罪网络核心人物的算法（ｃｒｉｍｉｎａｌ ｎｅｔｗｏｒｋ ｃｏｒｅ唱 ｆｉｇｕｒｅ ｄｉｓｃｏｖｅｒｙ，ＣＮＣＤ），其要点在于：ａ）赋权值，两个犯罪实体 节点之间的共现频率表示连接权重；ｂ）求最短路径，通过 Ｆｌｏｙｄ 算法找到任意两个节点间的最短路径，并保留距离小于等于５ 的最短路径。 算法主要过程为： ［９］ ａ）根据收集到的电子数据建立犯罪网络； ｂ）采用层次聚类发掘犯罪网络子图，即犯罪子团伙； ｃ）用最短路径和核心度挖掘犯罪子团伙中的核心人物。 ｉｎｐｕｔ： ｃｒｉｍｉｎａｌ ｎｅｔｗｏｒｋ ｖｅｒｔｅｘ： ｅｎｔｉｔｙ（ ｐｅｒｓｏｎ） ｅｄｇｅ： ｒｅｌａｔｉｏｎａｌ ｓｔｒｅｎｇｔｈ Ｋ： ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ／ｓｕｂｇｒｏｕｐｓ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ ｔｏ ｇｅｔ Ｋ ｓｕｂｇｒｏｕｐｓ； ｗｈｉｌｅ ｉ ｆｒｏｍ １ ｔｏ Ｋ ｃｏｒｅ ｆｉｇｕｒｅ ｉ ＝ｔｈｅ ｆｉｒｓｔ ｍｅｍｂｅｒ ｉｎ ｓｕｂｇｒｏｕｐ ｉ； ｌｅｎ ＝ｎｕｍｂｅｒ ｏｆ ｍｅｍｂｅｒｓ ｉｎ ｓｕｂｇｒｏｕｐ ｉ； ｗｈｉｌｅ ｊ ｆｒｏｍ ２ ｔｏ ｌｅｎ 　ｇｅｔ ｄｅｇｒｅｅ ｏｆ ｍｅｍｂｅｒ ｊ； 　ｇｅｔ ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｂｅｔｗｅｅｎ ｍｅｍｂｅｒ ｊ ａｎｄ ｏｔｈｅｒ ｍｅｍｂｅｒｓ ｉｎ ｓｕｂ唱 　　ｗｈｉｌｅ ｊ ｆｒｏｍ １ ｔｏ ｌｅｎ 　　ｇｅｔ ｂｅｔｗｅｅｎｎｅｓｓ ａｎｄ ｃｌｏｓｅｎｅｓｓ ｏｆ ｍｅｍｂｅｒ ｊ； 　　ｗｈｉｌｅ ｊ ｆｒｏｍ １ ｔｏ ｌｅｎ 　　ｇｅｔ ｃｏｒｅ ｖａｌｕｅｓ； 　ｇｅｔ ｃｏｒｅ ｍｅｍｂｅｒｓ； 算法具体实现的结果可以用图２、表４ 加以说明。 ｏｕｔｐｕｔ： ｃｏｒｅ ｍｅｍｂｅｒｓ ｇｒｏｕｐ ｉ； ·１００１· 　　　 犯罪网络挖掘系统，该系统对案件类型没有限制，对每种类型 案件的主要分析过程为：原始数据分析处理（原始语料去噪归 类等）、实体关系识别（构建关系树）、犯罪网络图可视化显示、 犯罪网络分析和发现。 表 ４　图 ２ 中各节点的四度计量 联系度 中介度 紧密度 核心度 节点 A B C D E ２ １ １ １ １ ４ ６ ５ ７ ６ １６ ８ ８ ８ ８ ．４０３ ４３２ ９９ ．３７３ ２８９ ８２ ．４８４ ５４０ ９５ ．３２９ ８７９ ６８ ．３７３ ２８９ ８２ ４ ２ ３ １ ２ 2畅1　系统功能展示 为了检验系统的健壮性、安全性和有效性，本文的实验采 用相关公安部门提供的 １ ５４５ 篇文档，经过去噪，得到有效相 关文档１ ３２１ 篇。 文档格式有 Ｗｏｒｄ、ＨＴＭＬ、ＴＸＴ 等，涉及五种 案例，分别是网络走私犯罪案例、网络聚集性案件相关文档、网 络赌博案例、宾馆同住人员分析和手机联系人频度分析。 在本系统中，案例中出现的实体被抽象为节点，实体之间 的关系被抽象成边，一个犯罪网络就能被抽象成小型的社会化 网络图结构，如图４ 所示。 在走私手机案件中，抽取出的实体有“ 大卡路里”“ 郑志 勇”“ 陈 登 立” “ 张 司 文” “ 赵 一 平” “ 成 达” “１３８９８１６５１９９” “０７３０４９９９８０１３００１４５１０” “ｚｈｅｎｇｚｈｉｙｏｎｇ７６５４＠２１ｃｎ．ｃｏｍ” “ｂｉ唱 ｂｅｒ１２３４＠ｈｏｔｍａｉｌ．ｃｏｍ”。 图４ 中抽取出了网名“ 大卡路里” 以 及正常中文姓名，同时包括案件中涉及的手机号码、银行账号、 电子邮箱等重要的通信信息。 实体关系网络图很清晰地显示 了用户关心的实体和其他实体之间的关系，公安人员能直观地 获取相关线索。 不同于 Ｘｕ 等人 提出的关系图显示方法，本 显示，并直接在网络图中标注每个节点的具体信息，更加清晰 明了。 为验证算法挖掘犯罪网络核心人物的准确性，本文选用案 情丰富的案件作为实验数据，抽取出的实体关系网络如图５ 所 示，系统计算出的节点核心度及其三个分量的结果如表５ 所示。 文开发的关系显示系统中不同的实体采用了不同的图标进行 ［１５］ 由表４ 可知，图２ 中核心度最高的点是 A，因此最核心的节 点应该是 A，这符合实际观察值，由此验证了该算法的有效性。 2　系统实现 为了更直观地验证本文算法的有效性，本文设计并开发了 

计 算 机 应 用 研 究 　 ·２００１· 表 ５　部分人物实体核心度三个分量 实体 联系度 中介度 紧密度 核心度 报，２００３，19（３）：１２０唱１２２． 第 ２８ 卷 算法，该算法有效性在系统的实现过程中得到了强有力的 证明。 为了能更好地服务于公安部门，进一步地研究将定位在实 现更加有效的系统上。 目前的系统虽然能在一定层次上满足 用户的需求，但是数据量大时系统处理时耗仍有一定提高的空 间，笔者将继续研究和探索更好的算法，以期能提高系统分析 处理数据的效率。 参考文献： ［１］ 邓宇琼．网络犯罪 证 据 的 提 取 和 固 定［Ｊ］．中 国 人 民 公 安 大 学 学 ［２］ 车万翔，刘挺，李生．实体关系自动抽取［Ｊ］．中文信息学报，２００５， 19（２）：１唱８． ［３］ 叶正，林鸿飞，苏绥，等．基于支持向量机和语义的人物属性抽取 ［Ｊ］．计算机研究与发展，２００７，44（Ｓ２）：２７１唱２７５． ［４］ 廖先桃．中文命名实体识别方法研究［Ｄ］．哈尔滨：哈尔滨工业大 学，２００６． ［５］ 韩冰，林鸿飞．基于 ＳＶＭ 的人物关系抽取［Ｃ］ ／／第七届中文信息 处理国际会议论文集（ＩＣＣＣ２００７）．武汉：电子工业出版社，２００７： ３３５唱３４１． ［６］ 李向阳，苗 壮．自 由 文 本 信 息 抽 取 技 术［Ｊ］．情 报 科 学，２００４，22 （７）：８１５唱８２１． ［７］ ＣＨＲＩＳＴＩＮＡ Ｇ， ＲＯＢＥＲＴＯ Ｂ， ＣＨＩＡＲＡ Ｄ Ｖ．Ｋｅｒｎｅｌ唱ｂａｓｅｄ ｒｅｌａｔｉｏｎ ｅｘｔｒａｃｔｉｏｎ ｆｒｏｍ ｉｎｖｅｓｔｉｇａｔｉｖｅ ｄａｔａ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ ３ｒｄ ＡＣＭ Ｗｏｒｋ唱 ｓｈｏｐ ｏｎ Ａｎａｌｙｔｉｃｓ ｆｏｒ Ｎｏｉｓｙ Ｕｎｓｔｒｕｃｔｕｒｅｄ Ｔｅｘｔ Ｄａｔａ．Ｂａｒｃｅｌｏｎａ， Ｓｐａｉｎ：［ｓ．ｎ．］，２００９：９３唱１００． ［８］ ＱＩＡＮ Ｌｏｎｇ唱ｈｕａ， ＺＨＯＵ Ｇｕｏ唱ｄｏｎｇ， ＫＯＮＧ Ｆａｎｇ， et al．Ｅｘｐｌｏｉｔｉｎｇ ｃｏｎｓｔｉｔｕｅｎｔ ｄｅｐｅｎｄｅｎｃｉｅｓ ｆｏｒ ｔｒｅｅ ｋｅｒｎｅｌ唱ｂａｓｅｄ ｓｅｍａｎｔｉｃ ｒｅｌａｔｉｏｎ ｅｘ唱 ｔｒａｃｔｉｏｎ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ ２２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａ唱 ｔｉｏｎａｌ Ｌｉｎｇｕｉｓｔｉｃｓ．２００８：６９７唱７０４． ［９］ 孙晓玲，林鸿飞．人际网络关系抽取和结构挖掘［Ｊ］．微电子学与 计算机，２００８，25（９）：２３３唱２３６． ［１０］ 于满泉．面向人物追踪的知识挖掘研究［Ｄ］．北京：中国科学院， ［１１］ 张晓燕，王挺，陈火旺．命名实体识别研究［Ｊ］．计算机科学，２００５， 32（４）：４４唱４８． ［１２］ ＨＡＮＹ Ｈ， ＡＨＭＥＤ Ｈ， ＳＡＲＡ Ｎ．Ｇｒａｐｈ ｂａｓｅｄ ｓｅｍｉ唱ｓｕｐｅｒｖｉｓｅｄ ａｐ唱 ｐｒｏａｃｈ ｆｏｒ ｉｎｆｏｒｍａｔｉｏｎ ｅｘｔｒａｃｔｉｏｎ［Ｃ］ ／／Ｐｒｏｃ ｏｆ Ｗｏｒｋｓｈｏｐ ｏｎ Ｔｅｘｔ唱 Ｇｒａｐｈｓ， ａｔ ＨＬＴ唱ＮＡＡＣＬ．２００６：９唱１６． ［１３］ ＬＩ Ｗｅｎ唱ｊｉｅ， ＺＨＡＮＧ Ｐｅｎｇ， ＷＥＩ Ｆｕ唱ｒｕ， et al．Ａ ｎｏｖｅｌ ｆｅａｔｕｒｅ唱ｂａｓｅｄ ａｐｐｒｏａｃｈ ｔｏ ｃｈｉｎｅｓｅ ｅｎｔｉｔｙ ｒｅｌａｔｉｏｎ ｅｘｔｒａｃｔｉｏｎ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＡＣＬ唱０８： ＨＬＴ．２００８：８９唱９２． ［１４］ 唐常杰，刘威，温粉莲，等．社会网络分析和社团信息挖掘的三项 探索———挖掘虚拟社团 的 结 构、核 心 和 通 信 行 为［Ｊ］．计 算 机 应 用，２００６，26（９）：２０２１唱２０２３． ［１５］ ＸＵ Ｊ Ｊ， ＣＨＥＮ Ｈ Ｃ．ＣｒｉｍｅＮｅｔ ｅｘｐｌｏｒｅｒ：ａ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｃｒｉｍｉｎａｌ ｎｅｔ唱 ｗｏｒｋ ｋｎｏｗｌｅｄｇｅ ｄｉｓｃｏｖｅｒｙ［Ｊ］．ACM Trans on Information Sys唱 tems，２００５，23（２）：２０１唱２２６． ［１６］ ＳＴＡＮＬＥＹ Ｗ， ＫＡＴＨＥＲＩＮＥ Ｆ．Ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ａｎａｌｙｓｉｓ：ｍｅｔｈｏｄｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．Ｃａｍｂｒｉｄｇｅ：Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，１９９４． ［１７］ ＧＩＲＶＡＮ Ｍ，ＮＥＷＭＡＮ Ｍ Ｅ Ｊ．Ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｓｏｃｉａｌ ａｎｄ ｂｉ唱 ｏｌｏｇｉｃａｌ ｎｅｔｗｏｒｋ［Ｊ］．Proc of the National Academy of Sciences， ２００２，99（１２）：７８２１唱７８２６． ２００６． 大卡路里 思乡之月 郑勇 林国 １ １ １ １ １ １ １ ２ 霍东才 大 ｌａｎｇ ｍｅｉｙｏｕ 张思文 ３０ ３ ４ ３ ２ ３ ３ ２７ ２９ ５２ ７５ ８７ ８８ ７７ ７７ ３２ ６３ １７ １５ １４ １４ １３ １３ ２８５ ．５１７ ２１２ ８１ ．４２２ ８１０ ８４ ．４２１ ５３１ ３７ ．３９２ ４４１ １２ ．３９３ ８１７ ５７ ．４２２ ５２９ ３７ ．４２２ ５２９ ３７ ．００４ ９８４ ６０ 　　公安操作人员设定的犯罪子网个数决定了抽取核心人物 的个数，本例中犯罪子网个数为 ２，抽取出的网络核心人物也 为２。 根据上述的计算结果，犯罪网络中的主要核心人物是 “大卡路里”和“霍东才”，这与公安部门人为分析的结果一致， 因此可以认为，本文设计和开发的系统能有效地协助公安部门 办案，提高破案效率。 2畅2　系统特点 系统的主要功能是分析处理海量案情数据，抽取实体关系 网络并可视化显示，本文中设计并实现的系统主要特点包括以 下几个方面： ａ）分析非结构化的数据并抽取出实体以及实体类型； ｂ）有效地抽取出实体之间的关系并用可视化的方法显示； ｃ）用层次聚类的方法识别出网络中的子图（犯罪子网络）； ｄ）根据节点核心度计算网络中核心人物和其他核心实体。 实际系统能分析非结构化的数据，对不同类型的数据具有 很高的适应性和兼容性，能在很大程度上协助公安人员办案， 取得了较高的用户满意度，得到了公安部门的肯定，能提高公 安部门破案效率，具有很强的实用价值。 3　结束语 尝试在将数据挖掘和信息抽取技术应用到抽取海量电子案情 为弥补目前我国在抽取电子破案信息上研究的不足，本文 信息方面进行探索式的研究，并开发了相应的系统。 首先将电 子证据按照数据格式进行分类，再将分类好的数据按照具体特 点进行分析，分析过程主要包括分词、指代消解、关系指示词分 析、实体关系抽取、犯罪子网识别和核心人物挖掘。 本文研究 和核心人物。 考虑到公安部门侦查案件的特点，本文定义了八 种实体关系，实验证明，该八种实体关系能全面涵盖犯罪案情 中所有的有用实体。 在此基础上，再根据预先定义关系类型抽 取出关系，并用可视化系统显示；同时基于六度分割理论，利用 层次聚类和 Ｆｌｏｙｄ 算法提出识别犯罪子网和核心人物的 ＣＮＣＤ 重点是定义并抽取实体关系以及挖掘关系网络中的犯罪子网