一种应用复杂网络特征的K-means初始化方法
- 格式：pdf
- 大小：250.83 KB
- 文档页数：3
Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 ２０１０，４６（６） １２７ 一种应用复杂网络特征的Ｋ－ｍｅａｎｓ初始化方法 田生文，王伊蕾，李阿丽 ＴＩＡＮ Ｓｈｅｎｇ－ｗｅｎ，ＷＡＮＧ Ｙｉ—ｌｅｉ，ＬＩ Ａ－ｌｉ
鲁东大学计算机科学与技术学院，山东烟台２６４０２５ Ｃｏｒｔｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｌｕｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｙａｎｔａｉ，Ｓｈａｎｄｏｎｇ ２６４０２５，Ｃｈｉｎａ Ｅ－ｍａｉｌ：ｓｗ＿ｔｉａｎ＠ｙａｈｏｏ．ｅｏｍ．ｅｎ
ＴＩＡＮ Ｓｈｅｎｇ－ｗｅｎ，ＷＡＮＧ Ｙｉ－ｌｅｉ，ＬＩ Ａ－ｌｉ．Ｋ－ｍｅａｎｓ ｉｎｉｔｉａｌｉｚａｔｉｏｎ ｍｅｔｈｏｄ ｕｓｉｎｇ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｎｃａｔｉｏｎｓ。２０１０，４６（６）：１２７－１２９．
Ａｂｓｔｒａｃｔ：Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｐａｒｔｉｔｉｏｎ－ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｉｔ ｉｓ ｓｉｍｐｌｅ ａｎｄ ｆａｓｔ ｔｏ ｃｏｎｖｅｒｇｅ，ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ Ｋ－ ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｄｅｐｅｎｄｓ ｏｎ ｔｈａｔ ｈｏｗ ｔｏ ｃｈｏｏｓｅ Ｋ ｓａｍｐｌｅｓ ａｓ ｔｈｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ．Ｔｈｉｓ ｐａｐｅｒ ｄｅｖｅｌｏｐｓ ｔｈｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ，ａｎｄ ｄｅｆｉｎｅｓ ｄｅｇｒｅｅ，ｃｏｎｇｒｅｇａｔｅｄ ｄｅｇｒｅｅ ａｎｄ ｃｏｎｇｒｅｇａｔｅｄ ｃｏｅｆｆｉｃｉｅｎｔ ｏｆ ｏｂｊｅｃｔｓ ｗｉｔｈ ｆｅａｔｕｒｅ，ａｎｄ ｃｈｏｏｓｅｓ ｔｈｅ Ｋ ｎｏｄｅｓ ｗｈｏｓｅ ｔｈｅ ｄｅｇｒｅｅ ａｎｄ ｃｏｎｇｒｅｇａｔｅｄ ｃｏｅｆｆｉｃｉｅｎｔ ａｒｅ ｌａｒｇｅｒ ｔｈａｎ ｔｈｅ ｏｔｈｅｒｓ ａｓ ｔｈｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ Ｋ——ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔ ｔｈａｎ ｔｈｅ ｏｒｉｇｉｎａｌ Ｋ－ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ；Ｋ－ｍｅａｎｓ；ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ；ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ
摘要： —ｍｅａｎｓ算法是一种基于划分的聚类算法，具有算法简单且收敛速度快的特点。但该算法的性能依赖于聚类中心的初始 位置的选择。拓展了复杂网络的重要特征，针对带有属性的数据对象所构成的数据集，定义了多维属性对象的度、聚集度和聚集系 数，选取度和聚集系数高的Ｋ个点作为Ｋ—ｍｅａｎｓ聚类的初始中心点。实验数据表明，改进后的Ｋ—ｍｅａｎｓ算法较传统的算法具有更 高的效率和准确度。 关键词：聚类；Ｋ—ｍｅａｎｓ算法；复杂网络特征；聚类初始点 ＤｏＩ：１０．３７７８８ ｉｓｓｎ．１００２—８３３１．２０１０．０６．０３６ 文章编号：１００２—８３３ｌ（２０１０）０６—０１２７—０３ 文献标识码：Ａ 中图分类号：ＴＰ１８
１引言 复杂网络是复杂系统的抽象，网络中的节点是复杂系统中 的个体，节点之间的边则是系统中个体之间按照某种规则而自 然形成的或人为构造的一种关系ｌ１］。自然界和人类社会的许多 系统可以用复杂网络进行建模，如社会关系网、万维网和科学 家合作网等。社团结构是复杂网络中的一个重要特性，通过研 究社团结构，可以发现社团内的共性，具有一定的实用价值。复 杂网络中的社团结构的发现类似于数据挖掘中的聚类问题。 聚类囟是将数据对象分组成为多个类或簇，在同一个簇中 的对象之间具有较高的相似度，而不同簇中的对象差别较大。 聚类除了在数据挖掘中应用外，图像分割、模式识别和信号压 缩等诸多领域中有着广泛的应用。目前，主要的聚类算法可分 为划分方法、层次方法、基于密度的方法、基于网格的方法和基 于模型的方法。这些聚类算法普遍存在对初始化参数敏感，难 以找到最优聚类，以及聚类有效性的问题。Ｋ—ｍｅａｎｓ算法是目 前应用最为广泛的基于划分的算法之一，它具有算法简单且收 敛速度陕的特点，但聚类的结果强依赖于初始中心点的选择。 针对Ｋ—ｍｅａｎｓ算法的不足之处，借鉴了加权复杂网络的 重要特征对其进行了优化。
２ Ｋ－ｍｅａｎｓ初始化的研究动态 Ｋ—ｍｅａｎｓ聚类算法ｐ是ＭａｃＱｕｅｅｎ等人于１９６７年提出。给 定—个数据集合 ｛ 。，ｄ２，…， ｝以及要生成的簇的数目Ｋ，Ｋ— ｍｅａｎｓ算法的聚类过程可表示为： （１）任意选取ｋ个对象作为初始簇的中心； （２）根据簇中对象的平均值，将Ｄ中所有对象分配到最近 的簇； （３）更新簇的平均值，即重新计算每个簇的中心； （４）重复（２）和（３），直至簇中心不再变化或迭代次数超过 设定的最大迭代次数。 原始Ｋ—ｍｅａｎｓ算法的性能依赖于聚类中心的初始位置的 选择，不同初始值可能导致不同的聚类结果，甚至存在无解的 情况。针对这个问题，人们提出了许多优化算法。Ｍｉｌｌａｎ喈旨出， Ｋ—ｍｅａｎｓ的初始值可由ｗａｒｄ目的层次聚类的方法得到。ｗａｒｄ 方法认为开始时每个数据点都是—个单独的类，每次从已有的 类中挑出最相似的两个类进行合并，直至合并到只有一个类为 止。在初始化Ｋ—ｍｅａｎｓ前，先用Ｗａｒｄ方法做一次聚类，当类的 个数合并为ｋ时，停止聚类，求出这ｋ个类的中心作为Ｋ－ｍｅａｎｓ 的初始值。Ｈｉｇｇｓｔａｌ￣ｑｌ Ｓｎａｒｅｙｒｒ￣人分别提出先用ＭａｘＭｉｎ算法对 数据点聚类，并将聚类结果的类中心作为Ｋ—ｍｅａｎｓ的初始值。
作者简介：田生文（１９７４一），男，讲师，主要研究领域为数据挖掘、复杂网络；王伊蕾（１９７９一），女，讲师，主要研究领域为数据挖掘、复杂网络；李阿丽 （１９７９一），女，助教，主要研究领域为复杂网络。 收稿日期：２００８—０９一Ｏｌ 修回日期：２００８—１１－１３ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 这两种初始化Ｋ～ｍｅａｎｓ方法本身就是一种聚类算法，Ｋａｕｆｍａｎ 和Ｒｏｕｓｓｅｅｎｗ［￣］提出了一种初始化Ｋ—ｍｅａｎｓ的方法：Ｋａｕｆｍａｎ ａｐｐｒｏａｃｈ（ＫＡ）。该方法逐个地从数据集中选出代表点，直至取 到ｋ个点为止，第一个代表点是距离数据集中心最近的那个 点，其余的代表点根据一个启发式的规则从剩余的点中选出。 ＫＡ算法中，第一个代表点可能是一个类的边缘点，甚至是一个 孤立点，因此不能很好地代表密集簇的中心；同时，由于ＫＡ算 法是一个启发式算法，第一个代表点的好坏直接影响其他代表 点的质量。钱线ｆ 人提出了初始化Ｋ－ｍｅａｎｓ的谱方法（ＥＫＭ）， 是一种叠代算法。ＥＫＭ通过数据点的相似度矩阵计算前ｋ个 特征值所对应的特征向量，进而叠代估计聚类初始中心。由于 ＥＫＭ算法在初始化时，所依据的特征向量是通过对原始数据 进行了多次转化而得到的，对于一些特殊的数据（例如孤立 点），其特征向量不能很好地反映原始数据的特性，若给定数据 集中类的结构不明显时，ＥＫＭ的聚类结果并不理想。 所提出的Ｋ—ｍｅａｎｓ初始化方法基于一个新的概念：数据 点的聚集特性ＣＦ，是在已知类的个数Ｋ的前提下，根据数据集 中数据点之问的聚集性和连接强度来计算各自的ＣＦ，从而确 定初始聚类中心。 ３改进的Ｋ－ｍｅａｎｓ聚类算法 ３．１ 多维属性数据对象的聚集性度量指标 复杂网络的研究对象更多的是节点以及节点间的边，而不 考虑节点本身的属性；而自然界中许多网络是由带有属性的节 点构成，例如某高校所有学生构成的网络中，节点学生由学号、 姓名、性别、年龄、成绩等属性描述，这样的网络中节点问没有 直连边，称这样的网络为多维属性数据对象所构成的Ｊ硼络，以 下简称“属性网络”。若将属性网络中的节点之间的距离视为权 重，则属性网络变成加权网络。该文正是借鉴了加权复杂网络 中关于加权度、加权聚集度和加权聚集系数的定义口ｏｌ，对属性 网络的度ＦＮＤ、聚集度ＦＮＫ和聚集系数ＦＮＣ进行了如下定义。 对于数据集，Ｊ＝ｆｄ ，ｄ：，…，ｄ ｌ，将数据对象ｄ （ｉ＝１，２，…，ｎ） 称为节点．则： ＦＮＤＦ∑Ｓｉｒｅ（ｄｉ，ａＩ） 其中Ｓｉｍ（ｄ ， ）是节点ｄ 与节点 之问的相似度，可以根据具 体情况选取欧氏距离的倒数或夹角余弦作为相似度计算函数。 令ｄＦ｛ １， ，…， ｝，ｄｊ＝｛ｙ１，Ｙ２，…，Ｙ ｝，其中Ｘｋ （｜ｊ｝＝１，２，…， ｍ）分别为节点ｄ 与 节点的属性，则欧氏距离的倒数作为相 似度的公式为： Ｓｉｍ（ｄｌ， ）＝—＝＝ ＝＝＝ （２） ＼／∑（靓 ） 夹角余弦相似度公式如下： ∑（ ） Ｓｉｍ（ｄ”ｄｊ） ｋ＝ｌ二＿．＝＝二二 （３） Ｖ ２×＼／ ＦＮＤ 反映了该节点ｉ与其他节点的连接强度。 ＦＮＫ；：∑Ｓｉｍ（ ，ｄ ） （４） （ ，以） Ｒ 其中 是以ｄ 为圆心，以ｎ个节点两两之间欧氏距离的平均 值为半径的圆内所有节点构成的集合。之所以定义这样的Ｒ， 是因为属性网络不同于复杂网络，只能用距离来衡量分别与节 点ｉ相邻的节点 和节点ｋ之间的关系。那么怎样设置一个门 限值来确定节点 和节点ｋ的关系为“紧密”或“稀疏”呢？这里 考虑到Ｋ—ｍｅａｎｓ是一个局部最优的算法，即Ｋ—ｍｅａｎｓ偏好发 现球形簇，对孤立点非常敏感，所以定义Ｒ为以ｄｚ为圆心的实 心圆。这样，节点聚集度越高，表明该节点落在类中越密集的区 域，因此将聚集度作为选择Ｋ—ｍｅａｎｓ初始聚类中心的一个因 素，可以在数据点密集的区域找到更为Ｉ冶当初始点。 ：ＦＮＫｒ／『Ｄｌ ＿黑 （５） ７ Ｄｉ一１
其中Ｄ 是Ｒ中节点的数目。ＦＮＣｚ体现了在节点ｉ局部范围内 各节点的相互连接密度和强度。 总之，在属性网络中，节点的度和聚集系数能更好地反映 该网络的局部聚集陛。 ３．２聚类初始中心点的选择 为了克服原始的基于划分的Ｋ—ｍｅａｎｓ聚类算法对初始中 心选择敏感性的缺点，同时考虑到聚类中心的节点不仅具有与 同类其他节点较强的连接强度，而且与之同属于一个类的其他 节点之间也具有较大的相互连接密度和强度，因此，所述的Ｋ～ ｍｅａｎｓ算法初始化时综合考虑节点的度和聚集系数两个指标， 称之为节点的聚集杼性ＣＦ，。其中ｉ＝１，２，３，…，．ｒｔ，即选取度和聚 集系数高的节点作为聚类的初始中心。
