K - M e a n s 聚 类 算 法
基于K-means聚类算法的入侵检测系统的设计
基于K-means聚类算法的入侵检测系统的设计
今天给大家讲述的是K-means聚类算法在入侵检测系统中的应用首先，介绍一下
聚类算法
将认识对象进行分类是人类认识世界的一种重要方法，比如有关世界的时间进程的研究，就形成了历史学，有关世界空间地域的研究，则形成了地理学。
又如在生物学中，为了研究生物的演变，需要对生物进行分类，生物学家根据各种生物的特征，将它们归属于不同的界、门、纲、目、科、属、种之中。
事实上，分门别类地对事物进行研究，要远比在一个混杂多变的集合中更清晰、明了和细致，这是因为同一类事物会具有更多的近似特性。
通常，人们可以凭经验和专业知识来实现分类。而聚类分析（cluster analysis）作为一种定量方法，将从数据分析的角度，给出一个更准确、细致的分类工具。
（聚类分析我们说得朴实一点叫做多元统计分析，说得时髦一点叫做数据挖掘算法，因为这个算法可以在一堆数据中获取很有用的信息，这就不就是数据挖掘吗，所以大家平时也不要被那些高大上的名词给吓到了，它背后的核心原理大多数我们都是可以略懂一二的，再
比如说现在AI这么火，如果大家还有印象的话，以前我们在大二上学习概率论的时候，我也和大家分享过自然语言处理的数学原理，就是如何让机器人理解我们人类的自然语言，比如说，苹果手机上的Siri系统，当时还让杨帆同学帮我在黑板上写了三句话，其实就是贝叶斯公式+隐含马尔可夫链。估计大家不记得了，扯得有点远了接下来还是回归我们的正题，今天要讨论的聚类算法。）
K-Means是常用的聚类算法，与其他聚类算法相比，其时间复杂度低，结果稳定，聚类的效果也还不错,
相异度计算
在正式讨论聚类前，我们要先弄清楚一个问题：如何定量计算两个可比较元素间的相异度。用通俗的话说，相异度就是两个东西差别有多大，例如人类与章鱼的相异度明显大于人类与黑猩猩的相异度，这是能我们直观感受到的。但是，计算机没有这种直观感受能力，我们必须对相异度在数学上进行定量定义。
要用数量化的方法对事物进行分类，就必须用数量化的方法描述事物之间的相似程度。一个事物常常需要用多个特征变量来刻画，就比如说我们举一个例证，就有一项比较神奇的技术叫面部识别技术，其实听起来很高大上，它是如何做到的，提取一个人的面部特征，比如说嘴巴的长度，鼻梁的高度，眼睛中心到鼻子的距离，鼻子到嘴巴的距离，这些指标对应得数值可以组成一个向量作为每一个个体的一个标度变量（）,或者说叫做每一个人的一个特征向量。
如果对于一群有待分类的样本点需用p 个特征变量值描述，则每
个样本点可以看成是Rp空间中的一个点。因此，很自然地想到可以用距离来度量样本点间的相似程度。这一距离的定义是我们所熟知的，它满足正定性，对称性和三角不等式。在聚类分析中，对于定量变量，最常用的是Minkowski （闵可夫斯基）距离
（这个名字大家应该有所耳闻，提出的闵可夫斯基空间解决了爱因斯坦的狭义相对论中遨游一边太空回来后分不清楚谁是哥哥，谁是弟弟的双生子佯谬问题，当然真正解决是还是爱因斯坦的广义相对论）当q = 1,2或q →+∞时，则分别得到
在 Minkowski 距离中，最常用的是欧氏距离，它的主要优点是当坐标轴进行正交旋转时，欧氏距离是保持不变的。因此，如果对原坐标系进行平移和旋转变换，则变换后样本点间的距离和变换前完全相同。
值得注意的是在采用 Minkowski 距离时，一定要采用相同量纲的变量。如果变量的量纲不同，测量值变异范围相差悬殊时，建议首先进行数据的标准化处理，然后再计算距离。
以距离的长短就来表示两个个体的之间的这个相似程度，那么到目前为止的话，我们就已经实现了目的可以定量的描述现实中两个个体的相似程度。
k均值聚类算法的计算过程：
（1）从D中随机取k个元素，作为k个簇的各自的中心。
（2）分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。
（3）根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。
（4）将D中全部元素按照新的中心重新聚类。
（5）重复第4步，直到聚类结果不再变化。
（6）将结果输出。
算法到此介绍完毕，接下来就看看基于K-means聚类算法入侵检测系统的设计
基于该算法的系统设计
1、研究背景
传统的入侵检测系统( Intrusion Detection System，IDS) 是采取分析和提取入侵模式和攻击特点，建立检测规则库及模式库，所以传统 IDS 在检测效率和智能性上存在明显不足。在网络带宽快速提高，入侵和攻击模式不断变化的新形势下，传统 IDS 的检测方式、检测效率面临巨大挑战，甚至不能即时响应和检测。数据挖掘( DataMining，DM ) 能够从海量数据中根据不同的挖掘算法，挖掘出具有不同用途的知识和信息。因此，可以将数据挖掘技术植入到IDS 中，应用适当的挖掘算法，就可解决前文提出的
IDS 效率和自适应问题。目前，DM + IDS 已成为入侵检测领域的一个重要研究方向.
入侵检测工作过程主要由数据采集、数据分析和响应三个步骤组成。美国互联网工程任务组(IETF)为入侵检测系统制定了标准，并发起制订了系列的建议草案，提出了入侵检测系统框架模型。此模型把
一个入侵检测系统分解为事件产生器、事件分析器、事件数据库和响应单元四个部分。
事件产生器进行网络数据的抓取和预处理，事件分析器进行规则的分析匹配，事件数据库存放规则模式，响应单元产生动作执行操作。根据采用的检测方法，入侵检测技术可分为异常检测和误用检测。
数据挖掘又称数据库中的知识发现( Knowledge Discover inDatabase，KDD),能够从大量的、海量的数据中提取出未知的、并具有用户期望价值的信息。
数据挖掘的过程，根据其工作内容，可分为数据准备、数据挖掘、挖掘结果的解释与评价三个阶段在传统的入侵检测系统中植入数据挖掘技术，数据挖掘技术可分为以下几种类型: 关联规则、序列模式、分类、聚类等，研究探索适当的数据挖掘算法，通过从海量网络数据中，过滤掉正常数据模式，只提取异常入侵模式，智能地构建入侵检测模型，就可以极大地提高传统入侵检测系统的检测效率，并拓展其自适应性，从而降低传统IDS的误检率。
2、IDS-K-means算法流程
分为三个大步骤：
输入：训练数据和半径参数
输出：训练数据的聚类
算法流程
（1）将输入的训练数据集T归一化预处理，减少特定较大数据对聚类结果的影响
（2）读入数据集T中的第一个数据X1，以X1位中心值，构造聚类C1
（3）重复（2），读入下一个数
（4）读入数据集T后续的数据，计算每一个数与已有的类中心值得距离
（5）若，将其归入到该类中，更新该类的中心值，将该类的成员数目加1
（6）若，将作为一个新的聚类中心
（7）重复输入数据，直到全部数据结束
输入：训练数据的聚类结果，阈值
输出：正常数据的聚类和异常数据的聚类
(1)?若某一个聚类中，其成员数目与全部数据之比大于或等于参数值β，则该类为正常行为数据的聚类，将其移入正常聚类表，构造正常行为模式库。
(2) 若某一类中，其成员数目与全部成员之比小于参数值β，则该类为异常行为数据的聚类，把其放入异常聚类表，构建异常行为模式库。
3、系统设计
各模块详细功能如下:
事件产生器: 包括数据包嗅探器和预处理器两个子模块。从网络中捕获数据包，并将获取的数据包进行分析解码处理后，供后面的模块使用。
聚类分析器: 采用 IDS K － means 算法构建网络正常行为模式库和异常行为模式库。
事件数据库: 存放异常入侵规则模式数据，并维护异常入侵规则数据，供误用检测和关联规则进行模式检测。
事件分析器: 分析和处理网络数据，包括异常检测和误用检测两个模块。实现过滤和检测双重功能。
(1) 过滤功能: 异常检测模块通过网络正常行为模式和异常模式对输入的网络数据进行模式识别，把正常的网络数据过滤，保留异常网络数据送误用检测。
(2) 检测功能: 误用检测将异常检测过滤后通过的疑似入侵数据与异常事件数据库中的入侵规则进行检测，判断该数据是哪一类入侵数据。
响应单元: 当误用检测为异常数据时，产生入侵行为触发，让 IDS 产生动作，阻止入侵行为继续发生，通过报警，记录到日志文件，通知防火墙切断该连接，通知管理员等。
关联规则分析: 将入侵的网络数据进行关联挖掘，挖掘出入侵行为与异常数据之间的关联关系，并将其转化为入侵规则，添加到入侵规则库中。
4、系统工作流程
该入侵检测系统的工作流程设计为两个阶段，分别为训练阶段（1）和检测阶段（2）
【1】?训练阶段图中的流程1所示，系统在训练阶段要将大量的
网络数据作为训练数据存入数据库。
（1）?根据数据取出关键特征进行预处理。
（2）?采用IDS K-means聚类算法对数据进行聚类分析。
（3）?提取网络数据正常模式和异常入侵数据模式
（4）?过滤正常网络数据
【2】?检测阶段
（1）?输入网络数据
（2）?对数据进行预处理
（3）?正常网络数据过滤，将网络数据与模式库中的数据进行匹配，如果为正常数据，过滤掉，提高系统的检出率
（4）?将入侵数据送误用检测，判断该入侵数据为哪一类攻击
（5）?触发响应模块，报警
（6）?如没有与入侵规则库匹配成功，该数据为未知攻击类型，则有关联规则挖掘楚攻击行为与数据的关系，将其添加到入侵规则库中，使系统具备了发现未知攻击的能力
以上都是从概念层面介绍了这个系统，接下来将以一次具体的实验测试来详细说明这个系统的工作过程
5、系统测试
2.算法对于初始值具有依赖性，不同的聚类初始中心值，往往会有不同的聚类结果，而随机选择的初始中心点可能导致聚类结果有很大的随机性，也一定能够程度上影响了迭代次数；
['sepal_length', 'sepal_width'], ['petal_length',
'sepal_width']]
Mat tmp = (Mat_float(1, 3) point[0], point[1], point[2]);
? centroids = mat(zeros((k,n)))
当然，MATLAB 也提供了 kmeans() 函数可供直接聚类使用，详情可参与其文档。
# output_data.to_excel(output_path) # 保存结果
? # clusterAssment第一列存放该数据所属的中心点，第二列是该数据到中心点的距离
答：分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。
数据挖掘又称数据库中的知识发现( Knowledge Discover inDatabase，KDD),能够从大量的、海量的数据中提取出未知的、并具有用户期望价值的信息。
总的来说，我们要提高聚类质量，那么就要不断的去优化簇内变差。但是传统划分算法开销巨大，所以这里我们引出了k-均值算法。