网络内容安全 | 内容要点总结

第一部分 重点内容摘要

1. 网络信息排级算法

1.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. 影响因子与网页获取数量缺乏科学性

1.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. 搜索时部分地考虑了页面内容，挖掘结果科学性大大增强。

1.3 两者比较

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

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

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

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

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

2. 垃圾信息如何过滤

搜索引擎优化（SEO）是一个多层次的过程，旨在提高网站在搜索引擎中的排名。然而，SEO实践可以分为两类：一种是通过优化网站内容和提升网页质量来实现，另一种则是构造垃圾信息。这里的关键是区分这两种方法，并理解它们如何影响搜索引擎的结果。

优化网站内容和提升网页质量：

  1. 内容质量：创建有价值、独特、且相关的内容是提高网站排名的基石。
  2. 关键词的使用：合理地在内容中使用关键词可以帮助搜索引擎更好地理解网站的主题和重点。
  3. 网站结构：良好的网站结构和导航可以帮助搜索引擎有效地抓取网站内容。

构造垃圾信息：

  1. 提高排名技术：如关键字垃圾（term spamming）和链接垃圾（link spamming），这些方法通过操纵关键词或链接来提高网站排名。
  2. 隐藏技术：包括内容隐藏（content hiding）、伪装（cloaking）和重定向（redirection）。这些技术旨在隐藏SEO策略，使其对用户和网络采集器不明显。

提高页面排名（PR）的方法：

  1. 提升网页质量：通过提供高质量、相关的内容和用户体验。
  2. 搜索引擎和分类目录登记：让网站更容易被发现和索引。
  3. 友情链接：与PR值高且主题相关的网站建立链接。
  4. 发布高质量软文：在大型网站上发布高质量的内容，如果被广泛接受和转载，可以提升网站的可见性和权威性。
  5. 提高搜索引擎收录页面数量：通过向Google提交所有页面，制作网站地图等方式来实现。

垃圾信息的过滤：

  1. 搜索引擎算法：搜索引擎不断更新其算法以识别和过滤垃圾信息。
  2. 用户反馈：用户报告的垃圾信息可以帮助搜索引擎识别和过滤不良内容。
  3. 自动检测工具：使用各种技术来自动识别和过滤垃圾信息。

总的来说，虽然SEO是提高网站排名的有效方法，但使用不当或滥用会导致负面效果，甚至可能导致网站被搜索引擎惩罚。因此，遵循最佳实践和道德标准是至关重要的。

3. 信息推荐算法

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

4. 文本预处理的必要性和主要内容

文本预处理在自然语言处理（NLP）中非常关键，因为它是处理和分析文本数据之前的重要步骤。文本数据通常非常杂乱，包含许多可能不影响数据分析的元素。通过预处理，我们可以清理和标准化文本数据，从而提高后续分析的质量和准确性。以下是文本预处理的主要内容和其必要性：

必要性

  1. 标准化: 处理文本数据时，面对的是各种格式和风格。预处理有助于标准化数据，使其更一致。
  2. 降低复杂性: 清洗掉无关的数据可以减少模型处理的复杂性，提高效率。
  3. 提高准确性: 清洗数据可以提升模型的准确性，因为模型可以专注于分析相关内容。
  4. 跨文化/语言的处理: 对于多语言数据，预处理有助于适应不同的语言规则和文化差异。

主要内容

  1. 去除噪声:
    • 去除HTML标签、非文本元素（如图片、视频代码等）。
    • 清除特殊字符、数字、符号等。
  2. 大小写转换:
    • 将所有文本转换为小写或大写，以消除大小写造成的变异。
  3. 标点符号和特殊字符的移除:
    • 去除标点符号和特殊字符，因为它们通常对文本的含义影响不大。
  4. 分词（Tokenization）:
    • 将文本分割成单词或短语，是NLP的基本步骤。
  5. 停用词去除:
    • 去除常见的停用词（如“的”，“是”，“在”等），因为它们通常对文本的主题或情感分析不起作用。
  6. 词干提取和词形还原（Stemming and Lemmatization）:
    • 将单词转换为基本形式，例如将“running”转换为“run”。
  7. 拼写校正:
    • 纠正拼写错误，尤其是在处理用户生成的内容时。
  8. 词汇标准化（如同义词替换）:
    • 替换同义词以减少词汇的多样性，并帮助模型更好地理解文本。
  9. N-gram创建:
    • 创建单词的组合，用于捕获文本中的短语或上下文信息。

总之，文本预处理是提高任何文本分析任务效果的重要步骤，它帮助模型更有效地理解和分析数据。

5. 汉语分词主要挑战和算法

5.1 正向最大匹配法

正向即从左往右取词，取词最大长度为词典中长词的长度，每次右边减一个字，直到词典中存在或剩下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. 结果为：“我们/在/野生动物园/玩”

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

最大匹配法分词的问题：

  • 最大词长的确定

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

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

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

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

5.2 最大概率法分词

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

例句：“有意见分歧”

对候选词wi的累计概率：

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

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

算法过程：

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

缺点：

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

6. 文档模型

6.1 布尔模型

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

文档检索→布尔逻辑运算

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

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

6.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值。

6.3 向量空间模型

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

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

TF-IDF = TF × IDF

7. 文本分类和聚类的评价

7.1 文本分类的评价方法

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

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

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

  4. F1：

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

  6. 微平均：

7.2 聚类的评价方法

  1. 轮廓系数 (Silhouette Coefficient):
    • 测量每个点与其群集内的其他点以及最近群集的点的距离。
    • 值范围在 -1（不正确的聚类）到 +1（非常紧密的聚类）。
  2. Davies-Bouldin 指数:
    • 聚类内部距离与聚类间距离的比率，较低的值表示更好的聚类分隔。
  3. 内聚度和分离度:
    • 内聚度测量群组内部的紧密程度，而分离度测量群组之间的距离。
  4. Calinski-Harabasz 指数:
    • 也称为方差比标准，它是群组之间方差与群组内方差的比率。
  5. Jaccard 指数:
    • 比较预测的聚类和实际聚类，尤其适用于有基准真值的情况。

8. 特征选择主要方法

8.1 文档频率 TF-IDF

TF-IDF算法

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

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

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

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

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

8.2 信息增益（IG: Information Gain）

8.3 互信息（MI: Mutual Information）

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

特点：

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

8.4 卡方（CHI）

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

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

9. 文本分类方法

9.1 KNN分类

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

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

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

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

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

优点：

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

缺点：

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

9.2 朴素贝叶斯

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

9.3 支持向量机（support vector machines, SVM）

特征空间上的训练集： 线性可分向量机的目标：找到分离的超平面并获得决策函数

  • 函数间隔： 给定一个训练样本 x是特征，y是结果标签，i表示第i个样本。定义函数间隔为：。 由于是一个训练样本，那么为了使函数间隔最远（更大的信息确定该样本是正例还是反例），所以，当yi = 1时，我们希望w ∗ xi + b能够非常大，反之是非常小。因此函数间隔代表了我们认为特征是正例还是反例的确信度。 函数间隔如果同时扩大w和b的话，点之间的距离会扩大，但是超平面没有变化。
  • 几何间隔：，表示了一个训练样本到超平面的距离。所以SVM实际的目的时找到函数间隔最小的那对样本，并且要让它的几何间隔最大。
  • 两者的关系：

最大间隔分类的超平面，就是要找到： 由函数间隔和几何间隔的关系，可以得到上式等价于： 其中取，最大化 和最小化 等价，因此线性可分支持向量机学习的最优化问题为：

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量(support vector)；支持向量是使约束条件式等号成立的点。

构造拉格朗日函数： 由于是对偶问题，从极小极大问题变为极大极小问题：

  1. 先求对w,b的极小值，对w,b分别求偏导，令等于0，得到： 带入原式中，得到：

  2. 对${w,b}L(w,b,) 对求极大，则是对 -{w,b}L(w,b,) $求极小，得到表达式：

  3. 定理：若 是上述式子的解，则存在，可以求得原始问题的解（偏导第一个式子，和最优化问题的取等条件）：

  4. 因此，分离超平面可以写成：

10. 文本聚类方法

10.1 基于划分的聚类

给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇。也就是说，它将数据划分为k个簇，而且这k个划分满足下列条件：

  • 每一个簇至少包含一个对象。
  • 每一个对象属于且仅属于一个簇。

10.1.1 聚类的差异

  • 类内差异

    类内差异度量了一个簇内部对象之间的相似性或紧密度。通常，我们希望簇内的对象越相似越好，这意味着在同一个簇中的对象应该彼此接近。

    类内差异可以通过计算簇内对象之间的平均距离或方差来衡量。较小的类内差异值表示簇内的对象更相似，簇内更紧密。例如：

  • 类间差异

    类间差异度量了不同簇之间的分离性或差异性。它表示不同簇之间的对象应该尽可能地不相似，这有助于区分不同的簇。

    类间差异可以通过计算不同簇之间的平均距离或方差来衡量。较大的类间差异值表示不同簇之间的对象更不相似，簇间更分离。例如：

  • 聚类的总体质量可以定义为 和 的单调组合，例如

10.1.2 k-means 算法

K均值聚类（K-Means Clustering）是一种常用的划分聚类算法，它被用来将数据集分成不同的簇。这个算法的主要思想是将数据点划分为k个簇，每个簇的中心是该簇内所有数据点的均值。

算法基本步骤：

  1. 初始化：首先，选择要分成的簇数k。然后从数据集中随机选择k个点作为初始簇的中心点，这些点可以是数据集中的实际数据点或者随机生成的点。
  2. 分配数据点：对于每个数据点，计算它与每个簇中心的距离，通常使用欧氏距离或其他距离度量。将数据点分配给距离最近的簇中心，使得它属于该簇。
  3. 更新簇中心：对于每个簇，计算簇内所有数据点的均值，并将该均值作为新的簇中心。
  4. 重复步骤2和步骤3：重复执行分配数据点和更新簇中心的步骤，直到满足停止条件。常见的停止条件包括簇中心不再发生明显变化，或者指定的迭代次数已达到。
  5. 输出结果：算法结束后，每个数据点都被分配到一个簇中。这就是K均值聚类的最终结果。

优点：

  1. 简单且易于理解：K均值聚类是一个直观和易于理解的算法。它的基本原理是直观的，容易实现和解释，因此适用于初学者和非专业人士。
  2. 计算效率高：K均值聚类在大规模数据集上运行效率很高，因为它的时间复杂度通常是线性的，而且算法迭代次数通常较少。
  3. 适用于均匀分布的簇：当数据的簇是凸形的、球形的或近似球形的时候，K均值聚类的效果通常很好。

缺点：

  1. 需要定义平均值：在簇的平均值被定义的情况下才能使用，可能不适用于某些应用。
  2. 需要预先指定簇数k：在使用K均值聚类之前，需要预先知道要分成多少个簇。选择不合适的k值可能导致聚类结果不准确。有一些方法可以帮助估计合适的k值，但仍然需要主观决策。
  3. 假设簇是凸形的：K均值聚类假设簇是凸形的，对于非凸形的簇效果较差。
  4. 不适用于不均匀大小和形状的簇：如果簇的大小和形状差异很大，K均值聚类可能会产生不理想的结果。
  5. 对异常值敏感：K均值聚类对异常值（离群点）敏感，异常值可能会影响簇的中心位置，从而导致不正确的聚类结果。

k-中心点算法：

k-means算法对于孤立点是敏感的。为了解决这个问题，引入了k-中心点算法，该算法不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。

10.1.3 PAM算法

PAM（Partitioning Around Medoids）算法是一种聚类算法，它是K均值聚类的一种改进版本，旨在解决K均值聚类对离群点和异常值敏感的问题。与K均值聚类不同，PAM算法使用数据点作为中心点，而不是数据的均值，这使得它对离群点更具鲁棒性。

k-medoids修正聚类中心的时候，是计算类簇中除开聚类中心的每点到其他所有点的聚类的最小值来优化新的聚类中心。正是这一差别使得k-mediod弥补了k-means算法的缺点：k-mediod对噪声和孤立点不敏感。

算法流程为：z

  1. 在总体n个样本点中任意选取k个点作为medoids
  2. 按照与medoids最近的原则，将剩余的n-k个点分配到当前最佳的medoids代表的类中（实现了初始的聚类）
  3. 对于第 i 个类中除对应medoids点外的所有其他点，按顺序计算当其为新的medoids时，准则函数的值，遍历所有可能，选取准则函数最小时对应的点作为新的medoids
  4. 重复2-3的过程，直到所有的medoids点不再发生变化或已达到设定的最大迭代次数
  5. 产出最终确定的k个类

准则函数： 最小化绝对误差：

另一种表达：

k‐均值迭代计算簇的中心的过程，在PAM算法中对应计算是否替代对象o′比原来的代表对象o能够具有更好的聚类结果，替换后对所有样本点进行重新计算各自代表样本的绝对误差标准。 若替换后，替换总代价小于0，即绝对误差标准减小，则说明替换后能够得到更好的聚类结果，若替换总代价大于0，则不能得到更好的聚类结果，原有代表对象不进行替换。 在替换过程中，尝试所有可能的替换情况，用其他对象迭代替换代表对象，直到聚类的质量不能再被提高为止。(贪心算法)

10.1.4 谱聚类算法

谱聚类算法 - 知乎 (zhihu.com)

算法流程：

优点：

  1. 谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到。

  2. 由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好。

缺点：

  1. 如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好。
  1. 聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同。

10.2 基于层次的聚类

基于层次的聚类方法是指对给定的数据进行层次分解，直到满足某种条件为止。该算法根据层次分解的顺序分为自底向上法和自顶向下法，即凝聚式层次聚类算法和分裂式层次聚类算法。

层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。

10.2.1 AGENS算法

AGNES 算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度有多种不同的计算方法。聚类的合并过程反复进行直到所有的对象最终满足簇数目。

算法步骤：

输入：包含n个对象的数据库。 输出：满足终止条件的若干个簇。

过程：

  1. 初始化：将每个对象当成一个初始簇。
  2. REPEAT
    1. 计算任意两个簇的距离，并找到最近的两个簇。
    2. 合并两个簇，生成新的簇的集合。
  3. UNTIL 终止条件得到满足。

两个簇之间的距离计算方式：

  1. 最小距离：两个簇中任意两个元素之间的距离的最小值 若采用最小距离的定义，簇与簇的合并方式称为单链接方法.

  2. 最大距离，距离的最大值

  3. 均值距离：两个簇中分别求的平均元素，然后做差

  4. 平均距离：两个簇中任意两个元素距离的平均值

终止条件：

  • 设定一个最小距离阈值D，如果最相近的两个簇的距离已经超过D，则它们不需再合并，聚类终止。
  • 限定簇的个数k，当得到的簇的个数已经达到k，则聚类终止。

缺点：

  1. 不可逆性：AGNES算法的一大缺点是一旦完成了两个簇的合并，就无法撤销这个操作。因此，如果在早期阶段错误地合并了两个不相似的簇，将会对最终的聚类结果产生较大的影响。这种不可逆性使得AGNES算法对于选择合适的距离度量和簇合并策略变得非常关键。
  2. 计算复杂性：AGNES算法在每次迭代中都需要计算所有对象两两之间的距离。这导致了算法的时间复杂度为O(n^2)，其中n是数据点的数量。因此，当数据集很大时，计算距离矩阵和查找最近簇的成本会很高，因此该算法对于大规模数据集不太适用。
  3. 对初始簇数的敏感性：AGNES算法的性能也受到初始簇数的影响。不同的初始簇数和初始簇合并顺序可能会导致不同的最终聚类结果。因此，选择合适的初始条件对于获得理想的聚类结果非常关键。
  4. 不适用于非凸簇：与K均值聚类不同，AGNES算法假定簇可以是任意形状，这在某些情况下可以是一个优点。然而，对于非凸形状的簇，AGNES算法也可能产生不太理想的结果。

10.2.2 DIANA算法

DIANA（Divisive Analysis）算法是一种层次聚类算法，与AGNES（Agglomerative Nesting）算法相反，它是自顶向下的方法。DIANA算法的主要目标是将数据集分割成多个子集，每个子集表示一个簇，然后继续将这些子集进一步划分，直到每个簇包含一个数据点。

算法步骤：

输入：包含n个对象的数据库。 输出：满足终止条件的若干个簇。

过程：

  1. 初始化：将所有对象整个当成一个初始簇。
  2. REPEAT
    1. 在所有簇中挑出具有最大直径的簇C。
    2. 找出簇C中与其它点平均相异度最大的一个点p，并把p放入splinter group，剩余的放在old party中。
    3. REPEAT
      1. 在old party中选择一个点q。
      2. 计算点q到splinter group中的点的平均距离D1，计算点q到old party中的点的平均距离D2，保存D2-D1的值。
      3. 选择D1-D2取值最大的点q'，如果D1-D2为正，把q'分配到splinter group中。
    4. UNTIL 没有新的old party的点被分配给splinter group。
    5. splinter group和old party为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。
  3. END.

简单的来说：

  1. 初始化，所有样本集中归为一个簇
  2. 在同一个簇中，计算任意两个样本之间的距离，找到 距离最远 的两个样本点a,b，将 a,b 作为两个簇的中心;
  3. 计算原来簇中剩余样本点距离 a，b 的距离，距离哪个中心近，分配到哪个簇中
  4. 重复步骤2、3 ……
  5. 直到，最远两簇距离不足阈值，或者簇的个数达到指定值，终止算法

10.2.3 Birch算法

BIRCH聚类算法原理 - 刘建平Pinard - 博客园 (cnblogs.com)

BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）算法是一种层次聚类算法，旨在处理大规模数据集。BIRCH的主要优势在于它能够高效地处理大量数据并生成紧凑的数据摘要，同时保持聚类质量。

Birch算法是层次聚类算法之一，该算法引入了聚类特征和聚类特征树(Clustering Feature Tree)。

聚类特征树的每个节点都可以用它的聚类特征(CF)表示,形式为，N为簇中样本的个数，LS为n个点的线性和，SS为样本的平方和。 CF有一个很好的性质，就是满足线性关系，即：

CF树的参数：

  • B：每个非叶子节点最多有B个分支
  • L：每个叶子节点最多有L个CF 分支
  • T：每个CF分支的直径不超过阈值T

算法可以分为两个步骤：

  1. BIRCH扫描数据库，建立一颗存放于内存的CF-树，它可以看作数据的多层压缩，试图保留数据内在的聚类结构。
  2. BIRCH采用某个(选定的)聚类算法对CF-树的叶子节点进行聚类，把稀疏的簇当做离群点删除，而把稠密的簇合并为更大的簇。

CF-树的构建流程：

  1. 从根节点开始：插入新样本时，从CF树的根节点开始搜索。
  2. 寻找最近的叶子节点和最近的CF节点：递归向下搜索，找到距离新样本最近的叶子节点以及叶子节点中最近的CF节点。这一步是为了确定新样本的插入位置。
  3. 检查CF节点的超球体半径是否满足阈值T：如果新样本被插入后，该CF节点对应的超球体半径（表示簇的范围）仍然满足小于阈值T，则说明可以将新样本加入到这个CF节点中，而无需进行分裂。在这种情况下，需要更新路径上所有的CF三元组以反映新样本的插入。
  4. 如果超球体半径不满足阈值T：如果插入新样本后，CF节点的超球体半径超过了阈值T，则需要进行分裂操作。
  5. 检查叶子节点的CF节点数量是否小于阈值L：如果当前叶子节点的CF节点数量小于阈值L，说明可以将新样本插入到当前叶子节点中。创建一个新的CF节点，将新样本放入该CF节点，然后将新的CF节点放入当前叶子节点。最后，需要更新路径上所有的CF三元组以反映新样本的插入。
  6. 如果CF节点数量已达到阈值L：如果当前叶子节点的CF节点数量已经达到阈值L，说明叶子节点已满，需要将叶子节点分裂为两个新的叶子节点。分裂过程如下：
    • 选择旧叶子节点中超球体距离最远的两个CF元组，这两个CF元组将成为两个新叶子节点的第一个CF节点。
    • 将其他CF元组和新样本元组按照距离远近的原则放入对应的新叶子节点。
    • 然后，依次向上检查父节点是否也需要分裂，如果需要分裂，则按照与叶子节点相同的方式进行分裂。
  7. 结束插入操作：插入完成后，CF树的结构和数据摘要已更新，插入操作结束。

BIRCH算法主要流程

  1. 将所有的样本依次读入，在内存中建立一颗CF Tree，它可以看作数据的多层压缩，试图保留数据内在的聚类结构。
  2. （可选）将第一步建立的CF Tree进行筛选，去除一些异常CF节点，这些节点一般里面的样本点很少。对于一些超球体距离非常近的元组进行合并。
  3. （可选）利用其它的一些聚类算法比如K-Means对所有的CF元组进行聚类，得到一颗比较好的CF Tree.这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构，以及一些由于节点CF个数限制导致的树结构分裂。
  4. （可选）利用第三步生成的CF Tree的所有CF节点的质心，作为初始质心点，对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。

从上面可以看出，BIRCH算法的关键就是步骤1，也就是CF Tree的生成，其他步骤都是为了优化最后的聚类结果。

  • 在构造完成CF-树以后，BIRCH采用某个(选定的)聚类算法对CF-树的叶子节点进行聚类，把稀疏的簇当做离群点删除，而把稠密的簇合并为更大的簇。这些聚类算法可以是k-means，或者分层凝聚法等。

  • BIRCH算法试图利用可用的资源来生成最好的聚类结果。通过一次扫描就可以进行较好的聚类，故该算法的计算复杂度是O(n)，n是对象的数目。

优点：

  1. 节约内存，所有的样本都在磁盘上，CF Tree仅仅存了CF节点和对应的指针。
  2. 聚类速度快，只需要一遍扫描训练集就可以建立CF Tree，CF Tree的增删改都很快。
  3. 可以识别噪音点，还可以对数据集进行初步分类的预处理。

缺点：

  1. 由于CF Tree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同.
  2. 对高维特征的数据聚类效果不好。此时可以选择Mini Batch K-Means。
  3. 如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。

10.3 基于密度的聚类

密度聚类方法的关键思想是通过检测局部密度变化来识别簇的边界，而不仅仅依赖于全局距离度量。密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。这使得密度聚类方法对不同形状、大小和密度的簇具有良好的适应性，并且对于噪声数据具有一定的鲁棒性。

10.3.1 DBSCAN算法

Visualizing DBSCAN Clustering (具象化演示网站)

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。 该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

一些重要概念：

  1. ε-邻域（Epsilon Neighborhood）：ε-邻域是指以某个数据点为中心，半径为 ε 的圆形区域，包括了距离该点在 ε 范围内的所有数据点。ε-邻域是用来衡量数据点之间距离的局部范围。
  2. 核心对象（Core Object）：在DBSCAN中，核心对象是指在 ε-邻域内至少包含 MinPts 个数据点的数据点。核心对象是密度高的数据点，是簇的中心。
  3. 直接密度可达（Directly Density-Reachable）：如果数据点 A 在数据点 B 的 ε-邻域内，且数据点 B 是核心对象，那么数据点 A 被称为直接密度可达于数据点 B。这意味着数据点 A 可以通过 ε-邻域内的密度较高的核心对象 B 直接到达。但是不能说B可以通过A直接到达，除非A也是核心对象。即密度直达是不对称的。
  4. 密度可达（Density-Reachable）：如果存在一条数据点序列 P1, P2, ..., Pn，其中 P1 = A，Pn = B，且对于任意相邻的数据点 Pi 和 Pi+1，Pi+1 是从 Pi 直接密度可达的，那么数据点 A 被称为密度可达于数据点 B。这表示通过一系列直接密度可达的数据点可以连接起点 A 和终点 B。密度可达也是不对称的。
  5. 密度相连（Density-Connected）：如果存在一个数据点 C，使得数据点 A 和数据点 B 都是密度可达于数据点 C，那么数据点 A 和数据点 B 被称为密度相连。密度相连是一种传递性的关系。密度相连时对称的。

简要步骤：

DBSCAN算法根据密度可达关系求出所有密度相连样本的最大集合，将这些样本点作为同一个簇。DBSCAN算法任意选取一个核心对象作为“种子”，然后从“种子”出发寻找所有密度可达的其他核心对象，并且包含每个核心对象的ε-邻域的非核心对象，将这些核心对象和非核心对象作为一个簇。当寻找完成一个簇之后，选择还没有簇标记的其他核心对象，得到一个新的簇，反复执行这个过程，直到所有的核心对象都属于某一个簇为止。

具体步骤：

  1. 初始化：选择两个参数，Epsilon（ε）和MinPts。
    • ε（Epsilon）：表示半径，它用于定义一个数据点的邻域范围。 ε 决定了数据点在 ε-邻域内有多少个邻居。
    • MinPts：表示在 ε-邻域内至少应包含的数据点数量。MinPts 用于确定核心点（密度足够高的点）。
  2. 选择起始点：从数据集中随机选择一个数据点作为起始点。
  3. 找到 ε-邻域：计算起始点到数据集中所有其他数据点的距离，并将距离小于 ε 的数据点视为起始点的 ε-邻域内的邻居。
  4. 核心点检测：如果 ε-邻域内的邻居数量不少于 MinPts，则将起始点标记为核心点。
  5. 扩展簇：如果起始点是核心点，那么开始从它的 ε-邻域内扩展簇。具体步骤如下：
    • 将起始点添加到当前簇中。
    • 对于 ε-邻域内的每个点，如果它是核心点，则将它的 ε-邻域内的邻居点也添加到当前簇中。
    • 递归地继续扩展簇，直到没有更多的核心点可以添加。
  6. 找到下一个起始点：如果当前簇已扩展完毕，则从数据集中选择下一个未访问的核心点作为新的起始点，然后重复步骤 3 到步骤 5。
  7. 标记噪声点：所有未被分配到任何簇的数据点被视为噪声点。
  8. 结束：当所有数据点都被分配到簇或标记为噪声点时，DBSCAN算法结束。

DBSCAN的输出是一组簇，每个簇包含若干核心点和它们的密度可达的数据点，以及一些噪声点。DBSCAN的主要优点包括对不同形状和大小的簇具有良好的适应性，能够自动确定簇的数量，以及对噪声数据点有一定的鲁棒性。这使得它在实际应用中广泛使用，尤其适用于发现具有不规则形状的聚类结构。

优点：

  1. 能够自动识别不同形状和大小的簇：DBSCAN不依赖于簇的形状和大小，能够识别具有不规则形状的聚类结构。这使得它在实际应用中非常灵活。
  2. 对噪声数据有较好的鲁棒性：DBSCAN能够自动将噪声数据点识别为孤立点或离群点，而不将其分配给任何簇。
  3. 不需要提前指定簇的数量：与许多其他聚类算法不同，DBSCAN无需事先指定要找到的簇的数量，它能够根据数据的本地密度自动确定簇的数量。

缺点：

  1. 对参数敏感：DBSCAN需要用户事先指定两个关键参数：ε（邻域半径）和 MinPts（核心点最小邻居数）。不同的参数选择可能导致不同的聚类结果，因此参数的选择需要谨慎，可能需要进行试验和调整。
  2. 可能产生边界点和孤立点：DBSCAN将数据点划分为核心点、边界点和噪声点，但边界点有时可能与多个簇关联，导致歧义。此外，DBSCAN可能将簇分成多个部分，这取决于参数的设置和数据的分布。
  3. 不适用于数据密度差异很大的情况：如果数据集中存在密度差异非常大的区域，DBSCAN可能不适用，因为 ε 和 MinPts 参数需要在整个数据集上保持一定的一致性，这可能会导致无法识别低密度区域的簇。

10.3.2 OPTICS算法

（4）聚类算法之OPTICS算法 - 知乎 (zhihu.com)

机器学习笔记（十一）聚类算法OPTICS原理和实践_optics聚类-CSDN博客

在 DBSCAN 算法中，邻域参数(E，MimPts)是全局唯一的，当样本点的密度不均匀或聚类间相差很人时，聚类质量较差。此外，DBSCAN 算法对邻域参数(E，MinPts)非常敏感，需要由用户指定参数，参数设置的不同可能导致聚类结果差别很大，当用户不了解数据集特征时，很难得到良好的聚类结果。为了克服这些缺点，安克斯特(Ankerst) 等人提出了 OPTICS 算法。

OPTICS 也是基于密度的聚类算法，但这一算法生成一个增广的簇排序，即所有分析对象的线性表，代表各样本点基于密度的聚类结构。从线性表的排序中可以得到基于任何邻域参数(E，MinPts)的 DBSCAN 算法的聚类结果。

重要概念：

  • 核心距离：对于一个给定的核心点X，使得X成为核心点的最小邻域距离 r 就是X的核心距离。

  • 可达距离：假设 q 是核心点。那么点 p 和点 q 的可达距离定义为： 即，如果X是核心对象，则对象 Y 到对象 X 的可达距离就是Y到X的欧氏距离和X的核心距离的最大值，如果X不是核心对象，则Y和X之间的可达距离就没有意义（不存在可达距离）。

算法流程：

输入： 数据集 D。 输出： 有序的输出结果队列 R，以及相应的可达性距离。 初始化：创建两个队列，有序队列 O 和结果队列 R。

如果数据集 D 中还有未处理的点或者存在核心点，则执行以下步骤：

  1. 选择一个未处理且为核心对象的样本点 P。
    • 将 P 放入结果队列 R 中，并从数据集 D 中删除 P。
  2. 找到样本点 P 在数据集 D 中的所有密度直达样本点 X，并计算 X 到 P 的可达距离。
    • 如果 X 不在有序队列 O 中，则将 X 及其可达距离放入 O 中。
    • 如果 X 已经在 O 中，检查如果 X 的新可达距离更小，则更新 X 的可达距离。
  3. 对有序队列 O 中的样本点按可达性距离从小到大进行排序。
  4. 如果有序队列 O 为空，则跳至步骤 1
  5. 如果有序队列 O 不为空，则执行以下步骤：
    1. 取出 O 中的第一个样本点 Y（即可达性距离最小的样本点）。
      • 将 Y 放入结果队列 R 中，并从数据集 D 和有序队列 O 中删除 Y。
    2. 如果 Y 不是核心对象，则执行以下步骤：
      • 重复步骤 5.1（即找 O 中剩余数据可达性距离最小的样本点）。
    3. 如果 Y 是核心对象，则执行以下步骤：
      • 如果 Y 已经在结果序列中，则不处理
      • 找到 Y 在数据集 D 中的所有密度直达样本点（如果某些点已经在结果序列中则跳过），并计算到 Y 的可达距离。
      • 按照步骤 2 将所有 Y 的密度直达样本点更新到 O 中。
  6. 重复以上步骤，直到算法结束

通过分析输出结果队列 R 中的数据点顺序以及它们的可达性距离，可以确定数据点之间的聚类结构。不同密度级别的簇会以不同的形式出现在结果队列中。通常，连续的数据点（可达性距离较小的数据点）表示同一簇内的点，而可达性距离较大的数据点表示不同簇之间的分隔点。

10.3.3 DENCLUE算法

DENCLUE（Density-Based Clustering of Applications with Noise）是一种基于密度的聚类算法，用于在数据集中发现聚类簇和噪声点。该算法通过建模数据点的局部密度分布来识别聚类簇，并使用核密度估计来确定数据点的聚类结构。以下是DENCLUE算法的关键特点和步骤：

其核心思想可以概括为以下几点：

  1. 影响函数（Influence Function）： DENCLUE将每个数据点的影响（影响其邻域的程度）形式化建模为一个数学函数，称为影响函数。这个函数描述了一个数据点对其周围邻域的影响程度，通常是一个随距离递减的函数。影响函数的选择可以根据问题的特性和数据的性质进行调整。
  2. 整体密度建模： DENCLUE通过将所有数据点的影响函数叠加在一起来建模数据空间的整体密度。这表示整体密度是由每个数据点的局部影响共同构成的，而不是简单地假定所有数据点具有相同的密度。这使得DENCLUE能够捕获数据集中不同区域的密度差异。
  3. 密度吸引点（Density Attractor）： 簇可以通过寻找全局密度函数的局部最大值来确定。在DENCLUE中，这些局部最大值被称为密度吸引点。密度吸引点表示数据集中的密度高点或局部聚类中心，因为它们是整体密度函数的局部极大值。DENCLUE的目标之一是识别这些密度吸引点，因为它们对应于聚类簇的核心。

优点：

  1. 对不规则形状和不均匀密度的聚类适应性好： DENCLUE能够发现各种形状的聚类簇，包括不规则形状和密度不均匀的簇，因为它基于数据点的局部密度分布进行建模。
  2. 对噪声点具有鲁棒性： DENCLUE可以有效地将噪声点识别为未连接到任何密度吸引点的数据点，这使得它对数据中的噪声具有较好的鲁棒性。
  3. 对密度变化敏感： 由于DENCLUE使用核密度估计来描述数据点的局部密度，因此它对密度的变化和梯度变化敏感，能够在数据集中捕获密度的细微差异。

缺点：

  1. 计算复杂度高： DENCLUE的计算复杂度较高，特别是在大规模数据集上运行时，需要处理大量的局部密度估计和梯度计算，因此在处理大数据时可能效率较低。
  2. 对参数敏感： DENCLUE需要设置一些参数，如影响函数和吸引子生成的停止条件。选择适当的参数值可能需要一些经验或试验，不合适的参数值可能会影响聚类结果。

11. 共生矩阵

11.1 构建方法

11.2 描述子中熵值（Entropy）、能量（Energy）的计算方式以及物理含义

12. 局部二值模式（LBP）

12.1 原始方法和定义

12.2 改进方法如何实现旋转不变性

13. 梯度方向直方图（HOG）

13.1 像素梯度的定义

13.2 （梯度）方向直方图构建方法

14. Harris 角点检测

14.1 原理以及角响应测度公式

15. 尺度不变特征变换（SIFT）

15.1 图像高斯核卷积、高斯差分核卷积的物理意义

15.2 如何实现对图像尺度和旋转具有不变性

16. 光流

16.1 光流的定义

17. Dense Trajectories （DT）

17.1 轨迹的形成方法（点跟踪）（可不考虑median filter），以及如何降低发生漂移的概率

17.2 MBH相对于HOF的优点

18. Improved Dense Trajectory

18.1 对DT进行改进的方面

19. 网络舆情的特点

PPT：

  1. 直接性

    网络舆情不像报纸、杂志和电视，要经过报选题、采访、编辑、审稿、发布或者播放等几个环节，而网民发帖，就没有中间环节，很直接，随意性很强，网络舆情发生以后，网民可以直接通过网站论坛、微信、QQ空间、博客等载体立即发表意见

  2. 突发性

    就是无法预测，突然发生，网络舆论的形成往往非常迅速,一个热点事件的存在加上一种情绪化的意见,就可以成为点燃一片舆论的导火索。

  3. 偏差性

    就是所表达的观点，与实际不符合，由于发言者身份隐蔽，并且缺少规则限制和有效监督，网络自然成为一些网民发泄情绪的空间。

GPT：

  1. 快速传播:由于互联网的普及和社交媒体平台的使用，信息可以在极短的时间内迅速传播到广泛的受众。
  2. 广泛参与:网络舆情通常涉及来自不同背景、不同地理位置的广泛用户群体，使得公众讨论更加多元化。
  3. 即时性:网络舆情反应迅速，用户可以实时表达和更新他们的观点和感受。
  4. 动态变化:网络舆情是高度动态的，随着新信息的出现和用户交互的进行，舆论可能迅速变化。
  5. 情绪化:网络空间中的匿名性和距离感有时会放大个体的情绪表达，使得网络舆情更加情绪化和极端。
  6. 多样性和分化:网络舆情通常表现出高度的多样性，不同群体可能有截然不同的看法和反应。
  7. 易受操纵和误导:网络谣言、虚假信息和有意的舆论操纵可能对网络舆情产生显著影响。
  8. 影响力:强烈的网络舆情可以影响公共政策、企业决策甚至社会运动。
  9. 多平台特性:不同的社交媒体平台和网络论坛可能孕育不同类型的舆情，这些平台之间的舆情交互也十分复杂。
  10. 长尾效应:一些网络舆情事件可能在短时间内消退，而其他一些则可能持续较长时间，甚至不时复燃。

20. 网络谣言和水军的分析

21. 话题检测和话题跟踪主要方法

21.1 话题检测：单遍聚类

采用增量式的在线聚类算法，即单遍聚类算法（single-pass slustering）

算法的主要步骤：

  1. 处理输入报道：算法按照报道的顺序逐一处理输入的报道。每篇报道被表示为一个向量，其中的特征项可以是报道中的词或短语，特征的权重使用TF-IDF或其变体进行计算。
  2. 计算相似度：对于每篇新报道，算法计算它与所有已知话题之间的相似度。这里的相似度是指新报道与话题的中心向量或平均向量之间的相似度。
  3. 归类报道：如果相似度值高于预设的合并阈值，就将新报道归类到与其相似度最高的话题中。这意味着新报道被认为与该话题相关。如果相似度值低于分裂阈值，算法将创建一个新的类簇来表示新话题，并将新报道放入该类簇中。如果处于两者之间，则不处理。
  4. 反复执行：重复执行上述步骤，处理每篇新报道，直到所有的报道都被处理一遍。
  5. 形成扁平聚类：最终，算法将形成一个扁平聚类，其中每个类簇代表一个话题或一个相关报道的集合。簇的个数取决于合并-分裂阈值的大小，较低的阈值可能导致更多的话题被检测到，而较高的阈值可能导致合并相似的话题。

一些改进：

  1. 每篇报道的内容被表示为一个查询，查询的特征项是动态变化的，是由数据流中所有已出现文档的前n个高频词组成的。随着时间的变化，以前所有的查询表示都需要在新的特征项上更新一遍。

  2. 由于未来的报道在实时环境下是未知的，需要根据一个辅助语料c来 计算IDF，这个辅助语料要与当前检测的文本数据流属于同一个领域， 计算方法如下：

  3. 进一步的研究表明，新闻报道的时间特征有助于提高在线话题检测的性能，数据流中时间接近的报道更有可能讨论相同的话题。因此，可以在阈值模型中增加时间惩罚因子，当第j篇报道与第i个查询（i<j ）进行比较时，相应的阈值定义如下：

21.2 话题跟踪：KNN

话题跟踪的主要任务是对特定话题进行追踪，即给定与特定话题相关的少量报道，检测出新闻报道流中与该话题相关的后续报道。

从信息检索的角度来看，话题跟踪与信息过滤有一些相似之处，因此可以借鉴信息过滤中的查询方法来进行话题跟踪。以下是如何利用信息过滤的查询方法进行话题跟踪的一般步骤：

  1. 建立查询器：

    首先，需要建立一个查询器，该查询器用于表示待跟踪的话题。这个查询器的构建是基于话题的训练语料。训练语料包括一些已知与待跟踪话题相关的报道作为正例样本，以及其他不相关的报道作为负例样本。

    查询器的目标是捕捉与待跟踪话题相关的关键词、短语或特征。

    查询器的构件方法有两种：基于向量空间模型、基于语言模型

  2. 计算相似度：

    对于每篇后续报道，使用建立的查询器来计算查询器与报道之间的相似度。这可以使用不同的相似性度量方法来实现，例如余弦相似度。

  3. 相似度阈值：

    设定一个相似度阈值，用于判断报道是否属于待跟踪的话题。如果报道与查询器的相似度高于设定的阈值，那么可以认为这篇报道与待跟踪话题相关。

  4. 跟踪与筛选：

    随着新报道的到来，计算它们与查询器的相似度，并与相似度阈值进行比较。如果相似度高于阈值，将报道纳入待跟踪话题的跟踪范围。否则，可以将其排除，认为不属于该话题。

  5. 实时更新：

    设定一个查询器调整阈值，当报道相似度大于查询器调整阈值时，重构查询器以吸收该话题的重要特征，定期或实时地更新查询器，以适应话题的变化和演化。

KNN算法基本步骤：

  1. 计算待测数据点与所有训练数据的距离；
  2. 距离值递增排序；
  3. 选出前K个最小距离；
  4. 统计这K个距离值所对应的标签的频数；
  5. 频数最大的标签即为预测类别。

22. 社交媒体中的突发事件检测方法

社交媒体特征：

  • 微博短文本限制：140个字
  • 向量稀疏
  • 特征词的文档频数分布是一个长尾分布，大部分的特征词都只在较少的微博中出现

突发特征检测方法：

  1. 假设检验方法：
    • 这种方法假设在一个给定的时间窗口内，特征词的生成概率服从正态分布。
    • 特征词的频率如果大于某个阈值，而且在该时间窗口内处于突发状态的概率小于5%，则被认为是突发特征词。
  2. 引入能量值方法：
    • 这个方法引入了能量值的概念，考虑了频率和发帖者的权威度。
    • 根据过去几个时间窗口内特征的权重值计算当前窗口内的能量值，增长速度越大，能量值越大。
    • 使用监督或无监督方法来根据能量值判断是否为突发特征词。
  3. Kleinberg的方法：
    • Kleinberg提出了一种使用隐马尔科夫模型（HMM）来表示特征词生成过程的方法。
    • 特征词在每个时间窗口内都处于一个状态，并以相应的概率被生成。
    • 突发状态对应于高频率，状态之间的转移需要付出代价。
    • 通过Viterbi算法求解HMM，确定最可能的状态序列，从而检测突发特征词。

23. 社交网络的节点排序

社交网络分析的核心问题是如何识别网络中的重要结点。 重要结点是指相比网络中其他结点而言能够在更大程度上影响网络结构特征与功能的一些特殊结点。 重要结点的数量一般非常少，但其影响可以快速传播到网络中的大多数结点。

定义：

  • 拓扑图记为：，结点集合：，边的集合：，n和m是结点数和边数。
  • 一个图的邻接矩阵记为：，当两节点有边时记为权重值（无带权网络记为1），否则记为0。
  • 网络中的一条路径是类似这样的一组结点和边的交替序列：

23.1 基于结点近邻的排序方法

最简单、最直观的方法：度中心性、K-壳分解

23.1.1 度中心性

在社交网络分析中，结点的重要性也称中心性，其主要观点是结点的重要性等价于该结点与其他结点的连接使其具有的显著特性。度中心性认为一个结点的邻居数目越多，其影响力就越大，这是网络中刻划结点重要性最简单的指标。

在有向图中，度中心性还需考虑结点的入度和出度。在带权网络中，还需考虑权重值。总的来讲，度中心性刻划的是结点的直接影响力，它认为一个结点的度越大，能直接影响的邻居就越多，换句话说就是该结点越重要。

23.1.2 K-壳分解

此方法将外围的结点层层剥去，处于内层的结点拥有较高的影响力。

  1. 初始化：

    假设网络中不存在度数为0的孤立结点。度数为1的结点是网络中最不重要的结点，首先从网络中删除度数为1的节点及其边。

  2. 迭代过程：

    循环执行以下步骤，直到网络中不再存在度数为1的节点：

      1. 从网络中删除度数为1的节点及其边。
      1. 检查删除操作后是否会产生新的度数为1的节点。
      1. 如果有新的度数为1的节点出现，继续执行步骤a；否则，执行下一步。

  3. 确定第一层（1-shell）：

    所有被删除的节点构成了第一层，其Ks值等于1。此时，剩余网络中的每个节点的度至少为2。

  4. 继续迭代：

    重复上述迭代过程，依次删除度数为1的节点，构建第二层（2-shell），第三层（3-shell），以此类推，直到网络中的所有节点都获得了Ks值。

23.2 基于路径的排序方法

23.2.1 接近中心性（closeness centrality）

接近中心性通过计算结点与网络中其他所有结点的距离的平均值来消除特殊值的干扰。

一个结点与网络中其他结点的平均距离越小，该结点的接近中心性就越大。 接近中心性也可以理解为利用信息在网络中的平均传播时长来确定结点的重要性。

计算任意一个结点 到其他结点的平均距离： 把的倒数定义为结点的接近中心性： 缺点：时间复杂度比较高。

23.2.2 Katz中心性

Katz中心性是一种用于分析网络中节点重要性的中心性度量方法。与接近中心性不同，Katz中心性不仅考虑节点之间的最短路径，还考虑它们之间的其他非最短路径。这个度量方法利用一个参数s（s ∈ (0, 1)）来衡量路径的权重，其中s是一个固定参数。

Katz中心性的计算基于网络中的路径关系矩阵，其中l(p)ij表示从节点vi到vj经过长度为p的路径的数目。通常，路径越短，权重越大。 这种中心性度量方法可以用于识别网络中的重要节点，它不仅考虑节点的直接连接，还考虑了间接连接和多跳路径，因此对于复杂网络的分析非常有用。但是时间复制度仍很高。

23.2.3 介数中心性（betweenness centrality）

通常提到的介数中心性一般指最短路径介数中心性（shortest path BC），它认为网络中所有结点对的最短路径中，经过一个结点的最短路径数越多，这个结点就越重要。

介数中心性指的是结点充当两个结点之间的短路路径的次数。结点充当“中介”的次数越多，介数中心性就越大。

结点的定义为： 其中，为从结点到的所有最短路径的数目，为从结点到的最短路径中经过的最短路径数目。

23.3 基于特征向量的排序方法

前述方法主要从邻居的数量上考虑对结点重要性的影响，基于特征向量的方法同时考虑了结点邻居数量和其质量两个因素。

23.3.1 特征向量中心性（eigenvector centrality）

特征向量中心性-CSDN

特征向量中心性认为一个结点的重要性既取决于其邻居结点的数量(该结点的度)，也取决于每个邻居结点的重要性。 即： 𝒙是邻接矩阵𝐴的特征向量。特征向量中心性定义为网络邻接矩阵的主特征向量。

23.3.2 PageRank算法

PageRank是一种度量结点间传递影响或连通性的算法，可以通过在相邻结点上迭代分配一个结点的秩来计算，也可以通过随机遍历图并计算在这些遍历过程中到达每个结点的频率来计算。

24. 社交网络链路预测

链路预测处理的是信息科学中最基本的问题——缺失信息的还原与预测。

链路预测根据某一时刻可用的结点及结构信息，来预测结点和结点之间出现链路的概率。链路预测任务实际上可被分为两类：

  • 第一类是预测新链路将在未来出现的可能性，
  • 第二类是预测当前网络结构中存在的缺失链路的可能性。

24.1 基于结点属性的相似性指标

前提假设是两个结点之间的相似性越大，两个结点之间存在链路的可能性越大。

有许多方法可以表示结点相似性，但最简单的方法是使用结点属性。如果他们具有相同的年龄、性别、职业和兴趣，则他们之间的相似性非常大。

24.2 基于局部信息的相似性指标

基于网络结构相似性的方法假设为：在网络中，两个结点之间相似性（或相近性）越大，它们之间存在连边的可能性就越大。

24.2.1 优先连接指标（preferential attachment，PA）

优先连接方法的主要思想是：在网络中，一条即将加入的新边连接到结点x的概率正比于结点x的度，从而在结点x和结点y之间产生一条链路的可能性正比于两结点度的乘积，即：

24.2.2 共同邻居指标（common neighbor，CN）

共同邻居定义两个结点产生链路的可能性正比于它们之间的共同邻居的数量。

例如，在社交网络中，如果两个陌生人有很多共同的朋友，那么这两个人成为朋友的可能性就比较大。

24.2.3 AA指标

他们根据共同邻居结点的度为每个结点赋予一个权重值，该权重等于该结点的度的对数分之一，从而AA 指标就等于两个结点的所有共同邻居的权重值之和。

24.2.4 资源分配指标（resource allocation，RA）

此方法假设每个结点都有一个资源单元，它将这些资源平均分配给它的邻居。

在没有直接连接的结点对vx和vy中，结点vx可以通过它们的共同邻居（kz为共同邻居结点的度，Tx为vx的邻居结点的集合）将一些资源分配给结点vy。因此，结点vx和vy的相似性可以定义为结点vy从结点vx获得的资源数量。 RA和AA的区别在于赋予共同邻居结点权重的方式不同。AA以的形式递减，RA以的形式递减。

24.3 基于路径的相似性指标

24.3.1 路径指标LP（local path）

同邻居指标可以看成考虑两个结点间的二阶路径数目的方法，如果在二阶路径基础上再考虑结点间的三阶路径数，就可以得到局部路径指标LP，定义为： 其中，α为可调参数，A表示网络的邻接矩阵，A2和A3则表示结点之间长度为2和3的路径的个数。

当α=0，LP指标就退化为CN指标，CN指标本质上也可以看成基于路径的指标，只是它只考虑二阶路径数目。

25. 社交网络扩散模型

25.1 线性阈值模型（Linear Threshold Model）

线性阈值模型( Linear Threshold Model) - 独立级联模型(Independent Cascade Model) - 言非 - 博客园

该模型表明：如果一个用户的采取行动的朋友的数量超过某个阈值，那么该用户才采取行动。

在线性阈值模型(Linear Threshold Model，LTM)中，每个结点 V 在0~1内均匀分布随机抽取一个阈值 。阈值 表示为了激活结点V，结点 V 的朋友需要被激活的比例。

25.2 独立级联模型（Independent Cascade Model）

独立级联模型( Independent Cascade Model，ICM）借鉴了交互粒子系统（ interac-ting particle)和概率论的理念。

与线性阈值模型不同，该模型关注信息的发送者( sender）胜过信息的接收者（receiver)。

在独立级联模型中，一个 结点w 一旦在 第t步 被激活，它只有一次机会激活它的邻接结点。 对于其 邻接结点v ，其被 结点w 激活的概率为 。

如果 v 被成功地激活，那么 v 就是 第 t+1 步 被激活的结点。在往后的信息扩散过程中, w 将不再试图去激活它其余的邻接结点。

在独立级联模型中，信息扩散过程与线性阈值模型的信息扩散过程相同，都从一个初始活动的结点集合开始，直到没有结点可以被激活而结束。

区别：

线性阈值模型

  • 以接收者为中心(receiver-centered)，通过观察一个结点的所有邻接结点，根据该结点的阈值决定是否可以激活该结点;
  • 结点的激活依赖于一个结点的全部邻接结点;
  • 一旦给定线性阈值模型中的阈值，网络中的信息扩散过程也就确定了。

独立级联模型

  • 以发送者为中心（sender-cen-tered)。当一个结点被激活后，它试图去激活它的所有邻接结点；
  • 一个结点独立地激活其所有的邻接结点（不一定都被激活)；
  • 信息扩散的过程随信息的级联过程（cascading process）而变。网络中的信息扩散过程不确定了。

25.3 影响力最大化问题

影响力最大化（Influence Maximization）是社交网络分析和信息扩散理论中的一个关键概念。它关注的核心问题是在一个给定的网络中找到一个最优的节点集合（称为种子集合），使得通过这些节点启动的信息传播能够影响尽可能多的其他节点。

影响力最大化问题通常通过贪心算法进行求解，其步骤大致如下：

  1. 初始化种子集合：起始时种子集合为空。
  2. 迭代选择节点：分多轮进行，每轮从网络中选择一个能带来最大影响力增量的节点加入到种子集合中。
  3. 评估影响力：使用特定的信息扩散模型（如独立级联模型或线性阈值模型）来评估加入新节点后种子集合的影响力。
  4. 重复直至满足条件：一般是迭代次数，或种子集合达到预定大小。

25.4 感染模型

感染模型常用的有：

  • Susceptible-Infected-Recovered (SIR) 模型
  • Susceptible-Infected-Susceptible (SIS) 模型

这个模型将人群分为三个部分：易感者（Susceptible）、感染者（Infected）、和移除者（Recovered或Removed）。

组件解释：

  1. 易感者 (S)：这部分人群尚未感染疾病，但由于没有免疫力，他们有可能被感染。在信息传播的背景下，这些人尚未接收到特定信息。

  2. 感染者 (I)：这部分人群已经感染疾病，并且具有传播病原体给易感者的能力。在信息传播的背景下，这些人已经接收到信息，并且可能将信息传播给其他人。

  3. 移除者 (R)：这部分人群曾经感染过疾病，但现在已经康复，获得免疫力，不再传播病原体。在信息传播的背景下，这些人可能已经失去传播信息的兴趣或能力。

关键参数：

  • 感染率（β）：易感者变成感染者的速率。这通常与感染者的密度和两者之间的接触频率有关。
  • 恢复率（γ/δ）：感染者变成移除者的速率。这个率反映了病程的平均持续时间。

25.5 SIR模型

SIR适用于对每个人一生中只能感染一次的病毒进行建模。

算法过程：

  1. 初始化状态

    所有节点分为三种状态：易感者（S），感染者（I），和移除者（R）。

    初始时，部分节点被设定为感染状态（I），其他节点为易感状态（S）。

    移除状态（R）的节点初始时数量为零。

  2. 模拟传播

    对于每一个时间步长（step）：

    遍历所有处于感染状态（I）的节点。

    对于每个感染节点：

    • 遍历其所有易感（S）状态的邻居节点。
      • 对每个易感邻居，有概率 p 使其变为感染状态（I）。这个概率 p 代表传染概率。
      • 每个感染节点在感染状态保持 t 个时间步长。

  3. 更新状态

    对于处于感染状态（I）的节点，跟踪其在感染状态下经过的时间步长。

    一旦某个感染节点在感染状态保持了 t 个时间步长，将其状态更新为移除状态（R）。

    进入移除状态（R）的节点不再参与传播过程，也不会再被感染。

  4. 迭代

    重复步骤2和步骤3，直到达到预设的模拟时间，或者直到没有更多的感染状态（I）的节点。

25.6 SIS模型

在SIS模型中，恢复的节点立即再次变得易感。

病毒 “strength”: s= β/ δ

一个图的产生流行病的阈值为 τ，如果s= β/ δ< τ，则流行病不会发生。则： 其中为邻接矩阵A的最大特征值。

第二部分 课后习题

以下习题来自《网络信息内容安全》杨黎斌等编著 第二版的课后思考题，习题答案由ChatGPT生成，仅供参考

第一章 绪论

1. 网络信息内容安全的主要技术有哪些？

2. 网络信息安全的安全要求有哪些？

3. 网络信息安全威胁包括什么？

4. 你认为有哪些方法（包括技术、管理等多方面）可以更好的保障网路信息内容的安全？

第二章 网络信息的获取

1. 简述互联网信息分类？

互联网信息可以根据不同的标准进行分类。一种常见的分类方法如下：

  1. 文本信息：包括网页内容、在线文档、博客文章等。
  2. 多媒体信息：包括图像、视频、音频文件等。
  3. 社交媒体信息：来自社交网络的帖子、评论、用户资料等。
  4. 结构化数据：如数据库中的数据、电子表格中的数据等。
  5. 非结构化数据：比如自由格式的文本、未经整理的多媒体文件等。

2. 简要描述网络媒体信息获取的一般流程？

网络媒体信息获取的一般流程通常包括以下几个步骤：

  1. 需求分析：确定需要收集的信息类型和目的。
  2. 数据源定位：确定可以获取所需信息的网络媒体源，如网站、社交媒体平台等。
  3. 数据抓取：使用工具（如网络爬虫）从指定的源抓取数据。
  4. 数据处理：对抓取的数据进行清洗、格式化、去重等处理。
  5. 数据存储：将处理后的数据存储在数据库或其他存储媒介中。
  6. 数据分析：对存储的数据进行分析，提取有价值的信息。

3. 描述基于浏览器模拟技术进行网络媒体信息获取过程？

基于浏览器模拟的信息获取主要涉及以下步骤：

  1. 模拟浏览器：使用工具（如Selenium、Puppeteer）来模拟真实浏览器的行为。
  2. 发送请求：模拟浏览器向目标网站发送请求，获取页面内容。
  3. 动态内容加载：如果页面有基于JavaScript的动态内容，模拟浏览器等待内容加载完毕。
  4. 数据提取：从加载完成的页面中提取所需信息，如文本、链接、图片等。
  5. 数据处理：对提取的数据进行必要的格式化和清洗。
  6. 存储与分析：将处理后的数据存储起来，并进行后续的分析。

4. 简要说明网络通信信息获取方案？

网络通信信息获取方案通常包括：

  1. 网络嗅探：使用网络嗅探工具（如Wireshark）捕获经过网络接口的数据包。
  2. 流量分析：分析捕获的数据包，提取通信内容和元数据。
  3. 端口监控：监控特定端口的通信，获取特定服务的交互数据。
  4. 协议分析：分析使用的通信协议（如HTTP、FTP、SMTP等），提取相关信息。

5. 数据包捕获技术的核心是什么？

数据包捕获技术的核心是：

  • 实时监听：实时监听网络接口，捕获经过的数据包。
  • 数据包解析：对捕获的数据包进行解码和解析，以理解其结构和内容。
  • 过滤和分类：根据需要过滤和分类数据包，以便更有效地处理和分析。
  • 性能和安全性：在保证不影响网络性能和安全的前提下进行数据包捕获。

第三章 网络信息内容预处理技术

1. 简述文本信息的语义特征？

文本信息的语义特征是指能够表达文本含义和内容的特性。这些特征通常包括：

  1. 词汇特征：文本中使用的词汇及其频率。
  2. 语法结构：文本的句子结构，如从句、主谓结构等。
  3. 上下文关系：词汇或句子在文本中的上下文关联。
  4. 主题和概念：文本涉及的主题和核心概念。
  5. 情感倾向：文本表达的情绪和态度，如积极、消极或中立。
  6. 实体和关系：文本中的具体实体（如人名、地点、组织）及其相互关系。

2. 如何进行文本特征提取？

文本特征提取通常包括以下步骤：

  1. 分词：将文本分解为单词或词素。
  2. 去除停用词：移除文本中的常见但无关紧要的词汇，如“的”、“和”等。
  3. 词性标注：识别每个词汇的词性，如名词、动词等。
  4. 词干提取或词形还原：将词汇还原到基本形式。
  5. 词袋模型：将文本转换为词频向量。
  6. TF-IDF分析：计算词汇的频率与逆文档频率，确定词汇的重要性。
  7. 主题模型：使用LDA等模型提取文本的主题分布。

3. 如何衡量特征抽取过程与选择过程所造成的信息损失？

衡量特征抽取和选择过程中的信息损失通常涉及以下方法：

  1. 重建误差：比较原始数据和基于抽取特征重建的数据之间的差异。
  2. 分类或回归性能：使用特征进行机器学习任务，观察性能变化，性能下降可能表明信息损失。
  3. 信息理论度量：使用信息熵等度量来评估信息的损失。

4. 为什么要进行特征重构，常用的方法有哪些？

特征重构的目的是为了改善数据的表示，增强模型的表现力或减少计算复杂性。常用的特征重构方法包括：

  1. 主成分分析（PCA）：通过线性变换将数据转换到新的坐标系统，减少特征的维度。
  2. 线性判别分析（LDA）：找到能够最大化类别间分离的特征子空间。
  3. 自编码器：使用神经网络学习数据的压缩表示，然后重构原始数据。
  4. t-SNE或UMAP：用于高维数据的非线性降维和可视化。
  5. 特征选择方法：如逐步回归、基于模型的特征选择（如使用随机森林的特征重要性）。

第四章 网络流量分析及入侵检测

1. 网络流量分析技术中常用的模型及方法有哪些?

网络流量分析常用的模型和方法包括：

  1. 统计模型：基于流量的各种统计特性（如流量大小、包数量、会话持续时间等）进行分析。
  2. 机器学习模型：使用分类、聚类等机器学习算法来识别流量模式。
  3. 异常检测：识别与正常流量模式显著不同的流量，可能指示入侵或其他安全问题。
  4. 行为分析：分析流量中的用户或系统行为，寻找异常或恶意行为。
  5. 签名检测：使用已知的攻击模式（签名）来识别流量中的威胁。

2. 入侵检测按信息收集模块的数据来源不同可分为哪几种?

入侵检测可以根据数据来源分为以下几种：

  1. 基于网络的入侵检测系统（NIDS）：分析经过网络的数据包。
  2. 基于主机的入侵检测系统（HIDS）：分析主机上的日志文件、系统调用等。
  3. 基于应用的入侵检测系统：专注于特定应用程序的日志和操作。

3. 基于聚类方法进行入侵检测的一般流程是什么?

  1. 数据收集：收集网络流量数据或系统日志。
  2. 特征提取：从收集的数据中提取相关特征。
  3. 数据预处理：清洗和标准化数据。
  4. 聚类算法应用：应用聚类算法如K-means或DBSCAN来对数据进行分组。
  5. 异常检测：识别与大多数数据显著不同的簇，可能表示异常或入侵。
  6. 评估和调整：评估检测结果并根据需要调整模型。

4. 简述k-means 算法和k-medoids算法的基本骤,并比较它们的优缺点

  • k-means算法：
    • 步骤：选择k个点作为初始质心，将每个点分配给最近的质心，重新计算质心，重复此过程直到质心稳定。
    • 优点：简单、易于实现，计算效率高。
    • 缺点：对异常值敏感，需要预先指定簇的数量。
  • k-medoids算法：
    • 步骤：与k-means类似，但质心是数据点，不是均值。
    • 优点：相比k-means，对噪声和异常值不那么敏感。
    • 缺点：计算成本高于k-means，因为需要计算所有点对的距离。

5. 找出下图 所示数据对象中所有明显分离的簇。

6. 采用k-means算法将 10 个流量数据对象(用(z,y)表示位置)聚类为3个族并分别采用欧氏距离、曼哈顿距离和明考斯基距离(g=3)。假设选择 A1,A2,A3作为初始聚类中心,请分别给出:(1)第一次循环后 3 个族的聚类中心;(2)最后聚类结果

题目数据对象:A1(3,10),A2(5,16),A3(15,22),A4(4,7),A5(11,23),A6(6,4),A7(14,3),A8.(21,15),A9(4,7),A10(10,16)

基于您提供的数据点和初始聚类中心，k-means算法的结果如下：

  • 第一次循环后的聚类中心：
    • A1: (6.2, 6.2)
    • A2: (7.5, 16.0)
    • A3: (15.67, 20.0)
  • 最后的聚类结果：
    • 聚类中心未变化。
    • 数据对象的聚类标签：A1, A4, A6, A7, A9 → 聚类 0; A2, A10 → 聚类 1; A3, A5, A8 → 聚类 2。

请注意，不同的距离度量（如欧氏距离、曼哈顿距离、明考斯基距离）可能会产生不同的聚类结果。上述结果基于默认的欧氏距离计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import numpy as np
from sklearn.cluster import KMeans

# 定义数据对象
points = np.array([
    [3, 10],  # A1
    [5, 16],  # A2
    [15, 22], # A3
    [4, 7],   # A4
    [11, 23], # A5
    [6, 4],   # A6
    [14, 3],  # A7
    [21, 15], # A8
    [4, 7],   # A9
    [10, 16]  # A10
])

# 初始化KMeans模型，设置聚类中心
kmeans = KMeans(n_clusters=3, init=points[:3], n_init=1, max_iter=1, random_state=0)
kmeans.fit(points)
centers_round_1 = kmeans.cluster_centers_

# 再次运行KMeans直到收敛
kmeans = KMeans(n_clusters=3, init=points[:3], n_init=1, random_state=0)
kmeans.fit(points)
final_centers = kmeans.cluster_centers_
final_labels = kmeans.labels_

centers_round_1, final_centers, final_labels

# Result
# (array([[ 6.2       ,  6.2       ],
#         [ 7.5       , 16.        ],
#         [15.66666667, 20.        ]]),
#  array([[ 6.2       ,  6.2       ],
#         [ 7.5       , 16.        ],
#         [15.66666667, 20.        ]]),
#  array([0, 1, 2, 0, 2, 0, 0, 2, 0, 1], dtype=int32))

第五章 网络信息内容过滤

1. 网页内容过滤有哪些应用?目前主要有哪些方法?

应用

  1. 父母控制：防止儿童访问不适宜的网站。
  2. 企业管理：限制员工访问与工作无关的网站以提高效率。
  3. 网络安全：阻止用户访问可能含有恶意软件或网络钓鱼的网站。
  4. 合规性：确保内容符合法规和政策要求。

方法

  1. URL过滤：基于黑名单或白名单阻止或允许特定网站的访问。
  2. 关键词过滤：根据页面内容中的特定词汇进行过滤。
  3. 动态内容分析：实时分析网页内容，识别和过滤不适宜的内容。
  4. 人工智能和机器学习：使用AI技术自动识别和过滤不适宜的内容。

2. 简单描述字符串匹配过滤算法。

字符串匹配过滤算法用于识别文本中的特定字符串（如不当词汇）。基本步骤包括：

  1. 定义敏感词库：确定需要过滤的字符串列表。
  2. 扫描文本：遍历目标文本，检查是否包含敏感词。
  3. 匹配与替换：当发现敏感词时，可以选择删除、替换或标记这些词。

3. 试描述网络信息内容过滤系统的基本框架

网络信息内容过滤系统通常包含以下组件：

  1. 数据收集模块：捕获网络流量或用户请求。
  2. 内容分析模块：分析捕获的内容，识别是否符合过滤规则。
  3. 决策与执行模块：基于分析结果做出决策，如阻止、警告或放行。
  4. 日志记录与报告：记录过滤活动并生成报告。

4. 简要描述网络信息内容过滤的主要方法。

  1. 基于规则的过滤：使用预定义的规则（如关键字、URL）来过滤内容。
  2. 基于行为的过滤：分析用户行为，如访问频率和时间，来确定是否过滤。
  3. 基于内容的过滤：分析页面的实际内容，包括文本、图片和视频。
  4. 机器学习方法：使用算法自动学习并识别需要过滤的内容。

5. 简单比较统计和逻辑方法的异同和优缺点。

统计方法

  • 特点：使用数据驱动的方法，依赖大量样本数据。
  • 优点：适应性强，可以处理复杂和模糊的数据。
  • 缺点：需要大量数据，可能不适用于数据量较小的场景。

逻辑方法

  • 特点：基于明确的逻辑规则。
  • 优点：清晰明确，易于理解和实施。
  • 缺点：缺乏灵活性，可能无法处理复杂和模糊的情况。

两者的主要区别在于处理数据的方式和适应性。统计方法更加灵活，但需要大量数据支持；逻辑方法则依赖明确的规则，适合处理清晰定义的问题。

6. 两个一模一样的碗,一号碗有 3 颗水果糖和 10 颗巧克力糖二号碗有水果糖和巧克力糖各 20 颗。现在随机选择一个碗,从中摸出一颗糖,发现是水果糖。请问这颗水果糖来自一号碗的概率有多大?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from sympy import *

# Define the probabilities
# P(B1) = probability of choosing Bowl 1
# P(B2) = probability of choosing Bowl 2
# P(F|B1) = probability of picking a fruit candy from Bowl 1
# P(F|B2) = probability of picking a fruit candy from Bowl 2

P_B1 = Rational(1, 2)  # Equal chance of picking either bowl
P_B2 = Rational(1, 2)
P_F_B1 = Rational(3, 13)  # 3 fruit candies out of 13 total candies in Bowl 1
P_F_B2 = Rational(20, 40) # 20 fruit candies out of 40 total candies in Bowl 2

# Calculate P(B1|F) using Bayes' Theorem
# P(B1|F) = (P(F|B1) * P(B1)) / (P(F|B1) * P(B1) + P(F|B2) * P(B2))

P_B1_F = (P_F_B1 * P_B1) / (P_F_B1 * P_B1 + P_F_B2 * P_B2)
P_B1_F.evalf()

# Result:
# 0.315789473684211

这颗水果糖来自一号碗的概率大约是 31.58%。

第六章 话题检测与跟踪

1、 话题检测与跟踪可以分为哪些子任务？

话题检测与跟踪（Topic Detection and Tracking, TDT）通常包括以下子任务：

  1. 话题检测（Topic Detection)：识别新闻流或文本流中的新话题或事件。
  2. 话题跟踪（Topic Tracking)：跟踪已识别话题的后续报道或相关讨论。
  3. 话题聚类（Clustering)：将相关的文档或报道归类到同一个话题。
  4. 新话题发现（New Event Detection, NED)：在文档流中发现之前未识别的新事件或话题。

2、简要描述话题检测与跟踪的研究体系？

话题检测与跟踪的研究体系主要包括：

  1. 数据预处理：包括文本清洗、分词、去除停用词等。
  2. 特征提取：从文本中提取关键词、实体、主题等特征。
  3. 模型构建：使用机器学习或统计模型来识别、跟踪话题。
  4. 相似度度量：定义和计算文本之间的相似度。
  5. 聚类和分类：根据相似度将文本分组或标记为特定话题。
  6. 效果评估：使用特定的评估指标和数据集来测试模型的性能。

3、话题检测与跟踪技术中，如何进行相似度计算？

在话题检测与跟踪技术中，相似度计算通常采用以下方法：

  1. 余弦相似度：计算文本表示向量之间的角度，常用于文本特征的向量化表示。
  2. Jaccard相似度：基于两组数据的交集和并集来计算相似度，适用于词集模型。
  3. 编辑距离：测量两个字符串之间的“距离”，例如利用Levenshtein距离。
  4. 基于模型的相似度：使用深度学习模型（如BERT）提取的高级特征来计算相似度。

4、话题检测与跟踪的模型中，进行聚类分类时策略原则一般是什么？

进行聚类分类时，策略原则一般包括：

  1. 高内聚低耦合：同一聚类内的文档应高度相似，而不同聚类之间的相似度应较低。
  2. 可解释性：聚类的结果应具有明确的意义，方便理解和解释。
  3. 动态适应性：能够适应新话题的出现和话题的演变。

5、如何评价话题检测与跟踪的效果，常用评测体系有哪些？

评价话题检测与跟踪的效果通常依赖于以下评测体系：

  1. 准确率（Precision)：正确识别的话题数量占识别话题总数的比例。
  2. 召回率（Recall)：正确识别的话题数量占实际话题总数的比例。
  3. F1分数：准确率和召回率的调和平均值，平衡两者的影响。
  4. ROC曲线和AUC值：用于评估模型在不同阈值下的性能。
  5. 聚类评估指标：如轮廓系数，用于评估聚类的质量。

除了这些量化指标，实际应用中还需要考虑模型的泛化能力、运行效率和易用性等因素。

第七章 社会网络分析

1. 社会网络分析常用的分析方法有哪些?

社会网络分析的常用方法包括：

  1. 网络结构分析：分析网络的整体结构，如网络密度、连通性等。
  2. 中心性分析：识别网络中重要的节点，包括度中心性、接近中心性和中介中心性等。
  3. 社区检测：识别网络中的社区或群体，分析群体的结构和特征。
  4. 网络动态分析：研究网络随时间的变化，包括节点和联系的增加或减少。
  5. 路径分析：研究节点之间的路径和距离，分析网络中的信息流动。
  6. 网络影响力分析：评估节点或群体在网络中的影响力。

2. 社会网络分析模型中,节点的地位一般如何进行评估?

在社会网络分析模型中，节点的地位通常通过以下指标评估：

  1. 度中心性：一个节点与其他节点的直接连接数，反映了节点的活跃程度和影响力。
  2. 接近中心性：一个节点到其他所有节点的平均距离，反映了节点的可达性。
  3. 中介中心性：一个节点在网络中起到桥梁作用的程度，即通过该节点的最短路径数量。
  4. 特征向量中心性：考虑节点的邻居节点的重要性，反映了节点在网络中的影响力。

3. 简要描述基于关键词抽取的中文新闻文档自动文摘方法实现流程

基于关键词抽取的中文新闻文档自动文摘实现流程通常包括：

  1. 预处理：包括分词、去除停用词等。
  2. 关键词提取：使用TF-IDF、TextRank等算法提取文档中的关键词。
  3. 句子权重计算：根据句子中包含的关键词及其重要性给句子打分。
  4. 摘要生成：选择得分最高的句子组成文摘。

4. 基于网络信息内容的社会网络分析技术与一般的社会网络分析相比有哪些特殊性?

与一般的社会网络分析相比，基于网络信息内容的社会网络分析有以下特殊性：

  1. 内容驱动：分析侧重于网络上的信息内容，如文本、图片、视频等。
  2. 动态性：网络信息内容快速变化，需要实时或近实时分析。
  3. 多模态分析：结合多种类型的数据（如文本、图像、链接）进行分析。
  4. 用户行为分析：重点关注用户的在线行为及其背后的动机和意图。

5. 未来影响社会网络分析的技术主要有哪些?

未来可能影响社会网络分析的技术主要包括：

  1. 人工智能和机器学习：提高数据处理和分析的效率和准确性。
  2. 大数据技术：处理和分析大规模网络数据。
  3. 自然语言处理：深入理解和分析社交媒体上的文本内容。
  4. 图神经网络：更有效地分析复杂的网络结构和关系。
  5. 隐私保护技术：在分析数据的同时保护用户隐私。
  6. 区块链技术：提供更安全、透明的数据交换和存储方式。

第八章 网络舆情分析

1. 互联网舆情具有什么特点?为什么要对舆情进行分析?

互联网舆情的特点包括：

  • 广泛性：信息来源广泛，涉及多个平台和渠道。
  • 快速性：信息传播速度极快，舆论形成迅速。
  • 多样性：内容形式多样，包括文本、图片、视频等。
  • 互动性：用户可以互动交流，形成复杂的舆论网络。
  • 影响力：网络舆情对公众意见、市场趋势等有重大影响。

进行舆情分析的原因：

  • 风险管理：预防和管理负面舆论，降低风险。
  • 政策制定：为政府和企业提供决策支持。
  • 市场分析：理解市场趋势和消费者需求。
  • 危机应对：在舆情危机发生时迅速做出反应。

2. 常见的网络舆情分析技术包括哪些环节?

网络舆情分析的常见环节包括：

  1. 数据采集：从各种网络平台收集相关的舆情数据。
  2. 数据预处理：清洗、标准化和组织数据。
  3. 情感分析：分析文本的情感倾向，如积极、消极或中立。
  4. 关键词提取：提取文本中的关键信息，如热门话题和关键词。
  5. 趋势分析：分析舆情的发展趋势和模式。
  6. 热点探测：识别热门话题和关注点。
  7. 报告生成：制作舆情分析报告，提供洞察和建议。

3. 为什么说一般的网络搜索技术无法满足网络舆情分析的需要?

一般的网络搜索技术无法满足网络舆情分析的需要，主要因为：

  • 搜索范围：舆情分析需要从更广泛的数据源中获取信息。
  • 实时性：舆情分析要求高度的实时性，以快速捕捉舆论变化。
  • 深度分析：舆情分析需要深入理解文本的情感和语境，不仅仅是关键词匹配。
  • 趋势追踪：舆情分析需要跟踪话题的发展和变化，而非简单的信息检索。

4. 网络舆情分析中监控目标热点自动发现功能主要利用了哪些典型的安全技术?

网络舆情分析中，监控目标热点自动发现主要利用的安全技术包括：

  • 数据挖掘：使用数据挖掘技术发现数据中的模式和趋势。
  • 机器学习：利用算法自动识别热点话题和关键信息。
  • 文本分析：使用NLP技术深入分析文本内容。
  • 实时监控：实时监控网络数据流，快速捕捉热点变化。
  • 情感分析：识别舆情的情感倾向和强度。

5. 未来影响网络舆情分析及预警技术主要有哪些?

未来可能影响网络舆情分析及预警技术的主要因素包括：

  1. 人工智能的发展：更高级的AI技术将提高分析的准确性和效率。
  2. 大数据技术：更强大的数据处理能力将允许分析更大规模的数据集。
  3. 自然语言处理的进步：更深入地理解和分析文本内容。
  4. 社交媒体的变化：社交媒体的新趋势和平台将影响舆情的形成和传播。
  5. 隐私和数据保护法规：可能限制对用户数据的访问和使用。
  6. 网络安全技术：保护数据和分析过程不受网络威胁影响。
#大三上 #期末复习 #网络内容安全
网络内容安全 | 内容要点总结
https://harrison-1eo.github.io/2023/12/20/网络内容安全总结/
作者
Harrison
发布于
2023年12月20日
更新于
2023年12月23日
许可协议