下载掌阅APP，畅读海量书库
立即打开
随着人工智能的迅速发展，其涉及的学科门类越来越多，如计算机科学、数学、心理学、哲学、语言学等。同时，人工智能在图像识别、语言处理、行政管理、金融等领域具有广泛的应用，特别是在军事领域，由于空天预警领域面临数据量大、关系复杂且难以快速处理的难题，人工智能作为一种革命性的技术，为预警情报的智能分析提供了新的技术途径。
智能优化算法又称现代启发式算法，是一种具有全局优化性能、通用性强且适用于并行处理的算法。智能优化算法可以针对某一问题，采用智能的方法寻找最优解。例如，在预警情报分析中，提取目标有效运动特征时会面临如何提取出最优特征的问题。这种算法一般具有严密的理论依据，而不单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。因此，采用智能优化算法可以通过启发式的方法提取出最符合要求的目标特征。下面重点介绍智能优化算法中的粒子群算法和遗传算法。
1.粒子群算法
粒子群优化（Particle Swarm Optimization，PSO）算法，简称粒子群算法，是一种全局寻优的智能优化算法，对解决群体问题有较好的效果。预警情报分析中目标的特征提取问题就属于典型的全局寻优问题，可用粒子群算法解决。
（1）算法思想。
粒子群算法是Kennedy和Eberhart受人工生命研究结果的启发，通过模拟鸟群觅食过程中的群聚行为而于1995年提出的一种基于群体智能的全局随机搜索算法。自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域之一是探索自然界生物的群体行为，从而在计算机上构建其群体模型。自然界中的鸟群和鱼群的群体行为一直是科学家研究的重点。生物学家Craig Reynolds在1987年提出了一个非常有影响力的鸟群聚集模型，在仿真中，每个个体应遵循的规则包括：①避免与邻域个体相冲撞；②匹配邻域个体的速度；③飞向鸟群中心，且整个群体飞向目标。仿真中仅利用这三条简单的规则，就可以非常近似地模拟出鸟群飞行的现象。其模型和仿真算法能够使“粒子”飞向解空间，并在最优解处降落。粒子群算法从这种模型中得到启示，并用于解决群体优化问题。Kennedy在他的书中详细描述了粒子群算法思想的起源。
（2）工作原理。
粒子群算法中每个优化问题的潜在解都是搜索空间中的“一只鸟”，称为粒子。所有粒子都有一个被优化函数决定的适应度（Fitness Value），每个粒子还有一个速度决定其飞翔的方向和距离。然后，粒子们就追随当前的最优粒子在解空间中搜索。粒子群算法初始化为一群随机粒子，然后通过迭代找到最优解。在每次迭代中，粒子通过跟踪两个极值来更新自己：第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个是整个种群目前找到的最优解，这个解是全局极值。另外，也可以不用整个种群而只用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。
假设在一个 D 维的目标搜索空间中，有 N 个粒子组成一个群落，其中第 i 个粒子表示为一个 D 维的向量 x i = （ x i 1 ， x i 2 ，…， x iD ）（ i= 1，2，…， N ）。第 i 个粒子的“飞行”速度也是一个 D 维的向量，记为 V i = （ v i 1 ， v i 2 ，…， v iD ）（ i= 1，2，…， N ）。第 i 个粒子迄今为止搜索到的最优位置称为个体极值，记为 P best = （ p i 1 ， p i 2 ，…， p iD ）（ i= 1，2，…， N ）。整个粒子群迄今为止搜索到的最优位置为全局极值，记为 g best = （ p g 1 ， p g 2 ，…， p gD ）。在找到这两个最优解时，粒子根据式（1.1）和式（1.2）来更新自己的速度和位置。
式中， c 1 、 c 2 为学习因子，也称为加速常数（Acceleration Constant）； w 为惯性因子； r 1 、 r 2 为[0，1]内的均匀随机数。式（1.1）右边由三部分组成。第一部分为惯性（Inertia）或动量（Momentum）部分，反映了粒子的运动习惯（Habit），代表粒子有维持自己先前速度的趋势；第二部分为认知（Cognition）部分，反映了粒子对自身历史经验的记忆（Memory）或回忆（Remembrance），代表粒子有向自身历史最佳位置逼近的趋势；第三部分为社会（Social）部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势。另外， i= 1，2，…， D ， v iD 是粒子的速度， v iD ∈ [ -v max ， v max ]， v max 是常数，由用户设定，用来限制粒子的速度。
（3）算法流程。
粒子群算法模拟动物种群的群体行为，通过自身经验和其他成员分享的经验改变自身运动方向，以此寻找食物。一般认为，任何一种模拟动物社会行为的寻优算法都为群智能优化算法。常见的群智能优化算法有蚁群算法、粒子群算法、蛙跳算法和人工蜂群算法等。
粒子群算法主要遵循邻近原则、品质原则、多样性反应原则、稳定性原则和适应性原则。其中，邻近原则是指种群中的个体可以进行简单的时空计算；品质原则是指种群可以对所处环境的品质因素产生反应；多样性反应原则是指种群应该在较大的范围内运动；稳定性原则是指当所处环境发生变化时，种群不必每次随之改变自身行为；适应性原则是指种群应该以付出较低代价为目的，适时改变自身行为。这些原则充分反映了此类优化算法中智能主体的自主性、反应性、学习性和适应性等智能特点。粒子群算法的一般流程如图1.4所示。
图1.4 粒子群算法的一般流程
首先初始化种群，其次计算种群内所有个体的适应度，再次获取个体自身经验和种群其他个体分享的经验，最后更新个体的运动方向。若仍未达到终止条件，则继续循环迭代；若达到终止条件，则输出最优解。在预警情报分析中，可将空中目标的特征按照种群类别进行划分，运用粒子群算法，经过不断迭代，寻找出最能代表目标类别的特征。
2.遗传算法
遗传算法（Genetic Algorithm，GA）用于模拟物种进化的过程，具有自动性、适应性等智能特点。在预警目标特征提取时，运用遗传算法能够较快地分析提取目标特征，分辨目标类别。
（1）算法演进。
遗传算法的起源可追溯到20世纪60年代初期。1967年，美国密歇根大学J.Holland教授的学生Bagley在他的博士论文中首次提出了遗传算法这一术语，并讨论了遗传算法在博弈中的应用。但早期研究缺乏对带有指导性的理论和计算工具的开拓。1975年，J.Holland等提出了对遗传算法理论研究极为重要的模式理论，出版了专著《自然系统和人工系统的适配》。该书系统阐述了遗传算法的基本理论和方法，推动了遗传算法的发展。20世纪80年代后，遗传算法进入兴盛发展时期，被广泛应用于自动控制、生产计划、图像处理、机器人等研究领域。
（2）工作原理。
遗传算法是从代表问题可能潜在的解集的一个种群（Population）开始的，而一个种群由经过基因编码的一定数目的个体（Individual）组成。每个个体实际上是染色体（Chromosome）带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，内部表现为某种基因组合，决定了个体性状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，开始就需要实现从表现型到基因型的映射，即编码工作。由于仿照基因编码很复杂，因此往往需要对编码进行简化，如二进制编码。
初代种群产生之后，按照适者生存和优胜劣汰的规则，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助自然遗传学的遗传算子进行组合交叉和变异，产生代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代种群更加适应环境，末代种群中的最优个体经过解码可以作为问题近似最优解。
（3）算法流程。
首先对优化问题的可行解进行数字化编码处理，其次随机创建初始种群，然后用适应度函数计算每条染色体的适应度，接下来进行选择操作获取较优的个体，再进行交叉和变异操作产生新的个体，避免陷入局部最优解，以更高效地寻找到全局最优解。遗传算法的流程如图1.5所示。
步骤1：通过随机方式创建若干按确定长度（长度与待求解问题的精度有关）编码的初始种群。
步骤2：通过适应度函数对每个个体进行评价，选择适应度高的个体参与遗传操作，适应度低的个体被淘汰。
步骤3：经过遗传操作（选择、交叉、变异）的个体集合形成新一代种群，直到满足终止条件。
步骤4：将后代种群中表现最好的个体作为遗传算法的执行结果。
遗传算法具有粒子群算法的部分性质，如该算法中也存在种群的概念。但是，遗传算法更偏向于进化，它可以不断地更新种群内的个体，而粒子群算法更偏重种群内部个体的信息协作。
图1.5 遗传算法的流程
在预警目标的智能提取算法中，可以在创建初始种群时编码，再通过选择操作、交叉操作和变异操作不断生成新的个体，以此更新种群，按照此法找出并提取最优的目标特征。
神经网络算法是深度学习技术的重要组成部分，是一类自适应非线性动态系统。神经网络算法就是模仿人类神经系统，通过神经元之间的各种连接来模拟人脑的信息处理过程，让机器像人类一样思考工作，甚至可以在某些方面超越人脑的能力，帮助人们解决更多的问题。
1.前馈神经网络
前馈神经网络（Feedforward Neural Network，FNN）简称前馈网络，是人工神经网络的一种。前馈神经网络采用一种单向多层结构，其中每一层包含若干神经元。在此种神经网络中，各神经元可以接收前一层神经元的信号，并输出到下一层。第0层称为输入层，最后一层称为输出层，其他中间层称为隐藏层。
（1）算法演进。
前馈神经网络是一种最简单的神经网络，各神经元分层排列。每个神经元只与前一层神经元相连，接收前一层的输出，并输出给下一层，各层间没有反馈。前馈神经网络是目前应用最广泛、发展最迅速的人工神经网络之一。其从20世纪60年代开始发展至今，理论研究和实际应用达到了很高的水平。
（2）工作原理。
前馈神经网络主要分为单层前馈神经网络和多层前馈神经网络。单层前馈神经网络是最简单的人工神经网络之一，其只包含一个输出层，输出层节点的值通过输入值乘以权重直接得到。取出其中一个神经元进行讨论，其输入到输出的变换关系为
式中， x i 是输入特征向量 X 的分量， X = { x 1 ， x 2 ，…， x n } T ； w ij 为 x i 到 y j 的连接权重；输出量 y j 是按照不同特征的分类结果； θ j 是偏置。
多层前馈神经网络有一个输入层，中间有一个或多个隐藏层（ Q 为隐藏层数量），有一个输出层，前馈神经网络中的输入与输出的变换关系为
这时每一层相当于一个单层前馈神经网络。例如，第 q 层，它形成一个 n q -1 维的超平面，对该层的输入模式进行线性分类，由于是多层的组合，最终可以实现对输入模式的较复杂的分类。
（3）算法流程。
整个网络中无反馈，信号从输入层向输出层单向传播，可用一个有向无环图表示。一个典型的多层前馈神经网络如图1.6所示。
在进行目标优化特征的提取时，可正向输入预警目标的基本特征，经过前馈神经网络处理后，输出能够辨别目标的优化特征。
2.循环神经网络
循环神经网络（Recurrent Neural Network，RNN）是一类以序列（Sequence）数据为输入，在序列的演进方向进行递归且所有节点（循环单元）链式连接的递归神经网络。其具体的表现形式是，网络会对前面的信息进行记忆并应用于当前输出的计算中，即隐藏层之间的节点不再是无连接的而是有连接的，并且隐藏层的输入不仅包括输入层的输出，还包括上一时刻隐藏层的输出。该算法可将上个节点的目标特征进行再次分析，增加了反馈功能，以保证目标特征的准确性。
图1.6 多层前馈神经网络
（1）算法演进。
对循环神经网络的研究始于20世纪八九十年代，并在21世纪初发展为深度学习（Deep Learning）算法之一。其中，双向循环神经网络（Bidirectional RNN，Bi-RNN）和长短时记忆（Long Short-Term Memory，LSTM）网络是常见的循环神经网络。
（2）工作原理。
在经典的循环神经网络中，状态的传输是从前往后单向进行的，然而在有些问题中，当前时刻的输出不仅与之前的状态有关，也与之后的状态有关，这就需要使用双向循环神经网络解决此问题。双向循环神经网络是由两个单向循环神经网络上下叠加在一起组成的，输出由这两个单向循环神经网络的状态共同决定。在每个时刻 t ，输入会同时提供给这两个方向相反的循环神经网络。双向循环神经网络结构如图1.7所示。
图1.7 双向循环神经网络结构
双向循环神经网络可以解决序列数据中长期依赖、梯度爆炸、梯度消失的问题。
LSTM网络是一种拥有三个“门”结构的特殊网络结构。LSTM网络靠一些“门”的结构让信息有选择性地影响神经网络中每个时刻的状态。门结构就是一个将Sigmoid函数和一个按位乘法结合在一起的操作。
称为门是因为使用Sigmoid函数作为激活函数的全连接神经网络层会输出一个0～1的数值，描述当前输入有多少信息量可以通过这个结构。这个结构的功能类似一扇门，当门打开时（输出为1），全部信息都可以通过；当门关上时（输出为0），任何信息都无法通过。LSTM网络单元结构如图1.8所示。
图1.8 LSTM网络单元结构
遗忘门和输入门至关重要。通过遗忘门和输入门，LSTM网络单元结构可以更加有效地决定哪些信息应该被遗忘，哪些信息应该被保留。
遗忘门：让循环神经网络“忘记”之前没有用的信息。遗忘门会根据当前的输入 X t 、上一时刻状态 C t -1 、上一时刻的输出 H t -1 共同决定哪一部分记忆需要被遗忘。
输入门：在循环神经网络“忘记”了部分之前的状态后，它还需要从当前的输入补充最新的记忆，这个过程需要输入门完成。输入门会根据 X t 、 C t -1 、 H t -1 决定哪些部分将进入当前时刻的状态 C t 。
输出门：LSTM网络单元结构在计算得到新的状态 C t 后需要产生当前时刻的输出，这个过程是由“输出门”完成的。输出门根据最新的状态 C t 、上一时刻的输出 H t -1 和当前的输入 X t 来决定该时刻的输出 H t 。
（3）算法流程。
循环神经网络算法具有短期记忆能力，可以处理时间序列数据。当前，RNN已经被广泛应用于文本处理、语音识别、语言翻译和序列预测等诸多领域。RNN结构如图1.9所示。
图1.9 RNN结构
不同于典型的全连接神经网络，RNN的隐藏层内有一种循环结构。如图1.9所示， X 是一个输入向量； S 是隐藏层向量； U 是从输入层到隐藏层的权重矩阵； O 是输出层向量； V 是从隐藏层到输出层的权重矩阵。另外， S 取决于当前的输入向量 X 和上一隐藏层的 s t -1 ； W 是上一隐藏层的值在本层的权重。RNN按时间展开如图1.10所示。
图1.10 RNN按时间展开
从图1.10中可知，在 t 时刻，神经元在接收输入向量 X 的同时还会受上一时刻 s t -1 的影响，最终得到隐藏层的值 s t ；然后得到输出层的值 o t 。输出层的所有神经元都与上一隐藏层的所有神经元相连，输出层的值为
式中， V 为输出层的权重矩阵； g 为激活函数。
隐藏层是RNN中的循环层，其值的计算公式为
式中， U 为输入向量 X 的权重矩阵； W 为上一时刻的输出作为这一时刻的输入的权重矩阵； ƒ 为激活函数。
将式（1.7）代入式（1.8），可得
从式（1.9）可以看出，RNN输出层的值 o t 与该时刻及其之前所有时刻的输入值 x t ， x t -1 ， x t -2 ， x t -3 ，…相关。这也正是RNN循环的意义所在。在对预警目标特征进行智能提取时，可对分段提取的结果进行分析，对正确的结果保留，对错误的结果删除，保证所提取特征的准确性。
在实际应用中，RNN一般采用梯度下降的方法训练模型，但是当处理较长序列时会发生梯度爆炸或梯度消失，RNN无法捕捉到长距离信息的影响。
3.卷积神经网络
卷积神经网络（Convolutional Neural Network，CNN）是一类包含卷积计算且具有深度结构的前馈神经网络，是深度学习的代表算法之一。卷积神经网络具有表征学习（Representation Learning）能力，能够按其阶层结构对输入信息进行平移不变分类。
（1）算法演进。
20世纪60年代，Hubel等通过对猫视觉皮层细胞的研究，提出了感受野这个概念。20世纪80年代，Fukushima在感受野概念的基础之上提出了神经认知机的概念，神经认知机可以看作卷积神经网络的第一个实现，其将一个视觉模式分解成许多子模式（特征），然后进入分层递阶式相连的特征平面进行处理。它试图将视觉系统模型化，使其在物体有位移或发生轻微变形的情况下也能完成识别。
CNN由纽约大学的Yann LeCun于1998年提出。CNN本质上是一个多层感知器，其成功的关键在于它所采用的局部连接和共享权重的方式，一方面减少了的权重的数量使得网络易于优化，另一方面降低了过拟合的风险。CNN是神经网络的一种，它的权重共享网络结构使之更加类似于生物神经网络，降低了网络模型的复杂度，减少了权重的数量。该优点在网络输入是多维图像时表现得更为明显，使图像可以直接作为网络的输入，避免了传统识别算法中复杂的特征提取和数据重建。在二维图像处理方面CNN有众多优势：能自行抽取图像特征，包括颜色、纹理、形状及图像的拓扑结构；在处理二维图像问题时，特别是识别位移、缩放及其他形式扭曲不变性的应用中具有良好的健壮性和较高的运算效率等。
（2）工作原理。
卷积神经网络仿造生物的视知觉机制构建，其隐藏层内的卷积核参数共享性和层间连接的稀疏性使得卷积神经网络能够以较小的计算量提取特征，如对像素和音频进行学习，有稳定的效果且对数据没有额外的特征工程要求。卷积神经网络是一种多层的监督学习神经网络，隐藏层的卷积层和池化层是实现卷积神经网络特征提取功能的核心模块。该网络模型通过梯度下降法最小化损失函数对网络中的权重参数逐层反向调节，通过频繁的迭代训练提高网络的精度。卷积神经网络的低隐层由卷积层和最大池化层交替组成，全连接层对应传统多层感知器的隐藏层和逻辑回归分类器。第一层全连接层的输入是由卷积层和池化层进行特征提取得到的特征图像。最后一层输出层是一个分类器，可以采用逻辑回归、Softmax回归甚至支持向量机对输入图像进行分类。
卷积神经网络结构包括卷积层、池化层、全连接层。每一层有多个特征图，每个特征图通过一种卷积滤波器提取输入的一种特征，每个特征图有多个神经元。
卷积层：使用卷积层的原因是，通过卷积运算，可以使原信号特征增强，并且降低噪声。
池化层：使用池化层的原因是，根据图像局部相关性原理，对图像进行池化，可以减小计算量，同时保持图像旋转不变性。
采样的目的主要是混淆特征的具体位置，因为某个特征找出来后，它的具体位置已经不重要了，我们只需要这个特征与其他特征的相对位置，如图像“8”，当我们得到了上面一个“o”时，我们不需要知道它在图像中的具体位置，只需要知道它下面又是一个“o”就可以了，因为“8”在图像中是偏左还是偏右都不影响我们认识它，这种混淆具体位置的策略能对变形和扭曲的图像进行识别。
全连接层：采用Softmax函数全连接，得到的激活值即卷积神经网络提取到的图像特征。
卷积层的map个数是在网络初始化时指定的，而map的大小是由卷积核和上一层输入map的大小决定的，假设上一层的map大小是 n⋅n ，卷积核的大小是 k⋅k ，则该层map的大小是（ n-k +1） ⋅ （ n-k +1）。
CNN的基本结构中包括两种特殊的神经元层，一是卷积层，每个神经元的输入与前一层局部相连，并提取该局部的特征；二是池化层，是用来求局部敏感性与进行二次特征提取的计算层。这种两次特征提取结构减小了特征分辨率，减少了需要优化的参数数目。
CNN是部分连接网络，其底层是特征提取层（卷积层），接着是池化层，然后可以继续增加卷积层、池化层或全连接层。用于模式分类的CNN，通常在最后层使用Softmax函数。
一般情况下，CNN的结构形式是：输入层→卷积层→池化层→（重复卷积、池化层）……→全连接（Full-Connected）层→输出层。输入层大小一般为2的整数倍，如32、64、96、224、384等。通常卷积层使用较小的Filter，如3×3，最大为5×5。池化层用于对卷积结果进行降维，如选择2×2的区域对卷积层进行降维，则选择2×2区域的最大值作为输出，这样卷积层的维数就降为之前的一半。
（3）算法流程。
CNN通过三种方法来实现识别图像的位移、缩放和扭曲不变性，即局域感受野、权重共享和次抽样。局域感受野指的是每一层网络的神经元只与上一层的一个小邻域内的神经单元连接，通过局域感受野，每个神经元可以提取初级的视觉特征，如方向线段、端点和角点等；权重共享使得CNN具有更少的参数，需要相对少的训练数据；次抽样可以减小特征的分辨率，实现对位移、缩放和其他形式扭曲的不变性。卷积层之后通常用一个次抽样层来缩短计算时间、建立空间和结构上的不变性。
构造好网络之后，需要对网络进行求解，如果像传统神经网络一样分配参数，则每个连接都会有未知参数。而CNN采用的是权重共享，一幅特征图上的神经元共享同样的权重可以大大减少自由参数，而且权重共享可以用来检测相同的特征在不同角度的表示效果。在网络设计中抽样层与卷积层通常交替出现，全连接层的前一层通常为卷积层。
在CNN中，权重更新是基于反向传播算法的。CNN本质上是一种从输入到输出的映射，它能够学习大量的输入与输出之间的映射关系，而不需要任何输入和输出之间的精确数学表达式，只要用已知的模式对网络加以训练，网络就具有输入、输出对之间的映射能力。卷积神经网络执行的是监督训练，所以其样本集是由向量对构成的，如输入向量、目标输出向量。所有这些向量对，都应该来源于网络即将模拟系统的实际“运行”结构，它们可以从实际运行系统中采集。在开始训练前，所有的权重都应该用一些不同的“小随机数”进行初始化。“小随机数”用来保证网络不会因权重过大而进入饱和状态，从而导致训练失败；“不同”用来保证网络可以正常学习。实际上，如果用相同的数值去初始化权重矩阵，则网络无学习能力。
训练算法主要包括四步，这四步分为以下两个阶段。
第一阶段，向前传播阶段。
步骤1：从样本集中取一个样本，输入网络。
步骤2：计算相应的实际输出；在此阶段，信息从输入层经过逐级变换，传送到输出层。这个过程也是网络在完成训练后正常执行的过程。
第二阶段，向后传播阶段。
步骤3：计算实际输出与相应的理想输出的差。
步骤4：按极小化误差的方法调整权重矩阵。
这两个阶段的工作一般受精度要求的控制。
网络的训练过程如下。
步骤1：选定训练组，从样本集中分别随机地寻求 N 个样本作为训练组。
步骤2：将各权重、阈值，设置成小的接近0的随机值，并初始化精度控制参数和学习率。
步骤3：从训练组中取一个输入模式加入网络，并给出它的目标输出向量。
步骤4：计算中间层输出向量，计算网络的实际输出向量。
步骤5：将输出向量中的元素与目标向量中的元素进行比较，计算输出误差；对于中间层的隐单元也需要计算出误差。
步骤6：依次计算各权重的调整量和阈值的调整量。
步骤7：调整权重，调整阈值。
步骤8：在经历 M 轮迭代后，判断指标是否满足精度要求，如果不满足，则返回步骤3，继续迭代；如果满足，就进入下一步。
步骤9：训练结束，将权重和阈值保存在文件中。这时可以认为各个权重已经达到稳定，分类器已经形成。再一次进行训练，直接从文件中导出权重和阈值进行训练，不需要进行初始化。
通过以上过程，将复杂繁多的预警目标特征进行简化后，即可输出可辨别目标类型的特征。
分类是在已知研究对象分为若干类的情况下，确定新的对象属于哪一类的过程。分类算法属于一种有监督学习。
1. K 最近邻算法
K 最近邻（ K -Nearest Neighbor， K NN）算法是一种经典的分类算法。在设定 K 值后，可以将多个目标按一定的要求分为 K 类，从而方便对预警情报进行深入分析。
（1）算法演进。
K NN算法由Cover和Hart于1968年提出，是一个理论上比较成熟的算法，其思想为：对于一个测试文本，计算它与训练样本中每个文本的相似度，找出 K 个最相似的文本，根据加权距离和判断测试文本的所属类别。随着 K NN算法的发展，其优点逐渐显现，理论成熟、思想简单，可用于非线性问题，训练时间短、计算复杂度低使得它在解决预警目标航线分类问题上有着很强的优越性，多用来解决相关问题。
（2）工作原理。
K NN算法是通过计算两个个体之间的距离及相似性来进行分类的，几乎适合任何数据集，同时计算量会很大。从训练集中找到和新数据距离最近的 K 条记录，然后根据这 K 条记录的分类来决定新数据的类别。因此，使用 K NN算法的关键是训练集与测试集的选取、距离或相似性度量指标的确定、 K 的大小及分类决策规则的确定。
K NN算法的核心思想：如果一个样本与特征空间中的 K 个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别样本的特征。其优点是无须进行训练，适合对稀有事件进行分类和多分类，效果好于支持向量机；缺点是对测试样本分类时的计算量大，内存开销大。
（3）算法流程。
第一，将数据分为训练集和测试集，计算测试集中的每个样本与训练集中所有样本的距离；第二，按照距离对训练样本进行排序；第三，选取距离最小的 K 个训练样本；第四，统计 K 个训练样本中所有出现过的类别及其频次，并将测试样本归类于出现频次最多的类别；第五，当所有测试样本分类完毕后，对比测试样本的分类类别与真实类别，计算分类的准确率。 K NN算法流程如图1.11所示。
2.支持向量机
支持向量机（Support Vector Machine，SVM）是一种二分类模型，属于有监督学习，它通过寻找一个超平面对样本数据进行二分类。
图1.11 K NN算法流程
（1）算法演进。
SVM是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。SVM建立在统计学习的VC维理论和结构风险最小原理的基础上，根据有限的样本信息在模型复杂性和学习能力之间寻求最佳折中，以期获得最好的推广能力。
（2）工作原理。
已知训练样本集为 D ={（ x 1 ， y 1 ），（ x 2 ， y 2 ），…，（ x n ， y n ）}，其中， y i 表示样本的类别，并且 y i =±1。分类示意图如图1.12所示，两种类型的样本通过一个超平面进行划分。该超平面的方程为
式中， w =（ w 1 ， w 2 ，…， w d ）表示该超平面的法向量； b 表示位移项。
x 是超平面外的一个样本点， x＇ 和 x＇＇ 是超平面上的两个点， w 是超平面的一个法向量，需要算出点 x 到超平面的距离，则
图1.12 分类示意图
垂直距离示意图如图1.13所示。从图1.13中可知，
x＇x
在法向量上的映射即点
x
到超平面的距离
h
。法向量的单位方向为
，则
图1.13 垂直距离示意图
（3）算法流程。
假设超平面对所有训练样本均正确分类。如果 y i =1，则 w T x ＞0；如果 y i =-1，则 w T x ＜0。令
间隔示意图如图1.14所示。
图1.14 间隔示意图
假设未知的符合要求的超平面为 f （ x ）= w T Φ （ x ）+ b 。当 x 为正例时， y =1；当 x 为负例时， y =-1。也就是说，当且仅当 f （ x ）＞0时， y i =1；当且仅当 f （ x ）＜0时， y i =-1。由此可得， y i ⋅f （ x ）＞0。由式（1.12）可得
通过对超平面进行放缩可以使 y i ⋅ [ w T Φ （ x ）+ b ]≥1。SVM需要一个超平面，使与该平面最近的点与该平面的距离最大，即
结合约束条件，目标函数可以简化为
即需要求
的极小值，为了计算方便可以将目标函数和约束条件转换为
通过求解式（1.17），即可得到符合要求的超平面，并对数据进行二分类。
预警情报关联规则问题的核心是基于两阶段频繁项集思想的递推算法，关联算法是数据挖掘中的一类重要算法。典型的关联算法包括Apriori算法和FP-Tree算法。
1.Apriori算法
Apriori算法在数据挖掘中应用较为广泛，常用来挖掘属性与结果之间的相关程度。对于这种寻找数据内部关联关系的做法，人们称其为关联分析或者关联规则学习。而Apriori算法就是其中非常著名的算法之一。
（1）算法演进。
Apriori算法是由Rakesh Agrawal和Ramakrishnan Srikant两位博士在1994年提出的关联规则挖掘算法。关联规则的目的就是在一个数据集中找出项与项之间的关系，也称为“购物篮分析”（Market Basket Analysis），因为“购物篮分析”很贴切地表达了适用于该算法的情景中的一个子集。Apriori算法应用广泛，可用于消费市场价格分析、猜测顾客的消费习惯。
（2）工作原理。
Apriori算法的核心是在大规模数据集中寻找频繁项集和关联规则。频繁项集是指经常出现在一起的物品或者属性的集合；关联规则是指物品或者属性之间存在的内在关系（统计学上的关系）。所以，Apriori算法主要包含两大模块的内容：一是寻找频繁项集的函数模块；二是探索关联规则的函数模块。
支持度与置信度是实现Apriori算法无法回避的两个概念，支持度用来寻找频繁项集，置信度用来确定关联规则。
支持度是指频繁项集在全体数据样本（all sample）中所占的比例：
置信度体现为，在一个数据出现后，另一个数据出现的概率，或者说数据的条件概率为
（3）算法流程。
Apriori算法将发现关联规则的过程分为两个步骤：第一步，通过迭代，检索出事务数据库 Φ 中的所有频繁项集，即支持度不低于用户设定的阈值的项集；第二步，利用频繁项集构造出满足用户最小信任度的规则。其中，挖掘或识别出所有频繁项集是该算法的核心，其计算量占整个计算量的大部分。
以商品购买为例，假设一家商店出售4种商品，分别为商品0、商品1、商品2、商品3，我们希望通过挖掘买家购买商品的订单数据，来决定进行促销的商品组合，可能的商品组合如图1.15所示。
图1.15 商品组合示意图
针对这些商品，我们的目标是从大量购买数据中找到曾经被一起购买的商品。在寻找频繁项集的过程中，采用支持度来过滤商品组合。针对4种商品，我们要在整体数据集上进行15次轮询，才可以统计出每个频繁项集的支持度。在数据量较大，且商品种类不止4种的情况下，还要采用轮询的方式进行统计吗？轮询带来的运算量也是巨大的，并且随着商品种类的增加，频繁项集的组合种类也将变为2 N -1种，运算代价呈现指数级增加。为了解决这个问题，研究人员在Apriori原理的基础上设计了Apriori算法。
Apriori算法流程如下：如果一个项集是频繁的，那么它的所有子集也是频繁的；反之，如果一个项集是非频繁的，那么它的所有超集（包含该非频繁项集的父集）也是非频繁的。于是，可以将图1.15适当优化，得到改进的商品组合，如图1.16所示。
图1.16 改进的商品组合示意图
根据图1.16，我们知道项集{2，3}是非频繁的，那么它的所有超集也是非频繁的。在实际计算过程中，一旦计算出{2，3}的支持度不满足最小支持度，就不需要再计算{0，2，3}、{1，2，3}和{0，1，2，3}的支持度了，因为它们也都是非频繁项集。
2.FP-Tree算法
Apriori算法的缺点是需要多次扫描事务数据库，耗费了大量的运算时间和运行内存。FP-Tree算法有效解决了此类问题，该算法在不生成候选项的情况下，可实现Apriori算法的功能。FP-Tree算法在航线关联中可减小操纵员的人为误差，为关联编批提供系统支持。
（1）算法演进。
针对Apriori算法的缺点，J.Han等人于2000年提出了不产生候选频繁项集的方法，即FP-Tree算法，该算法直接将事务数据库压缩成一个频繁模式树，然后通过这棵树生成关联规则。FP-Tree算法和Apriori算法一样，都必须人为设定最小支持度阈值，再利用此阈值进行筛选。
（2）工作原理。
FP-Tree算法的基本工作原理：首先，扫描整个事务数据库一次，生成频繁项集，并把它们按降序排列，排除支持度计数小于min_sup的项，产生结果集 L ；其次，按照项集描绘出FP-Tree，同时保留关联信息；最后，再扫描事务数据库一次，由下向上顺序挖掘，删除FP-Tree中的子节点，即可产生所需要的频繁模式。FP-Tree算法的基本数据结构，包含一个FP-Tree和一个项头表，每一项通过一个节点链指向它在树中出现的位置。FP-Tree算法基本结构如图1.17所示。
图1.17 FP-Tree算法基本结构
需要注意的是，项头表需要按照支持度递减排序，在FP-Tree中高支持度的节点只能是低支持度节点的祖先节点。
FP-Tree算法中有以下几个基本概念。
FP-Tree：把事务数据库中的各个事务数据项按照支持度排序后，把每个事务中的数据项降序插入到一棵以null为根节点的树中，同时在每个节点处记录该节点出现的支持度。
条件模式基：包含FP-Tree中与后缀模式一起出现的前缀路径的集合，也就是同一个频繁项在FP-Tree中的所有节点的祖先路径的集合。例如，I3在FP-Tree中共出现了3次，其祖先路径分别是{I2，I1:2（频度为2）}，{I2:2}和{I1:2}。这3个祖先路径的集合就是频繁项I3的条件模式基。
条件树：将条件模式基按照FP-Tree的构造原则形成一个新的FP-Tree，如图1.18所示。
图1.18 新的FP-Tree
（3）算法流程。
步骤1：构造项头表，扫描事务数据库一遍，得到频繁项的集合 F 和每个频繁项的支持度。把 F 按支持度递减顺序排序，记为 L 。
步骤2：构造原始FP-Tree，把数据库中每个事务的频繁项按照 L 中的顺序进行重排，并按照重排之后的顺序把每个事务的每个频繁项插入以null为根的FP-Tree中。如果插入时频繁项节点已经存在了，则把该频繁项节点支持度加1；如果插入时该节点不存在，则创建支持度为1的节点，并把该节点链接到项头表中。
步骤3：调用程序，开始进行挖掘。
聚类分析又称群分析，是研究（样本或指标）分类问题的一种统计分析方法，是数据挖掘的重要算法。聚类（Cluster）分析是由若干模式（Pattern）组成的。通常，模式是一个度量（Measurement）的向量，或者是多维空间中的一个点。聚类分析以相似性为基础，在一个聚类中的模式之间比不在一个聚类中的模式之间具有更高的相似性。
1. K -Means算法
K -Means算法（ K -Means Clustering Algorithm， K 均值聚类算法）是一种迭代求解的聚类分析算法。其步骤是，预先将数据分为 K 组，随机选取 K 个预警目标作为初始聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个预警目标分配给距离它最近的聚类中心。聚类中心及分配给它的对象代表一个聚类。每分配一个样本，聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类、没有（或最小数目）聚类中心再发生变化、误差平方和局部最小，最终达到航迹关联的结果。
（1）算法演进。
K -Means算法是典型的基于距离的聚类算法，于1982年由Lloyod提出。它是简单而又有效的统计聚类算法，一般采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度越高。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。
（2）工作原理。
假设要把样本集分为 c 个类别，步骤如下。
步骤1：适当选择 c 个类别的初始聚类中心。
步骤2：在第 k 次迭代中，对任意一个样本，求其到 c 个聚类中心的距离，将该样本归到距离最短的聚类中心所在的类。
步骤3：利用均值等方法更新该类的中心值。
步骤4：对于所有的 c 个聚类中心，如果利用步骤2和步骤3的迭代法更新后，中心值保持不变，则迭代结束，否则继续迭代。
算法描述如下：
输入： k ，data[ n ]；
步骤1：选择 k 个初始聚类中心，如 c [0]=data[0]，…， c [ k -1]=data[ k -1]。
步骤2：对于data[0]，…，data[ n ]，分别与 c [0]，…， c [ k -1]比较，若与 c [ i ]的差值最小，就标记为 i 。
步骤3：对于所有标记为 i 的点，重新计算 c [ i ]={所有标记为 i 的data[ j ]之和}/标记为 i 的个数。
步骤4：重复步骤2和步骤3，直到所有 c [ i ]值的变化小于给定阈值。
K -Means算法属于无监督的聚类算法，其优点是简单易懂、便于操作和运算迅速，聚类效果不错，在工程领域被广泛应用。该算法初始聚类中心的选择和距离公式的构建是关键，对算法的收敛起决定性作用。
（3）算法流程。
步骤1：从 n 个数据对象中任意选择 k 个作为初始聚类中心。
步骤2：根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分。
步骤3：重新计算每个（有变化）聚类的均值（中心对象）。
步骤4：循环步骤2和步骤3直到每个聚类不再发生变化为止，即标准测度函数收敛为止。
注意：一般采用均方差作为标准测度函数。
K -Means算法接收输入量 k ，然后将 n 个数据对象划分为 k 个聚类以便使所获得的聚类满足：同一聚类中的对象相似度较高；不同聚类中的对象相似度较低。各聚类本身尽可能紧凑，而各聚类之间尽可能分开，意味着同一目标的航迹紧凑，不同目标的航迹分开。
聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
2.DBSCAN算法
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法是一个比较有代表性的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。它按照预警目标航线的密度进行分类，确定航迹所属批次。
（1）算法演进。
DBSCAN算法是Martin Ester、Hans-Peter Kriegel等人于1996年提出的一种基于密度空间的数据聚类方法，也是最常用的一种聚类方法。该算法将具有足够密度的区域作为距离中心，并使该区域不断生长，一个聚类可以由其中的任何核心对象唯一确定。DBSCAN算法的目的在于过滤低密度区域，发现稠密度样本。与传统的基于层次的聚类和划分聚类的凸形聚类簇不同，该算法可以发现任意形状的聚类簇。与传统的算法相比它有如下优点。
①聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。
②与 K -Means算法相比，不需要输入需要划分的聚类个数。
③聚类簇的形状没有偏倚。
④可以在需要时输入过滤噪声的参数。
（2）工作原理。
DBSCAN算法基于一组邻域来描述样本集的紧密程度，参数（ ε ，Minpts）用来描述邻域的样本分布紧密程度。其中， ε 描述了某一样本的邻域距离阈值，Minpts描述了某一样本距离为 ε 的邻域中样本的最小个数。
假设样本集 D =（ x 1 ， x 2 ，…， x m ），则DBSCAN算法中对密度的具体描述如下。
① ε 邻域：对于 x j ∈ D ，其 ε 邻域包含样本集 D 中与 x j 的距离不大于 ε 的子样本集，即 N ε （ x j ）={ x i ∈ D |distance（ x i ， x j ）≤ ε }，这个子样本集中的样本个数记为| N ε （ x j ）|。
②核心对象：对于任意样本 x j ∈ D ，如果其 ε 邻域对应的 N ε （ x j ）至少包含Minpts个样本，即| N ε （ x j ）|≥Minpts，则 x j 是核心对象。
③密度直达：如果 x i 位于 x j 的 ε 邻域中，且 x j 是核心对象，则称 x i 由 x j 密度直达；反之， x j 不一定由 x i 密度直达，除非 x i 也是核心对象。
④密度可达：对于 x i 和 x j ，如果存在样本序列 p 1 ， p 2 ，…， p T ，满足 p 1 = x i 、 p T = x j ，且 p t+ 1 由 p t 密度直达，则称 x j 由 x i 密度可达。也就是说，密度可达满足传递性，此时序列中的传递样本 p 1 ， p 2 ，…， p T -1 均为核心对象，因为只有核心对象才能使其他样本密度直达。注意，密度可达也不满足对称性，这个可以由密度直达的不对称性得出。
⑤密度相连：对于 x i 和 x j ，如果存在核心对象 x k ，使 x i 和 x j 均由 x k 密度可达，则称 x i 和 x j 密度相连。注意，密度相连是满足对称性的。
（3）算法流程。
DBSCAN算法流程如下。
输入：样本集 D =（ x 1 ， x 2 ，…， x m ）、邻域参数（ ε ，Minpts）、距离度量方式。
输出：簇划分 C 。
步骤1：初始化核心对象集合 Ω =∅，初始化聚类簇数 k =0，初始化未访问样本集合 Γ = D ，簇划分 C = ∅ 。
步骤2：对于 j =1，2，…， m ，按下面的步骤找出所有核心对象。
①通过距离度量方式，找到样本 x j 的 ε 邻域子样本集 N ε （ x j ）。
②若子样本集中样本个数满足| N ε （ x j ）|≥Minpts，则将样本 x j 加入核心对象集合： Ω = Ω ∪{ x j }。
步骤3：如果核心对象集合 Ω =∅，则算法结束，否则转入步骤4。
步骤4：在核心对象集合 Ω 中，随机选择一个核心对象 o ，初始化当前簇核心对象队列 Ω cur ={ o }，初始化类别序列号 k = k +1，初始化当前簇样本集合 C k ={ o }，更新未访问样本集合 Γ = Γ -{ o }。
步骤5：如果当前簇核心对象队列 Ω cur =∅，则当前簇 C k 生成完毕，更新簇划分 C ={ C 1 ， C 2 ，…， C k }，更新核心对象集合 Ω = Ω-C k ，转入步骤3。
步骤6：在当前簇核心对象队列 Ω cur 中取出一个核心对象 o＇ ，通过邻域距离阈值 ε 找出所有的 ε 邻域子样本集 N ε （ o＇ ），令 Δ = N ε （ o＇ ）∩ Γ ，更新当前簇样本集合 C k = C k ∪ Δ ，更新未访问样本集合 Γ = Γ-Δ ，转入步骤5。
输出结果为：簇划分 C ={ C 1 ， C 2 ，…， C k }。
通过以上步骤，可将杂乱无章的综合前航迹按照密度进行划分，提取预警目标的真实航迹，以便对预警目标进行后续处理。