（计算机应用技术专业论文）基于案例的刑事审讯辅助决策算法研究及应用.pdf

大连理工大学硕士学位论文 摘要 刑事审讯是公安系统中最重要、最复杂、涉及范围最广的任务之一。审讯是侦查人员 为揭露案件真相，证实犯罪和查明犯罪人，依法就案件事实和其他案件有关的问题以言词 的方式对犯罪嫌疑人进行提问，以获取真实供述或辩解的一项侦查行为。审讯工作的基本 研究对象是受审查人的心理活动和他们在不同审讯阶段的行为表现。这一系统化的知识隐 藏在公安系统中大量的犯罪案例信息之中。现有的审讯过程主要基于侦查人员的先验知 识，浪费大量的人力和物力，存在误判、漏判的现象，并且存在因为处理时间缓慢而导致 贻误破案时机的情况。另外目前在该领域，数据分散在各部门而各个部门的数据又相互独 立处理，需要人工建立联系，效率低下，缺乏智能化的统计与分析功能。 本文以大连市公安局项目刑事审讯辅助决策支持系统为研究背景，详细介绍了数据挖 掘技术在犯罪案例信息中的应用，并从三个不同的方面进行研究探讨。 首先对粗糙集知识进行学习，运用粗糙集知识对犯罪案例信息中连续值属性进行离散 化。使用这种方法能够充分考虑各个连续值属性之间的影响，可以有效地减少不合理和多 余的划分点。 在利用粗糙集知识将连续值属性离散化后，再运用贝叶斯网络的相关知识给出部分刑 事审讯案例的贝叶斯网络模型，包括个性心理特征分类模型和审讯对策方式模型。 最后运用关联分析方法对不同案例进行分析，实现了对大量的犯罪案例信息进行数据 挖掘，找出大量案例记录数据中的潜在规律，并生成关联模型。此外，刑事犯罪案例的增 加是迅猛飞速的，针对这一事实运用关联模型的快速增量更新方法进行模型的更新。 本文运用知识发现中的不同方法对公安系统犯罪案例信息进行挖掘，得到了部分案例 合理的数据挖掘模型。可以用于度量案例中各种因素对于特定案例所起的作用，给出对于 特定案例审讯的可行性审讯方案，提高审讯办案过程的准确率和效率。模型设计了开放的 问题定义、挖掘、推理模块，可以对问题进行分析研究，具有一定的通用性和扩展性，通 过试验测试，取得了和实际情况接近的效果。 关键词：刑事审讯；数据挖掘；粗糙集；贝叶斯网络；关联规则 大连理工大学硕士学位论文 r e s e a r c ha n da p p l i c a t i o ni nc r i m i n a li n t e r r o g a t i o na s s i s t a n td e c i s i o n a l g o r i t h m sb a s e d o nc a s e s a b s t r a c t c r i m i n a li n t e r r o g a t i o ni st h em o s ti m p o a a n ta n dc o m p l e xt a s ko fp o l i c es y s t e m t h r o u g h a s k i n gs u s p e c t sf o rt h ec r i m i n a lr e a l i t ya n dc o r r e l a t i v eq u e s t i o n si sr e v e a l i n gt h et r u t h ，p r o v i n gt h e c r i m i n a lr e a l i t y ，f i n d i n gs u s p e c t s t h ef u n d a m e n t a lr e s e a r c ho b j e c to ft h ei n t e r r o g a t i o nw o r ki s s u s p e c t s 。p s y c h o l o g i c a la c t i v i t ya n db e h a v i o rp e r f o r m a n c ei 1 1t h ed i f f e r e n ti n t e i r o g a f i o n a ls t a g e t h i ss y s t e m a t i z e dk n o w l e d g eh i d e si nt h eh u g ec r i m ec a s ei n f o r m a t i o nd e p o s i t e di nt h ep o l i c e s y s t e m c u n e n ti n t e r r o g a t i o np r o c e s sc o s t sm a s s i v em a n p o w e ra n dr e s o u r c e s ，h a st h ep h e n o m e n o n o fw r o n g j u s t i c e ，a n ds o m e t i m e sc a u s e st od e l a yt h ei n v e s t i g a t i o no p p o r t u n i t ys i t u a t i o nb e c a u s eo f t h ep r o c e s st i m ei sl o n g m o r e o v e r , a tp r e s e n ti nt h i sd o m a i n , t h e r ea r em a n ys c a t t e r e ds e r v i c ed a t a , w h i c hh a sb e e nd i s t r i b u t e di nd i f f e r e n td e p a r t m e n t s ；d e p a r t m e n t sd a t ai sp r o c e s s e di n d e p e n d e n t l y a n dt h er e l a t i o n sn e e dt ob em a n u a l l ye s t a b l i s h e d , s ot h ee f f i c i e n c yi sl o wa n dd a t al a c k st h e i n t e l l e c t u a l i z e ds t a t i s t i c sa n da n a l y s i s t h i sp a p e rt a k e st h er e s e a r c hb a c k g r o u n do fd a l i a np o f i c ep r o j e c t c r i m i n a li n t e r r o g a t i o n a s s i s t a n td e c i s i o ns u p p o r ts y s t e m t h i sp a p e ri l l u s t r a t e sd a t am i n i n gt e c h n o l o g yi nt h ec i i m i n a l i n t e r r o g a t i o nc a s e s ，i n c l u d i n gd i s c u s s i n gf r o mt h r e ed i f f e r e n ta s p e c t s f i r s t l y ，t h i sp a p e rr e s e a r c hal o to ft e c h n o l o g i e sa b o u tr o u g hs e ta n da p p l i e sr o u g hs e tt o a t t r i b u t ed i s c r e t eo f c r i m i n a ic a s e s t h i sm e t h o ds u f f i c i e n t l yt h i n k sc o r r e l a t i v ea t t r i b u t e si n f l u e n c e s a n da v a i l a b l yr e d u c e su n r e a s o n a b l ea n dr e d u n d a n tp a r t i t i o n a f t e ra t t r i b u t ed i s c r e t e ，t h ep a p e rg i v e st h eb a y e s i a nn e t w o r km o d e la b o u tp a r t i a lc r i m i n a l i n t e i r o g a t i o nc a s e sb a s e do nt h ec o r r e l a t i v et e c h n o l o g i e so fb a y e s i a nn e t w o r k , i n c l u d i n gc r i m e s u s p e c tp s y c h o l o g yc h a r a c t e r i s t i cc l a s s i f i c a t i o nm o d e la n di n t e r r o g a t i o ns t r a t e g ym o d e l f i n a l l y , t h i sp a p e ra n a l y s i sa l o to fc r i m i n a lc a s e sb yu s i n gt h ea s s o c i a t i o nr u l e s ，f i n i s h e sd a t a m i n i n ga p p l i c a t i o ni 1 1 c r i m i n a lc a s e s ，h a st h ep o t e n t i a lr u l e sa b o u td a t ar e c o r d sa n db u i l d st h e a s s o c i a t i o nm o d e l s i ta p p l i e st of i n d i n gt h er u l e sf r o mal o to fc o r r e l a t i v ec a s e sa n dp u t sf o r w a r d f e a s i b l ei n t e r r o g a t i o np r o j e c t st op e o p l e i ti m p r o v e st h ei n t e r r o g a t i o na c c u r a c ya n de f f i c i e n c y b e c a u s eo ft h ep r o l i f e r a t i o no fc 打m i n a lc a s e s ，t h ep a p e rb r i n g sf o r w a r da ni n c r e m e n t a lu p d a t i n g a l g o r i t h mf o rm i n i n ga s s o c i a t i o n r u l e s t h ep a p e ra p p l i e sd i f f e r e n tt e c h n o l o g i e si nk n o w l e d g ed i s c o v e r yt ot h ed a t am i n i n gi 1 1t h e c r i m i n a li n t e r r o g a t i o nc a s e sa n dg e t sr e a s o n a b l ed a t am i n i n gm o d e l t h em o d e li sc o m p o s e do f o p e n i n gp r o b l e md e f m i t i o n ，d a t am i n i n ga n dc o n s e q u e n c e i th a su n i v e r s a l i t ya n de x p a n s i b i l i t yt o 茎堡垦! 墨王墨型塑型至! 塑型堡箜竺些婴塞墨壁旦 a n a l y z e a l lk i n do fq u e s t i o n s t h er e s u l t so f e x p e r i m e n th a v eo b t a i n st h ep o l i c ep m f e s s i o n a l s a p p r o v a l k e yw o r d s ：c r i m i n a li n t e r r o g a t i o n ；d a t am i n i n g ；r o u g hs e t ；b a y e s i a nn e t w o r k ； a s s o c i a t i o nr u l e s 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用规 定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：跟! l ：重函 导师签名 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或者其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究 所做的贡献均已在论文中做了明确的说明并表示t n 意。 大连理工大学硕士学位论文 引言 随着数据库技术的广泛应用，各行各业都积累了大量有用数据。这些数据所隐含的内 在联系可能就是有价值的知识，如何发现、提取这些知识和规则并加以利用就成了当务之 急。数据挖掘就是从大量的数据中提取隐含的、未知的、对决策有潜在价值的知识和规则 的过程。 刑事审讯是指侦查人员为了进一步查明和证实犯罪事实，依照刑事诉讼法的有关规 定，对犯罪嫌疑人进行讯问的一种侦查行为。由于各种案件的复杂性、犯罪嫌疑人的多样 性、审讯人员的素质差异等因素，使刑事审讯成为最重要、最复杂、涉及范围最广的公安 工作任务之一。现有的审讯过程常常浪费了大量人力和物力，并存在一定的偏差，因此迫 切需要建立一套以现代信息技术为基础，用于辅助审讯人员的辅助决策支持系统。当今计 算机技术特别是人工智能、专家系统、数据挖掘等技术的飞速发展为实现辅助决策打下了 坚实的基础。本文主要是对实际案例中犯罪嫌疑人、时间、地点、犯罪原因结果等进行 科学系统的数据分析，运用数据挖掘算法找出大量案例的隐含关联，并将结果用于辅助决 策。 目前在国内外，将计算机处理应用到犯罪相关领域的实例非常少。美国政府与其国内 大学合作，对犯罪相关数据等进行研究，成功开发了c o p l i n k 系统，该系统使用代理技 术和数据挖掘技术对分散在国内各个部门的相关数据进行分析处理【2 】。国内对该领域的研 究刚刚起步，目前宁波大学与公安部门进行合作研究【3 j ，方法是：使用关联分析和序列分 析进行尝试性数据挖掘，使用决策树对犯罪信息进行分类研究。 对知识发现、数据挖掘等相关知识进行了深入的学习研究，主要涉及到三个方面：粗 糙集、贝叶斯网络和关联规则。相关的主要工作有： ( 1 ) 对知识发现和数据挖掘技术进行了深入的研究，针对刑事审讯案例的特点着重研 究了粗糙集、贝叶斯网络和关联规则。 ( 2 ) 针对粗糙集，提出运用粗糙集知识对犯罪案例信息中连续值的属性进行离散化。 ( 3 ) 对犯罪案例信息中连续值属性进行离散化后，再运用贝叶斯网络的相关知识给出 部分刑事审讯案例的贝叶斯网络模型，实现了对审讯过程的辅助支持。 ( 4 1 关联模型的生成及增量更新，特别是针对激增的刑事犯罪案例这一事实提出了一 个关联模型的快速增量更新方法。 本文首先介绍了数据挖掘及知识发现等相关基础知识，对数据挖掘的概念、分类、方 法以及发展趋向作了简要概述。第二部分是对刑事审讯这一问题进行描述，指出基于案例 的辅助决策在刑事审讯中的重要性。第三部分是学习了粗糙集的基本概念、特点、数学描 张恒昆：基于案例的刑事审讯辅助决策算法研究及应用 述，并对本文所用到的属性离散化算法进行了深入的阐述。接下来描述了在贝叶斯网络研 究方面的工作，对贝叶斯网络中用到的结构学习方法、参数学习方法和推理算法进行了分 析，其中实现的贝叶斯网络结构学习算法是一种贝叶斯网络学习的启发式算法，参数学习 的算法是期望最大化算法，推理算法实现的是g i b b ss a m p l i n g 方法，并进行了实验数据测 试，给出了部分刑事审讯相关的贝叶斯网络模型，最后对结论进行了分析和总结。最后一 部分是研究了关联规则的基本概念并用关联分析中的a v d o l i 算法对案例记录进行试验性分 析，从中发现不同案例间隐含的关联性信息。最后针对犯罪案例激增这一事实并利用关联 模型生成过程所保留的中间结果( 支持度) 用快速增量更新方法进行关联模型的增量更新， 得到更新的关联模型。 大连理工大学硕士学位论文 1 基础知识 1 1 数据挖掘技术 数据挖掘( d a t am i n m 曲的实质是一种发现知识的应用技术，是从大量的、不完全的、 有噪声的、模糊的、随机的原始数据中，提取隐含在其中的、人们事先不知道的、但又是 潜在有用、可信、新颖的信息和知识的过程。从广义角度讲数据、信息是知识的表现形 式，但在数据挖掘中更多把概念、规则、模式、规律和约束等看作知识。原始数据可以是 结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据， 甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的或非数学的、演绎的或 归纳的。发现的知识可以被用于信息管理、查询优化、决策支持、过程控制等。总之，数 据挖掘是- - f q 广义的交叉学科，它的发展和应用涉及到不同的领域，尤其是数据库、人工 智能、数理统计、可视化、并行计算【j 】等。 数据挖掘也被称为数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 6 ，对于 它的研究主要基于三大技术支柱，包括数据库、人工智能和数理统计。图1 1 简要描述了 数据挖掘技术的形成过程。数据库理论的发展促成了数据仓库的形成，人工智能的发展促 进了机器学习的进步，同时这些技术与传统的数理统计理论的结合，最终促迸了数据挖掘 的产生。 图i ，l 数据挖掘的形成 f i g 1 1d a t am i n i n gf o r m a t i o n 1 1 1 数据挖掘的任务和步骤 数据挖掘的任务就是利用各种分析工具在海量数据中发现模型和数据之间的关系。在 实际应用中，可分为：分类、聚类、关联规则发现、序列模式发现、孤立点分析等。数据 挖掘的一般的步骤是同：采样；特征探索、分析和预处理；问题明确化、数据调整和技术 张匾昆：基于案例的刑事审讯辅助决策算法研究及应用 选择；模型的研发、知识的发现；模型和知识的综合解释、评价。数据挖掘的整个流程是 反复进行的，需要不断优化和逼近真实、正确的情况。 数据挖掘系统体系构成 8 1 ： 典型的数据挖掘系统的体系构成中，数据库、数据仓库或者是其他一些信息存储媒介 为数据挖掘的工作对象；服务器主要是响应数据挖掘引擎的请求，提取相应的数据；领域 知识库主要用来指导挖掘的过程，以及用来评价挖掘出来的候选模式；数据挖掘引擎是整 个系统的核心部分，可以由以下模块组成：分类模块、关联规则模块、聚类分析模块、时 序模块和异常分析模块等。 模式评价模块主要是根据一定的度量标准来与数据挖掘模块交互，以使数据挖掘向着 我们感兴趣的方向进行，往往越是高效的数据挖掘系统这种交互影响的程度越高；图形用 户界面主要是为方便用户与数据挖掘系统的交互：由用户提出挖掘任务、指定重要的挖掘 参数以及由当前返回的结果指导进行更进一步的挖掘工作。 此外，作为数据挖掘准备工作的数据离散化、数据变换、数据清洗和数据挖掘结果的 可视化显示以及挖掘结果的评估等技术也属于数据挖掘研究的范畴。 1 1 2 数据挖掘方法和技术 数据挖掘方法有多种，其中比较典型的有分类分析、聚类分析、相关性分析、偏差分 析、建模、可视化【1 9 1 。 ( 1 ) 分类分析 分类分析提出一个分类函数或分类模型，该模型能把数据库中的数据项映射到给定类 别中的一个。要构造分类模型，需要一个训练样本数据集作为输入，训练集由一组数据库 记录或元组组成，每个元组包含一些字段值，又称“属性”或“特征”，这些字段和测试 集中记录的字段相同。另外，每个训练样本记录有一个类别标识。分类目标是分析训练集 中的数据，利用数据中能得到的特征，为每一类建立一个除当的描述或模型，然后根据这 些分类描述对测试数据进行分类或产生更恰当的描述。可以举一个简单的例子，基于债务 水平、收入水平和工作情况，可对给定用户进行信用风险分析。其中债务情况是最重要的 属性，公司根据债务程度将用户分成三类：高债务、一般债务、无债务，并且类别标记已 赋给了各个记录。分类分析就是分析该数据库的记录数据，对每个债务等级做出准确描 述，如“债务记录良好的客户是指那些年收入在5 万元以上，年龄在3 5 4 5 岁之间的人 士”，然后根据这些描述对其它具有相同属性的数据库记录进行分类。 在分类分析中，分类模型的构造方法有统计方法、决策树、神经网络方法及机器学习 方法等。统计方法包括贝叶斯法和非参数法f 近邻学习或基于事例的学习) ，对应的知识表 示为判别函数和原型事例。神经网络方法主要是多层前向神经网络的误差反向传播( e r m r 大连理工大学硕士学位论文 b a c kp r o p a g a t i o n ，b p ) 算法【埘，用模型表示是前向反馈神经网络模型，该算法的实质是一 种非线性的判别函数。机器学习方法包括决策树法和规则归纳法，前者对应的表示是决策 树或判别树，后者则一般为产生式规则。另外，近年来又出现了一种称为粗糙集( r o u g h s e o 的新的理论方法，它将知识表示为产生式规则。 f 2 ) 聚类分析 聚类与数据挖掘中的分类不同，在分类模块中，对于目标数据库中存在哪些类这一信 息我们是知道的，我们要做的就是将每一条记录分别属于哪一类标记出来；与此相似但又 不同的是，聚类是在预先不知道目标数据库到底有多少类的情况下，希望将所有的纪录组 成不同的类或者说“聚类”( c l u s t e r ) ，并且使得在这种分类情况下，以某种度量为标准的 相似性，在同一聚类之间最小化，而在不同聚类之间最大化。事实上，聚类算法中一大类 算法的相似性都是基于距离的，而且由于现实数据库中数据类型的多样性，关于如何度量 两个含有非数值型字段的记录之间的距离的讨论有很多，并提出了相应的算法。在很多应 用中，由聚类分析得到的同一个聚类中的成员都可以被统一看待。聚类分析的算法可以分 为以下几大类：分裂法、层次法、基于密度的方法、基于网格的方法和基于模型的方法 等。 聚类的用途是很广泛的。在商业上，聚类可以帮助市场分析人员从他们的消费者数据 库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯；在生物 学中，它可以被用来辅助研究动、植物的分类，可以用来分类具有相似功能的基因，还可 以用来发现人群中的些潜在的结构等等；聚类还可以用来从地理数据库中识别出具有相 似土地用途的区域：可以从保险公司的数据库中发现汽车保险中具有较高索赔概率的群 体；还可以从一个城市的房地产信息数据库中，根据房情、房价及地理位置分成不同的 类：还可以用来从万维网上分类不同类型的文档等。同时，聚类分析作为数据挖掘中的一 个模块，它既可以作为一个单独的工具以发现数据库中数据分布的一些深入的信息，并且 概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；聚类分析 也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。 聚类分析是一个具有很强挑战性的领域，它的一些潜在的应用对分析算法提出了特别 的要求，下面列出一些典型的要求： 可伸缩性：这里的可伸缩性是指算法要能够处理大数据量的数据库对象，比如处 理上百万条纪录的数据库。这就要求算法的时间复杂度不能太高，最好当然是多项式时间 的算法。值得注意的是，当算法不能处理大数据量时，用抽样的方法来弥补也不是一个好 主意，因为这通常导致歪曲的结果。 处理不同字段类型的能力：算法不仅要能处理数值性的字段，还要有处理其它类 张恒昆：基于案例的刑事审讯辅助决策算法研究及应用 型字段的能力，例如：布尔型、枚举型、序数型以及混合型等。 发现具有任意形状的聚类的能力：很多聚类分析算法采用基于欧几里德距离的相 似性度量方法，这一类算法发现的聚类通常是一些球状的、大小和密度相近的类，可以想 到，现实数据库中的聚类可以是任意的形状，甚至是具有分形维度的形状，故要求算法有 发现任意形状的聚类的能力。 输入参数对领域知识的弱依赖性：很多聚类算法都要求用户输入一些参数，例如 需要发现的聚类数，结果的支持度、置信度等，聚类分析的结果通常都对这些参数很敏 感，但另一方面，对于高维数据，这些参数又是相当难以确定的。这样就加重了用户使用 这个工具的负担，使得分析的结果很难控制。一个好的聚类算法应该针对这个问题，给出 一个好的解决方法。 能够处理异常数据：现实数据库中常常包含有异常数据，或者数据不完整，缺乏 某些字段的值，甚至是包含错误数据的现象，有一些聚类算法可能会对这些数据很敏感， 从而导致错误的分析结果。 结果对输入记录顺序的无关性：有些分析算法对纪录的输入顺序是敏感的，也即， 对同一个数据集，将它以不同的顺序输入到分析算法，得到的结果会不同，这是我们不希 望的。 处理高维数据的能力：一个数据库或者数据仓库都有很多的字段或者维，一些分 析算法在处理维数比较少的数据集时表现不错，例如两、三维的数据；人的理解能力也可 以对两、三维数据的聚类分析结果的质量做较好的判别，但对于高维数据就没有那么直观 了。所以对于高维数据的聚类分析是很具有挑战陛的，特别是考虑到在高维空间中，数据 的分布是极其稀疏的，而且形状也可能是极其不规则的。 增加限制条件后的聚类分析能力：现实的应用中总会出现各种其它限制，我们希 望聚类算法可以在考虑这些限制的情况下，仍有较好的表现。 结果的可解释性和可用性：聚类的结果最终都是要面向用户的，所以结果应该是 容易解释和理解的，并且是可应用的。这就要求聚类算法必须与一定的语义环境，语义解 释相关联。领域知识是如何影响聚类分析算法的的设计是很重要的一个研究方面。 常见的几大类聚类分析算法的基本思想p 1 l j ： 分裂法( p a r t i t i o n i n gm e t h o d s ) ：给定一个有个元组或者纪录的数据集，分裂法将 构造k 个分组，每一个分组就代表一个聚类，k o 当且仅当卜 。n z a ： ( 3 ) ；( x ) 旬当且仅当 x 。n x = o 。 显然有口；( x ) f o ，1 。这里的隶属关系是根据已有的分类知识客观计算出来的，可以 被解释为一晕中条件概率，能够从全域上的个体加以计算，不是主观给定的i “。 知识的粒度性是造成使用已有知识不能够精确的表示某些概念的原因。这就产生了关 于不确定的“边界”思想。粗糙集理论中的模糊性就是一种基于边界的概念，即一个不精 确的概念具有模糊的不可被明确划分的边界。为刻画模糊性，每个不精确概念由一对称为 上近似与下近似的精确概念来表示。因此模糊和不确定性在此有了联系，即模糊性是由不 确定性来定义的。一般的，在给定的近似空间中，并非所有的对象子集都可以用给定的知 识来表示成概念，这样的子集就认为是粗糙集( 即不精确的或近似的概念) 。但是，粗糙集 可以通过两个精确的概念( 上近似和下近似) 来粗糙的定义，这就使我们可以精确的讲述不 确定的概念。另外，用隶属函数、上近似和下近似还可以定义粗糙集的包含关系与相等关 系。 属性离散化算法也属于数据挖掘的方法。离散化算法可以分为无监督离散化算法和有 监督离散化算法两类。国内外学者针对连续属性的离散化，已提出许多方法，比较著名的 有等距离划分方法、等频率划分方法、统计检验方法、信息熵方法、m d 方法和基于聚类 的方法等，这些算法都可归结为利用选取的断点对连续属性构成的空间进行划分，得到有 限个区域，并用数字对每个区域进行标号。目前已经证明了连续属性的最优划分问题是 卜田h a r d 问题。根据公安局刑事审讯系统的库结构的特点，表中离散化属性占有绝大部 分。又因为本文所研究的贝叶斯网络算法处理的是离散化变量，所以需要对非离散化属性 进行离散化处理，本文采用粗糙集理论对连续属性进行离散化。 3 2 改进的属性离散化算法 3 2 1 基本概念 定义1 知识表示系统s = ( u ，a ) ，u = x t ，屯，屯，) ，u 为非空的有限集论域，a 为非空的属性有限集。 定义2 令s = ( u ，爿) 为一知识表示系统，口4 ，定义b 不可分辨二元关系为 i n d ( 回，即d r d ( b ) = ( 工，y ) u 2 ，v b e b ，b ( x ) = 6 ( y ) ，6 为元素x 在属性曰上的值。 大连理工大学硕士学位论文 定义3 令s = f u ，a ) 为一知识表示系统，z u ，丑4 ，定义石的下近似为 且倒= 工：( 工u ) n ( x l n d 俐盖) ) 为。定义b + 御= z ：( x e u ) n ( 卜】。例n x g ) ) 为z 的上近似。 定义4 令s = f 矾彳) 为一知识表示系统，其中c ，d a ，c v d = a ，且曰c c ，定义 p o s 。( d ) = v 且( x ) ：z d ( d ) 为d 的b 正域a 定义5 令s = f u ，a ) 为一知识表示系统，其中c ，d c a ，c v d = a ，且b c c ，定义 b 与d 之间的依赖度定义为七= c a r d ( p o 岛( d ) ) c a r d ( u ) ，若k = 1 ，则称知识占完全依赖 于知识d ，若k = 0 ，则知识b 与知识d 完全独立，若o k = k ，转到6 ) ，否则若七( c ，d ) k ，对所有d = 1 ，2 3 m ，令m d = m d + 1 ，转到2 ) ( 6 ) 初值d = 1 ； ( 7 ) 对第d 维属性进行减类，即令m d = m d 一1 ，重新计算k ( c ，d ) ，若k ( c ，d ) 不变， 令m d 为该属性的新类数，若k f c ，d ) 变小，则类数仍保持以前的m d ，即m d = m d + l ； ( 8 ) 令d = d + l ，返回7 ) ，直到d = ，l ； ( 9 ) 返回6 ) ，直到各条件属性不能再减类或是属性对应的m d = 2 为止。 此算法由增类和减类两部分组成，首先增类，经过排序的各条件属性使用离差平方和 ( 其余方法也可1 的系统聚类法进行聚类，同时用依赖度k 进行检验，如果满足设定的k 值，增类停止，否则继续。然后减类，对于各条件属性进行减类，如果减类后仍满足属性 依赖度k 则继续减类直到计算出的依赖度小于k 。此算法进行分类时充分考虑了其它属性 的影响，减少了不合理的和多余的划分点的影响。但是该算法对属性的选择顺序有敏感 性，所以要将属性按照重要性进行排序。对于属性的重要性要在这里是依照先验规则或经 验。可以采取不同的顺序，多次进行离散化，以取得最好的分类。 3 3 审讯案例数据测试 表31 决策属性表 t a b 3 1d e c i s i o na t 扛i b u t e st a b l e 大连理工大学硕士学位论文 首先根据先验知识对属性进行排序，重要的属性放在前面。如表3 1 所示。a 。，a ：为 条件属性，d 为决策属性( 一般情况下都是离散的) ，其中条件属性的重要性由a 。到a ：递 减。a l 为年龄，a 2 为犯罪时间，d 为案件类型。 表3 2 分为3 类 t a b 3 2t h r e ed a s s e st a b l e 表3 3 离散结果 t a b3 3t h er e s u l t st a b l e 张恒昆：基于案例的刑事审讯辅助决策算法研究及应用 首先将所有条件属性值划分成两类，计算k ( c ，d 1 _ 0 7 8 ，继续将条件属性增至3 类， 如表3 2 所示。 计算k ( c ，d ) = 1 满足预先设定的减类条件k ，进行减类，最后得到分类数，- 2 ， m ，- 3 ，见表3 3 所示。 算法分类时充分考虑了年龄和犯罪时间这两个属性之间的影响，减少了不合理的和多 余的划分点的影响。从结果看分类的结果不是特别理想，存在误差，这可能是因为只有年 龄和犯罪时间两个连续值属性不足以决策出案件类型，需要其它一些属性值，例如f 教育程 度、性格等1 ，这里只是对这两个连续值属性进行离散化。 大连理工大学硕士学位论文 刑事审讯案例的贝叶斯网络分析 4 1 贝叶斯网络描述与刑事审讯 4 1 1 贝叶斯网络的数学描述 假定有随机变量集合k = k ，k ，k ，u 表示k 的取值，表达式 p ( 嵋= h ，k = i ：2 ，k = 唯) 表示一个联合概率，即变量k ，k ，圪的值分别是v 。，v ：，k 时 的概率。从理论上讲，给定一个随机变量集合的完全联合概率函数，就能计算出所有边缘 概率和更低阶的联合概率。但是当有一个很大的随机变量集合时，指定所有联合概率或更 低阶联合概率的任务就难于处理了。但是，在大多数应用中，联合概率都满足一定的条 件，这些条件使得对它们的指定和计算变得可行。 可以按照一个条件概率来表达一个联合概率，其一般形式为： p ( k ，k ) 2 珥p ( k ，k ) ( 4 1 ) 式( 4 1 ) 通常称为链规则1 9 1 。 贝叶斯网络采用图形化的网络结构直观的表达变量的联合分布及条件独立性，这对概 率推理是非常有用的，因为贝叶斯网络表示的条件独立能大量节约概率推理计算。 一个贝叶斯网络是一个有向无环图( d i r e c c e da _ c y c l i cg r a p h ，d a g ) ，有代表变量的节点 及连接这些节点的有向边构成。图4 1 是一个简单的贝叶斯网络示例( 略去了条件概率) 。 图4 1 贝叶斯网络结构示例 t a b 4 1b a y e s i a nn e t w o r ks t r u c t u r ec h a r t 用符号占( g ，p ) 表示一个贝叶斯网络，b ( g ，尸) 由以下两部分组成 张恒昆：基于案例的刑事审讯辅助决策算法研究及应用 f 1 、一个具有个节点的有向无环图g 。图中节点代表随机变量，节点间的有向边代 表节点间的相互关系。节点变量可以是任何问题的抽象。通常认为有向边表达了一种因果 关系，故贝叶斯网络有时叫做因果网。非常重要的是，有向图蕴涵了条件独立性假设，贝 叶斯网络规定了图中每个节点k 的条件独立于由k 的父节点给定的非k 后代节点构成的任 何节点子集。也就是说，如果用爿( k ) 表示后代节点构成的任何节点子集，用丌( k ) 表示 11 m 的直接双亲节点，则 p ( ki 爿( k ) ，兀( k ) ) 叩( ki 兀( k ) ) ( 4 2 ) ( 2 ) 一个与每个节点相关的条件概率表( c o n d i t i o n a lp r o b a b i l i t i e st a b l e ，c z r ) p 。条件 概率表尸可以用p ( kl 兀( k ) ) 来描述，它表达了节点同其父节点的相关关系条件概 率。没有任何父节点的节点概率为其先验概率。因为有了节点及其相互关系和条件概率 表，故贝叶斯网络可以表达网络中所有节点( 变量) 的联合概率。将条件独立性应用于链规 则式( 4 1 ) ，可得： p ( k ) = 森p ( k i 丌( k ) ) 用( 4 3 ) 式表达图4 1 中变量的联合概率可以得到式( 4 4 ) ： ( 4 3 ) p ( 伽，c ，哪) = 冉p ( 巧l 兀( k ) ) = p ( e i c ，。) p ( 。) p ( c 伽( b f 爿) p ( 爿) ( 4 4 ) 可见，贝叶斯网络使变量的联合概率求解大大简化。假设所有变量都是二值变量( 例如 取t r u e 或f a l s e ) ，对于k 个变量l 青况，由链规则式( 4 1 ) ，求联合概率需要指定2 。个独立 的联合概率。如j _ ( - 6 时，这个值为2 6 = 6 4 。而由式( 4 4 ) ，只需指定1 4 个概率即可。当k 值增大时，需要指定的概率数目的减少就更为显著，这种减少使得难于处理的问题变得可 以( 或更容易) 处理。 4 1 2 贝叶斯网络与刑事审讯 用于数据挖掘的贝叶斯网络方法主要有以下几个特点： 大连理工大学硕士学位论文 ( 1 ) 贝叶斯网络可以处理不完整和带有噪声的数据集。它用概率测度的权重来描述数 据间的相关性，从而解决了数据间的不一致，甚至是相互对立的问题。 f 2 ) 贝叶斯网络用图形的方法描述数据间的相互关系，语义清晰，可理解性强，这将 有助于利用数据间的因果关系来进行预测分析。 ( 3 ) 由于贝叶斯网络具有因果和概率性语义，它有助于先验知识和概率的结合，容易 与优化决策方法相结合。 现实的刑事案件处理过程之中要使用大量的历史数据。刑事信息之中存在不完整数据 的情况，信息之间具有强逻辑性、强因果关系，适合使用贝叶斯网络处理。所以本文将贝 叶斯网络应用到刑事审讯过程之中，作为人工处理的辅助工具，加快处理过程，精确处理 结果。 4 2 基于审讯案例的贝叶斯网络学习 描述一个贝叶斯网络需要两个部分，即每个图的拓扑结构( 简称结构) 和每个联合概率 分布的参数，它们都可以从数据中学习得出。所以贝叶斯网络学习可以划分为两大步骤 【l 0 q ： ( 1 ) 结构学习( s t r u c t u r el e a r n i n g ) ：利用训练样本集，尽可能结合先验知识，确定最合 适的贝叶斯网络模型拓扑结构； ( 2 ) 参数学n ( p a r a m e t e rl e a r n i n g ) ：在给定的拓扑结构下，确定贝叶斯网络模型的参 数。 根据实际情况，学习贝叶斯网络细分为以下四种类型： 类型1 ：结构已知，变量全部可见； 类型2 ：结构已知，变量部分可见； 类型3 ：结构未知，变量全部可见； 类型4 ：结构未知，变量部分可见。 在实际应用中，用户往往不能给出问题的一个结构模型，所以本文从结构学习入手， 再进行参数学习，然后确定贝叶斯网络模型。针对刑事审讯案例的特点，在贝叶斯网络学 习算法中用到第二种学习贝叶斯网络类型，即结构已知，变量部分可见。 4 2 1 结构学习 一般贝叶斯网络的构建是首先由相关领域的专家根据事物间的关系来确定出结构模 型，即有向无环图，然后再利用其他方法确定每个节点的条件概率，但这样构建的网络模 型无法保证其客观性和可靠性，因此要将数据和先验知识结合来共同构建贝叶斯网络。 张恒昆：基于案例的刑事审讯辅助决策算法研究及应用 建立贝叶斯网络拓扑结构的总体过程是，首先，必须确定模型相关的变量及其解释。 ( 1 ) 确定模型需要解决的问题；( 2 ) 确定与该问题相关的所有的属性，及其观测值，并确定 其中值得建立模型的子集；( 3 ) 将属性组织成互不相容的而且穷尽其所有状态。其次，建 立一个表现条件独立断言的有向无环图。最后，确定局部概率分布p ( x ，lf 口i ) 。 贝叶斯网络结构学习分为基于搜索评分的方法和基于依赖分析的方法。其中基于搜索 评分的方法通常是给定一个初始结构f 或空结构) ，逐步增加或删减连接边，改进网络模 型，从而搜索和选择出一个与样本数据拟合的最好的结构。根据不同的评分准则，学习算 法可分为基于贝叶颠方法的算法、基于最大熵的算法和基于最小描述长度的算法。基于搜 索评分结构学习步骤为： ( 1 ) 初始化贝叶斯网络为孤立节点； ( 2 ) 使用启发式方法为网络加边； ( 3 ) 使用评分函数评测新的结构是否为更好； 贝叶斯评f f f ( b a y e s i a ns c o r em e t r i c ) ； 基于墒的评分； 最小描述长度m d i ( m i n i m a ld e s c r i p t i o nl e g t h ) 。 ( 4 ) 重复这个过程，直到找不到更好的结构。 基于依赖分析的方法是通过使用条件独立性检验c o n d i t i o n a li n d e p e n d e n c e ( c d 找到网 络的依赖结构。基于依赖分析的方法如下： ( 1 ) 初始化图结构b = ，a = o ，r = o ，o ： 对每一节点对，计算它们的互信息，并将互信息大于某一域值的节点对按互信息 值的大小顺序加入到s 中； ( 3 ) 从s 中取出第一个点对，并从s 中删除这个元素，把该点对加入到边集4 中； ( 4 ) 从5 中剩余的点对中，取出第一个点对，如果这两各界点之间不存在开放路径， 再把该点对加入爿到中，否则加入到r 中； ( 5 ) 重复4 ) ，直到s 为空； ( 6 ) 从尺中取出第一个点对； ( 7 ) 找出该点对的某一块集，在该子集上做独立性检验，如果该点对的两个节点，仍 然相互依赖，则加入到4 中； ( 8 ) 重复6 ) ，直到r 为空； ( 9 ) 对爿中的每一条边，如果除这条边外，仍旧含有开放路径，则从爿中临时移出该 边，并在相应的块集上作独立性测试，如果仍然相关，则将其返回到爿中，否则从a