8

嗨,我正在尝试从 1999 年 darpa 数据集中对网络数据进行聚类。不幸的是,我并没有真正使用相同的技术和方法获得聚类数据,而不是与一些文献相比。

我的数据是这样的:

Matlab 图1

如您所见,它不是很集群。这是由于数据集中存在大量异常值(噪声)。我已经查看了一些异常值删除技术,但到目前为止我没有尝试过真正清理数据。我尝试过的方法之一:

%% When an outlier is considered to be more than three standard deviations away from the mean, determine the number of outliers in each column of the count matrix:

    mu = mean(data)
    sigma = std(data)
    [n,p] = size(data);
    % Create a matrix of mean values by replicating the mu vector for n rows
    MeanMat = repmat(mu,n,1);
    % Create a matrix of standard deviation values by replicating the sigma vector for n rows
    SigmaMat = repmat(sigma,n,1);
    % Create a matrix of zeros and ones, where ones indicate the location of outliers
    outliers = abs(data - MeanMat) > 3*SigmaMat;
    % Calculate the number of outliers in each column
    nout = sum(outliers) 
    % To remove an entire row of data containing the outlier
    data(any(outliers,2),:) = [];

在第一次运行中,它从从完整数据集中选择的 1000 个标准化随机行中删除了 48 行。

这是我在数据上使用的完整脚本:

    %% load data
        %# read the list of features
        fid = fopen('kddcup.names','rt');
        C = textscan(fid, '%s %s', 'Delimiter',':', 'HeaderLines',1);
        fclose(fid);

        %# determine type of features
        C{2} = regexprep(C{2}, '.$','');              %# remove "." at the end
        attribNom = [ismember(C{2},'symbolic');true]; %# nominal features

        %# build format string used to read/parse the actual data
        frmt = cell(1,numel(C{1}));
        frmt( ismember(C{2},'continuous') ) = {'%f'}; %# numeric features: read as number
        frmt( ismember(C{2},'symbolic') ) = {'%s'};   %# nominal features: read as string
        frmt = [frmt{:}];
        frmt = [frmt '%s'];                           %# add the class attribute

        %# read dataset
        fid = fopen('kddcup.data_10_percent_corrected','rt');
        C = textscan(fid, frmt, 'Delimiter',',');
        fclose(fid);

        %# convert nominal attributes to numeric
        ind = find(attribNom);
        G = cell(numel(ind),1);
        for i=1:numel(ind)
            [C{ind(i)},G{i}] = grp2idx( C{ind(i)} );
        end

        %# all numeric dataset
        fulldata = cell2mat(C);

%% dimensionality reduction 
columns = 6
[U,S,V]=svds(fulldata,columns);

%% randomly select dataset
rows = 1000;
columns = 6;

%# pick random rows
indX = randperm( size(fulldata,1) );
indX = indX(1:rows)';

%# pick random columns
indY = indY(1:columns);

%# filter data
data = U(indX,indY);

% apply normalization method to every cell
maxData = max(max(data));
minData = min(min(data));
data = ((data-minData)./(maxData));

% output matching data
dataSample = fulldata(indX, :)

%% When an outlier is considered to be more than three standard deviations away from the mean, use the following syntax to determine the number of outliers in each column of the count matrix:

mu = mean(data)
sigma = std(data)
[n,p] = size(data);
% Create a matrix of mean values by replicating the mu vector for n rows
MeanMat = repmat(mu,n,1);
% Create a matrix of standard deviation values by replicating the sigma vector for n rows
SigmaMat = repmat(sigma,n,1);
% Create a matrix of zeros and ones, where ones indicate the location of outliers
outliers = abs(data - MeanMat) > 2.5*SigmaMat;
% Calculate the number of outliers in each column
nout = sum(outliers) 
% To remove an entire row of data containing the outlier
data(any(outliers,2),:) = [];

%% generate sample data
K = 6;
numObservarations = size(data, 1);
dimensions = 3;

%% cluster
opts = statset('MaxIter', 100, 'Display', 'iter');
[clustIDX, clusters, interClustSum, Dist] = kmeans(data, K, 'options',opts, ...
'distance','sqEuclidean', 'EmptyAction','singleton', 'replicates',3);

%% plot data+clusters
figure, hold on
scatter3(data(:,1),data(:,2),data(:,3), 5, clustIDX, 'filled')
scatter3(clusters(:,1),clusters(:,2),clusters(:,3), 100, (1:K)', 'filled')
hold off, xlabel('x'), ylabel('y'), zlabel('z')
grid on
view([90 0]);

%% plot clusters quality
figure
[silh,h] = silhouette(data, clustIDX);
avrgScore = mean(silh);

这是与输出不同的两个集群:

在此处输入图像描述

如您所见,数据看起来比原始数据更干净、更聚集。但是我仍然认为可以使用更好的方法。

例如观察整体聚类,我仍然有很多来自数据集的噪音(异常值)。可以在这里看到:

在此处输入图像描述

我需要将异常行放入单独的数据集中以供以后分类(仅从聚类中删除)

这是 darpa 数据集的链接,请注意 10% 数据集的列数显着减少,大部分有 0 或 1 的列已被删除(42 列到 6 列):

http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html

编辑

数据集中保存的列是:

src_bytes: continuous.

dst_bytes: continuous.

count: continuous.

srv_count: continuous.  

dst_host_count: continuous.

dst_host_srv_count: continuous.         

重新编辑:

根据与 Anony-Mousse 的讨论和他的回答,可能有一种方法可以使用 K-Medoids http://en.wikipedia.org/wiki/K-medoids减少聚类中的噪声。我希望我目前拥有的代码没有太大变化,但到目前为止我还不知道如何实现它来测试这是否会显着降低噪音。因此,只要有人可以向我展示一个工作示例,这将被接受为答案。

4

2 回答 2

10

请注意,不鼓励使用此数据集:

该数据集有错误:KDD Cup '99 数据集(网络入侵)被认为是有害的

重新考虑使用不同的算法。k-means 并不真正适合混合类型的数据,其中许多属性是离散的,并且具有非常不同的尺度。K-means 需要能够计算合理的均值。对于二进制向量,“0.5”不是一个合理的平均值,它应该是 0 或 1。

另外,k-means 不太喜欢异常值。

绘图时,请确保等比例缩放它们,否则结果会看起来不正确。您的 X 轴长度约为 0.9,您的 y 轴只有 0.2 - 难怪它们看起来被压扁了。

总的来说,也许数据集没有 k-means 风格的集群?您绝对应该尝试基于密度的方法(因为这些方法可以处理异常值),例如 DBSCAN。但是从你添加的可视化来看,我会说它最多有 4-5 个集群,它们并不是很有趣。它们可能可以在某些维度上通过多个阈值来捕获。

平行坐标

这是 z 归一化后数据集的可视化,在平行坐标中可视化,包含 5000 个样本。亮绿色是正常的。

您可以清楚地看到数据集的特殊属性。所有攻击在属性 3 和 4(count 和 srv_count)上明显不同,并且最集中在 dst_host_count 和 dst_host_srv_count。

我也在这个数据集上运行了 OPTICS。它发现了许多集群,其中大多数是酒红色的攻击模式。但它们并不是很有趣。如果你有 10 台不同的主机 ping-flooding,它们将形成 10 个集群。

光学集群

您可以很好地看到OPTICS成功地聚集了许多此类攻击。它错过了所有橙色的东西(也许如果我将 minpts 设置得更低,它会相当分散),但它甚至在葡萄酒色攻击中发现了*结构),将其分解为许多单独的事件。

真正理解这个数据集,您应该从特征提取开始,例如将此类 ping 洪水连接尝试合并到一个聚合事件中

另请注意,这是一个不现实的场景

  1. 攻击中有众所周知的模式,特别是端口扫描。这些最好用专门的端口扫描检测器检测,而不是学习
  2. 模拟的数据有很多完全没有意义的“攻击”模拟。例如90 年代的Smurf 攻击,占数据集的 50% 以上,Syn flood 占另外 20%;而正常流量<20%!
  3. 对于这类攻击,有众所周知的签名。
  4. 许多现代攻击(例如 SQL 注入)都使用通常的 HTTP 流量,并且不会在原始流量模式中显示异常。

只是不要将此数据用于分类或异常值检测。只是不要。

引用上面的 KDNuggets 链接:

因此,我们强烈建议

(1) 所有研究人员停止使用 KDD Cup '99 数据集,

(2) KDD Cup 和 UCI 网站在 KDD Cup '99 数据集网页上包含警告,通知研究人员该数据集存在已知问题,以及

(3) 会议和期刊的同行审稿人 ding 论文(甚至直接拒绝它们,这在网络安全社区中很常见),其结果仅来自 KDD Cup '99 数据集。

这既不是真实的数据,也不是现实的数据。去拿点别的东西。

于 2012-07-07T23:18:15.430 回答
9

首先要做的事情是:您在这里要求很多。供将来参考:尝试将您的问题分解为更小的部分,并发布几个问题。这会增加您获得答案的机会(并且不会花费您 400 声望!)。

幸运的是,我了解您的困境,并且喜欢这种问题!

除了这个数据集与 k-means 可能存在的问题之外,这个问题仍然足够通用,也适用于其他数据集(因此谷歌人最终会在这里寻找类似的东西),所以让我们继续解决这个问题。

我的建议是我们编辑这个答案,直到你得到相当满意的结果。

集群数

任何聚类问题的第 1 步:选择多少个聚类?我知道有几种方法可以用来选择适当数量的集群。有一个不错的wiki 页面,其中包含以下所有方法(以及更多方法)。

视力检查

这可能看起来很傻,但如果你有很好分离的数据,一个简单的图可以告诉你已经(大约)你需要多少个集群,只需查看。

优点:

  • 快的
  • 简单的
  • 在相对较小的数据集中分离良好的集群上效果很好

缺点:

  • 和肮脏的
  • 需要用户交互
  • 很容易错过较小的集群
  • 使用这种方法很难处理具有不太好的分离集群或其中很多集群的数据
  • 这都是相当主观的——下一个人可能会选择与你不同的金额。

剪影情节

如您的其他问题之一所示,silhouettes绘制图表将帮助您更好地决定数据中的正确聚类数量。

优点:

  • 比较简单
  • 通过使用统计措施减少主观性
  • 表示选择质量的直观方式

缺点:

  • 需要用户交互
  • 在极限情况下,如果您采用与数据点一样多的集群,则轮廓图会告诉您这最佳选择
  • 它仍然是相当主观的,不是基于统计手段
  • 计算成本可能很高

肘法

与轮廓图方法一样,您kmeans重复运行,每次使用大量集群,您会看到数据中的总方差中有多少是由这次kmeans运行选择的集群解释的。将有许多集群,其中解释方差的数量会突然增加很多,比之前选择的集群数量(“肘部”)要少得多。那么从统计上讲,肘部是集群数量的最佳选择。

优点:

  • 无需用户交互——可以自动选择肘部
  • 在统计上比上述任何一种方法都更可靠

缺点:

  • 有点复杂
  • 仍然是主观的,因为“肘部”的定义取决于主观选择的参数
  • 计算成本可能很高

异常值

一旦您使用上述任何方法选择了集群的数量,就该进行异常值检测以查看集群的质量是否有所提高。

我将从使用肘部方法的两步迭代方法开始。在伪 Matlab 中:

data = your initial dataset
dataMod = your initial dataset

MAX = the number of clusters chosen by visual inspection

while (forever)

    for N = MAX-5 : MAX+5
        if (N < 1), continue, end
        perform k-means with N clusters on dataMod
        if (variance explained shows a jump)
            break
    end

    if (you are satisfied)
        break
    end

    for i = 1:N
        extract all points from cluster i 
        find the centroid (let k-means do that)
        calculate the standard deviation of distances to the centroid
        mark points further than 3 sigma as possible outliers
    end

    dataMod = data with marked points removed

end

困难的部分显然是确定是否you are satisfied。这是算法有效性的关键。这部分的粗略结构

if (you are satisfied)
    break
end

会是这样的

if (situation has improved)
    data = dataMod

elseif (situation is same or worse)
    dataMod = data
    break            
end

situation has improved异常值较少时,或者为 的所有选择解释的方差N优于while. 这也是要摆弄的东西。

无论如何,我不会称之为第一次尝试。如果有人在这里看到不完整、缺陷或漏洞,请发表评论或编辑。

于 2012-07-12T10:57:27.467 回答