网络内容安全 | 笔记

第一章 网络信息内容获取技术

一、网络信息内容获取模型

1.1 网络信息内容获取模型

image-20231210155128073

1.2 网络媒体信息获取原理

image-20231210155651684

网络媒体信息获取的分类

  1. 全网信息获取
  2. 定点信息获取
  3. 基于主题的信息获取和元搜索

1.3 网络通信信息获取原理

image-20231210160648258

二、搜索引擎技术

中文搜索引擎的关键技术:

  • 网页内容分析
  • 网页索引
  • 查询解析
  • 相关性计算

2.1 网上采集算法（爬虫）

image-20231210160930099

按照系统结构和实现技术，大致可以分为以下几种类型：

  • 通用网络爬虫（General Purpose Web Crawler）
  • 聚焦网络爬虫（Focused Web Crawler）
  • 增量式网络爬虫（Incremental Web Crawler）
  • 深层网络爬虫（Deep Web Crawler）

爬虫过程主要分为一下四步：

  1. 初始URL集合
  2. 信息获取：根据来自网络地址集合或URL队列中的每条网络地址信息，确定获取内容所采用的信息发布协议。基于特定协议的网络交互机制，向信息发布网站请求所需内容。
  3. 信息解析：从网络响应信息相应位置提取发布信息的主体内容（信息关键字段包括：信息来源、信息标题、信息失效时间、信息最近修改时间等等）。
  4. 信息判重：主要基于网络媒体信息URL与内容摘要两大元素，实现信息采集/存储的与否判断。

爬虫URL抓取策略：

  • 深度优先遍历策略
  • 宽度优先遍历策略
  • 反向链接数策略：反向链接数表示的是一个网页的内容受到其他人的推荐的程度/引用的次数。因此，很多时候搜索引擎的抓取系统会使用这个指标来评价网页的重要程度，从而决定不同网页的抓取先后顺序。
  • Partial PageRank策略：对于于已经下载的网页，连同待抓取URL队列中的URL，形成网页集合，计算每个页面的PageRank值，计算完之后，将待抓取URL队列中的URL按照PageRank值的大小排列，并按照该顺序抓取页面
  • OPIC策略：在算法开始前，给所有页面一个相同的初始现金（cash）。当下载了某个页面P之后，将P的现金分摊给所有从P中分析出的链接，并且将P的现金清空。对于待抓取URL队列中的所有页面按照现金数进行排序。
  • 大站优先策略：对于待抓取URL队列中的所有网页，根据所属的网站进行分类。对于待下载页面数多的网站，优先下载。

2.2 排级算法

网页排级是对搜索结果的分析，使那些更具“重要性”的网页在搜索结果中的排名获得提升，从而提高搜索结果的相关性和质量。

1. PageRank

原理：民主表决

核心思想： 在互联网上，如果一个网页被很多其它网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。.

假设互联网是一个有向图，在其基础上定义随机游走模型，即一阶马尔可夫链，表示网页浏览者在互联网上随机浏览网页的过程。假设浏览者在每个网页依照连接出去的超链接以等概率跳转到下一个网页，并在网上持续不断进行这样的随机跳转，这个过程形成一阶马尔可夫链。PageRank表示这个马尔可夫链的平稳分布。每个网页的PageRank值就是平稳概率。

对于网页关系：

image-20231210162423298

有转移矩阵（随机游走模型，即一阶马尔可夫链）为： 随机游走在某个时刻 访问各个结点的概率分布就是马尔可夫链在时刻 的状态分布，可以用一个 维列向量 表示，那么在时刻 访问各个结点的概率分布 满足： PageRank 的基本定义：

给定一个包含 个结点的强连通且非周期性的有向图，在其基础上定义随机游走模型。假设转移矩阵为 ， 在时刻 访问各个结点的概率分布为： 则极限 存在，极限向量 表示马尔可夫链的平稳分布，满足 若随机游走的特点是从一个结点到有有向边连出的所有结点的转移概率相等，则该马尔科夫链有平稳分布 ，满足上式。

平稳分布 称为这个有向图的 PageRank；平稳分布 的各个分量称为各个结点的PageRank值。 其中满足： 这里 表示指向结点 的结点集合， 表示结点 连出的有向边的个数。

PageRank 的一般定义： 第二项称为平滑I页，由于采用平滑项，所有结点的 PageRank 值都不会为 0。并且所有结果和为1.

计算方法： 其中 是入度， 是出度， 是影响因子，取0.85。

为每个页面赋相同的初值，计算每个页面的PR值，应满足所有页面PR值和为1。若和不为1，则按比例对所有结果进行缩小，使得其和为1.

网页数量过大问题的解决方法：

  • 稀疏矩阵
  • MapReduce

优点：

  1. 直接高效
  2. 主题集中

缺点：

  1. 完全忽略网页内容，干扰挖掘结果
  2. 结果范围窄
  3. 影响因子与网页获取数量缺乏科学性

2. HITS

在HITS算法中，每个页面被赋予两个属性：Hub属性和Authority属性。具有上述两种属性的网页分为两种：Hub页面和Authority页面。

Hub（枢纽）页面：类似于一个分类器，其为包含了很多指向高质量Authority页面链接的网页。例如，hao123首页汇集了全网优质网址，故可以认为其是一个典型的高质量Hub网页；

Authority（权威）页面：类似于一个聚类器，其为与某个领域或者某个话题相关的高质量网页。例如，京东首页、淘宝首页等，都是与网络购物领域相关的高质量网页。

枢纽值（Hub Scores）页面上所有导出链接指向页面的权威值之和。

权威值（Authority Scores）所有导入链接所在的页面的枢纽值之和。

HITS算法的目的即是通过一定的技术手段，在海量网页中找到与用户查询主题相关的高质量Authority页面和Hub页面，尤其是Authority页面，因为这些页面代表了能够满足用户查询的高质量内容，搜索引擎以此作为搜索结果返回给用户。

HITS算法基于两个重要的假设：

  1. 一个高质量的Authority页面会被很多高质量的Hub页面所指向；
  2. 一个高质量的Hub页面会指向很多高质量的Authority页面。

算法步骤：

  1. 接受一个用户查询的请求。
  2. 将查询提交给某个现有的搜索引擎，并在返回的搜索结果中，提取排名在前n（n一般取200左右）的网页，得到一组与用户查询高度相关的初始网页集合，这个集合被称作为 root set（即根集）
  3. 在根集的基础上，将与根集内网页有直接链接指向关系的网页（每个网页取d个，d一般取50左右）扩充进来形成base set（即扩展集）。
  4. 计算最终集中所有页面的Hub值和Authority值。
  5. 依据Authority值对页面进行排序，取值较高的前若干位返回作为用户查询结果的响应。

缺点：

  1. 计算效率低，实时性差
  2. “主题漂移”
  3. 易被作弊者操纵结果：作弊者可以建立一个很好的Hub页面，再将这个网页链接指向作弊网页，可以提升作弊网页的Authority得分
  4. 结构不稳定：在原有的“扩充网页集合”内，如果添加删除个别网页或者改变少数链接关系，则HITS算法的排名结果就会有非常大的改变。

优点：

  1. 知识范围扩大。
  2. 搜索时部分地考虑了页面内容，挖掘结果科学性大大增强。

3. 比较

HITS算法是与用户输入的查询请求密切相关的，而PageRank与查询请求无关。所以，HITS算法可以单独作为相似性计算评价标准，而PageRank必须结合内容相似性计算才可以用来对网页相关性进行评价。

HITS算法因为与用户查询密切相关，所以必须在接收到用户查询后实时进行计算，计算效率较低；而PageRank则可以在爬虫抓取完成后离线计算，在线直接使用计算结果，计算效率较高。

HITS算法的计算对象数量较少，只需计算扩展集合内网页之间的链接关系；而PageRank是全局性算法，对所有互联网页面节点进行处理。

从两者的计算效率和处理对象集合大小来比较，PageRank更适合部署在服务器端，而HITS算法更适合部署在客户端。

HITS算法存在主题泛化问题，所以更适合处理具体化的用户查询；而PageRank在处理宽泛的用户查询时更有优势。

2.3 搜索引擎与垃圾信息关系

搜索引擎优化（Search Engine Optimization）：利用工具或其他手段，使目标网站符合搜索引擎的搜索规则，从而获得较好的排名。

SEO分为两类：

  • 优化网站内容，提升网页质量
  • 构造垃圾信息

垃圾信息制造手段包括：

  • 提高排名（Boosting）技术
    • 关键字垃圾（term spamming）
    • 链接垃圾（link spamming）
  • 隐藏（Hiding）技术
  • 对所使用的Boosting技术进行隐藏，尽量不让用户和网络采集器发现
  • 主要技术包括内容隐藏（content hiding）、伪装（cloaking）和重定向（redirection）

如何提高PR：

  • 提升网页质量
  • 登录搜索引擎和分类目录；以及友情链接，如果能获得来自PR值不低于4并与你的主题相关或互补的网站的友情链接，且很少导出链接，那样效果更好
  • 写一些高质量的软文，发布到大型网站，如果得到大家的认可，你的网址会被无数的网站转载
  • 搜索引擎收录一个网站的页面数量，如果收录的比例越高，对提高PR值越有利
    • 把所有页面都提交给Google
    • 制作一个网站地图/导航，包含所有要添加的网站，然后提交网站地图

三、数据挖掘技术

从大量非结构化、异构的Web信息资源中发现兴趣性（interestingness）的知识，包括概念、模式、规则、规律、约束及可视化等形式的非平凡过程.

image-20231210170657144
image-20231210170707640
image-20231210170720314

四、信息推荐技术

信息推荐算法：

  • 基于内容推荐：根据用户已选择的对象，推荐其他类似属性的对象作为推荐。
  • 协同过滤推荐：推荐相似用户所选择的对象
    • 启发式方法：使用与新用户c相似的用户c’对一个对象的评价来预测s对新用户c的效用，进而判断是否推荐s给c。
    • 基于模型的方法：利用用户c对众多对象的评分来学习一个c的模型，然后使用概率方法对新的对象s的推荐效用进行预测。
  • 组合推荐
    • 后融合组合推荐：融合两种或两种以上的推荐方法各自产生的推荐结果，判断使用其中的哪个推荐结果更好。属于结果层次上的融合
    • 中融合组合推荐：以一种推荐方法为框架，融合另一种推荐方法。
    • 前融合组合推荐：直接融合各种推荐方法。

五、信息还原技术

  1. 电脑还原技术
    • 软件还原
    • 硬件还原
  2. 网页还原技术
    • 数据包捕获技术：网络数据包的捕获技术采用的网卡接收方式为混杂方式
    • 协议还原技术
    • 网页内容还原技术
  3. 多媒体信息还原技术.

六、课后题：

1. 各技术详细介绍

  1. 交互（Interaction）: 是指人与计算机或其他设备之间的通信和数据交换。在软件设计中，良好的交互设计可以提高用户体验和效率。
  2. 信息浏览（Information Browsing）: 指用户在互联网或内部系统上查找和浏览信息的过程。有效的信息浏览依赖于用户界面设计和搜索算法的优化。
  3. GYM: 通常指代互联网领域的三大巨头：谷歌（Google）、雅虎（Yahoo）、微软（Microsoft）。这些公司在搜索引擎、在线服务和软件开发等多个方面具有显著影响。
  4. URL（Uniform Resource Locator）: 是一种网络资源的地址格式，用于在互联网上定位和访问网页、图片、视频等资源。
  5. Crawler（网络爬虫）: 是一种自动访问网页并从中提取信息的程序，常用于搜索引擎索引、数据分析和网络内容监控。
  6. Sniffer（网络嗅探器）: 是一种监测和分析网络流量的工具，用于网络安全、故障诊断和网络性能分析。
  7. Promiscuous（混杂模式）: 是指网络设备（如网卡）接收并处理经过其网络接口的所有数据包，而不仅是发往该设备的数据包。这在网络监控和分析中很有用。
  8. Web挖掘（Web Mining）: 指从网络数据（如网页内容、用户行为数据）中提取有用信息和模式的技术，可用于市场分析、搜索引擎优化等领域。
  9. SEO（Search Engine Optimization，搜索引擎优化）: 指通过优化网站结构和内容，提高网站在搜索引擎中的排名和可见性的技术。
  10. 数据挖掘（Data Mining）: 是从大量数据集中通过算法分析提取有价值信息和隐藏模式的过程，广泛应用于商业、科研等领域。

2. 信息获取技术分类及详细说明

信息获取技术可以分为以下几个主要类别：

  1. 数据采集技术：包括网络爬虫、API调用等，用于从互联网或其他数据源收集信息。
  2. 数据处理技术：涉及数据清洗、数据转换等，用于提高数据质量和便于进一步分析。
  3. 信息检索技术：包括搜索引擎技术、数据库查询等，用于从大量数据中查找特定信息。
  4. 数据分析技术：如数据挖掘、统计分析等，用于从数据中提取洞见和知识。
  5. 用户界面技术：涉及交互设计、信息可视化等，用于改善用户获取和处理信息的体验。

3. 信息内容获取模型详细内容

信息内容获取模型通常包含以下步骤：

  1. 需求分析：确定用户或系统需要什么样的信息，包括信息的类型、深度和用途。
  2. 信息源定位：识别和选择合适的信息源，如网络、数据库或其他数据存储。
  3. 信息获取：实际从信息源中获取信息，可能通过搜索、订阅、数据采集等方式进行。
  4. 信息处理：对获取的信息进行加工和整理，包括过滤无关信息、数据格式转换等。
  5. 信息存储：将处理后的信息储存于数据库或其他存储媒介，以便后续使用。
  6. 信息展示和传递：将信息以合适的方式呈现给用户，可能包括图表、报告或交互界面等。

4. PageRank核心原理及排名过程

PageRank是基于网页之间链接关系的一种算法，用于衡量网页的重要性。其核心原理和排名过程包括：

  1. 链接投票：一个网页链接到另一个网页，被视为对后者的“投票”或推荐。
  2. 重要性传递：重要的网页链接到的网页也被认为更重要。
  3. 排名计算：通过迭代计算所有网页的PageRank值。每个网页的PageRank值是所有链接到它的网页的PageRank值的总和，按链接数量和质量加权。
  4. 迭代更新：这个过程反复进行多次，直到所有网页的PageRank值达到稳定。

5. 信息还原技术的各方面

信息还原技术主要包括：

  1. 数据恢复：从损坏、格式化或者删除的存储设备中恢复数据。
  2. 错误检测与纠正：利用算法检测数据传输或存储过程中的错误，并进行修正。
  3. 信息重构：在部分数据缺失或损坏的情况下，尝试基于现有数据和模式重建原始信息。
  4. 备份和恢复策略：定期备份重要数据，并在数据损坏时进行恢复。
  5. 文件系统修复：修复损坏的文件系统，恢复文件系统的结构和存储的数据。

第二章 文本挖掘基础：文本预处理

一、文本挖掘的背景

image-20231210211057717

二、分词

2.1 数字的识别

使用正则表达式识别（有限状态自动机）

2.2 词语标记（Tokenization）算法

算法过程：

  1. 指针从左到右扫描字符char，存储在W[i]中，i++
  2. 如果当前指针位置char是分隔符 并且W不是空格，则将分隔符之前的内容输出为一个单词，并从句子中删除整个单词，并清空W 如果W是空格，则清空W，并从句子中删除这个空白字符

2.3 词性还原（Lemmatization）算法：

屈折型语言的词的变化形式：

  • 屈折变化：词性不变，但形式发生变化，例如动词的过去式、单三等
  • 派生变化：词性变化，一个单词从另外一个不同类单词或词干衍生过来。
  • 符合变化：两个或更多个单词以一定的方式组合成一个新的单词。

需要：

  • 词典（Dict）
  • 前缀表（PrefixList）
  • 后缀表（SuffixList）
  • 有关屈折词尾变形的规则（Rules）

算法过程：

待分析的词语W，单词字符数为d，i=1

  1. 在词典（Dict）中查找单词W，如果找到，直接输出
  2. 如果i<=(d/2)
    1. 从W中取出i个尾字符串，W成为两部分W1+W2
    2. 到后缀表（SuffixList）中查找W2，如果查到，调用规则，对W1进行处理，得到W1'
    3. 到Dict中查找W1'，如果找到，输出W1' 和 W2
    4. i=i+1

2.4 汉语分词

汉语分词面临的问题：

  • 重叠词、离合词（担心：担什么心）、词缀
  • 汉语的切分歧义
    • 交集型歧义（交叉型歧义）：如果字串abc既可切分为ab/c，又可切分为a/bc。 有意见： 我 对 他 /有/意见。 总统/有意/见他。
    • 组合型歧义（覆盖型歧义）：若ab为词，而a和b在句子中又可分别单独成词。 – 马上：我/马上/就 来。 他/从/马/上/下来。
    • 混合型歧义
  • 汉语的未登录词（词库中没收录的词语）

1. 正向最大匹配法（MM）

正向即从左往右取词，取词最大长度为词典中长词的长度，每次右边减一个字，直到词典中存在或剩下1个单字。

举例：

sentence = '我们在野生动物园玩'

user_dict = ['我们', '生动', '野生', '动物园', '野生动物园', '物','玩']

词典最大长度 max_len = 5

匹配过程：

  1. 最大长度为5，从头取出5个字“我们在野生”，然后进行扫描

    第1次：“我们在野生”，扫描词典，无 第2次：“我们在野”，扫描词典，无 第3次：“我们在”，扫描词典，无 第4次：“我们”，扫描词典，有

    扫描中止，输出第1个词为“我们”，去除第1个词后，开始第2轮扫描

  2. 取出“在野生动物”进行扫描

    第1次：“在野生动物”，扫描词典，无 第2次：“在野生动”，扫描词典，无 第3次：“在野生”，扫描词典，无 第4次：“在野”，扫描词典，无 第5次：“在”，只剩下一个字，输出

    扫描中止，输出一个字为“在”，去除第2个词后，开始第3轮扫描

  3. 取出”野生动物园“，在字典中，输出

  4. 取出”玩“，只有一个字，输出

  5. 结果为：“我们/在/野生动物园/玩”

如果词典中有词语”在野“，则分词结果为：“我们/在野/生动/物/园/玩”

2. 逆向最大匹配法（RMM）

逆向即从后往前取词，其他逻辑和正向相同。

例如上个例子中，先取出”生动物园玩“，从前往后删除字，“动物园玩”、“物园玩”、“园玩”、“玩”，取出“玩”

3. 双向最大匹配

依次采用正向最大匹配和反向最大匹配

  • 如果结果一致则输出
  • 如果结果不一致，则采用其他方法排歧

正向最大匹配法，最终切分结果为：“我们/在野/生动/物/园/玩”，其中单字字典词为2，非词典词为1。 逆向最大匹配法，最终切分结果为：“我们/在/野生动物园/玩”，其中，单字字典词为2，非词典词为0。 非字典词：正向(1)>逆向(0)（越少越好） 单字字典词：正向(2)=逆向(2)（越少越好） 总词数：正向(6)>逆向(4)（越少越好） 因此最终输出为逆向结果。

最大匹配法分词的问题：

  • 最大词长的确定

    词长过短，长词会被切错（“中华人民共和国”） 词长过长，效率就比较低

  • 掩盖了分词歧义问题，没有处理

    能发现部分交集型歧义，无法发现组合型歧义

    对于某些交集型歧义，可以增加回溯机制来改进最大匹配法，对不在字典的单字进行进一步处理

4. 最大概率法分词

一个待切分的汉字串可能包含多种分词结果，将其中概率最大的作为该字串的分词结果。

例句：“有意见分歧”

对候选词wi的累计概率：

左邻词：“意见”和“见”都是“分歧”的左邻词

最佳左邻词：某个候选词有若干个左邻词，其中累计概率最大的为最佳左邻词。

算法过程：

  1. 对一个待分词句子，从左到右取出所有候选词
  2. 查出每个候选词的概率，并记录每个候选词的全部左邻词
  3. 计算每个候选词的累计概率，得到最佳左邻词
  4. 到达尾词w_n，并且w_n的累计概率最大，则w_n是终点词
  5. 从终点词开始向前，输出每个词的最佳左邻词，则为分词结果

缺点：

  • 并不能解决所有的交集型歧义问题
  • 无法解决组合型歧义问题

三、文档模型

1. 布尔模型

建立在经典的集合论和布尔代数的基础上，每个词在一篇文档中是否出现，对应权值为0或1

文档检索→布尔逻辑运算

优点：简单、易理解、简洁的形式化。

缺点：准确匹配，信息需求的能力表达不足。

2. 词袋模型

在信息检索中，BOW模型假定对于一个文档，忽略它的单词顺序和语法、句法等要素，将其仅仅看作是若干个词汇的集合，文档中每个单词的出现都是独立的，不依赖于其它单词是否出现。

Wikipedia上给出了如下例子:

John likes to watch movies. Mary likes too.

John also likes to watch football games.

根据上述两句话中出现的单词, 我们能构建出一个字典 (dictionary):

{"John": 1, "likes": 2, "to": 3, "watch": 4, "movies": 5, "also": 6, "football": 7, "games": 8, "Mary": 9, "too": 10}

该字典中包含10个单词, 每个单词有唯一索引, 注意它们的顺序和出现在句子中的顺序没有关联. 根据这个字典, 我们能将上述两句话重新表达为下述两个向量:

[1, 2, 1, 1, 1, 0, 0, 0, 1, 1]

[1, 1, 1, 1, 0, 1, 1, 1, 0, 0]

这两个向量共包含10个元素, 其中第i个元素表示字典中第i个单词在句子中出现的次数. 因此BoW模型可认为是一种统计直方图 (histogram). 在文本检索和处理应用中, 可以通过该模型很方便的计算词频.

词袋模型中，向量中可以使用1/0值表示是否出现，可以使用词频，也可以填入TF-IDF值。

3. n-gram模型

？（ngram不能向量化的表示一个文章）

4. TF-IDF算法

词频（TF）= 某词在文章中出现的总次数 / 文章的总词数

逆文档频率（IDF）= log（语料库的文档总数 / （包含该词的文档数 + 1））

TF-IDF = TF × IDF

四、文档相似度计算

4.1 基于概率模型的相关度

BM25算法

4.2 基于向量空间模型的相关度

SVM

4.3 基于向量内积的相关度

1. 欧式距离

2. 向量内积相似度

3. 余弦相似度

4. Jaccard相似度

4.4 基于文本序列的相关度

  1. 序列比较
  2. 海明距离
  3. 编辑距离

第三章 文本分类

文本分类的基本步骤：

一、评价指标

  1. 准确率：预测正确的样本总数 ÷ 总样本数

  2. 精确率（Precision）：预测正确的样本数 ÷ 预测出来的样本数，即

  3. 召回率（Recall）：预测正确的样本数 ÷ 标志的样本数（即事实上正确的样本数），即

  4. F1：

  5. 宏平均：把每个类别都当作正类计算一下precision，recall，f1然后求和求平均

  6. 微平均：

二、特征选择

2.1 文档频率（DF: Document Frequency）

TF-IDF算法

TF-IDF算法的主要思想是：如果某个词或短语在某一篇文章中的出现频率TF越高，而且在其它文章中很少出现，那么认为此词或者短语具有很好的类别区分能力，适合用来分类。

在统计之前必须要过滤掉文档中的停用词。当然TF-IDF的精确度有时候可能不太高，它仍有不足之处，单纯地认为文本频率越小的单词就越重要，而文本频率越大的单词就越无用，显然这并不完全正确。

计算出文档中每个词的TF-IDF的值，然后按照降序排列，取前面的几个词作为特征属性。这里由于只取前K大的，有比较优秀的O(n)算法。

在文本分类中单纯地用TF-IDF来判断一个特征属性是否具有区分度是不够的，原因主要有如下两个：

  • 没有考虑特征词在类间的分布 如果一个特征词在各个类之间分布都比较均匀，那么这样的词对分类没有任何贡献；而如果一个特征词集中分布在某个类中，在其它类中都出现但是出现的频率很小很小，那么这个词能很好地代表这个类的特征属性，但是TF-IDF不能很好地区别这两种情况。
  • 没有考虑特征词在类内部文档中的分布 在类内部文档中，如果特征词均匀分布在其中，那么这个特征词能够很好地代表这个类的特征，如果只在几篇文档中出现，那么不能够代表这个类的特征。

2.2 信息增益（IG: Information Gain）?

条件熵：在某一条件下，随机变量的不确定性。

信息增益：在某一条件下，随机变量不确定性减少的程度。

在信息增益中，重要的衡量标准就是看这个特征能够为分类系统带来多少信息，带来的信息越多，那么该特征就越重要。通过信息增益选择的特征属性只能考察一个特征对整个系统的贡献，而不能具体到某个类别上，这就使得它只能做全局特征选择，即所有的类使用相同的特征集合。

2.3 互信息（MI: Mutual Information）

互信息是事件A和事件B发生相关联而提供的信息量，在处理分类问题提取特征的时候就可以用互信息来衡量某个特征和特定类别的相关性，如果信息量越大，那么特征和这个类别的相关性越大。反之也是成立的。 其中X，Y分别对应词项t和类别出现的情况c（有若干种可能，下表中是二元模型，即只有两种可能）

特点：

  • MI(t,c) 的值越大，t对C的区分能力越强
  • 同一个类中，相对稀有的词t会得到较大的值
  • 一个词如果频次不够多，但是又主要出现在某个类别里，那么就会出现较高的互信息，从而给筛选带来噪音。 所以为了避免出现这种情况可以采用先对词按照词频排序，然后按照互信息大小进行排序，然后再选择自己想要的词，这样就能比较好的解决这个问题。

2.4 卡方（CHI）

卡方检验是数理统计中一种常用的检验两个变量是否独立的方法。在卡方检验中使用特征与类别间的关联性来进行量化，关联性越强，特征属性得分就越高，该特征越应该被保留。

卡方检验最基本的思想是观察实际值和理论值的偏差来确定理论的正确性。通常先假设两个变量确实是独立的，然后观察实际值与理论值的偏差程度，如果偏差足够小，那么就认为这两个变量确实是独立的，否则偏差很大，那么就认为这两个变量是相关的。

三、分类算法

3.1 KNN分类

输入没有标签的新数据后，将新数据与样本集中数据进行比较，然后算法提取样本集中最相似数据（最近邻）的分类标签。

一般来说，只选择样本数据集中前N个最相似的数据。K一般不大于20，最后，选择k个中出现次数最多的分类，作为新数据的分类。

距离计算：方式有多种，比如常见的曼哈顿距离计算、欧式距离计算等等。

欧式距离计算公式： KNN 算法最简单粗暴的就是将预测点与所有点距离进行计算，然后保存并排序，选出前面 K 个值看看哪些类别比较多。

K值的选择：通过交叉验证（将样本数据按照一定比例，拆分出训练用的数据和验证用的数据，比如6：4拆分出部分训练数据和验证数据），从选取一个较小的 K 值开始，不断增加 K 的值，然后计算验证集合的方差，最终找到一个比较合适的 K 值。

优点：

  • 简单、有效
  • 重新训练方便
  • 计算时间和空间的规模与训练集规模成线性关系
  • KNN是一种非参的（不会对数据做出任何的假设）、惰性的（没有明确的训练数据的过程）算法模型。

缺点：

  • 对内存要求较高，因为该算法存储了所有训练数据。
  • 预测阶段可能很慢。
  • 对不相关的功能和数据规模敏感。

3.2 贝叶斯分类

贝叶斯公式： 类别特征特征类别类别特征 假设每个样本数据由n维特征向量 表示，且有m个类别，由 表示。朴素贝叶斯分类器的目标是对于一个给定的未知类别的样本 ，为其分配具有最高后验概率的类 在朴素贝叶斯分类中，“朴素”的条件独立假设为：假设每个特征对于其他特征是独立的，即特征之间相互独立。则 在文本分类中，对一个文档X可能的类别均计算贝叶斯概率，其中分母都是带分类的文章的特征向量，因此只需比较分子即可。

3.3 SVM分类

1. SVM介绍

支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。

分类：

  • 线性可分支持向量机：硬间隔最大化
  • 线性支持向量机：训练数据近似线性可分时，通过软间隔最大化
  • 非线性支持向量机：当训练数据线性不可分时，通过使用核技巧(kernel trick)及软间隔最大化

2. SVM算法原理

SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

参考：【机器学习】支持向量机 SVM - 知乎 (zhihu.com)

（1）间隔最大化

超平面可表示为： 点 到超平面的距离是： 支持向量到超平面的距离为 ，其他点到超平面的距离大于

对于每个数据：，有： 将移动到分母后，是一个正数，对优化无影响，所以可以省略，两个式子合并后得到： 支持向量到超平面的距离可以写为：

为了最大化这个距离，则需要最小化，等价的，需要最小化

因此得到最优化问题： （2）对偶问题

得到带有约束条件的问题： 引入松弛变量得到，则得到 Lagrange 函数： 其中引入了n个Lagrange 乘子，和n个松弛变量。

则原来的 转化为 问题。

对求导，得到极值点出的必要条件： 其中第二个式子 有两种情况：

  • ，约束条件不起作用，且
  • ，约束条件起作用，且

则综合可得：，即支持向量的，其他向量的

由此方程组转换为，得到不等式约束优化优化问题的 KKT条件： 的最后一项中 ，则进一步转化为 ： 由于 ，则 ，为了找到最优的参数 ，使得 接近目标，故问题转换为

那么最优化问题转换为：

拉格朗日函数对偶性，将最小和最大的位置交换一下，得到：

3. SVM求解过程

主要问题是： （） 求解线性可分的 SVM 的步骤为：

  1. 构造拉格朗日函数：

  2. 利用强对偶性转化： 对参数 w 和 b 求偏导数： 得到： 带回函数中，得到： 即：

  3. 得到问题： 这是一个二次规划问题，问题规模正比于训练样本数，我们常用 SMO(Sequential Minimal Optimization) 算法求解。通过 SMO 求得最优解 。

  4. 求偏导数时得到：