不规则的k-means聚类图,异常值去除

Question

嗨,我正在努力尝试从1999 darpa数据集中聚类网络数据.不幸的是,我并没有真正得到集群数据,与一些文献相比,使用相同的技术和方法.

我的数据是这样的:

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

%% 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.我希望我目前拥有的代码没有太大的变化,但是我还不知道如何实现它来测试这是否会显着降低噪音.因此,假设某人可以向我展示一个有效的例子,这将被接受为答案.

Answer 1

请注意,不建议使用此数据集:

该数据集存在错误: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泛洪,它们将形成10个集群.

你可以很好地看到OPTICS设法集中了许多这些攻击.它错过了所有橙色的东西(也许如果我设置了较低的碎片,它是相当分散的)但它甚至在葡萄酒色的攻击中发现了*结构,将其分解为许多单独的事件.

要真正了解此数据集,您应该从功能提取开始,例如将此类ping泛洪连接尝试合并到聚合事件中.

另请注意,这是不切实际的情况.

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

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

引用上面的KDNuggets链接:

因此,我们强烈建议您这样做

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

(2)KDD杯和UCI网站在KDD杯'99数据集网页上发出警告,告知研究人员数据集存在已知问题,以及

(3)会议和期刊的同行评审员(甚至直接拒绝它们,在网络安全社区中很常见),结果仅来自KDD杯'99'数据集.

这既不是真实的也不是现实的数据.去得到别的东西.

Answer 2

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

幸运的是,我理解你的困境,只是喜欢这样的问题!

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

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

集群数量

任何群集问题的第1步:要选择多少个群集？我知道有几种方法可以选择适当数量的聚类.有一个很好的维基页面,包含下面的所有方法(还有一些).

视力检查

这可能看起来很愚蠢,但是如果你有完全分离的数据,一个简单的情节可以告诉你(大约)你需要多少个集群,只需看一看即可.

优点:

• 快
• 简单
• 适用于相对较小的数据集中分离良好的聚类

缺点:

• 又脏又脏
• 需要用户互动
• 很容易错过较小的集群
• 通过这种方法很难做到分离较少的簇或其中很多簇的数据
• 这完全是主观的 - 下一个人可能会选择与你不同的金额.

剪影情节

如您在其他一个问题中所述,制作一个silhouettes图表可以帮助您更好地决定数据中适当数量的聚类.

优点:

• 相对简单
• 通过使用统计测量来降低主观性
• 直观的方式来表示选择的质量

缺点:

• 需要用户互动
• 在极限情况下,如果您采用与数据点一样多的聚类,剪影图将告诉您这是最佳选择
• 它仍然是相当主观的,不是基于统计手段
• 可能是计算上昂贵的

肘法

与剪影图方法一样,您kmeans每次都使用更多的聚类重复运行,并且您可以看到数据中的总差异有多少是由此kmeans运行选择的聚类解释的.将存在许多聚类,其中解释的方差量将突然增加少于先前任何聚类数量("肘")的选择.从统计学上讲,肘部是群集数量的最佳选择.

优点:

• 无需用户交互 - 可以自动选择弯头
• 统计上比任何上述方法更有声音

缺点:

• 有点复杂
• 仍然是主观的,因为"肘部"的定义取决于主观选择的参数
• 可能是计算上昂贵的

离群值

使用上述任何方法选择群集数量后,就可以进行异常值检测,以查看群集的质量是否有所改善.

我将使用elbow方法从两步迭代方法开始.在伪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当有较少的异常值,或explaned对于所有选择的变化N是比以前的循环过程中更好while.这也是一个可以解决的问题.

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