基于knn的智能手机即时通讯工具取证方法
基于knn的智能手机即时通讯工具取证方法
【技术领域】
[0001] 本发明属于电子通讯技术领域，涉及一种数据分析方法，尤其涉及一种基于KNN的 智能手机即时通讯工具取证方法。
【背景技术】
[0002] 随着移动互联网的快速发展，智能手机已经成为人们生活中不可缺少的一部分。 与此同时，利用智能手机实施的犯罪活动也屡见不鲜。传统的手机取证通常是对手机中的 短信、通话记录等信息进行取证。随着微信等社交软件的兴起，利用社交软件进行的犯罪活 动也变得越来越猖獗。正是由于微信的流行，对微信的取证显得尤为重要。
[0003] 人们在使用微信进行聊天、交友、上传照片时产生了大量的数据，取证人员要对这 些大量繁杂的数据进行分析，从中找出与案件相关的数据，需要一种行之有效的方法。
[0004] KNN是一种基于实例学习、非参数的分类技术，简单易行，分类效果良好，对不同数 据集都有很好的可操作性，被广泛应用于基于统计的机器学习中。
【发明内容】
[0005] 本发明所要解决的技术问题是：提供一种基于KNN的智能手机即时通讯工具取证 方法，可以提高数据挖掘效率及准确度。
[0006] 为解决上述技术问题，本发明采用如下技术方案：
[0007] -种基于KNN的智能手机即时通讯工具取证方法，对即时通讯工具会话进行分类 之前，先计算会话间的相似度;首先对训练集中的所有会话进行特征选择，选取出特征词， 统计出特征词的权重；然后利用基于同义词词林的词语相似度计算得出特征词间的相似 度，相似度大于设定阈值的词语视为同义词，权重较大者为代表特征词，权重较小者取其权 重与相似度之积为其权重，最后用向量表示会话；
[0008] 所述方法具体包括：
[0009] 步骤S1、对聊天会话进行预处理：中文分词，统计词频;预处理的任务是去掉文本 中与分类无关的部分;对于中文文本而言，词与词之间并没有十分明显的切分标志，所以需 要进行分词；目前的分词方法主要分为基于理解的方法、基于字符串匹配的方法以及基于 统计的方法;在分词时还要对其进行词性的标注、人名以及地名等这些专有名词的识别； [0010]步骤S2、用公式(3)计算出所有词的权重，根据权重值选择特征词；
[0012]其中，w (t，c)表示特征词t在会话c中的权重，Nc表示会话总数，Nt表示特征词总数， tf ( t，C )表示特征词t在会话C中的词频，cf表示训练会话集中出现词t的会话数；
[0013] 目前计算机能够识别的对象为0和1，因此聊天内容在被计算机处理之前，需要将 聊天转换成〇和1代码的形式;在一个会话中往往包含很多特征项，这些特征项中有一些对 会话分类有价值，有一些对会话分类没有价值，通过计算权重的大小来区分有价值或者没 有价值的特征项；
[0014] 步骤S3、计算词语相似度;基于同义词词林计算各类特征词的相似度，选择最优特 征词；
[0015]步骤S4、用特征词的权重向量来表示会话；
[0016] 步骤S5、用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天，可疑聊 天与犯罪有关；
[0017] 步骤S6、用召回率、准确率、查全率等方法对分类结果进行评估;会话分类系统评 估的标志是分类器对会话分类的速度与分类的准确度;分类器的分类速度取决于分类器的 计算公式是否简约;分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相 比较，当两者结果相似度越高，则说明分类器的准确性就越高;评估分类器3个指标分别为 运算速率、准确率以及召回率；
[0018] 准确率计算公式：
[0019]
[0020] 召回率计算公式：
[0021]
[0022]准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就 要牺牲召回率；同样，就要牺牲准确率；因此，F1值就是一种使得文本分类准确率与召回率 达到平衡的计算方法，进而对分类结果进行测评;F1值计算公式为
[0024] 利用同义词词林，对即时通讯工具聊天内容进行词语相似度计算，选出最佳特征 词，然后用向量表示会话，再用KNN算法对会话进行分类，能够较快地从大量聊天记录中找 到与案件相关的数据。
[0025] -种基于KNN的智能手机即时通讯工具取证方法，所述方法包括：
[0026] 对即时通讯工具会话进行分类之前，先计算会话间的相似度；
[0027] 首先对训练集中的所有会话进行特征选择，选取出特征词，统计出特征词的权重；
[0028] 然后利用基于同义词词林的词语相似度计算得出特征词间的相似度，相似度大于 设定阈值的词语视为同义词，权重较大者为代表特征词，权重较小者取其权重与相似度之 积为其权重；
[0029]最后用向量表示会话。
[0030] 作为本发明的一种优选方案，所述方法具体包括：
[0031] 步骤S1、对聊天会话进行预处理：中文分词，统计词频;预处理的任务是去掉文本 中与分类无关的部分；
[0032] 步骤S2、用公式(3)计算出所有词的权重，根据权重值选择特征词；
[0034]其中，w( t，c)表示特征词t在会话c中的权重，Nc表示会话总数，Nt表示特征词总数， tf (t，c)表示特征词t在会话c中的词频，cf表示训练会话集中出现词t的会话数；
[0035]步骤S3、计算词语相似度;基于同义词词林计算各类特征词的相似度，选择最优特 征词；
[0036]步骤S4、用特征词的权重向量来表示会话；
[0037]步骤S5、用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天，可疑聊 天与犯罪有关；
[0038] 步骤S6、用召回率、准确率、查全率等方法对分类结果进行评估;会话分类系统评 估的标志是分类器对会话分类的速度与分类的准确度;分类器的分类速度取决于分类器的 计算公式是否简约;分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相 比较，当两者结果相似度越高，则说明分类器的准确性就越高。
[0039] 作为本发明的一种优选方案，步骤S1中，对于中文文本而言，词与词之间并没有十 分明显的切分标志，需要进行分词;在分词时还要对其进行词性的标注、人名以及地名等这 些专有名词的识别。
[0040] 作为本发明的一种优选方案，步骤S2中，聊天内容在被计算机处理之前，将聊天转 换成0和1代码的形式;部分会话中包含多个特征项，这些特征项中有一些对会话分类有价 值，有一些对会话分类没有价值，通过计算权重的大小来区分有价值或者没有价值的特征 项。
[0041] 作为本发明的一种优选方案，步骤S6中，评估分类器3个指标分别为运算速率、准 确率以及召回率；
[0042]准确率计算公式：
[0043]
[0044] 召回率计算公式：
[0045]
[0046]准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就 要牺牲召回率；同样，就要牺牲准确率；因此，F1值就是一种使得文本分类准确率与召回率 达到平衡的计算方法，进而对分类结果进行测评;F1值计算公式为
[0 048] 利用同义词词林，对即时通讯工具聊天内容进行词语相似度计算，选出最佳特征 词，然后用向量表示会话，再用KNN算法对会话进行分类，从大量聊天记录中找到与案件相 关的数据。
[0049] 本发明的有益效果在于:本发明提出的基于KNN的智能手机即时通讯工具取证方 法，可利用聚类算法对即时通讯工具聊天内容进行分类，从大量的聊天数据中迅速挖掘出 与案件相关的数据，引入词语相似度，计算会话之间的距离，实现即时通讯工具取证。本发 明可以提高数据挖掘效率及准确度。
【附图说明】
[0050]图1为同义词词林5层结构图 [0051]图2为会话分类流程图。
【具体实施方式】
[0052]下面结合附图详细说明本发明的优选实施例。
[0053] 实施例一
[0054] Android系统作为统领智能手机市场的一个移动操作系统，拥有巨大的用户数量。 本发明提出了一种基于KNN的Android智能手机微信取证方法，利用聚类算法对微信聊天内 容进行分类，从大量的聊天数据中挖掘出与案件相关的数据，引入词语相似度，计算会话之 间的距离，为取证人员提供了一种有效的微信聊天分类方法。
[0055] -、KNN 算法
[0056] KNN算法是聚类算法中的一种重要算法，聚类是指将物理或抽象的集合分组成为 由类似的对象组成的多个类的过程;KNN算法的思想是:计算一个点A与其他所有点之间的 距离，取出与该点最近的k个点，然后统计这k个点里面大部分的点所属的分类，则点A属于 该分类；
[0057] 假设有c个类：ω 1，ω 2，···，c〇C，kl，k2，···，kc分别是类ω 1，ω 2，···，c〇C的样本个 数，则判定函数可定义为
[0058] yi(A)=ki,i = l,2,---,c (1)
[0059] 根据公式⑴，判定规则为:如果yj(A)=max ki，贝ljAeWjo
[0060] 假设A包含m个样本，每个样本有η个分量:Xi = (xu，xi2，xi3，…，xin)，i = l，2,3，···， m。样本Y = (y l，y2，y3，…，yn)是待分类的样本，计算Y与每个样本的欧几里得距离：
[0062]选出k个距离Y最小的样本，则这k个样本就是与Y最邻近的样本，统计出这k个样本 所属的分类，则Y属于样本数量最多的分类。
[0063] 二、词语相似度计算步骤
[0064] 为了对微信的聊天内容进行聚类分析，将微信聊天记录转化成向量的形式;与某 人的会话表示为C: (Wi，W2，…，Wn)，其中Wi是第i个特征项的权重;η表示会话C中特征项的个 数;特征项是指出现在聊天中并能表示该会话特点的基本语言单位。在聊天中一般选择文 字中的字、词或词组作为特征;特征项的权重Α是指能够代表会话C能力的大小，它体现了 该特征在会话C中的重要程度;要将会话表示为一个向量，首先要将会话分词，由这些词作 为向量的维数来表示聊天内容;最初的向量表示使用布尔权重的计算方法，即会话中出现 了该词，则向量中该维为1，否则为〇;但这种方法无法体现这个词在会话中的作用程度，本 文采用项频率逆文档频率公式来计算：
[0066]其中，w( t，c)表示特征词t在会话c中的权重，Nc表示会话总数，Nt表示特征词总数， tf (t，c)表示特征词t在会话c中的词频，cf表示训练会话集中出现词t的会话数；
[0067]本发明采用《同义词词林》中的方法进行同义词分类，请参阅图1。
[0068]随着级别的递增，词义刻画越来越细，到了第5层，每个分类里词语数量已经不大， 很多只有一个词语，已经不可再分，可以称为原子词群、原子类或原子节点。
[0069]基于同义词词林的义项相似度的主要思想是:基于同义词词林结构，利用词语中 义项的编号，根据两个义项的语义距离，计算出义项相似度;两个义项A和B的相似度，用Sim 表不：
[0071]其中，a是系数，η是分支层的节点总数，k是两个分支间的距离；计算词语相似度 时，把两个词语的义项分别两两计算，取最大值作为两个词语的相似度值；
[0072]三、基于KNN的微信会话分类
[0073]对微信会话进行分类之前，应先计算会话间的相似度。首先对训练集中的所有会 话进行特征选择，选取出特征词，利用公式(3)统计出特征词的权重。然后利用基于同义词 词林的词语相似度计算得出特征词间的相似度，设相应的阈值为0.8,即相似度大于0.8的 词语视为同义词，权重较大者为代表特征词，权重较小者取其权重与相似度之积为其权重， 最后用向量表示会话。
[0074]本发明基于KNN的智能手机即时通讯工具取证方法，具体包括如下步骤：
[0075] (1)对聊天会话进行预处理：中文分词，统计词频。预处理的任务是去掉文本中与 分类无关的部分。对于中文文本而言，词与词之间并没有十分明显的切分标志，所以需要进 行分词。目前的分词方法主要分为基于理解的方法、基于字符串匹配的方法以及基于统计 的方法。在分词时还要对其进行词性的标注、人名以及地名等这些专有名词的识别。
[0076] (2)用公式(3)计算出所有词的权重，根据权重值选择特征词。目前计算机能够识 别的对象为〇和1，因此聊天内容在被计算机处理之前，需要将聊天转换成〇和1代码的形式。 在一个会话中往往包含很多特征项，这些特征项中有一些对会话分类有价值，有一些对会 话分类没有价值，如何才能辨别某一特征项是否对会话分类有价值，在这里提出了权重这 一概念，通过计算权重的大小来区分有价值或者没有价值的特征项。
[0077] (3)计算词语相似度。基于同义词词林计算各类特征词的相似度，选择最优特征 1·^] 〇
[0078] (4)用特征词的权重向量来表示会话。
[0079] (5)用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天（与犯罪有 关)。
[0080] (6)用召回率、准确率、查全率等方法对分类结果进行评估。会话分类系统评估的 标志是分类器对会话分类的速度与分类的准确度。分类器的分类速度取决于分类器的计算 公式是否简约。分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相比 较，当两者结果相似度越高，则说明分类器的准确性就越高。评估分类器3个指标分别为运 算速率、准确率以及召回率。
[0081 ]准确率计算公式：
[0082]
[0083]召回率计算公式：
[0084]
[0085] 准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就 要牺牲召回率；同样，就要牺牲准确率。因此，F1值就是一种使得文本分类准确率与召回率 达到平衡的计算方法，进而对分类结果进行测评。F1值计算公式为
[0086]
[0087]本发明利用同义词词林，对微信聊天内容进行词语相似度计算，选出最佳特征词， 然后用向量表示会话，再用KNN算法对会话进行分类，能够较快地从大量聊天记录中找到与 案件相关的数据。
[0088] 综上所述，本发明提出的基于KNN的智能手机即时通讯工具取证方法，可以提高数 据挖掘效率及准确度。本发明利用聚类算法对即时通讯工具聊天内 容进行分类，从大量的 聊天数据中挖掘出与案件相关的数据，引入词语相似度，计算会话之间的距离，实现即时通 讯工具取证。
[0089]这里本发明的描述和应用是说明性的，并非想将本发明的范围限制在上述实施例 中。这里所披露的实施例的变形和改变是可能的，对于那些本领域的普通技术人员来说实 施例的替换和等效的各种部件是公知的。本领域技术人员应该清楚的是，在不脱离本发明 的精神或本质特征的情况下，本发明可以以其它形式、结构、布置、比例，以及用其它组件、 材料和部件来实现。在不脱离本发明范围和精神的情况下，可以对这里所披露的实施例进 行其它变形和改变。
【主权项】
1. 一种基于KNN的智能手机即时通讯工具取证方法，其特征在于，对即时通讯工具会话 进行分类之前，先计算会话间的相似度;首先对训练集中的所有会话进行特征选择，选取出 特征词，统计出特征词的权重;然后利用基于同义词词林的词语相似度计算得出特征词间 的相似度，相似度大于设定阈值的词语视为同义词，权重较大者为代表特征词，权重较小者 取其权重与相似度之积为其权重，最后用向量表示会话； 所述方法具体包括： 步骤Sl、对聊天会话进行预处理：中文分词，统计词频;预处理的任务是去掉文本中与 分类无关的部分;对于中文文本而言，词与词之间并没有十分明显的切分标志，所以需要进 行分词；目前的分词方法主要分为基于理解的方法、基于字符串匹配的方法以及基于统计 的方法;在分词时还要对其进行词性的标注、人名以及地名等这些专有名词的识别； 步骤S2、用公式(3)计算出所有词的权重，根据权重值选择特征词；其中，W (t，C)表示特征词t在会话C中的权重，N。表示会话总数，Nt表示特征词总数，tf (t，c)表示特征词t在会话c中的词频，cf表示训练会话集中出现词t的会话数； 目前计算机能够识别的对象为〇和1，因此聊天内容在被计算机处理之前，需要将聊天 转换成〇和1代码的形式;在一个会话中往往包含很多特征项，这些特征项中有一些对会话 分类有价值，有一些对会话分类没有价值，通过计算权重的大小来区分有价值或者没有价 值的特征项； 步骤S3、计算词语相似度;基于同义词词林计算各类特征词的相似度，选择最优特征 词； 步骤S4、用特征词的权重向量来表示会话； 步骤S5、用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天，可疑聊天与 犯罪有关； 步骤S6、用召回率、准确率、查全率等方法对分类结果进行评估;会话分类系统评估的 标志是分类器对会话分类的速度与分类的准确度;分类器的分类速度取决于分类器的计算 公式是否简约；分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相比 较，当两者结果相似度越高，则说明分类器的准确性就越高;评估分类器3个指标分别为运 算速率、准确率以及召回率； 准确率计算公式：召回率计算公式：准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就要牺 牲召回率；同样，就要牺牲准确率；因此，Fl值就是一种使得文本分类准确率与召回率达到 平衡的计算方法，进而对分类结果进行测评;Fl值计算公式为) 利用同义词词林，对即时通讯工具聊天内容进行词语相似度计算，选出最佳特征词，然 后用向量表示会话，再用KNN算法对会话进行分类，能够较快地从大量聊天记录中找到与案 件相关的数据。2. -种基于KNN的智能手机即时通讯工具取证方法，其特征在于，所述方法包括： 对即时通讯工具会话进行分类之前，先计算会话间的相似度； 首先对训练集中的所有会话进行特征选择，选取出特征词，统计出特征词的权重； 然后利用基于同义词词林的词语相似度计算得出特征词间的相似度，相似度大于设定 阈值的词语视为同义词，权重较大者为代表特征词，权重较小者取其权重与相似度之积为 其权重； 最后用向量表示会话。3. 根据权利要求2所述的基于KNN的智能手机即时通讯工具取证方法，其特征在于： 所述方法具体包括： 步骤Sl、对聊天会话进行预处理：中文分词，统计词频;预处理的任务是去掉文本中与 分类无关的部分； 步骤S2、用公式(3)计算出所有词的权重，根据权重值选择特征词；其中，W (t，C)表示特征词t在会话C中的权重，N。表示会话总数，Nt表示特征词总数，tf (t，c)表示特征词t在会话c中的词频，cf表示训练会话集中出现词t的会话数； 步骤S3、计算词语相似度;基于同义词词林计算各类特征词的相似度，选择最优特征 词； 步骤S4、用特征词的权重向量来表示会话； 步骤S5、用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天，可疑聊天与 犯罪有关； 步骤S6、用召回率、准确率、查全率等方法对分类结果进行评估;会话分类系统评估的 标志是分类器对会话分类的速度与分类的准确度;分类器的分类速度取决于分类器的计算 公式是否简约；分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相比 较，当两者结果相似度越高，则说明分类器的准确性就越高。4. 根据权利要求3所述的基于KNN的智能手机即时通讯工具取证方法，其特征在于： 步骤Sl中，对于中文文本而言，词与词之间并没有十分明显的切分标志，需要进行分 词;在分词时还要对其进行词性的标注、人名以及地名等这些专有名词的识别。5. 根据权利要求3所述的基于KNN的智能手机即时通讯工具取证方法，其特征在于： 步骤S2中，聊天内容在被计算机处理之前，将聊天转换成O和1代码的形式;部分会话中 包含多个特征项，这些特征项中有一些对会话分类有价值，有一些对会话分类没有价值，通 过计算权重的大小来区分有价值或者没有价值的特征项。6. 根据权利要求3所述的基于KNN的智能手机即时通讯工具取证方法，其特征在于： 步骤S6中，评估分类器3个指标分别为运算速率、准确率以及召回率； 准确率计算公式：召回率计算公式：准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就要牺 牲召回率；同样，就要牺牲准确率；因此，Fl值就是一种使得文本分类准确率与召回率达到 平衡的计算方法，进而对分类结果进行测评;Fl值计算公式为利用同义词词林，对即时通讯工具聊天内容进行词语相似度计算，选出最佳特征词，然 后用向量表示会话，再用KNN算法对会话进行分类，从大量聊天记录中找到与案件相关的数 据。
【专利摘要】本发明揭示了一种基于KNN的智能手机即时通讯工具取证方法，包括：对即时通讯工具会话进行分类之前，先计算会话间的相似度；首先对训练集中的所有会话进行特征选择，选取出特征词，统计出特征词的权重；然后利用基于同义词词林的词语相似度计算得出特征词间的相似度，相似度大于设定阈值的词语视为同义词，权重较大者为代表特征词，权重较小者取其权重与相似度之积为其权重；最后用向量表示会话。本发明提出的基于KNN的智能手机即时通讯工具取证方法，可以提高数据挖掘效率及准确度。本发明利用聚类算法对即时通讯工具聊天内容进行分类，从大量的聊天数据中挖掘出与案件相关的数据，引入词语相似度，计算会话之间的距离，实现即时通讯工具取证。
【IPC分类】G06F17/27, G06K9/62
【公开号】CN105488029
【申请号】CN201510864641
【发明人】李保印
【申请人】西安闻泰电子科技有限公司
【公开日】2016年4月13日
【申请日】2015年11月30日
【技术领域】
[0001] 本发明属于电子通讯技术领域，涉及一种数据分析方法，尤其涉及一种基于KNN的 智能手机即时通讯工具取证方法。
【背景技术】
[0002] 随着移动互联网的快速发展，智能手机已经成为人们生活中不可缺少的一部分。 与此同时，利用智能手机实施的犯罪活动也屡见不鲜。传统的手机取证通常是对手机中的 短信、通话记录等信息进行取证。随着微信等社交软件的兴起，利用社交软件进行的犯罪活 动也变得越来越猖獗。正是由于微信的流行，对微信的取证显得尤为重要。
[0003] 人们在使用微信进行聊天、交友、上传照片时产生了大量的数据，取证人员要对这 些大量繁杂的数据进行分析，从中找出与案件相关的数据，需要一种行之有效的方法。
[0004] KNN是一种基于实例学习、非参数的分类技术，简单易行，分类效果良好，对不同数 据集都有很好的可操作性，被广泛应用于基于统计的机器学习中。
【发明内容】
[0005] 本发明所要解决的技术问题是：提供一种基于KNN的智能手机即时通讯工具取证 方法，可以提高数据挖掘效率及准确度。
[0006] 为解决上述技术问题，本发明采用如下技术方案：
[0007] -种基于KNN的智能手机即时通讯工具取证方法，对即时通讯工具会话进行分类 之前，先计算会话间的相似度;首先对训练集中的所有会话进行特征选择，选取出特征词， 统计出特征词的权重；然后利用基于同义词词林的词语相似度计算得出特征词间的相似 度，相似度大于设定阈值的词语视为同义词，权重较大者为代表特征词，权重较小者取其权 重与相似度之积为其权重，最后用向量表示会话；
[0008] 所述方法具体包括：
[0009] 步骤S1、对聊天会话进行预处理：中文分词，统计词频;预处理的任务是去掉文本 中与分类无关的部分;对于中文文本而言，词与词之间并没有十分明显的切分标志，所以需 要进行分词；目前的分词方法主要分为基于理解的方法、基于字符串匹配的方法以及基于 统计的方法;在分词时还要对其进行词性的标注、人名以及地名等这些专有名词的识别； [0010]步骤S2、用公式(3)计算出所有词的权重，根据权重值选择特征词；
[0012]其中，w (t，c)表示特征词t在会话c中的权重，Nc表示会话总数，Nt表示特征词总数， tf ( t，C )表示特征词t在会话C中的词频，cf表示训练会话集中出现词t的会话数；
[0013] 目前计算机能够识别的对象为0和1，因此聊天内容在被计算机处理之前，需要将 聊天转换成〇和1代码的形式;在一个会话中往往包含很多特征项，这些特征项中有一些对 会话分类有价值，有一些对会话分类没有价值，通过计算权重的大小来区分有价值或者没 有价值的特征项；
[0014] 步骤S3、计算词语相似度;基于同义词词林计算各类特征词的相似度，选择最优特 征词；
[0015]步骤S4、用特征词的权重向量来表示会话；
[0016] 步骤S5、用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天，可疑聊 天与犯罪有关；
[0017] 步骤S6、用召回率、准确率、查全率等方法对分类结果进行评估;会话分类系统评 估的标志是分类器对会话分类的速度与分类的准确度;分类器的分类速度取决于分类器的 计算公式是否简约;分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相 比较，当两者结果相似度越高，则说明分类器的准确性就越高;评估分类器3个指标分别为 运算速率、准确率以及召回率；
[0018] 准确率计算公式：
[0019]
[0020] 召回率计算公式：
[0021]
[0022]准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就 要牺牲召回率；同样，就要牺牲准确率；因此，F1值就是一种使得文本分类准确率与召回率 达到平衡的计算方法，进而对分类结果进行测评;F1值计算公式为
[0024] 利用同义词词林，对即时通讯工具聊天内容进行词语相似度计算，选出最佳特征 词，然后用向量表示会话，再用KNN算法对会话进行分类，能够较快地从大量聊天记录中找 到与案件相关的数据。
[0025] -种基于KNN的智能手机即时通讯工具取证方法，所述方法包括：
[0026] 对即时通讯工具会话进行分类之前，先计算会话间的相似度；
[0027] 首先对训练集中的所有会话进行特征选择，选取出特征词，统计出特征词的权重；
[0028] 然后利用基于同义词词林的词语相似度计算得出特征词间的相似度，相似度大于 设定阈值的词语视为同义词，权重较大者为代表特征词，权重较小者取其权重与相似度之 积为其权重；
[0029]最后用向量表示会话。
[0030] 作为本发明的一种优选方案，所述方法具体包括：
[0031] 步骤S1、对聊天会话进行预处理：中文分词，统计词频;预处理的任务是去掉文本 中与分类无关的部分；
[0032] 步骤S2、用公式(3)计算出所有词的权重，根据权重值选择特征词；
[0034]其中，w( t，c)表示特征词t在会话c中的权重，Nc表示会话总数，Nt表示特征词总数， tf (t，c)表示特征词t在会话c中的词频，cf表示训练会话集中出现词t的会话数；
[0035]步骤S3、计算词语相似度;基于同义词词林计算各类特征词的相似度，选择最优特 征词；
[0036]步骤S4、用特征词的权重向量来表示会话；
[0037]步骤S5、用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天，可疑聊 天与犯罪有关；
[0038] 步骤S6、用召回率、准确率、查全率等方法对分类结果进行评估;会话分类系统评 估的标志是分类器对会话分类的速度与分类的准确度;分类器的分类速度取决于分类器的 计算公式是否简约;分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相 比较，当两者结果相似度越高，则说明分类器的准确性就越高。
[0039] 作为本发明的一种优选方案，步骤S1中，对于中文文本而言，词与词之间并没有十 分明显的切分标志，需要进行分词;在分词时还要对其进行词性的标注、人名以及地名等这 些专有名词的识别。
[0040] 作为本发明的一种优选方案，步骤S2中，聊天内容在被计算机处理之前，将聊天转 换成0和1代码的形式;部分会话中包含多个特征项，这些特征项中有一些对会话分类有价 值，有一些对会话分类没有价值，通过计算权重的大小来区分有价值或者没有价值的特征 项。
[0041] 作为本发明的一种优选方案，步骤S6中，评估分类器3个指标分别为运算速率、准 确率以及召回率；
[0042]准确率计算公式：
[0043]
[0044] 召回率计算公式：
[0045]
[0046]准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就 要牺牲召回率；同样，就要牺牲准确率；因此，F1值就是一种使得文本分类准确率与召回率 达到平衡的计算方法，进而对分类结果进行测评;F1值计算公式为
[0 048] 利用同义词词林，对即时通讯工具聊天内容进行词语相似度计算，选出最佳特征 词，然后用向量表示会话，再用KNN算法对会话进行分类，从大量聊天记录中找到与案件相 关的数据。
[0049] 本发明的有益效果在于:本发明提出的基于KNN的智能手机即时通讯工具取证方 法，可利用聚类算法对即时通讯工具聊天内容进行分类，从大量的聊天数据中迅速挖掘出 与案件相关的数据，引入词语相似度，计算会话之间的距离，实现即时通讯工具取证。本发 明可以提高数据挖掘效率及准确度。
【附图说明】
[0050]图1为同义词词林5层结构图 [0051]图2为会话分类流程图。
【具体实施方式】
[0052]下面结合附图详细说明本发明的优选实施例。
[0053] 实施例一
[0054] Android系统作为统领智能手机市场的一个移动操作系统，拥有巨大的用户数量。 本发明提出了一种基于KNN的Android智能手机微信取证方法，利用聚类算法对微信聊天内 容进行分类，从大量的聊天数据中挖掘出与案件相关的数据，引入词语相似度，计算会话之 间的距离，为取证人员提供了一种有效的微信聊天分类方法。
[0055] -、KNN 算法
[0056] KNN算法是聚类算法中的一种重要算法，聚类是指将物理或抽象的集合分组成为 由类似的对象组成的多个类的过程;KNN算法的思想是:计算一个点A与其他所有点之间的 距离，取出与该点最近的k个点，然后统计这k个点里面大部分的点所属的分类，则点A属于 该分类；
[0057] 假设有c个类：ω 1，ω 2，···，c〇C，kl，k2，···，kc分别是类ω 1，ω 2，···，c〇C的样本个 数，则判定函数可定义为
[0058] yi(A)=ki,i = l,2,---,c (1)
[0059] 根据公式⑴，判定规则为:如果yj(A)=max ki，贝ljAeWjo
[0060] 假设A包含m个样本，每个样本有η个分量:Xi = (xu，xi2，xi3，…，xin)，i = l，2,3，···， m。样本Y = (y l，y2，y3，…，yn)是待分类的样本，计算Y与每个样本的欧几里得距离：
[0062]选出k个距离Y最小的样本，则这k个样本就是与Y最邻近的样本，统计出这k个样本 所属的分类，则Y属于样本数量最多的分类。
[0063] 二、词语相似度计算步骤
[0064] 为了对微信的聊天内容进行聚类分析，将微信聊天记录转化成向量的形式;与某 人的会话表示为C: (Wi，W2，…，Wn)，其中Wi是第i个特征项的权重;η表示会话C中特征项的个 数;特征项是指出现在聊天中并能表示该会话特点的基本语言单位。在聊天中一般选择文 字中的字、词或词组作为特征;特征项的权重Α是指能够代表会话C能力的大小，它体现了 该特征在会话C中的重要程度;要将会话表示为一个向量，首先要将会话分词，由这些词作 为向量的维数来表示聊天内容;最初的向量表示使用布尔权重的计算方法，即会话中出现 了该词，则向量中该维为1，否则为〇;但这种方法无法体现这个词在会话中的作用程度，本 文采用项频率逆文档频率公式来计算：
[0066]其中，w( t，c)表示特征词t在会话c中的权重，Nc表示会话总数，Nt表示特征词总数， tf (t，c)表示特征词t在会话c中的词频，cf表示训练会话集中出现词t的会话数；
[0067]本发明采用《同义词词林》中的方法进行同义词分类，请参阅图1。
[0068]随着级别的递增，词义刻画越来越细，到了第5层，每个分类里词语数量已经不大， 很多只有一个词语，已经不可再分，可以称为原子词群、原子类或原子节点。
[0069]基于同义词词林的义项相似度的主要思想是:基于同义词词林结构，利用词语中 义项的编号，根据两个义项的语义距离，计算出义项相似度;两个义项A和B的相似度，用Sim 表不：
[0071]其中，a是系数，η是分支层的节点总数，k是两个分支间的距离；计算词语相似度 时，把两个词语的义项分别两两计算，取最大值作为两个词语的相似度值；
[0072]三、基于KNN的微信会话分类
[0073]对微信会话进行分类之前，应先计算会话间的相似度。首先对训练集中的所有会 话进行特征选择，选取出特征词，利用公式(3)统计出特征词的权重。然后利用基于同义词 词林的词语相似度计算得出特征词间的相似度，设相应的阈值为0.8,即相似度大于0.8的 词语视为同义词，权重较大者为代表特征词，权重较小者取其权重与相似度之积为其权重， 最后用向量表示会话。
[0074]本发明基于KNN的智能手机即时通讯工具取证方法，具体包括如下步骤：
[0075] (1)对聊天会话进行预处理：中文分词，统计词频。预处理的任务是去掉文本中与 分类无关的部分。对于中文文本而言，词与词之间并没有十分明显的切分标志，所以需要进 行分词。目前的分词方法主要分为基于理解的方法、基于字符串匹配的方法以及基于统计 的方法。在分词时还要对其进行词性的标注、人名以及地名等这些专有名词的识别。
[0076] (2)用公式(3)计算出所有词的权重，根据权重值选择特征词。目前计算机能够识 别的对象为〇和1，因此聊天内容在被计算机处理之前，需要将聊天转换成〇和1代码的形式。 在一个会话中往往包含很多特征项，这些特征项中有一些对会话分类有价值，有一些对会 话分类没有价值，如何才能辨别某一特征项是否对会话分类有价值，在这里提出了权重这 一概念，通过计算权重的大小来区分有价值或者没有价值的特征项。
[0077] (3)计算词语相似度。基于同义词词林计算各类特征词的相似度，选择最优特征 1·^] 〇
[0078] (4)用特征词的权重向量来表示会话。
[0079] (5)用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天（与犯罪有 关)。
[0080] (6)用召回率、准确率、查全率等方法对分类结果进行评估。会话分类系统评估的 标志是分类器对会话分类的速度与分类的准确度。分类器的分类速度取决于分类器的计算 公式是否简约。分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相比 较，当两者结果相似度越高，则说明分类器的准确性就越高。评估分类器3个指标分别为运 算速率、准确率以及召回率。
[0081 ]准确率计算公式：
[0082]
[0083]召回率计算公式：
[0084]
[0085] 准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就 要牺牲召回率；同样，就要牺牲准确率。因此，F1值就是一种使得文本分类准确率与召回率 达到平衡的计算方法，进而对分类结果进行测评。F1值计算公式为
[0086]
[0087]本发明利用同义词词林，对微信聊天内容进行词语相似度计算，选出最佳特征词， 然后用向量表示会话，再用KNN算法对会话进行分类，能够较快地从大量聊天记录中找到与 案件相关的数据。
[0088] 综上所述，本发明提出的基于KNN的智能手机即时通讯工具取证方法，可以提高数 据挖掘效率及准确度。本发明利用聚类算法对即时通讯工具聊天内 容进行分类，从大量的 聊天数据中挖掘出与案件相关的数据，引入词语相似度，计算会话之间的距离，实现即时通 讯工具取证。
[0089]这里本发明的描述和应用是说明性的，并非想将本发明的范围限制在上述实施例 中。这里所披露的实施例的变形和改变是可能的，对于那些本领域的普通技术人员来说实 施例的替换和等效的各种部件是公知的。本领域技术人员应该清楚的是，在不脱离本发明 的精神或本质特征的情况下，本发明可以以其它形式、结构、布置、比例，以及用其它组件、 材料和部件来实现。在不脱离本发明范围和精神的情况下，可以对这里所披露的实施例进 行其它变形和改变。
【主权项】
1. 一种基于KNN的智能手机即时通讯工具取证方法，其特征在于，对即时通讯工具会话 进行分类之前，先计算会话间的相似度;首先对训练集中的所有会话进行特征选择，选取出 特征词，统计出特征词的权重;然后利用基于同义词词林的词语相似度计算得出特征词间 的相似度，相似度大于设定阈值的词语视为同义词，权重较大者为代表特征词，权重较小者 取其权重与相似度之积为其权重，最后用向量表示会话； 所述方法具体包括： 步骤Sl、对聊天会话进行预处理：中文分词，统计词频;预处理的任务是去掉文本中与 分类无关的部分;对于中文文本而言，词与词之间并没有十分明显的切分标志，所以需要进 行分词；目前的分词方法主要分为基于理解的方法、基于字符串匹配的方法以及基于统计 的方法;在分词时还要对其进行词性的标注、人名以及地名等这些专有名词的识别； 步骤S2、用公式(3)计算出所有词的权重，根据权重值选择特征词；其中，W (t，C)表示特征词t在会话C中的权重，N。表示会话总数，Nt表示特征词总数，tf (t，c)表示特征词t在会话c中的词频，cf表示训练会话集中出现词t的会话数； 目前计算机能够识别的对象为〇和1，因此聊天内容在被计算机处理之前，需要将聊天 转换成〇和1代码的形式;在一个会话中往往包含很多特征项，这些特征项中有一些对会话 分类有价值，有一些对会话分类没有价值，通过计算权重的大小来区分有价值或者没有价 值的特征项； 步骤S3、计算词语相似度;基于同义词词林计算各类特征词的相似度，选择最优特征 词； 步骤S4、用特征词的权重向量来表示会话； 步骤S5、用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天，可疑聊天与 犯罪有关； 步骤S6、用召回率、准确率、查全率等方法对分类结果进行评估;会话分类系统评估的 标志是分类器对会话分类的速度与分类的准确度;分类器的分类速度取决于分类器的计算 公式是否简约；分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相比 较，当两者结果相似度越高，则说明分类器的准确性就越高;评估分类器3个指标分别为运 算速率、准确率以及召回率； 准确率计算公式：召回率计算公式：准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就要牺 牲召回率；同样，就要牺牲准确率；因此，Fl值就是一种使得文本分类准确率与召回率达到 平衡的计算方法，进而对分类结果进行测评;Fl值计算公式为) 利用同义词词林，对即时通讯工具聊天内容进行词语相似度计算，选出最佳特征词，然 后用向量表示会话，再用KNN算法对会话进行分类，能够较快地从大量聊天记录中找到与案 件相关的数据。2. -种基于KNN的智能手机即时通讯工具取证方法，其特征在于，所述方法包括： 对即时通讯工具会话进行分类之前，先计算会话间的相似度； 首先对训练集中的所有会话进行特征选择，选取出特征词，统计出特征词的权重； 然后利用基于同义词词林的词语相似度计算得出特征词间的相似度，相似度大于设定 阈值的词语视为同义词，权重较大者为代表特征词，权重较小者取其权重与相似度之积为 其权重； 最后用向量表示会话。3. 根据权利要求2所述的基于KNN的智能手机即时通讯工具取证方法，其特征在于： 所述方法具体包括： 步骤Sl、对聊天会话进行预处理：中文分词，统计词频;预处理的任务是去掉文本中与 分类无关的部分； 步骤S2、用公式(3)计算出所有词的权重，根据权重值选择特征词；其中，W (t，C)表示特征词t在会话C中的权重，N。表示会话总数，Nt表示特征词总数，tf (t，c)表示特征词t在会话c中的词频，cf表示训练会话集中出现词t的会话数； 步骤S3、计算词语相似度;基于同义词词林计算各类特征词的相似度，选择最优特征 词； 步骤S4、用特征词的权重向量来表示会话； 步骤S5、用KNN分类算法来实现会话的分类，即分为正常聊天或可疑聊天，可疑聊天与 犯罪有关； 步骤S6、用召回率、准确率、查全率等方法对分类结果进行评估;会话分类系统评估的 标志是分类器对会话分类的速度与分类的准确度;分类器的分类速度取决于分类器的计算 公式是否简约；分类的准确度在于使用该分类器对会话分类的结果与人工分类结果相比 较，当两者结果相似度越高，则说明分类器的准确性就越高。4. 根据权利要求3所述的基于KNN的智能手机即时通讯工具取证方法，其特征在于： 步骤Sl中，对于中文文本而言，词与词之间并没有十分明显的切分标志，需要进行分 词;在分词时还要对其进行词性的标注、人名以及地名等这些专有名词的识别。5. 根据权利要求3所述的基于KNN的智能手机即时通讯工具取证方法，其特征在于： 步骤S2中，聊天内容在被计算机处理之前，将聊天转换成O和1代码的形式;部分会话中 包含多个特征项，这些特征项中有一些对会话分类有价值，有一些对会话分类没有价值，通 过计算权重的大小来区分有价值或者没有价值的特征项。6. 根据权利要求3所述的基于KNN的智能手机即时通讯工具取证方法，其特征在于： 步骤S6中，评估分类器3个指标分别为运算速率、准确率以及召回率； 准确率计算公式：召回率计算公式：准确率与召回率是一种此消彼长的关系，即分类要想获得较高的准确率，往往就要牺 牲召回率；同样，就要牺牲准确率；因此，Fl值就是一种使得文本分类准确率与召回率达到 平衡的计算方法，进而对分类结果进行测评;Fl值计算公式为利用同义词词林，对即时通讯工具聊天内容进行词语相似度计算，选出最佳特征词，然 后用向量表示会话，再用KNN算法对会话进行分类，从大量聊天记录中找到与案件相关的数 据。
【专利摘要】本发明揭示了一种基于KNN的智能手机即时通讯工具取证方法，包括：对即时通讯工具会话进行分类之前，先计算会话间的相似度；首先对训练集中的所有会话进行特征选择，选取出特征词，统计出特征词的权重；然后利用基于同义词词林的词语相似度计算得出特征词间的相似度，相似度大于设定阈值的词语视为同义词，权重较大者为代表特征词，权重较小者取其权重与相似度之积为其权重；最后用向量表示会话。本发明提出的基于KNN的智能手机即时通讯工具取证方法，可以提高数据挖掘效率及准确度。本发明利用聚类算法对即时通讯工具聊天内容进行分类，从大量的聊天数据中挖掘出与案件相关的数据，引入词语相似度，计算会话之间的距离，实现即时通讯工具取证。
【IPC分类】G06F17/27, G06K9/62
【公开号】CN105488029
【申请号】CN201510864641
【发明人】李保印
【申请人】西安闻泰电子科技有限公司
【公开日】2016年4月13日
【申请日】2015年11月30日
最新回复(0)