２０１２年第２５期 ＳＣＩＥＮＣＥ＆ＴＥＣＨＮＯＬＯＧＹ ＩＮＦＯＲＭＡＴＩＯＮ Ｏ高校讲坛０ 科技信息 一种高效的Ｋ—ｍｅａｎｓ聚类算法 王娟 （兰州工业学院软件工程系甘肃兰州７３００５０） 【摘要】聚类算法作为一种重要的数据挖掘的方法，能找到样本中相对集中的区域。本文分析了一些常用聚类算法以及局限性，并且针对 Ｋ—ｍｅａｎｓ算法中初始点的选择，讨论了一种改进的Ｋ—ｍｅａｎｓ算法的实现过程，以期得到比较理想的聚类效果。 【关键词】数据挖掘；聚类；Ｋ—ｍｅａｎｓ 数据挖掘（Ｄａｔａ Ｍｉｎｉｎｇ）ｔ”．在人工智能领域，又被称为数据库中的 所有对象的均值）：不断重复这一过程直到聚类中心不变为止。ｋ个聚 知识发现（Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ｉｎ Ｄａｔａｂａｓｅ，ＫＤＤ），通过分析数据库中 类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的 的海量数据．．找出其中的规律，挖掘出来的知识可用于信息管理、决 策支持、过程控制等方面。聚类算法作为数据挖掘的重要方法之一，越 来越受到人们的重视。聚类（Ｃｌｕｓｔｅｒ）分析是由若干模式（Ｐａｔｔｅｒｎ）组成 的．通常．模式是一个度量（Ｍｅａｓｕｒｅｍｅｎｔ）的向量，或者是多维空间中 的一个点 聚类分析以相似性为基础．在一个聚类中的模式之间比不 在同一聚类中的模式之间具有更多的相似性。 本为提出了一种改进的Ｋ—ｍｅａｎｓ算法，该算法具有较高的效率。 １ 常用聚类算法刚及其局限性 １．１划分法（ｐａｒｔｉｔｉｏｎｉｎｇ ｍｅｔｈｏｄｓ１ 给定一个有Ｎ个元组或者纪录的数据集．划分法构造Ｋ个分组． 每一个分组就代表一个聚类，Ｋ＜Ｎ。而且这Ｋ个分组满足下列条件： （１）每一个分组至少包含一个数据纪录；（２）每一个数据纪录属于且 仅属于一个分组；对于给定的Ｋ，算法首先给出一个初始的分组方法． 以后通过反复迭代的方法来改变分组．使每一次改进之后的分组方案 都较前一次好。使用这个基本思想的算法有：Ｋ—ＭＥＡＮＳ算法、Ｋ～ ＭＥＤＯＩＤＳ算法、ＣＬＡＲＡＮＳ算法。 ｌ＿２层次法（ｈｉｅｒａｒｃｈｉｃａｌ ｍｅｔｈｏｄｓ） 这种方法对给定的数据集进行层次似的分解．直到某种条件满足 为止。具体又可分为“自底向上”和“自顶向下”两种方案。例如在“自底 向上”方案中．初始时每一个数据纪录都组成一个单独的组．在接下来 的迭代中．它把那些相互邻近的组合并成一个组．直到所有的记录组 成一个分组或者某个条件满足为止。代表算法有：ＢＩＲＣＨ算法、ＣＵＲＥ 算法、ＣＨＡＭＥＬＥＯＮ算法等。 １＿３ 基于密度的方￣（ｄｅｎｓｉｔｙ—ｂａｓｅｄ ｍｅｔｈｏｄｓ１ 这个方法的指导思想就是，只要一个区域中的点的密度大过某个 阈值，就把它加到与之相近的聚类中去。代表算法有：ＤＢＳＣＡＮ算法、 ＯＰＴＩＣＳ算法、ＤＥＮＣＬＵＥ算法等 １．４基于网格的方法（ ｄ—ｂａｓｅｄ ｍｅｔｈｏｄｓ１ 这种方法首先将数据空间划分成为有限个单元（ｃｅｌ１）的网格结 构所有的处理都是以单个的单元为对象的。这么处理的一个突出的 优点就是处理速度很快。代表算法有：ＳＴＩＮＧ算法、ＣＬＩＱＵＥ算法、 ＷＡＶＥ—ＣＬＵＳＴＥＲ算法。 １．５。基于模型的方法（ｍｏｄｅｌ—ｂａｓｅｄ ｍｅｔｈｏｄｓ１ 基于模型的方法给每一个聚类假定一个模型．然后去寻找能个很 好的满足这个模型的数据集。通常有两种尝试方向：统计的方案和神 经网络的方案 上述这些算法的缺点在于对样本数据的分布进行了一定的假设． 处理大数据集和高维数据集。尤其是对处理存在孤立点的大文档集时 不够有效 ２改进的Ｋ—ｍｅａｎｓ算法描述 ２．１ Ｋ—ｍｅａｎｓ算法描述 Ｋ—ｍｅａｎｓ算法接受输入量ｋ：然后将ｎ个数据对象划分为ｋ个聚 类以便使得所获得的聚类满足：同一聚类中的对象相似度较高：而不 同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值 所获得一个“中心对象”（引力中心）来进行计算的 Ｋ—ｍｅｄ ｎｓ算法的工作过程说明如下：首先从ｎ个数据对象中任意 选择ｋ个对象作为初始聚类中心：而对于剩下的其它数据对象．根据 它们与聚类中心的相似度，将它们分别分配给与其最相似的以聚类中 心为代表的聚类；然后再计算每个所获新聚类的聚类中心（该聚类中 １６８ 分开。 ２．２改进的Ｋ一Ⅱｌｅａｎｓ算法描述 聚类的初始点选择对ｋ－ｍｅａｎｓ聚类算法有很大影响 通常情况 下．初始点往往是随机选择的．因此聚类的结果也常常是局部最优的 因而如果更合理的选择初始点．那么聚类结果也会更加合理．同时聚 类的速度也会会很大提高。为了保证初始点是分散而不是密集的，因 而引入了距离概念：同时，为了消除孤立点对聚类结果的影响，引入密 度的概念 以任意一个点作为中心．正数ｒ作为半径．就能得到一个邻 域．落入邻域内的其它点的个数就是该点的密度．选择密度足够大的 点作为初始聚类中心 那些密度太小的点就可以看作是孤立点（‘‘脏” 点）。根据密度选取初始点 的具体方法如下： ２．２．１设置正数ｒ和ｄ。ｒ是用来计算密度的半径，ｄ是两个聚类中心 的初始距离．通常ｒ小于ｄ ２．２．２以ｒ为半径计算每个点的密度．选择密度最大的点作为第１个 聚类中心。然后计算这个中心与密度为第２大的点两者之间的距离． 如果距离小于ｄ．则为“脏”点，不考虑这个点。反之选择这个点为第２ 个中心。然后挑选密度为第３大的点，计算它与前两个聚类中心的距 离。如果距离小于ｄ，不考虑，反之，选它作为第３个中心 以此类推 这样初始聚类中心之间的距离就相对的加大了．因此也就避免了 初始中心太靠近而影响聚类结果。另外，这样处理使中心点的初始输 入顺序按照密度大小排列．因而算法对输入顺序不敏感．会得到更好 的聚类结果 但半径ｒ和距离ｄ都是经验值，对于距离ｄ．假定它是半径ｒ的倍 数，对于半径ｒ的选择，用一种自适应选择最佳密度半径的方法 通常 人们期望的是最大的密度应该等于或小于一个类中样本点的个数．所 以我们用ｎ除以ｋ得到一个类中的近似平均点数．ｎ为所有样本点的 个数，乘以一个系数（例如０．８或０．５），这样最大密度锁定在０．８＊ｎ／ｋ到 Ｏ．５＊ｎ／ｋ之间。方法如下： 赋给ｒ一个初始值．如果最大密度大于０．８ ｎ／ｋ．则ｒ减去一个定 长（如Ｏ．０５）。再次计算最大密度，如果最大密度小于Ｏ．５＊ｎ／ｋ．则ｒ加上 一个步长，然后再计算最大密度，这样找到ｒ值．它对应的最大密度在 ０．８＊ｎ／ｋ到０．５＊ｎ／ｋ之间。相应的可以进一步确定最佳的聚类初始点 ２．３改进的Ｋ—ｍｅａｎｓ算法性能分析 实验表明，在运用误差平方和准则函数测度聚类效果时．最佳聚 类结果对应于目标函数的极值点．由于目标函数存在着许多局部极小 点，而算法的每一步都是沿着目标函数减小的方向进行．若初始化落 在了一个局部极小点附近，就会造成算法在局部极小处收敛。因此初 始聚类中心的随机选取可能会陷入局部最优解．而难以获得全局最优 解。针对这种情况，采用了基于密度的处理方法来获得初始聚类中心． 并取得了较优的聚类效果 Ｋ－ｍｅａｎｓ算法对于文档中的孤立点很敏感，这类Ｋ～ｍｅａｎｓ文档将 对聚类结果产生较大的影响。而初始聚类中心是基于密度的选取方法 的聚类算法对存在孤立点的文档集能得到较好的聚类结果 ３总结 本文针对Ｋ—ｍｅａｎｓ算法在文档聚类过程中对初始聚类中心的问 题提出了一种算法，实 表明了该算法的有效性。 【参考文献】 ［１］Ｊｉａｎｗｅｉ Ｈａｎ，Ｍｉｃｈｅｌｉｎｅ Ｋａｍｂｅｒ．Ｄａｔａ Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ ａｎｄ Ｔｅｃｈｎｉｑｕｅｓ［Ｍ］ Ｓｉｍｏｎ Ｆｒａｓｅｒ Ｕｎｉｖｅｒｓｉｔｙ，２０００． （下转第２２９页） 科技信息 。外语论坛ｏ ＳＣＩＥＮＣＥ＆ＴＥＣＨＮＯＬＯＧＹ ＩＮＦＯＲＭＡＴＩＯＮ ２０１２年第２５期 语戏剧晚会以及英语听说读写译的竞赛．让学生在实践中得到锻炼 ［１］教育部高等教育司．大学英语课程教学要求【Ｍ］．上海外语教育出版社．２００４ 激发学习动机和兴趣，增强学习英语的信心，提高其综合应用能力。 （１）． ［２］周军，刘晓娟．高职高专学生英语应用能力培养初探［Ｊ］．甘肃科技，２００９（９）： １８７－１８８． ３结束语 总之。独立学院大学英语的教学改革迫在眉睫．培养的学生要适 作者简介：￣ｂ￣（１９８２－－），女，湖北宜昌人，三峡大学科技学院，讲师，研究 应社会的需求，即培养综合应用型人才，体现在英语教学方面就是要 方向为英语语言教学。 以培养学生英语综合应用能力为目标。只有不断转变教师观念．改进 刘建新（１９５＿ｒ），女，湖北宜昌人，三峡大学，副教授，研究方向为英语语 教学方法，培养学生自主学习能力，激发学生的学习动机，强化听说读 言教学。 写译能力，才能真正提高学生的英语综合应用能力。 ［责任编辑：王洪泽］ 【参考文献】 （上接第１６８页）［２］Ａｌｓａｂｔｉ，Ｒａｎｋａ Ｓ，ｓｉｎｇｈ Ｖ．Ａｎ ｅｆｆｉｃｉｅｎｔ ｋ—ｍｅａｎｓ ｃｌｕｓｔｅｒｉ“ｇ ｅｎｈａｎｃｅ ｔｅｘｔ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｕｓｉｎｇ ｕｎｌｂｅｌａｅｄ ｄａｔａ［ｃ】ｌ Ｃａｎａｄａ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ａｌｇｏｒｉｔｈｍ，ＩＰＰＳ－９８【Ａ】，，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｉｒｓｔ Ｗｏｒｋｓｈｏｐ ｏｎ Ｈｉｓｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｄａｔｅ Ｍｉｎｉｎｇ［Ｃ１．Ｏｒｌａｎｄｏ。ｎｏｒｉｄａ．ＵＳＡ，１９９８． ［３］Ｅｓｔｅｒ Ｍ，Ｋｒｉｅｇｅｌ Ｈ Ｐ，Ｓａｎｄｅｒ Ｊ，ｅｔ ａ１．Ａ Ｄｅｎｓ＠一Ｂａｓｅ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｏｎ Ｋｎｏｗｌｅａｇｅ Ｄｉｓｅｏｒｖｅｒｙ ｎｄ Ｄａｔａａ Ｍｉｎｉｎｇ．Ｐｏｒｔｌｎｄ １ａ９９６．２０：２２６—２３１． ＳＩＣ．ＫＤＤ，２００２． 作者简介：王娟（１９８１．８一），女，讲师，主要从事计算机软件、数据库方面的 Ｄｉｓｃｏｖｅｒｉｎｇ Ｃｌｕｓｔｅｒｓ ｉｎ Ｌａｒｇｅ Ｓｐｍｉ￣Ｄａｔａｂａｓｅｓ ｗｉｔｈ Ｎｏｉｓｅ［Ｊ］．Ｐｒｏｃ．２ｎｄ Ｉｎｔ，Ｃｏｎｆ． 研究。ｆ ４ ｉＲａｓｋｕ￣ｉ Ｂ，Ｆｅｒｒ Ｈ，Ｋｏｗａｌｃｚｙｋ Ａ．Ｃｏｍｂｉｎｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｎｄ ｃｏ—ｔｒａｉｎｉｎｇ ｔｏ ［责任编辑：王洪泽】 一（上接第１７１页）一生不能忘记的就是辅导员，所以辅导员是影响学生 ［３］浅谈对高校辅导员工作的认识【Ｊ］．科技信息，２０１０，７． 生的导师。 ［４］曲建武－一位老辅导员的，ｇ＇Ｎ［Ｊ１．高校辅导员学刊，２０ｏ９，１ 【参考文献】 ［１］中共中央、国务院关于进一步加强和改进大学生思想政治教育的意见学习 辅导员读本【Ｍ】．北京：中国人民大学出版社，２００５． ［２］程艺．崇高的使命伟大的事业光明的前途明．高校辅导员学刊，２００９，１． 作者简介：姜素华（１９８Ｏ．１【卜），女，内蒙古赤峰人，商丘师范学院，助教，主 要从事学生思想教育管理工作。 ［责任编辑：王洪泽］ （上接第１７８页）研究完积分的性质。我们在此有必要研究积分的 【参考文献】 ［１］华东师范大学数学系，编著．数学分析：上【Ｍｊ．高等教育出版社，１９８７，９：１４４— 中值定理 １６０． 若函数 ）在闭区间［ａ，ｂｌｉ连续，则在积分区间［ａ，ｂｌ－ｋ￣少存 ［２］贾建华，王克芬，编著傲积分证明方法初析【Ｍ］．南开大学出版社，１９８９，８：１７７— 在一个点 ［ａ，ｂ】，使下式成立 ，ｎ ２１７． Ｊ ｆ（ｘ）ｄｘ ）（ｂ－ａ）． 研究以上性质让我们更方便的应用定积分．在此以后，我们对于 定积分的运算和定积分的实际应用能够更好的学习。 ［３］郝涌，李学志，等，编著．数学分析考研精编［ＭＩ．信阳师范学院数学系出版． ［４］魏国强，编著．高等数学研究［Ｍ】．西北工业大学出版社，２００２，２：５８—６０． ［责任编辑：王洪泽］ （上接第１８９页）是最重要但也是最容易忽视的情景语境。译者应该将 所有的故事情节了解透彻之后才下笔翻译。 ２．２故事中人物的肢体语言 这里所说的肢体语言包括人物的动作、 面部表情、说话时的语调等．他们对确定人物之间微妙复杂的关系起 着重要的作用．从对确定语篇中词语的意思起着关键的作用。 ２．３文化语境的陷阱。如果考虑了情景语境．语篇依然不能连贯，那 就要注意语篇中是否含有文化因素 由于英汉两种语言在文化上的巨 大差异，译者往往一不小心就掉进了文化的陷阱．所以翻译时一定要 切记不要望文生义．因为即使很简单的词语或表达都可能或包含着文 化的因素。 ２．４文化词语的翻译策略 关于文化词语很多翻译理论家提出了不 同的翻译策略．但笔者认为。作为字幕的译者．在选择翻译策略时首先 ｆ参考文献】 ［１］王冬竹＿语境与话语ｆＭ１．眙尔滨：黑龙江人民出版社，２００１． ｆ２瑚壮麟．语篇的衔接与连贯［ＭＩ上海：上海外语教育出版社，１９９４． ［３］李运兴．语篇翻译引论『Ｍ］．北京：中国对外翻译出版公司，２００１． ［４］张春柏．影视翻译初探『Ｊ１．中国翻译，１９９８（２）． ［５］钱绍昌．影视翻译：翻译园地中越来越重要的领域Ⅱ１．中国翻译，２ｏｏｏ（１） ［６］李运兴．字幕翻译的策略 ．中国翻译，２００１（７）． 注释： ①本文英文字幕来自Ｔ 字幕组，译文１来自圣城家园字幕组。译文２来 自破烂熊字幕组． 考虑的应该是观众的接受度及字幕对观众产生的交流效果。● ［责任编辑：汤静】