相对密度离群点检测算法-广东工业大学精品课程.ppt

(2) 模型评估 利用改进的最近邻分类方法INN(Improved Nearest Neighbor) 评估测试集中的每个对象。INN方法具体描述如下： 对于测试集 中对象p，计算p与每个簇的距离 若 ，则说明p是已知类型的行为，将簇 的标识作为p的标识，否则说明p是一种新的行为，将p标识为可疑对象——候选离群点 。 * 协同计算与知识工程 * (3) 模型更新 对于测试集 中对象p，按照前面聚类的方式，对新增对象进行增量式聚类更新 用建立模型同样的方法对所有簇重新标记其类别。 * 协同计算与知识工程 * 离群点挖掘方法的评估 可以通过下表所示混淆矩阵来描述离群点挖掘方法的检测性能。在离群点检测问题中，并不关注预测正确的normal类对象，重点关注的是正确预测的outlier类对象。 * 协同计算与知识工程 * 预测类别 outlier normal 实际类别 outlier 预测正确的outlier 预测错误的outlier normal 预测错误的normal 预测正确的normal 离群点检测方法准确性的两个指标 检测率(Detection rate)表示被正确检测的离群点记录数占整个离群点记录数的比例； 误报率(False positive rate)表示正常记录被检测为离群点记录数占整个正常记录数的比例。 期望离群点挖掘方法对离群数据有高的检测率，对正常数据有低的误报率，但两个指标之间会有一些冲突，高的检测率常常会导致高的误报率。也可以采用ROC曲线来显示检测率和误报率之间关系 * 协同计算与知识工程 * 例7 采用基于聚类的离群点挖掘方法处理UCI中KDDCUP99 数据集 入侵检测问题可以看成一类特殊的离群点挖掘问题。 KDDCUP99数据集包含了约4900000条攻击记录。总共22种攻击，分为DOS，R2L，U2R，Probing等4类；总共有41个特征，其中9个分类特征，32个数值型特征。整个数据集太大，通常使用一个10%的子集来测试算法的性能；这个子集随机分割为P1，P2和P3三个子集，其中P1含40459条记录(normal占96%)，P2含19799条记录(normal占98.7%)。P3中包含有P1中没有出现过的ftpwrite，guess_passwd，imap，land，loadmodule，multihop，perl，phf，pod，rootkit，spy，warezmaster等攻击类型。 * 协同计算与知识工程 * (1)模型建立 以P1为训练集建立模型(取 =0.05)，求得EX=0.234，DX=0.134， r取EX+0.5DX=0.30。表6-6给出了按离群因子给P1聚类结果簇标识的结果，可见，聚类较好地将normal记录和attack记录划分到不同簇中，簇的离群因子能很好地将簇区分为”normal”和” outlier”(即对应于攻击记录)，使得建立的模型具有很好的分类能力。 * 协同计算与知识工程 * 序号 簇大小 正常记录数 攻击记录数 簇标识 1 360 0 360 outlier 2 5 0 5 outlier 3 94 0 94 outlier 4 1339 203 1136 outlier 5 2134 2134 0 normal 6 2408 2405 3 normal 7 7 6 1 normal 8 16 16 0 normal 9 132 130 2 normal 10 15 15 0 normal 11 19 18 1 normal 12 171 171 0 normal 13 5442 5440 2 normal 14 22618 22607 11 normal 15 3896 3896 0 normal 16 61 61 0 normal 17 1742 1736 6 normal 从静态离群点检测的角度看，对于数据集P1，利用离群因子可以检测P1中98.4%的攻击记录。 (2) 模型检验 用建立的模型在P3上进行测试，检测率结果如下表。 表在KDDCUP99数据集上的检测性能 * 协同计算与知识工程 * 总的检测率 误报率 对未见攻击的检测率 98.62% 0.20% 4.30% (3) 模型更新效果 在P1上建立模型，然后用P2更新模型，再在P3上检测。表6结果表明随着模型的更新(也就是有效信息的不断增加)，检测率和误报率没有明显变化，但对未见攻击的检测率明显提高。如果初始建模时训练集不够大，检测准确性将会随着模型的更新而逐步提高，直到稳定在某个水平 * 协同计算与知识工程 * 总的检测率 误报率 对未见攻击的检测率 98