聚类算法简介-ppt

《聚类算法简介-ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、聚类算法简介什么是聚类?聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小;为什么需要聚类?对相似的文档或超链接进行聚类，由于类别数远小于文档数，能够加快用户寻找相关信息的速度;聚类图示聚类中没有任何指导信息，完全按照数据的分布进行类别划分什么是分类?数据集合，类别标记集合数据集合：训练数据待分类数据已知问题：方法：根据训练数据获得类别划分标准分类图示训练数据待分类数据聚类与分类的区别有类别标记和无类别标记;有监督与无监督;（有训练语料与无训练语料）TrainAndClassification（分类）;

2、NoTrain（聚类）;聚类的基本要素定义数据之间的相似度;聚类有效性函数（停止判别条件）;1.在聚类算法的不同阶段会得到不同的类别划分结果，可以通过聚类有效性函数来判断多个划分结果中哪个是有效的;2.使用有效性函数作为算法停止的判别条件，当类别划分结果达到聚类有效性函数时即可停止算法运行;类别划分策略（算法）;通过何种类别划分方式使类别划分结果达到有效性函数;相似度EuclideanDistance数据表示为向量，向量中某一维对应数据某一特征或属性仅计算了数据向量中属于同一维度特征的权值差距;聚类有效性函数最小误差（）:最小方差:衡量同一类别内数据的平均误差和;衡量属于不

3、同类别的数据与类别中心的的误差和;聚类算法的简单分类基于划分:K-means,K-medoids基于层次:HFC基于密度:DBSCAN基于网格:CLIQUE,STINGK-means初始参数-类别数&初始类别中心;聚类有效性函数-最小误差;优点：聚类时间快;缺点：对初始参数敏感;容易陷入局部最优;K-means步骤1设置初始类别中心和类别数;2根据类别中心对数据进行类别划分;3重新计算当前类别划分下每类的中心;4在得到类别中心下继续进行类别划分;5如果连续两次的类别划分结果不变则停止算法;否则循环2～5;初始值敏感初始化4个类别中心;左侧的全体数据仅与第一个类别中心相似;层

4、次聚类分裂或凝聚算法运行到某一阶段，类别划分结果达到聚类标准时即可停止分裂或凝聚;基于聚类的入侵检测方法由于IDS需要处理的数据量非常大，对建模和检测的准确性、时效性要求高，因此在研究基于聚类的入侵检测方法时重点考虑三个方面的要求：聚类算法时间复杂度低；聚类精度高，能将不同类型的数据聚集在分离的簇中；给簇准确做标记，能得到较准确的分类模型。基于聚类的检测方法主要由两大模块构成：模型建立第一步：对训练集进行聚类；第二步：利用聚类结果得到分类模型；模型评估检测率：被正确检测的攻击记录数占整个攻击记录数的比例。误报率：表示正常记录被检测为攻击的记录数占整个正常记录数的比例。未见攻

5、击类型的检测率：表示测试集中出现而训练集中没有出现的新类型攻击记录被正确检测的比例。基于聚类的入侵检测方法分类有指导的入侵检测方法通过在已标记为正常和入侵的数据集上进行训练，建立分类模型，通过检测数据偏离各分类模型的偏差来检测非正常的、潜在的入侵行为。方法的有效性取决于训练数据集的质量。要求训练数据被正确地标记为正常或攻击，如果标记不正确，则算法可能会将某种入侵行为及其变种看成正常而不能检测，从而使检测率降低，或者将正常行为看成入侵，使误报率提高。有指导的聚类检测过程1.初始时，簇集合为空，读入一个新的对象；2.以这个对象构建一个新的簇，该记录的类别标记作为新簇类别的标志；

6、3.若已到数据库末尾，则转6，否则读入新对象，利用给定的距离定义，计算它与每个簇间距离，并选择最小的距离；4.若最小距离超过阈值ｒ，或对象的类别与其最近簇的类别不同，转2；5.否则将该对象并入具有最小距离的簇中并更新该簇的各类属性值的统计频度及数值属性的簇中心，转3；6.结束。基于聚类的入侵检测方法分类无指导的入侵检测方法是在未标记的数据上训练模型并检测入侵，不需要任何先验知识，可能检测新的、未知的入侵。基于基本的假定：正常行为较入侵行为占绝对的比例；入侵行为偏离正常行为是可以区别的。聚类簇无指导的聚类检测过程1.模型建立第一步：对训练集T1进行聚类，得到聚类结果T1={C

7、1,C2,…,Ck}；第二步：给簇做标记：统计每个簇Ci（1≤i≤k）的异常因子或数据量的大小。2.确定模型：确定每个簇的类中心和半径阈值ｒ。3.利用最近邻分类方法对测试集中的每个对象进行分类；实验数据集KDDCUPKDDCup1999入侵数据包是真正的网络数据，它是在军事网络坏境中运用非常广泛的模拟入侵攻击所得到的数据集。包含大约490万条数据纪录。通过检测记录中是否包含有攻击行为以及攻击行为的类别，把记录标记成为正常记录或是某种攻击的记录。并且认为这些标记都是正确可信的。实验数据集KDDCUPKDDCup199