高维数据子空间聚类:进化的方法

文摘

集群高维数据一直是一个重大的挑战由于固有的稀疏点。大多数现有的聚类算法成为大幅低效如果所需的相似性度量计算数据点之间全面的空间。在本文中,我们提出了一个健壮的多目标子空间聚类(MOSCL)算法对高维聚类的具有挑战性的问题。MOSCL的第一阶段执行子空间相关性的分析检测密集和稀疏区域的位置在检测后的数据集。密集的地区它消除离群值。MOSCL发现子空间密集地区的数据集和生成子空间集群。在彻底的合成实验和实际数据集,我们证明MOSCL子空间聚类优于玛聚类算法。另外我们调查的影响第一阶段检测密集地区的子空间聚类的结果。我们的研究结果表明,消除异常值提高子空间聚类的准确性。聚类结果验证了聚类错误(CE)距离在不同的数据集。MOSCL可以发现各子空间簇与高质量,和MOSCL效率优于玛。

1。介绍

聚类问题涉及的发现均匀组根据某种相似性度量的数据。研究了集群的任务在统计数据1),机器学习(2- - - - - -4,生物信息学3,5- - - - - -7,最近在数据库8- - - - - -10]。聚类算法找到一个分区内的点,点一个集群更相似点在不同的集群(11]。在传统的集群每个维度是同样加权计算点之间的距离。大多数的聚类算法表现良好的低维数据集(12- - - - - -15]。然而,在高维特征空间,他们的性能和效率恶化在更大程度上由于高维度[16]。我们不得不面对的另一个困难在处理聚类是数据的维数。在集群任务中,压倒性的高维度问题提出了一种双方面。首先,无关紧要的存在属性可以消除任何希望在集群趋势,因为这些特性导致算法搜索集群没有集群的存在。这也发生在低维数据,但是存在的可能性与尺寸无关的特性和数量增长。第二个问题是所谓的“维数的诅咒。“对于集群这意味着集群不显示所有属性隐藏不相关的属性或模糊噪声。聚类方法通常是基于距离(如分区和分层聚类)或密度(如density-based方法)。在[17]作者研究高维度的影响最近的邻居和最远的邻居一个对象的在细节。他们已经证明下列方程不同的分布:

这个声明,正式,与成长维度最近邻的距离,几乎是等于距离最远的邻居(距离变得越来越相似)。因此,基于距离的聚类方法功能有问题,在高维空间中提取有意义的模式集群中只有一个对象(最近邻)或几乎完整的数据集(最远的邻居)。图1显示集群嵌入在高维数据集的不同子空间。

密度也遭受诅咒的维度。在[18]作者描述一个更高的维度对密度分布的影响:99%的ten-dimensional的质量正态分布在点到原点的距离大于1.6。这种效果是直接相反的在低维空间:90%的对象的距离小于1.6 SD从原点关于一维分布。Density-based聚类方法(19,20.]因此问题来确定一个区域的密度随着对象是分散在空间的数据。基于网格的方法(10,21,22)能够发现任何形状的集群,也相当快。然而,这些方法解决如何有效集群非常大的数据集,不适合在内存中。此外,这些方法也只与输入工作空间与低到中等数量的维度。随着空间的维数增加,基于网格的方法面临一些严重的问题。细胞的数量呈指数级增长,发现相邻的高密度细胞聚集变得非常昂贵。通常,特别是在高维空间中,并不是所有的尺寸都相关的数据绑定等维度,对于一个给定的集群。至关重要的聚类方法能够检测集群被嵌入到子空间可能由不同的维度组合在不同的地方的数据。

这些观察激励我们努力提出一个新颖的子空间聚类算法称为多目标子空间聚类(MOSCL)有效集群高维数值数据集。MOSCL的第一阶段执行子空间相关性的分析检测密集和稀疏的地区和它们的位置在检测后的数据集。密集的地区它消除离群值。讨论细节的关键方面提出MOSCL算法包括表示方案,最大化健身功能、遗传算子和小说。在现实世界彻底的合成实验和数据集,我们证明MOSCL等子空间聚类方法优于玛(23]。另外我们调查的影响第一阶段检测密集地区的子空间聚类的结果。MOSCL评估由集群的性能测量误差(CE)的距离24]。它是一种直观的方式来比较聚类,因为它使用的比例分不同的集群的生成子空间簇和真正的子空间集群经过最优匹配的集群。

本文的其余部分的结构如下。节2,我们回顾一些相关工作。部分3描述多目标子空间聚类。部分3.1提出了预处理阶段检测稠密和稀疏的地区和删除离群值。部分3.2描述了多目标子空间聚类的设计理念(MOSCL)算法。部分4提出了实验评价。最后,我们得出结论5。

2。相关工作

子空间算法可以分为两类:而基于分区的子空间聚类算法和基于网格的子空间算法。而基于分区算法的集合对象分割成相互排斥的群体。每组的子集维度显示了子空间最大的相似性称为集群。类似于这类方法,则大多数算法定义一个目标函数是最小化在搜索。这些方法和之间的主要区别算法则是这里的目标函数与子空间每个集群所在的地方。集团(探索聚类)(25)是第一批子空间算法,试图找到集群的子空间内数据集。该算法结合了密度和基于网格的聚类,并使用一种先验的风格技巧找到可集群子空间。集团很难发现高质量的集群在所有的子空间。这可能是因为单位密度不同密度的不同子空间识别等基数单位在所有子空间利用绝对单位密度阈值。它可能遭受精度和回忆之间的权衡。SUBCLU (density-connected子空间聚类)26)克服了基于网格的方法的局限性的依赖定位网格。而不是使用网格它使用density-connected DBSCAN(集19)集群模型。SUBCLU基于自底向上,贪婪算法来检测density-connected集群在高维数据子空间。然而SUBCLU也患有密度差异的问题。玛(投影聚类)23),而基于分区的一个典型的子空间聚类算法,搜索一个分区数据集的集群一起每个集群组维度是相关的。玛是变化的-medoid算法,集群的数量和维度的平均数量的集群需要指定运行前的算法。这个算法还假定一个数据点最多可以分配给一个空间集群或分类作为一个局外人,而一个维度可以属于多个集群。ORCLUS(面向任意投影集群生成)27从玛)是一种泛化23),发现在面向任意子空间簇。ORCLUS发现预计集群作为一组数据点一起一组正交向量这些数据点紧密聚集在定义的子空间。这两种方法的一个局限是,形成当地的过程是基于整个空间的维数。然而,它不是有用的找邻居与非常低维数据集投影集群。此外,玛和ORCLUS要求用户提供平均子空间的维数,也很难在现实生活中的应用。火灾(滤波器优化子空间聚类)28)是一个通用高效的子空间聚类的框架。一般以这样一种方式,它适用于各种集群概念。通过最大点击(子空间聚类的分类数据深裂的派系)[29日)使用一个小说制定分类子空间簇,基于矿业派系的概念深裂的图。它实现了一个高效的算法深裂的最大派系,这对应于集群。科(聚类对象属性的子集)(30.正式的子空间聚类问题作为一个优化问题。与互斥算法返回子空间集群与集群每个数据点分配到一个子空间。一维子空间可以属于不止一个集群。然而,每个集群嵌入的子空间是没有明确的算法。发现(快速和智能的子空间聚类算法使用维度投票)(31日)算法,使用一个维度投票技术找到子空间集群。维度的距离来衡量点之间的距离定义不仅基于价值信息,但也维度信息。DENCOS(密度有意识的子空间聚类)32)解决密度差异问题;在该算法中,作者设计一种新颖的子空间聚类模型发现集群基于子空间的地区相对密度,在集群被认为是区域的密度相对较高的比该地区在一个子空间密度。基于这个想法,不同密度阈值自适应地确定发现集群在不同的子空间基数。

基于网格的子空间聚类算法把数据矩阵作为高维电网和聚类过程搜索网格中的密集的地区。ENCLUS(基于熵的聚类)33)使用熵代替密度和覆盖启发式来修剪掉无趣的子空间。找到相关,高密度和高覆盖率子空间使用水平智慧搜索,用于集团(25]。然而,这种算法发现只有在有意义的集群存在的子空间,没有显式地找到实际的集群。更重要的修改集团提出了黑手党,扩展了基本单位在集团利用适应性和大小可变的单位在每个维度。这些大小可变的垃圾箱作为构建块形成单位更高的子空间。黑手党(34)也利用候选人generate-and-test方案生成候选密集单位更高的子空间,从而导致不可避免的信息重叠聚类结果。pMAFIA(合并自适应有限的时间间隔和不仅仅是一个小团体)(35)提出了用自适应单元代替刚性的用于集团(25]。每个维度划分为小尺寸的窗户,然后相邻窗口有相似的分布是合并形成更大的窗户。然而,在小团体的搜索复杂度成倍增加的函数维数最高的密集的单位。pMAFIA可能难以发现集群高品质在所有子空间基数。医生(density-based最佳投影聚类)36)提出了一种最优投影的数学定义集群以及蒙特卡罗算法来计算的近似最优投影集群。医生尝试不同的种子和相邻数据点,为了找到优化质量的集群功能。重复整个过程来寻找其他的预测集群。很明显,因为医生扫描整个数据集重复,其执行时间是非常高的。O-Cluster(正交分割聚类)37)聚类方法结合小说分区与轴平行策略积极抽样技术来识别连续输入空间的高密度区域。EWKM(熵权重——)算法38)是一个新的——类型为高维稀疏数据子空间聚类算法。该算法同时最小化在集群色散和最大化的负熵聚类过程。

3所示。多目标子空间聚类

遗传算法、进化算法的特定类,被公认是适合多目标优化问题。在我们的工作中,我们采用多目标子空间聚类算法(MOSCL)基于子空间的聚类数据集的方法。在本节中,我们讨论预处理阶段的重要概念和MOSCL的设计概念。

3.1。预处理阶段

预处理步骤的目的是确定所有维度的数据集展览一些集群结构通过发现密集区域和他们的位置在每个维度39]。通过集群结构是指一个地区有一个点的密度高于周边地区。这样密集的地区代表一些集群的一维投影。因此,很明显,通过检测密集地区每个维度,我们能够区分维度相关的集群和无关紧要的人。确定维度代表潜在候选人有关维子空间集群。无关的属性包含噪声/异常值和稀疏数据点(23]。

让我们首先给出一些定义。让的数据集数据点的维数。让所有属性的集合的数据集,让是对应的维数据空间。任何维子空间的的空间吗维度的属性,。子空间的基数被定义为维度形成这个子空间的数量。输入由一组维点,在那里。一个点的投影在一个子空间用。数据点之间的距离函数用dist。假设dist之一吗规范。的最近的数据点的邻居对于任何是用。更正式的集合最近的数据点的邻居是最小的设置至少包含数据点的数据集。为了检测人口稠密地区附近的每个属性计算方差的每个数据点测量的方差最近的邻居(40]。附近的数据点的方差被定义为 在哪里和。在这里表示的集合最近的邻居的在属性和是一组的中心;计算中心

一个大的价值意味着数据点属于一个稀疏的区域,而小表明它属于一个密集的地区。计算最近的邻居是一个昂贵的任务,尤其是当数据点的数量是非常大的。我们可以搜索最近的邻居在一个有效的方式通过预分类值在每个属性和限制距离比较的数量最多值。使用方差程度的主要优势是,它提供了一个相对测量的密集的地区从稀疏的地区更容易区分。另一方面,当一个维度包含只有稀疏的区域,所有的估计同样的尺寸往往是非常大的。我们的目标是确定是否密集的区域出现在一个维度。为了确定每个维度密集的地区,我们都感兴趣的组有一个小差异程度的预定义的密度阈值。因此,设置是一个合理的选择。我们应用二进制的密度阈值估计的重量的数据点。如果,然后和属于一个密集的地区;其他的和属于一个稀疏的地区。我们获得一个二进制矩阵它包含的信息是否每个数据点落在一个密集的地区的一个属性。表1显示了一个二进制矩阵它包含的信息是否每个数据点落在一个密集的地区的一个属性或稀疏的地区。很明显,计算取决于输入参数和阈值。我们设置值的方差,这表明数据点属于一个密集的地区。在实践中,因为差异程度是密集的地区的指标发生显著的变化取决于属性及其值,首先我们正常吗为每一个属性通过映射到区间申请前阈值。事实上,该参数的作用是直觉上容易理解,它可以设置方差度这不够有意义的,因为很少有邻居也距离接近于零。

显然,参数预期的最小集群大小有关,应该远小于对象的数量吗的数据。获得清楚的方差的一个点,我们选择在这个阶段。为了捕捉不相关的属性和离群值,我们使用二进制相似系数来衡量二进制数据点之间的相似性为在矩阵。一个常用的二进制数据的相似性度量是Jaccard系数(41]。这种方法被定义为变量编码为1的数量这两个州的数量除以变量编码为1一种或两种状态。在预处理阶段,我们需要一个相似性测量能体现二进制数据点之间的重叠的程度识别密集地区的矩阵。由于密集的地区由1编码矩阵,我们相信Jaccard系数适用于1日我们的任务,因为它只考虑匹配很重要。Jaccard系数给出 在哪里表示数量的维度的两个对象具有相同的二进制值1。同样的,和数一数的维度两个物体有不同的二进制值。Jaccard系数(41)值在0和1之间。一对点被认为是类似的,如果它们之间的估计Jaccard系数超过某个阈值。我们设置阈值的值等于0.8,测量两个二进制向量之间的相似程度,在预处理阶段。另一方面,很明显,当所有的二进制权重为一个二进制数据点在矩阵相关的数据点,等于零吗系统被认为是一个异类,因为它不属于任何发现密集的地区。识别异常值被丢弃的数据集及其对应的矩阵的行被排除。通过消除异常值的数据集的大小减少与大小现在新的二进制权重的关联矩阵(见表2)。MOSCL使用这些二进制矩阵的权重染色体的表示。MOSCL使用修改后的距离函数,考虑贡献才从相关维计算数据点之间的距离和集群中心。具体而言,我们将二进制权重在矩阵欧氏距离。

这使距离测量更有效,因为计算距离仅限于子集的数据点密度值。形式上,一个点之间的距离和集群中心被定义为

3.2。多目标子空间聚类算法

在本节中,我们将住在MOSCL的重要的设计问题,包括个人代表、适应度函数、选择算子、搜索算子,精英主义。MOSCL的过程的基本步骤1。

3.2.1之上。表示

对于任何遗传算法,需要描述每个染色体表示感兴趣的人群中(42]。问题是结构化的表示方法决定了所使用的算法和遗传算子。每个染色体是由一系列基因特定的字母。一个字母可以包含二进制数字(0和1),浮点数,整数,和符号(43]。子空间的一个简单但有效的表示方案是标准二进制编码;所有人都表示为二进制字符串和固定长度相等,在那里是数据集的维数。使用二进制字母集基因的等位基因,每一位个人将承担“0”和“1”的值,分别说明其相应的属性是否被选中(“0”表示相应的条件是没有“1”,反之亦然)。作为一个简单的例子,110101年个人数据流的维度代表了一个四维子空间集群包含1日,2日,4日和6日数据集的属性。在我们的方法中,每个染色体是由一系列矩阵描述,在那里特征空间的维数和吗是子空间簇的数量所描述的染色体。也就是说,算法的染色体是当第一个写的值的权重维度的第一子空间集群,下一个点代表第二子空间的权重集群等等。

3.2.2。目标函数

在单目标优化问题中,目标函数和适应度函数通常是相同的,通常使用可交换(43]。因此,质量评价个人的简略优化问题可以直接进行基于目标函数值。单目标方法的数据聚类可以根据标准分类他们优化(44]。一组聚类算法试图形成紧凑的球状星团通过最小化的星团内数据点之间的距离和集群代表,如——(12)平均链接凝结的聚类(13)和自组织映射(45]。另一组聚类算法试图形成集群的数据项接近彼此陷入相同的集群,因此优化连通性。这一类的聚类算法可以发现任意形状的簇;然而,他们可能会失败,当集群相互接近。这组聚类算法的两个例子是单一链接凝结的集群,自聚类算法与单一判据可以找到一个类别集群形状和失败的另一类。相比之下,目标函数和适应度函数不同遗传多目标优化。目标函数,通过应用决策向量,产生一个维目标向量。MOSCL使用多目标遗传算法在适应度评价包括寻找子空间簇的多目标函数。第一个目标测量每个子空间集群的密度。另一方面最小化密实度试图尽可能多的子空间集群的集群数据集。密度和紧性,因此这两个目标可以让semioptimal集群交互的解决方案。的数学定义的目标MOSCL如下。

让被设置的维度属性。我们定义一个属性的密度“1”条目的一部分的列,表示。一个子空间的密度集群表示为数据点的数量之间的比率是包含在子空间集群和数据集的数据点的总数。我们提出一种加权密度测量,发现所有子空间簇的密度。一个子空间集群的加权密度表示为被定义为的比率和平均密度中包含的所有属性;也就是说,,在那里集群是子空间中包含的属性的数量。我们称之为分母重量。第二个目标是最小化的星团内方差或密实度。测量密实度之间的子空间聚类,我们使用加权形式的欧氏距离作为距离测量。为了为子空间聚类,定义加权欧氏距离的数据点和可以被认为是预测和在自己的子空间。密实度的方程 在哪里子空间聚类和吗是二进制权重与每个属性相关联。这使距离测量更有效,因为计算距离仅限于子集密度值的对象。因此通过最小化这一目标我们给更高的健身紧凑的子空间簇。

3.2.3。选择

选择操作符支持个人的选择从人口将允许伴侣为了创建新一代的人。遗传算法方法尝试开发健身方法和精英主义规则,快速找到一组最优的值和可靠46]。但最终,它是负责的选择方法的选择新一代的父母。因此,选择过程负责制作的映射输入人口的健身价值的概率选择的概率,因此一个人的遗传物质被传递给下一代。这里我们采用锦标赛选择法(47因为它的时间复杂度较低。比赛方法的基本概念如下:随机选择一个正数旅游人口的染色体和从他们最好的安装项目复制到一个中间人口。重复的过程次,在这里人口规模。锦标赛选择的算法程序所示2。

3.2.4。交叉

交叉是遗传算法的特性区别与其他的优化技术。与其他遗传算法优化技术必须计算一个健身价值,选择个人排列,使用变异防止局部收敛在最高点。但是,只有遗传算法使用交叉带一些属性从一个从第二父母父母和其他属性。我们使用了统一的跨界(48该算法。统一的交叉应用于基因的染色体,同时进行。随机选择两个染色体作为父母从目前的人口。交叉产生后代的染色体位基础上,复制每个等位基因来自父母一个概率。的是一个随机实数区间均匀分布。让和有两个家长,让和后代染色体;的在每个后代被定义为等位基因。

例如染色体和染色体为均匀交叉选择如下:

的随机数为交叉生成。现在复制每个等位基因来自父母的概率讨论了在均匀交叉操作。所得的后代

3.2.5。突变

与交叉和选择运营商,变异并不一定适用于所有个人(49]。多个突变规格可供选择:,制服,和正常。每个突变类型有一个独立的概率被应用于每个人。因此,一些人可能被几个突变突变的方法,有些人可能由单个突变突变的方法,和一些人可能并不是突变。这里我们应用突变基因(48]。这导致一些孩子的基因被颠倒过来:“1”改为“0”和“0”改为“1”。基因值修改如下: 在哪里变异的基因,现有的基因值,然后呢是一个正态分布随机数,意思是0和标准偏差。一些试验和错误程序后,我们发现,当等于0.1。

3.2.6。精英主义

当创建一个新的人口通过交叉和变异,我们有很高的机会失去最好的子空间簇发现前一代由于随机性的进化的本质50]。因此,除了Pareto-based选择方法,我们也使用精英主义方法实现不断提高人口的子空间集群。我们采用归档方式实现MOSCL精英主义。在我们的精英主义策略,最好的最好或几个子空间是直接复制到新的人口,连同其他新产生的个体交配池。此外,所有的解决方案获得MOSCL在不同世代将存储在外部存档。MOSCL在当前实现中,没有限制存档,用于存储所有MOSCL中获得的解决方案。

4所示。实验评价

本节中的实验报告使用了2.0 GHz酷睿2处理器2 GB的内存。数据准备完成后,我们可以进行实验评价MOSCL和比较与其他竞争MOSCL方法的性能。我们使用合成和真实数据集的性能评价实验。有四个主要参数MOSCL中使用,也就是说,一代又一代的总数中执行MOSCL(用),个人在每一代的人口的数量(用),两个选择之间的交叉个体的概率将被执行(用的概率),最后每一位个体的变异(用)。典型的参数设置在MOSCL,,,。一个可以改变的价值规范这些参数以获得不同的搜索工作负载和MOSCL优势。

4.1。性能测量

MOSCL是集群中使用的性能测量误差(CE)的距离24子空间聚类)。它是一种直观的方式来比较聚类,因为它使用的比例分不同的集群的生成子空间簇和真正的子空间集群经过最优匹配的集群。换句话说,它的扩展和nondiagonal混淆矩阵的元素,最小化行和列的所有可能的排列。CE距离已被证明是最理想的测量指标在分区之间协议的背景下,预计/子空间聚类(24]。

我们有两个子空间集群:是一家集实验投影生成子空间集群和是一个真正的子空间簇的集合。为了构造一个聚类误差距离测量子空间簇,我们需要定义联盟,和子空间的交集集群在GS和RS。我们表示的两个子空间簇GS和RS 在哪里和子空间聚类的支持GS和RS。RS的支持的定义是,在那里子空间集群的支持吗,由。的是一个子集的数据点的,是一个子集的尺寸吗。让表示混淆矩阵,其中代表数量的数据点在子空间的交集集群和;我们可以代表作为

我们使用匈牙利法(51)找到一个排列集群的标签,这样的对角线元素之和是最大化。表示这个最大化。子空间聚类的聚类错误(CE)的距离是由

卡斯特错误(CE)的价值总是在0和1之间。越相似的两个分区RS和GS, CE值越小。

4.2。数据集

4.2.1。准备合成数据集

数据生成器生成的合成数据集(23]。它允许控制生成的数据集的大小和结构通过数量和维数等参数子空间簇,特征空间的维数和密度参数对整个数据集,以及为每个集群。中使用的参数合成数据生成数据集的大小集群的数量维度的数据集,平均集群维度域的每个维度的值,标准偏差值的范围内,这是与在每个集群的分布有关,和离群值百分比。使用这些参数,所得数据生成器通过定义其中集群将被分发种子点,以及与每个这样的种子点相关的维度(23]。然后,它决定了多少分将与每个集群最后产生集群关联点。集群点生成的投影值根据正态分布的相关维度,意思是随机选择的和标准偏差值。实验通过使用10的数据集进行分析到50000年,数量的维度到250年,,。的值和设置为1%和5%的标准差维度,分别。

4.2.2。真实数据集

我们还测试了算法的乳腺癌,蘑菇数据集,和多个特性数据(MF)。这三个数据集可从UCI机器学习库(http://archive.ics.uci.edu/ml/]。癌症数据集包含30 569实例特性。蘑菇和22个属性数据集包含8124个实例。多个特性数据(MF)的特性包括手写的数字(“0”到“9”)从荷兰的集合中提取实用的地图。二百每个集群模式(总共2000模式)已经在二进制数字化图像。这些数字代表在以下六个方面特性集(文件):(1)mfeat-fou: 76字符形状的傅里叶系数;(2)mfeat-fac: 216简介相关性;(3)mfeat-kar: 64 Karhunen-Love系数;(4)mfeat-pix: 240像素的平均值窗户;(5)mfeat-zer: 47泽尼克时刻;(6)mfeat-mor: 6形态学特征。

对于实验结果,我们使用五个特性集(mfeat-fou, mfeat-fac, mfeat-kar mfeat-zer, mfeat-mor)。每个特性的值都是标准化意味着0和方差1。

4.3。MOSCL结果分析

的可伸缩性MOSCL随着数据集的大小和维度将在本节中讨论。在所有的实验中,返回的结果的性能MOSCL与玛相比要好。

4.3.1。可伸缩性和数据集的大小

的可伸缩性MOSCL与数据集的大小是描绘在图2。结果数据大小的缩放验证该算法成线性比例。通过使用获得的实验数据集不同数据点的数量从1000年的50000人。数据集的维度值设置为20。数据分组在5集群10百分比数据点生成的离群值。这组实验,为所有集群的有限维分布的点均匀分布。MOSCL成功定位所有输入集群内40代,平均。MOSCL的执行时间与玛(23]。轻微的非线性来自提取的点聚集的最后阶段维度。

4.3.2。可伸缩性和维度的数据集

图3显示的可伸缩性MOSCL随着数据集的维数增加50到250。在这一系列的实验中,每个数据集都有5000数据点和有5个集群嵌入在一些五维子空间。此外,随着数据维数的增加,遗传算子的应用变得越来越昂贵的主要原因是越来越多的约束检查计算需要的个人没有重叠的候选解决方案。在可伸缩性实验数据集的维数,执行MOSCL通常比玛(23]。结果显示运行时增加的线性增加维度的数据集。

4.3.3。可伸缩性平均集群维度

图4显示集群平均执行时间的依赖关系维度,后者从10增加到50 100 -维数据空间。在每种情况下,数据集有50000点分布在集群5固定10%水平的异常值。于超线性加速的执行时间的维度隐藏的集群解释如下:隐藏的集群的维数越高,越有可能进化搜索运营商产生染色体在有界的维度。它需要额外的操作来获得一个可行的染色体。此外,随着维度隐藏的集群的增加,更多的可用空间变异和交叉操作符。更高的平均集群维度增加遗传算子的计算开销。

可伸缩性实验表明,MOSCL尺度也对大型和高维数据集。

4.3.4。结果真实的数据集

聚类结果的质量评估的准确性。通过玛算法准确性对乳腺癌数据为71.0%,小于94.5%通过MOSCL聚类算法。增强的性能由MOSCL相比与玛表明有些尺寸可能不相关的一些集群数据。蘑菇数据集通过MOSCL一定准确度为93.6%,大于的准确性(84.5%)通过玛在相同的数据。玛和MOSCL用于集群曼氏金融数据。通过这些算法精度这一数据是94.5%和83.5%,分别。这样的结果表明,中等数量的维度的数据没有对算法产生重大影响,在聚类过程中考虑所有维度。MOSCL总共50代执行。实验结果显示玛MOSCL算法相比的优越性。该算法MOSCL检测到高质量的子空间簇在所有真正的数据集,但玛是无法检测到它们。 The accuracy results of the real data sets are presented in Table3。

4.3.5。性能度量的聚类结果

我们计算了CE距离为所有使用子空间聚类CE距离聚类结果。MOSCL能够实现高度准确的结果,其性能通常是一致的。从图我们可以看出5,MOSCL更健壮的集群比玛维数算法。实验表明,我们的算法能够检测集群及其相关维度在各种情况下准确。MOSCL成功避免了无关紧要的选择维度在所有这些实验中使用的数据集。的结果比那些由MOSCL玛不太准确。当数据集包含预期的低维度、玛表现不佳。

5。结论

在本文中,我们提出了一个健壮的MOSCL(多目标子空间聚类)算法对高维聚类的具有挑战性的问题,说明我们的算法的适用性测试和比较与先前的工作。MOSCL的第一阶段执行子空间相关性的分析检测密集和稀疏的地区和它们的位置在检测后的数据集。密集的地区它消除离群值。MOSCL发现子空间密集地区的数据集和生成子空间集群。讨论细节的关键方面提出方法,MOSCL,包括表示方案,最大化健身功能、遗传算子和小说。我们的大型实验和高维合成和真实世界数据集显示MOSCL优于子空间聚类玛的数量级。此外,我们的算法处理数据时产生精确的结果离群值。仍有许多明显的方向探索在未来。MOSCL的有趣的行为生成的数据集维数较低表明,我们的方法可以用来从基因表达数据中提取有用的信息,通常有一个高水平的背景噪音。另一个有趣的方向探索延长MOSCL预处理阶段的范围从属性相关性分析属性的相关性。

引用

1. l·c·汉密尔顿现代数据Analyis:应用统计学的第一道菜布鲁克斯/科尔,1990。
2. d·h·费雪,“迭代优化和简化分层聚类,”学报第一国际会议上知识发现和数据挖掘(KDD ' 95)加拿大蒙特利尔,页118 - 123,,1995。视图:谷歌学术搜索
3. j·史和j·马利克规范化削减和图像分割,”IEEE模式分析与机器智能,22卷,不。8,888 - 905年,2000页。视图:出版商的网站|谷歌学术搜索
4. Kumar n和k . Kummamuru”Semisupervised集群与度量学习使用相对比较,”IEEE工程知识和数据,20卷,不。4、496 - 503年,2008页。视图:出版商的网站|谷歌学术搜索
5. m·h·邓纳姆数据挖掘:入门和高级的主题,普伦蒂斯霍尔出版社,2003。
6. a . Thalamuthu i Mukhopadhyay, x郑,g . c .曾“在微阵列的基因聚类方法评价和比较分析,“生物信息学,22卷,不。19日,2405 - 2412年,2006页。视图:出版商的网站|谷歌学术搜索
7. z . k . Wang Du、y陈和李,“V3COCA:一个有效的聚类算法对于复杂对象及其在乳腺癌中的应用研究和诊断,”仿真建模实践和理论,17卷,不。2、454 - 470年,2009页。视图:出版商的网站|谷歌学术搜索
8. j .桑德m .酯h . Kriegel, x,“Density-based集群在空间数据库:GDBSCAN算法及其应用,”数据挖掘和知识发现,卷2,不。2、169 - 194年,1998页。视图:谷歌学术搜索
9. b . r . s . a .年轻的时候,高效的数据挖掘算法与联邦数据库(博士。论文)辛辛那提大学,2007。
10. g . Sheikholeslami s Chatterjee和a .张“WaveCluster:小波空间数据聚类方法在非常大的数据库中,“非常大的数据基地杂志》上,8卷,不。3 - 4、289 - 304年,2000页。视图:谷歌学术搜索
11. 汉和m . Kamber,数据挖掘:概念和技术,摩根Kaufmann出版商,旧金山,加州,美国,2011年。
12. j·麦昆,“一些分类方法和多变量分析观察,”第五伯克利分校学报》研讨会上数学,统计,概率1卷,第297 - 281页,1967年。视图:谷歌学术搜索
13. e . m . vooorhees”,实现烧结的层次化聚类算法用于文档检索”信息处理和管理,22卷,不。6,465 - 576年,1986页。视图:谷歌学术搜索
14. t·张,r . Ramakrishnan, m . Livny“白桦:一个有效的数据聚类方法,非常大的数据库,”诉讼的ACM SIGMOD ACM SIGMOD数据管理国际会议记录,25卷,不。2,页103 - 114,1996年6月。视图:谷歌学术搜索
15. s·r·Rastogi”治疗:一个有效的聚类算法对大型数据库”诉讼的ACM SIGMOD国际会议管理的数据,27卷,不。2,页73 - 84,ACM出版社,1998年。视图:谷歌学术搜索
16. f·科恩,佩奇b, c .凯利斯”在“维度诅咒”和“自相似性的祝福- - - - - -”IEEE工程知识和数据,13卷,不。1,第111 - 96页,2001。视图:出版商的网站|谷歌学术搜索
17. k·拜尔,j·戈尔茨坦,r . Ramakrishnan,轴,“当最近的邻居是有意义的,”第七届国际会议的程序数据库理论(ICDT 99),页217 - 235,伦敦,英国,1999年。视图:谷歌学术搜索
18. b·w·西尔弗曼密度估计的统计和数据分析查普曼和大厅,伦敦,英国,1986年。
19. m .酯惠普Kriegel, x,“density-based算法发现集群与噪音,大型空间数据库”第二届国际会议上知识发现和数据挖掘(KDD ' 96)Portand,页226 - 223年,矿石,美国,1996年。视图:谷歌学术搜索
20. DENCLUE 2 a . Hinneburg和h·加布里埃尔。”基于核密度估计,0:快速聚类”先进的智能数据分析七世施普林格,页70 - 80年,柏林,德国,2007年。视图:谷歌学术搜索
21. a . h . Pilevar和m . Sukumar GCHL: grid-clustering算法对于高维很大空间数据基地,“模式识别的字母,26卷,不。7,999 - 1010年,2005页。视图:出版商的网站|谷歌学术搜索
22. 杨j . w . Wang, r .蒙次”刺痛:统计信息网格的空间数据挖掘方法,”学报》第23届国际会议上非常大的数据基地(VLDB 97)卷,97年,第195 - 186页,1997年。视图:谷歌学术搜索
23. c . c . Aggarwal c . Procopiuc j·l·沃尔夫和j·s·公园,“快速投影聚类算法,”学报1999年ACM SIGMOD国际会议管理的数据,28卷,不。2、61 - 72年,1999页。视图:谷歌学术搜索
24. a . Patrikainen和m . Meila子空间聚类相比,“IEEE工程知识和数据,18卷,不。7,902 - 916年,2006页。视图:出版商的网站|谷歌学术搜索
25. r . Agrawal j·耶尔克、d . Gunopulos和p . Raghavan”自动的高维数据子空间聚类数据挖掘应用程序”学报ACM-SIGMOD会议的管理数据,27卷,不。2、94 - 105年,1998页。视图:谷歌学术搜索
26. k .甘蓝类蔬菜,惠普Kriegel·克罗格”Density-connected高维数据子空间聚类,”程序4日暹罗国际会议数据挖掘(长效磺胺的04),p . 2004。视图:谷歌学术搜索
27. c . c . Aggarwal和p . s . Yu”发现广义投影集群在高维空间中,”学报2000年ACM SIGMOD国际会议管理的数据卷,29号2、70 - 81年,2000页。视图:谷歌学术搜索
28. h . Kriegel·克罗格先生还建议,香肠,”一个通用框架,有效的高维数据子空间聚类,”第五届IEEE国际会议数据挖掘学报》(ICDM ' 05)2005年11月,页250 - 257。视图:出版商的网站|谷歌学术搜索
29. m·j·扎基·m·彼得斯,即同意,和t . Seidl”点击:矿业集群子空间分类数据集的有效算法,”数据和知识工程,60卷,不。1,51 - 70,2007页。视图:出版商的网站|谷歌学术搜索
30. j·h·弗里德曼和j·j . Meulman“聚类对象的属性子集,”英国皇家统计学会杂志》上,卷66,不。4、815 - 839年,2004页。视图:出版商的网站|谷歌学术搜索
31. k .哇,j . Lee m . Kim和y·李,“发现:一个快速和智能的子空间聚类算法使用维投票,”信息与软件技术,46卷,不。4、255 - 271年,2004页。视图:出版商的网站|谷歌学术搜索
32. y, j .黄k .壮族d·杨和m .陈“密度有意识的高维数据子空间聚类,IEEE工程知识和数据,22卷,不。1、16 - 30,2010页。视图:出版商的网站|谷歌学术搜索
33. a·w·c·h . Cheng傅,c . h . Cheng a·w·傅和y张“Entropy-based子空间聚类挖掘数值数据,”第五届ACM SIGKDD学报》国际会议上知识发现和数据挖掘,第93 - 84页,1999年。视图:谷歌学术搜索
34. s . Goil h . s .乐,a . Choudhary“黑手党:高效、可扩展的子空间聚类对于非常大的数据集,”第五届ACM SIGKDD学报》国际会议上知识发现和数据挖掘,第452 - 443页,1999年。视图:谷歌学术搜索
35. h·s·乐、美国Goil和a . Choudhary“自适应网格聚类巨大的数据集,”学报第一暹罗国际会议数据挖掘(SDM (01),1卷,2001页。视图:谷歌学术搜索
36. c . m . Procopiuc m·琼斯,p . k .阿加瓦尔和t . m . Murali“蒙特卡罗算法快速投影聚类”学报2002年ACM SIGMOD国际会议管理的数据2002年6月,页418 - 427。视图:谷歌学术搜索
37. b . l . Milenova和m·m·坎波斯”O-Cluster:可伸缩集群的大型高维sata集,”Oracle数据挖掘技术甲骨文公司,页290 - 297年,2002年。视图:谷歌学术搜索
38. l, m . k . Ng, j . z黄”一个熵加权子空间聚类的k - means算法高维稀疏数据,”IEEE工程知识和数据,19卷,不。8,1026 - 1041年,2007页。视图:出版商的网站|谷歌学术搜索
39. a·w·e·k·k·Ng傅,r . c . Wong“投影直方图聚类,IEEE工程知识和数据,17卷,不。3、369 - 383年,2005页。视图:出版商的网站|谷歌学术搜索
40. a . Elke玻姆,惠普Kriegel, p .克罗格,i m·戈尔曼和a . Zimek“检测和可视化子空间集群的层次结构,”数据库的发展:概念、系统和应用程序施普林格,页152 - 163年,柏林,德国,2007年。视图:谷歌学术搜索
41. 美国罗伯特和p h·a·斯尼斯数值分类的原则,1963年w·h·弗里曼。
42. d·e·戈德堡遗传算法在搜索、优化和机器学习,addison - wesley, 1989。
43. e . r . Hruschka r . j . g . b . Campello A . A . Freitas和卡瓦略·A·c·p·l·f·“进化算法聚类的调查。”IEEE系统,人与控制论C,39卷,不。2、133 - 155年,2009页。视图:出版商的网站|谷歌学术搜索
44. j . Handl和j·诺尔斯,“进化的多目标聚类方法,”IEEE进化计算,11卷,不。1,56 - 76,2007页。视图:出版商的网站|谷歌学术搜索
45. t . Kohonen自组织映射施普林格,卷。30日,2001年。
46. d·e·戈德堡和k . Deb,”比较分析遗传算法中使用的选择方案,”遗传算法的基础,51卷,页61801 - 62996,乌尔班纳,1991年。视图:谷歌学术搜索
47. j·e·贝克,分析遗传算法的选择的影响[博士。论文)田纳西州,纳什维尔范德比尔特大学的研究生院,美国,1989年。
48. j . Yeh和j·c·傅“分层遗传算法分割的多光谱人类大脑核磁共振,”专家系统与应用程序,34卷,不。2、1285 - 1295年,2008页。视图:出版商的网站|谷歌学术搜索
49. j . h .荷兰,适应在自然和人工系统,密歇根大学出版社,安阿伯市,密歇根州,美国,1975年。
50. d . Thierens d·戈德堡,“精英重组:一个集成的选择复合遗传算法”学报第一IEEE会议进化计算,IEEE国际代表大会上计算智能(欧洲94年)1994年6月,页508 - 512。视图:谷歌学术搜索
51. l·b·乔恩·j·h·弗里德曼,a·f·拉斐尔”一个算法寻找最佳匹配对数预期的时间,“ACM交易的数学软件,3卷,不。3、209 - 226年,1977页。视图:谷歌学术搜索

版权

版权©2013年辛格Vijendra Sahoo Laxman。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。