机器学习浅析

ID：Computer-network

信息安全领域内有两类人，一类人害怕机器学习，一类人明白机器学习在很大程度上解决了垃圾邮件问题但同样害怕机器学习。机器学习被描述为“一种不用显式编程，并能让计算机具备自学能力的人工智能”时，感觉很吓人。计算机如何在不被显式编程的情况下来完成某件事情？为了更好地理解机器学习，还是来看看Tom M.Mitchell在1997年的《Machine Learning》中的著名定义：

如果一个计算机程序针对某类任务T以P衡量的性能根据经验E来自我完善，那么我们称这个计算机程序在从经验E中学习，针对某类任务T和性能度量P。

现在清楚什么是机器学习了吗？这个宽泛的定义很难帮助人们来理解这个概念，它仅仅描述了机器学习抽象的结果，而没有介绍什么是机器学习，怎么来应用机器学习。

一、检测恶意软件

假设您已经记录了所有系统的内存和处理器的使用情况。花费一番精力后，您已经检查了250台计算机，发现有些系统已经感染了恶意软件，有些系统则是正常（没有恶意软件）。但是还有另外445个系统没有检查，您想节约时间并通过已检查得到的数据来判断这445个系统是否感染了恶意软件。

这个例子将用R语言来构建一个算法，该算法被训练用来完成对系统是否感染恶意软件进行分类。首先加载主机上的数据并对数据进行检查（参考代码1）。

代码1

在上面示例中，53台主机被标记为“已感染”，194台主机被标记为“正常”。另外，处理器数据和内存信息已经做了归一化处理。这样可将这些数字保持在同一尺度内。当用机器学习方法比较不同变量时，对变量进行归一化是非常重要的。为了进一步探索这些数据，可将这些数据绘制出来（见代码2）。基于感染恶意软件的状态可以比较并区分处理器和内存数据（见图1）。

代码2

图1  系统中的处理器和内存

是否发现已感染的系统似乎使用了更多的处理器和内存资源？根据这些已知主机的相对位置（图1中的散点图），也许可以编写一个算法将这些数据进行分类。在此之前，最好还是做一个小计划。首先需要考虑使用哪种机器学习算法，然后想办法测试这种算法有什么优点。在实际问题中，最好还是尝试几种不同的算法和特征。

1、开发机器学习算法

每次看到算法（algorithm）这个词的时候，试着在脑海里用“一系列的指令”来替代，因为这其实就是算法的本质。您需要编写一系列指令来告诉计算机如何检查和理解这些数据（这样它才能学习）。然后计算机可以将它所学到的知识应用到这些系统中并进行分类，而这些知识您并不知道。

您是否知道自己对编程有多不了解？尽管您绝对是在写电脑程序，但您并不能明确地写出电脑用的判决准则，这两点是有区别的。您的一系列的指令（算法）会明确告诉计算机怎么去检查这些数据，它应该通过这些数据怎样建立自己的判决准则。与设计传统防火墙、入侵检测防御系统的编程方法相比，这些数据并不会直接向计算机传达判决准则。在这些准则方法中，人们试图找到最好的方法然后显式编写相应的规则并让计算机来执行。这种方法有它的局限性，遗憾的是，我们的安全系统几年前已经达到了这个限制。在机器学习中，计算机从数据中学习并将学习成果应用到其他数据中。和人类相比，计算机发现数据之间微小差异的能力更强，而这也是机器学习现在所做的工作。

这里提到的“模型”（model）和“算法”（algorithm）似乎有些容易混淆。二者之间的差异很小，甚至有点令人困惑。“模型”一词用得比较普遍，它仅仅定义了怎样将各个元素结合起来。“算法”是实现一个“模型”的特定方法，所以同一个“模型”可以用许多不同的“算法”来实现。

回到图1中所展示的数据上来，也许您想编写一串指令来了解正常主机上的处理器和内存使用情况，然后同被感染主机上的处理器和内存使用情况进行比较。一旦发现这两组数据集中有一些不同的信息后，就可以向计算机发送指令将这些信息应用到收集到从未知/未分类的系统收集到的数据上。切记这里的目标是让计算机来判断系统是否感染上恶意软件。思考下面这个简短的算法，看看它是否容易理解和执行：

（1）定义和训练一个算法：

a）计算已知且感染恶意软件系统的处理器和内存平均使用情况。

b）计算已知正常系统的处理器和内存平均使用情况。

（2）使用处理器和内存使用情况来预测未知系统是否感染恶意软件：

a）如果处理器和内存使用情况更接近感染主机的平均情况，将该系统标为已感染。

b）如果处理器和内存使用情况更接近正常主机的平均情况，将该系统标为正常。

请注意第一步中的用词，是“训练”这个算法。这也是描述机器何时从数据中学习的术语；数据训练算法，就像师傅教徒弟一样；用来对算法进行训练的数据被称作训练数据（training data）。在这个简单的示例中，训练仅涉及用训练数据对感染和未感染系统的平均使用情况进行计算。这是一个单步的训练过程，相比之下，大多数真正的机器学习算法使用迭代或者多步训练过程。

2、验证算法

在根据这个算法进行实际决策之前，应首先保证该算法是有效的，需要使用一些方法来测试这个算法对于预测系统感染的准确程度。与其把全部数据用作算法训练，不如留一部分测试，预测恶意软件算法的准确性。在测试过程中有一个好方法，即机器学习。机器学习也是由计算机科学和统计学演变而来的，很适合用在这里。许多技术都涉及验证您做的决策，这一步在整个过程中十分必要，它已演变成模型选择过程中不可或缺的一步。

对于这个示例，验证比较简单，将原始数据分为两个数据集即可。在比较严格的机器学习项目中，也许需要将原始数据分为多个数据集，在这些数据集上进行多轮迭代来完成训练和测试（包括验证在内）。

就像刚才提到的，将数据分为两组。第一组是训练数据，需要使用它来对算法进行训练；第二组则是测试数据，主要用来测试所采取的方法。为了确保数据分组的随机性，可使用sample()命令。首先要生成原始数据的随机抽样索引（即在向量数据中的位置），并用它将原数据分为训练数据和测试数据。怎么对数据分组并没有明确的规则（不同技术的划分方法不用），只需使用三分之一的数据用来测试，并使用剩下三分之二的数据来训练算法。因为这里有一些随机性，所以我们通过设置随机数生成器的种子来使分组操作可重复（见代码3）。

代码3

现在可以基于训练数据训练算法，并通过测试数据来验证算法的好坏。请牢记，用于验证有很多健壮的方法。像这样对数据分组进行训练和测试比仅仅空想算法好很多，但是在实际使用中，还是需要使用更健壮的验证方法，例如交叉验证。

3、实现机器学习算法

回想一下上面算法训练的第一步，即分别计算被感染和正常系统中处理器和内存的平均使用情况。基于“state”字段取行子集（即只返回感染主机和正常主机），并将它应用到“proc”和“mem”字段的列中。整理组后的数据可直接传递到colMeans()函数，该函数可计算这两列的均值，然后返回一个包含两个元素的命名向量（见代码4）。

代码4

这里计算出来的均值之间的差异并不小，所以这个相当简单的方法可能比较好地实现了这个简单的算法。现在已经有了训练好的算法，可以准备进行预测了，下一步需要创建一个predict.malware()函数（见代码5）。这需要接收一个叫“data”的单一命名向量，抽取其中的“proc”和“mem”值，然后计算这些值与刚才在算法训练过程中得到的均值距离有多远。用什么方法计算距离最好呢？回想一下几何课和勾股定理：a2+b2=c2，公式中a和b是三角形的两条边，c是斜边。这个就是“欧几里得距离”，它是基于欧几里得理论的。在这里，a是训练和测试得到两个proc值的差，b是训练和测试得到两个mem值的差。得到这两个距离后，仅仅做比较即可。最小的那个就是预测值（见代码5）。

代码5

如果愿意的话可以随便传进一些值并检查一下输出结果。现在，基于测试数据的一切操作都准备好了。可以使用apply()函数来传递测试数据，函数的第一个参数是测试数据集，第二个参数设为1，表示应用到每一行（如果为2的话表示应用到每一列）。然后需要将刚才得到的predict.malware作为第三个参数传递到apply()函数中（见代码6）。apply()函数把每一行数据转换成一个命名向量。在这里需要细心一些，因为“state”和“host”变量都是字符，当apply()函数将数据传进来后整个向量将转换成一个字符型向量。这就是为什么在predict.malware()函数中使用as.numeric()将“proc”和“mem”转换回数值变量。

代码6

从不差到更好，再到零模型。

上面描述的只是一个非常基础的算法，对它进行描述也是出于讨论的目的。在统计学中有一个概念叫零模型（null model），这是一个非常简单的模型，一般都尽量建立一个优于它的模型（或者至少不会更差）。例如，在ZeroAccess木马感染数据中，零模型可以是从所有州的机器（5253台）中计算平均感染率。这个零模型（用于预测）不需要州的任何数据就可以估测出一个州有5253台被感染的主机。在这个示例中，通过省略和取消一些变量的使用来简化这个模型。从直观感觉上看，您也许能发现所有州的均值并不是很合适预测，但这就是最终目标。以这个模型为参考点，并超越它。即使这看起来像是废话，但我们并不是开玩笑。您可以花很长时间来准备数据和训练一个复杂的支持向量机，但它可能表现得比这个简单的模型还差。还是先花时间构建一个可以基本满足条件的简单模型，再在此基础上改进和优化吧。

一旦测试数据在那段代码上运行起来，您会得到预测值的集合，并将这些预测值和真实值进行比较（看到这个方法的力量了吗？）。为了判断该方法表现的好坏，需要看看在测试数据上预测准确率有多少。可以计算预测准确的数量（实际值test$state和预测值prediction相同）除以预测的总数量（见代码7）。

代码7

这个非常简单的算法预测准确率差不多达到了88%，这也许仅是对如何划分数据的描述而不是对算法功能的表达。但总的来说，88%的预测准确率对第一个机器学习算法来说已经相当不错了，算法最终结果如图2所示（见彩图）。

图2  从算法中预测

这个分类器在两个均值之间构建了一条直线，并垂直于相交线。处于直线上面部分的数据被预测成感染恶意软件，而下面部分的数据则被预测成未感染，分类错误的个体在图2中进行了明确标示。从图中可以看出直线上面部分有多少被误标记为正常系统，下面部分有多少被判为被感染系统。

二、从机器学习中获益

既然已经看过一个相当简单的示例（或许过于简单），您应该在机器学习带来的思维变化方面有一个基本的了解。机器学习不是侧重于设置规则和签名，而是把重点转向基于计算机直接从数据中学习并不断调整。阈值和正则表达式规则的时代很快一去不复返。

在您了解有关机器学习的益处之前，需要了解两种机器学习算法：有监督算法和无监督算法。使用哪种类型主要取决于拥有的数据类型，而不是取决于个人喜好。

有监督算法要求训练集已经知道像前面样例那样的样本。样例中的数据已经标识了主机是否被恶意程序感染。另一个例子是ZeroAccess数据，已知在每个州和国家有多少感染并且能够通过州和国家把这些数据与其他数据关联起来。有监督学习只有当有标记或已知数据时应用才合理。

无监督算法通常用于预先不知道期望输出什么样的数据。无监督学习尽可能“让数据自己说话”。举个例子，想一想亚马逊或Netflix的推荐系统。这些系统从电影出租或购买电影的历史数据出发，应用无监督学习技术根据数据中的模式将相似的人（确切地说是他们的习惯）分组。这使他们能够推荐其他像您一样的人购买过的商品。事先不必确定每个组是应当什么。无监督方法使您发现各个组及关联关系，好像没用其他方法就做了其他有代表性的深入探索。考虑到这些方法的无监督本质，很难用无监督方法确切证明一些事，但不是它的设计目标。使用无监督学习方法您将会发现一些有趣的关系。

参数化还是非参数化，这是个问题。

除了有监督和无监督，机器学习算法也可以按有参和无参方法来划分。参数化（parametric）这个词是指作为训练步骤的结果，模型或算法中至少有一个参数需要估计。线性回归就是个有参模型。1m()命令输出的一部分是线性系数（参数），然后把它用于回归分析中的预测和推理。把这个与随机森林算法相比，训练一个随机森林算法不需要估计参数。取而代之的是生成一系列决策树用于之后的分类。

1、用机器学习回答问题

机器学习能回答什么样的问题？它能解决什么样的问题？广义上讲，机器学习能帮您解决如下问题：

分类

定量预测

推理

探索和发现

文首的例子已经介绍了分类的概念，就是要判断主机是否被感染。分类（classification）是识别一些事物的类别归属或决定应该贴上哪些标签的过程。通常根据一系列可能的类别和描述这些类别的已知数据开始分类（所以它属于有监督算法）。许多在信息安全中的策略挑战只围绕着一个分类问题，如“这是不是恶意的？”机制用于对用户认证并授权，但是他们的行为是否与正常用户还是恶意用户相匹配？此HTTP请求有效吗，或者来源攻击是否合理？这些都是分类算法最擅长解决的问题。

如果您想要预测数量呢？机器学习（和经典统计学）提供了做定量预测（quantitative prediction）的方法。总体做法可能会使有很强工程背景的人有点不习惯，觉得根本不可能预测。但是，别紧张，没人说数据中隐藏着精确的未来。但是您可以利用数据做一个很好的估计。给出一系列观察值和结果输出（再强调一次，这些是有监督方法），可以构建一个估计未来值的预测模型。

回顾一下线性回归分析。如果利用另一个州6百万人发生的怪异事件做回归分析，可以预测那个州ZeroAccess感染少于5000个。虽然这个例子不完全是实际发生的，但是您也可以用这项技术估计下个月的带宽使用量，或者甚至可以预测下一次DDoS攻击的量级。

有时最终结果不是预测数量或类别，只是想知道观测的变量对决策的贡献、对结果的影响有多大。这种情况下要用推理（inference）的方法。您可以用推理的方法来描述您的环境。这些变量有多重要？有关处理器和内存使用情况的数据是不是判别主机受感染的最佳预测因素？举个例子，线性回归把多个变量送到单一分析中，并看出每一个变量怎样对结果做出贡献以及变量之间的定量关系。有监督和无监督方法都支持变量的推理，推理是任何模型或算法最重要的部分。

机器学习的最后一项应用是探索和发现（exploration and discovery）。这个领域无监督算法表现极佳，但有监督算法也支持探索。有时您被困在一堆数据中，想知道数据中存在的关系和模式。使用如多维尺度分析和层次聚类的方法会帮助您探索并获得从简单描述性统计得不到的数据深层内容。

2、评测良好的性能

良好的学习核心是良好的反馈。如果您创建模型和算法却从不检测是否表现良好，那么注定要重复相同的错误，而且几乎不可能有改善。这就是一些评测有监督算法性能的技术的基本概念。理解无监督算法一般不需要证明（或证伪）某推测的重要性。

根据常识，评测任何预测算法性能的最佳方法是简单地看看它预测的有多么好（如果您是个悲观主义者也可以看预测有多么差）。这里没有一个完美的办法，因此您要选一个比所有可用方法更好的方法（不要简单地因为有缺点而拒绝一个有用的方法）。所有梦幻的数学公式在描述过程时无非只是在一个简单主题上变化：如果您处理的是定量数值，选择预测值最贴近观察值的方法。如果您处理的是分类系统，选择正确分类数最多的模型。

在经典的回归分析中，计算每个预测值和观察值的差值平方后求和。将差值平方，放大了更大的距离，保护了更小值，给出了比较好的质量表征。这个用术语来讲是误差平方和（Sum Square of Errors,SSE）。在用多种方法表达同一件事的传统下，它也称为平方误差、残差平方和（SS residual）或平方残差（RSS）。

因为计算SSE要累加平方差，样本量越大，SSE值越大。这导致当训练集和测试集数据点数量不同时无法比较。可以除以数据点的数量（样本大小）来标准化SSE，这样当样本大小不同时也能比较结果。这个结果叫做均方误差（Mean Squared Error,MSE）。这个概念先于训练集和测试集，它是在用于训练的数据集上进行计算。仅依赖训练数据MSE的挑战是容易过拟合。比较定量模型和算法的一个办法是计算MSE并比较多种方法和特征选择。

因为学习算法是从数据中“学习”，就有可能学得太多或对数据过于信任。这种情况下，算法可能在训练数据上表现相当好，但在实际数据中运行时就不幸失败了。这叫做过拟合，它发生于训练算法在拟合训练数据时过于强势。因为训练数据是样本，它有自己怪异的模式和特征，但这些与全体数据不符。理想情况下，我们希望学习过程忽略掉训练数据的怪异模式，只关注应用于总样本的特征。意识到过拟合是件好事，下面将介绍一些用来检测和避免过拟合的方法。

3、选择特征

在训练算法和评测性能之前，您需要对数据进行处理。机器学习中讲的比较少的一点是怎样着手选择要收集的数据用于分析。收集到并用于算法中的变量称为特征（feature）。在经典统计学中也叫做解释、独立或预测变量（或一些其他名称）。文首的例子中的处理器和内存使用量就是用于训练算法的特征。

特征选择的棘手之处是选择初始特征集没什么准则，这就需要领域专业知识来主导。您选择了可能重要的数据点，然后在这些数据上运行某个算法并检测它们是否真正对输出有所贡献。尽管试图抓住所有要点，但要记住数据收集和清理是有代价的（至少在时间和资源上）。还要注意许多方法在变量少时表现好，变量多时表现却很差。

举个例子，如果想改进恶意软件分类器，您可能会从网络流量日志中抽取变量，如使用的端口和协议、频度、数量作为出发点。最初的变量不那么重要，因为无论最初怎么选择都毋庸置疑会出现错误，没关系。抓取有意义的数据然后试着去理解它们。您会发现只有一些变量有用，或没有一个变量效果好，或者结合使用才好。但关键是特征选择是一个迭代过程。最后，您不应该只关注特征对输出结果贡献有多大，也要看整体算法性能有多好（或准确），然后在上面尝试改进。

（1）使用最优子集

给定一系列特征，怎样确定包括或排除哪些？一种方法是尝试特征的每种组合，选择表现最优的特征子集。这种技术恰如其分地称为最优子集（best subset）法。尝试每种可能的组合，即是这种方法的优点，也是缺点。一方面，它可以发现不用暴力方法找不到的特征组合。另一方面，必须测试全部特征组合，这要花费相当多的时间。作为参考，在整个算法和验证步骤中，在20个变量上使用最优子集选择法将花费至少一百万次迭代。

最优子集法还有一点值得注意。随着特征数增加，找到虚假特征关系的可能性也会增加。幸好这种情况不会悄无声息地发生。这种方法的过拟合会看上去在训练数据上极佳，但在测试数据上表现很差。解决这个问题的途径之一是在测试集上应用若干个最优子集，或转而用其他技术。

（2）使用逐步比较

因为最优子集的暴力方法不可行或不可取，所以逐步逼近法可能是一种较好的折衷。这种方法逐步构造正确的特征集，而不是一下子投入全部。在逐步逼近过程的前段，这种方法首先对每个特征分别训练。保留表现最优的特征，然后向结果中再添加一个特征并重复前面的过程。根据贡献大小，这些特征被依次添加。当添加完全部特征，每步表现最优的算法已经比较过了，最终选择的集合就是全局最优的特征集合。

与最优子集法相比，这种方法的优点是在迭代过程中极大地降低了数量。缺点是没有试过所有组合，从而可能忽略掉最优组合。在某些情况下，单独一个特征表现最优，在添加其他特征后就不会有最优表现了。您也可以将逐步比较法倒过来用，一开始使用全部特征，然后按顺序回退，移除最没用的特征，直到只剩下一个特征。最终，您看到了所有最优组合并选择最优的特征。

4、验证您的模型

无论您怎样做特征选择，都要验证算法性能如何。每种算法的工作原理、生成和关注的测试统计量可能有细微差别。有几个验证成果的通用方法，它们几乎能用于所有算法。最广泛应用的是交叉验证（cross-validation）。另一类验证方法是一些重采样方法，比如自举法或刀切法。

文首的例子首先将247个观察值划分开来，其中训练集用来训练算法，测试集用来测试训练得如何。数据是随意划分的，2/3作为训练数据，剩下的1/3作为测试数据。这么做的一个缺点是不能对取出的1/3数据做训练，在训练过程的输出会引入更多差异。

假如重复切分和测试过程，这样会不会所有数据都对训练和测试算法起作用呢？通过生成多组训练和测试集并比较所有划分方法的结果是有可能提高算法准确度的。这种方法叫做交叉验证，它的效果比您只切分一次数据更好。

执行交叉验证通常的方法是把数据切分成相等的几份（多于一两份），然后每次取一份作为测试数据，反复迭代。这叫做k折交叉验证（k-fold cross-validation），因为您把数据折叠了k次（每次取一份）。例如，回顾第一个例子中的数据，将它划分为10份，整个过程重复10次，每次取不同的测试数据集和稍有不同的训练数据集。综合（平均）了每次迭代后准确度的估计值，算法在新数据上运行会有更高的置信度。

K折交叉验证的一个变种是把份数设置成数据中的样本数，这样结果就是留一交叉验证（leave-one-out cross validation）。这样命名是因为您可以从训练集中按顺序留下一个值，对整个数据集测试这一个数据。这种方法的结果在评估算法时往往更准确，但会带来计算上的开销。

三、具体的机器学习方法

机器学习的方法众多，我们选出了一些方法，简要地说明它们的独特之处，包括其优缺点等。然而机器学习领域非常的宽泛和精深，所以很多方法这里并不会一一提及。不过，不要因此认为未提及的方法不太重要或者效果不太好。与此相反，类似神经网络或支持向量机的方法在某些情况下会有更好的效果。我们仅选取几种方法作为介绍和概述。

1、有监督学习方法

有监督学习方法要求训练数据是已知或者标记过的。除非您有来自已知正常和被感染系统的数据，否则将无法应用有监督学习方法进行恶意软件的检测。虽然在有些情况下这会带来一定的挑战，但是有监督学习方法的效果会让这种额外的付出变得值得。

（1）线性回归（和变换）

当涉及自变量的定量预测和推理时，线性回归是一种非常流行的方法，效果也很好。线性回归自19世纪末开始出现，现在已发展成为一个稳健而灵活的方法。线性回归一个早期的突破是，其可被用于处理非线性的数据。例如，图3中的线就是利用线性回归方法对数据进行拟合的结果。

图3  非线性数据的线性回归结果

您能看出图3中的线性关系吗？不管您相不相信，图中的线性关系确实存在。线性回归中“线性”一词指的是估计出的线性系数（linear coefficient），而不是数据。换句话说，您可以用一个线性模型来描述非线性数据。这里的技巧是，在运行线性回归之前对数据做变换。重新观察图3，可以发现x和y之间的关系是三次多项式，以及围绕y=x3的一些变动。因此，对变量x进行变换后将其包括在模型中，从而可以估计这些变量的线性系数。在对变量进行变换时，要注意不要过度拟合数据。通过增加足够多的变换变量可以非常完美地拟合训练数据，但是这种方法在测试数据或真实数据上的效果会非常差。

线性回归方法有很多的变化和细微差别，这使得其功能强大，特别是当和前面所提到的一些方法相结合的时候。经典的线性回归依赖于p值来评估模型和变量的显著性。近几年的趋势则将验证方法也整合进来，如交叉验证，用于模型的选择和验证。可以参考R中的lm()和glm()命令来了解如何运行线性回归。

（2）逻辑回归

线性回归可用于定量变量的预测，所以当问题不是定量的时候，线性回归就失效了。例如，在文首例子中，当您需要将主机分类为感染和未感染时，线性回归是不会有帮助的。相反，您可以借助逻辑回归进行处理，该方法是对线性回归的一种扩展。逻辑回归的输出结果只有两个，是或否。图4给出了训练数据的逻辑回归结果。

图4  感染测试数据的逻辑回归结果

输出结果（x轴）是基于输入变量所估计出的主机被感染的概率。将输出结果同测试数据的已知数值（y轴，实际情况中此值未知）对应绘制在图上。很明显，在给定这些输入值的情况下，就能正确估计出大部分主机的状态。不管判断阈值如何设定（例如，在0.4以上的主机被认定为已感染），都会产生一定的假阳性（主机未感染，被认定为已感染）和假阴性（主机已感染，被认定为未感染）。习惯上，逻辑回归主要用于进行逻辑分类（是或否）。

在R中，有多种方法可以运行逻辑回归，然而，glm()能够处理大多数的情况。

（3）K近邻

K近邻方法可以用一个通用的体育类比来很好地描述。假设您想要从世界上任意一个地方随意选择一个人，然后预测他所喜爱的运动队。当您随意选择那个人时，您可以问他的邻居和朋友们（他们中的k个，其中k值保持一致）喜欢哪支队伍。然后，您可以确定他的邻居们喜欢哪只队伍的人最多，然后假设您选出的那个人跟他的邻居们兴趣一致。

K近邻算法做的是同样的事情。给定一组已知的（这是有监督学习方法）的变量，对于每个新的数据点，该算法使用离其最近的k个数据点（您选择的k值），并假设新的数据点与它的邻居们类似。这与文首例子中的线性分类很不相同。这种方法的准确度随着观测数量的增加而增加。该方法的一个缺点是，它对k值的选择很敏感。当k非常大时，这种方法的划分边界会越来越接近线性。总的来说，K近邻方法是一个非常高效的分类方法，并且优于许多其他的方法，值得我们认真理解。

在R中，class软件包中提供了K近邻方法的支持（以及其他的knn函数）。

（4）随机森林

随机森林法建立在决策树的概念上，擅长处理多维数据（特征很多的数据）。决策树就是IT工作者所认为的流程图。从一棵树的顶部开始，通过观测特征与决策树内阈值的比较，将分支沿着不同的方向分下去。给定数据类型后，能够想象可以构造出的各种决策，如果数据高于平均水平，放在这里；如果数据符合该类别，则放在那里。如果数据非常复杂，则必须要用到一个以上的决策树。有个称为boosting的方法能够创建大量的决策树，然后根据所有的决策树得出总体结果。boosting极大地改进了分类的效果。虽然单棵决策树的效果较差，但是他们的效果与最佳效果的差距都在可估范围内。因此，查看所有的决策树总能得到最优答案（找到森林延伸的地方）。

boosting决策树的效果很好，但容易受到噪声的影响。篮子中的一两个坏鸡蛋会不断地将决策树引向诡异而又难以察觉的方向，进而使最后结果出现偏差。随机森林法只利用一个小的特征子集进行建树，进而消除了这个问题。这虽然使得单棵决策树的预测效果更差，但是总体效果则得到了提升，因为包含噪声的变量只存在于单棵树所选的特征子集中，并不会受到森林中每棵树的影响。

随机森林带来了一种新的思维方式，属于非参数方法。该方法并不试图创建一个真实的模型，然后推导出模型的参数（如回归方法）。与此相反，随机森林创建了一大批的弱预测器，然后将他们聚合在一起。这就像去到一个新的小镇，只向游客询问方向。许多结果偏离度很大，但是当把所有结果聚合在一起的时候，您可能就会得到您想要的结果。

正如您想的那样，绝对不会试图用纸和笔来应用随机森林方法。这种方法基于随机特征的随机点，可以创建出上百甚至上千棵多分支的决策树，而且这些只需一台电脑的帮助即可完成。在R中，randomForest软件包提供了随机森林的方法。探索对应的并行方法同样是值得的，doParallel软件包提供了多核运算的解决方案，可以减少随机森林所需的计算时间。

机器学习所面临的挑战之一就是有些方法是如此的复杂和抽象，以至于推动着人类理解的界限。在某些时候，您会遇到一种方法所需的理解能力和它带来的性能之间的权衡。神经网络就是这种权衡的一个例子。在某些情况下，神经网络能提供更好的性能，但是他们相当复杂、难以理解以及理解不透而难以合理调校。您可能会选择一种易于理解、容易向别人讲解和易于使用的方法，即便伴随着性能上的些许下降，您也会满意。鉴于信息安全很多决策的复杂性，任何使用机器学习的方法都会比不使用方法要好。

2、无监督学习方法

无监督学习的方法在寻找数据潜在的模式和关系时非常有用。在给出的一堆数据中，都有什么样的趋势存在呢？

（1）K均值聚类

K均值，类似K近邻方法，使用“k”表示方法中的一个变量。k是要生成的类别个数。K均值方法遵循以下算法：

1）在数据中随机选定k个“中心点”。

2）将所有数据点分配给最近的中心点。

3）基于分配好的数据点，计算出一个新的（平均）中心。

4）移动中心点到新计算的（平均）中心。

5）重复步骤2）到4），直到步骤4）中所有的中心不再变动。

请注意步骤1中的K均值方法引入了随机性。这意味着，如果您重新运行K均值聚类，您可能会得到不同的聚类结果。图5给出了相同数据对应多个不同k值的聚类结果。在R中kmeans()函数可用于K均值聚类。

图5  K均值聚类结果及中心点

（2）层次聚类

K均值的缺点是必须要指定类别数目，而层次聚类则无需如此，能够得出数据内的所有类别。层次聚类的输出被称为树状图，看起来像一棵树，从顶部开始，依次向下分成两个分支，直到所有的对象都各成一类。从算法上说，这种方法实际上是从底部每个数据都各成一类开始，然后遍历所有类别配对进行比较，寻找最相似的类别配对。当找到相似的类别时，将两个类别合并起来。重复此过程直到顶部只有一个类别包含所有的数据。

层次聚类的优点是，可以在树的任意一点截断，观察聚类结果。

（3）主成分分析

主成分分析（principal component analysis，PCA）能够减少特征数目，留下真正重要的特征，是少数几种降维（dimension reduction）方法之一。PCA在高度相关的数据集上效果最好，因为它能够用少量的变量捕捉到数据的大部分变化。PCA的结果是推导出的成分列表，按照所描述的数据方差大小排序。当数据被提炼成这种形式，便可以抽出其中显著的成分，使用这些数据进行进一步处理，而不是用之前具有更多维度的数据。在R中运行PCA需要使用prcomp()命令。

（4）多维尺度分析

有时候您可能想看到聚类结果的图形化展示。然而当数据是多维的时候这是个问题，因为高于三维（甚至在平面屏幕或纸上展现第三维都是困难的）的事物无法进行可视化。对应的解决方案可以使用一种多维尺度分析（multidimensional scaling，MDS）的方法。如同PCA一样，MDS也可以进行数据降维。它可以将多维数据压缩到两维，从而可以可视化对象间的相似性。

四、实验：攻击数据聚类

这里，我们仍使用VERIS社区数据库来演示数据的多维尺度分析和层次聚类分析。

原本分析攻击数据的方法是简单地数数类别，看看哪些经常发生，然后从这些信息里概括出结论。但这里的挑战在于如果结论不能很好地适应该数据，结论有可能过于宽泛。简单处理数据之后，会发现不同的行业有不同的问题。当然，每个行业也有一些共性，例如他们处理的信息类型相同，导致一些行业要有针对性地增加或减少。同一行业的一些组织更有可能与同行业类似，因此这些数据也有可能会展现一些模式。

接下来的问题是：

不同行业间的事件有多少差异（相似）？

这个问题很有意思，也很有挑战。我们刚开始的感觉是不同的行业应该是不同的。解决该问题最好的方法就是聚类。如果您能找到行业间具有区分性的变量，那就可以计算行业间的“距离”，以确定哪些行业相似，哪些具有独特的特征。

我们首先要把VCDB数据转换成矩阵（见代码8）。我们还没怎么接触过R里面的矩阵，不过这些矩阵与固定行和列宽度的数据帧较为相似。（类似电子表格的单元格，哪些是“行”长和“列”宽。）矩阵唯一的特性就是所有变量的类型必须相同（比如字符类型或数值类型）。现在的工作是把VCDB转换成数值矩阵。还好，verisr包已经有这个函数，即veris2matrix()。使用时要先加载versir包。

代码8

看下dim()的输出，VCDB的数据转换成的矩阵有1643行（每行代表数据仓库里的一个事件），264列。每一列是单独的枚举类型，可以通过colnames()命令查看每列的名字，当用veris2matrix()创建一个矩阵时，会为VERIS数据的每个类型创建唯一的一个列。例如，如果黑客的攻击中会涉及SQL注入攻击，矩阵中就会有一列，action.hacking.variety.SQLi，对应的值会根据事件中有没有注入攻击赋值成0或1，并填充完整个事件矩阵。如果所有的事件都没有SQL注入，这一整列不会显示。从这点看，这个矩阵就是0或1的集合，这么看，这些数据的直接用处不大，但会作为基础数据用于产生训练数据。

下面，我们来定义比较受害行业时用到的变量。为了得到变量列表，您可以简单看下列名。使用victim.industry来获得列名，然后把这些列名作为变量（见代码9）。这步转换您可以通过verisr中的函数foldmatrix()完成，这个函数的参数是刚才创建的数值矩阵以及变量列表（根据变量对矩阵进行处理，本例的变量是受害行业）。

代码9

您还可以传入另外两个参数，第一个变量是min，代表每个行业中事件数的最小阈值。如果一个行业的事件数小于min，这次分析中不会包含该行业。本实验中，您可以将min设为10。另一个变量是clean，该变量会调用函数清理最后的矩阵，将小于min的行删掉，同时删除所有值都相同的列。之所以进行清理是因为那些变量对分析没有帮助，如果用这个方法进行PCA分析的话，必须提前清理矩阵，否则会报错。

总共有17个行业（实际上是来自NAICS规范的17个两位行业代号）。经过清理之后，矩阵少了13列，现在矩阵的每一行代表一个行业，每一列代表一个VERIS变量。对应的值代表该行业中VERIS变量对应事件的比例。

例如，保健服务行业的SQL注入对应的值（action.hacking.variety列）是0.4，即100个保健行业内出现的事件中有40次包含SQL注入。可以通过比较发现这点，对一个变量跨行业进行比较就会发现不同。

1、受害行业的多维尺度分析

前面的所有工作都是为了准备好数据以便于在行业间进行多维尺度分析，这也是最神奇的地方。在数据分析的很多任务中，用于数据准备的时间比用于数据分析的时间还多。第一步是将行业和变量的矩阵转换成距离矩阵。距离矩阵使用Canberra距离（该距离在原点出衡量较准）度量行业间的两两距离。然后就可以用cmdscale()处理距离矩阵，该函数会将数据显示到一个二维画板上（见代码10）。

代码10

看一下cmdscale()的返回结果，已经有了x,y的坐标，完全可以用于可视化。实际上，您可以执行plot（cmd）看下这些点的分布。但是，现在的点还没有标签，我们需要花些时间来做一个更直观的图表。如果能显示出行业的事件的多少，图表会更加漂亮。由于您有原始的vmat矩阵，完全可以统计每个行业事件的次数。然后，应该用行业名替换掉NAICS的行业代号，因为这些行业代号看起来不是很友好。您可以装载verisr包中的industry2数据然后将行业代号映射成标签（见代码11）。

代码11

现在cmd中有两个变量：ind.count和txt.label，可以创建一个数据表格然后调用ggplot2()画图了（见代码12）。

代码12

使用ggplot theme()命令去掉所有内容是因为在显示时，比例和标签是不相关的。您可以看出一个行业相对于其他行业的相对位置，以为这里x，y坐标使用Canberra刻度来表示距离，数值大小并不是我们看到的意思。

图6很有意思，您可以看出保健行业和政府行业的受害者比较相似（很有可能是因为统计数据中大量的设备丢失或出错）。顶部的比较小的住宿类和零售类也很有意思，他们都遭到过“对销售点砸窗抢劫”的袭击。左下角的三个类需要进一步研究数据，否则很难说为什么这三个类会聚在这里。

图6  行业攻击的基础MDS点

2、受害行业的层次聚类分析

尽管图6可以完成一些类的可视化，但仍应比较谨慎。MDS将多维实体缩减为二维肯定会丢失一些细节。图6可以作为可视化的问题来讨论，不过作为进行深层分析的起始点也许更佳。

所以让我们重新对数据进行层次聚类，用数学驱动聚类。您可以简单地用hclust命令处理idist距离矩阵并用图表显示（代码13）。为了是标签更易读懂，您可以重新标注原始的行业矩阵的行名，重新运行dist()命令来重新创建带有可读标签的idst矩阵。

代码13

从图7中可以看出何时以及如何进行聚类。最后的结果是它们都自成一“类”，因为每个行业都是唯一的一个类。现在您可以使用cuttree()命令将层次树分成一定数量的类。可以尝试任何您喜欢的聚类数，但这里显示6个类。由于您是主观地切割树，所以没办法确定切割点处会有6个类（也无法确定可以分出多少个类）。只能说，如果层次聚类划分为6个类，结果是生成了6个类。

图7  受害行业的层次聚类

当执行cuttree()命令时，会读入hclust()命令的输出和要得到的聚类数，cuttree会返回一个聚类数大小的向量，标明每个行业属于哪个类。然后可以用一个颜色来表示一个类，重新绘制图表（代码14）。要实现这点，可以通过把cuttree()命令转化为一个参数并加入到之前创建的indf对象中。然后重新绘制彩色图表，见图8。

代码14

图8  受害行业聚类后的MDS图

还记得前面我们提到这一过程将多维数据转换成两维数据吗？看图8，可以发现，应该将运输业聚类到左下角的行业中，而不是离它近的贸易行业。尝试着改变cuttree()命令中的聚类数目。从这个详细的可视化中，应该发现更多的问题，而不是找到答案。为什么保健行业自己成为一类？为什么NAICS代号44的零售业和代号45的零售业差别明显。信息行业为什么会是现在的样子？好在我们有数据，这些问题的答案等着我们去发现。

五、结语

像R和Python这样的开源应用让机器学习算法运行起来相当简单。然而，将机器学习算法运行起来和运行得好相差甚远。无论喜不喜欢，机器学习深深扎根于统计学和数学，没有好的数学基础就试图深入这些技术可能会产生更多的问题。学习的最佳方式是动手实践：抓取（或生成）数据，阅读博文、书籍和文档，然后尝试一些方法。沿着这条路走保证会有些挫折，但成果是能更好地学习和更加全面地理解数据甚至您周围的世界，这些知识能够直接服务于您和您的组织正面临的日常基础安全决策。

微信公众号：计算机与网络安全

ID：Computer-network

【推荐书籍】