叶 羲目啦术 麟 应用研究 基于多特征选择的聚类方法研究 马元元 （中山职业技术学院信息工程学院，广东中山５２８４０４） 摘要：特征选择是数据挖掘和机器学习领域中聚类分析的一种常用分析处理方式，目前已广泛运用于文本资源分类和数据集的聚类中， 在未被标记的资源集处理环境中，让计算机自己学习使用一些特征相关度量的选择方法。总结了一种基于多特征选择算法的聚类方法 （ＭＦＳＣ），在资源集中，对多特征进行聚类特征方法选择、分类，将关系相关性较强的划分为同类簇群，再依次从每个簇群中轮询特征代表性 较强的归为一类集合，最终达到去除弱依赖特征和特征冗余的结果。实验证明ＭＦＳＣ特征集约效果较高、性能较稳定。 关键词：特征选择；多特征；聚类；ＭＦＳＣ 中图分类号：ＴＰ３０１ 文献标识码：Ａ 文章编号：１００７．９４１６ｆ２０１７）０５－０１３９－０３ Ｃｌｕｓｔｅｒｉｎｇ Ｒｅｓｅａｒｃｈ Ｂａｓｅｄ ｏｎ Ｍｕｌｔｉｐｌｅ Ｆｅａｔｕｒｅ Ｓｅｌｅｃｔｉｏｎ Ｍａ Ｙｕａｎｙｕａｎ （Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｃｈｏｏｌ，Ｚｈｏｎｇｓｈａｎ Ｐｏｌｙｔｅｃｈｎｉｃ，Ｚｈｏｎｇｓｈａｎ Ｇｕａｎｇｄｏｎｇ ５２８４０４） Ａｂｓｔｒａｃｔ：ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｉｓ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ａｎ￣ｙｓｉｓ ｏｆｄａｔａ ｍｉｎｉｎｇ ａｎｄ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｉｎ ｔｈｅ ｉｆｅｌｄ ｏｆａ ｃｏｍｍｏｎ ａｎａｌｙｓｉｓ ｍｅｔｈｏｄ，ｈａｓ ｂｅｅｎ ｗｉｄｄｙ ｕｓｅｄ ｉｎ ｔｅｘｔ ｃｌａｓｆｉｆｉｃａｄｏｎ ａｎｄ ｃｌｕｓｔｅｒｉｎｇ ｏｆｒｅｓｏｕｒｃｅ ｄａｔａ ｓｅｔｓ，ｉｎ ｔｈｅ ｕｎｌａｂｅｌｅｄ ｓｅｔ ｏｆｒｅｓｏｕｒｃｅｓ ｐｒｏｃｅｓｓｉｎｇ ｅｎｖｉｒｏｎｍｅｎｔ，ｌｅｔ ｔｈｅ ｃｏｍｐｕｔｅｒ ｃｈｏｏｓｅ ｔｈｅｉｒ ｏｗｎ ｌｅａｒｎｉｎｇ ｍｅｔｈｏｄｓ ｕｓｉｎｇ ｓｏｍｅ ｃｈａｒａｃｔｅｒｉｓｉｔｃｓ ｒｅｌａｔｅｄ ｔｏ ｍｅａｓｕｒｅ．Ｔｏ ｅｘｐｌｏｒｅ ａｎｄ ｓｕｍｍａｒｉｚｅ ａ ｍｕｌｉｔｐｌｅ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ（ＭＦＳＣ）ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ａｎｄ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ，ｗｈｉｃｈ ｕｓｅ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｉｔｃ ｉｎｔｅｒｖａｌ ｉｎｔｅｒｍｅｄｉａｔｅ ｋｅｙ ｓｉｎｇｌｅ ｆｅａｔｕｒｅ ｃｌｕｓｔｅｒｉｎｇ，ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ ｗｈｉｃｈ ｆｅａｔｕｒｅｓ ｔｈｅ ｃｏｎｃｅｎｔｒａｔｉｏｎ ｏｆｒｅｓｏｕｒｃｅｓ ｎｉ ｔｈｅ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｃｌａｓｓｉｉｆｃａｔｉｏｎ，ｄｉｖｉｄｅｓ ｈｔｅ ｒｅｌａｔｉｏｍｈｉｐ ｉｓ ｓｔｒｏｎｇ ｆｏｒ ｈｔｅ ｓａＹ￣１ｅ ｃｌｕｓｔｅｒ，ｔｈｅｎ ｆｒｏｍ ｅａｃｈ ｃｌｕｓｔｅｒ ｉｎ ｔｈｅ ｐｏｌｌｎｉｇ ｆｅａｔｕｒｅ ｒｅｐｒｅｓｅｎｔａｔｉｖｅ ｉｓ ｃｈｓｓｉｆｉｅｄ ａｓ ａ ｃｌａｓｓ ｓｅｔ．ｔｏ ｒｅｍｏｖｅ ｈｔｅ ｗｅａｋ ｄｅｐｅｎｄｅｎｃｅ ａｎｄ ｆｅａｔｕｒｅ ｒｅｄｕｎｄａｎｃｙ ｒｅｓｕｌｔｓ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ＭＦＳＣ ｆｅａｔｕｒｅ ｉｓ ｈｉｇｌｌｌｙ ｅｆｆｅｃｔｉｖｅ ａｎｄ ｓｔａｂｌｅ． Ｋｅｙ ＷｏｒｄＳ：Ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ；Ｍｕｌｔｉ ｆｅａｔｕｒｅ；Ｃｌｕｓｔｅｒｉｎｇ；ＭＦＳＣ １引言 成若干个数据簇，要求有较强的依赖和相关性，而不同的数据簇相 近年来，随着大数据、云计算、人工智能等前沿技术的广泛应 关性尽可能的小，然后对文本进行聚类分析后的分类信息可作为对 用，互联网庞大的信息的处理和使用，成为了广大业内学者研究的 用户行为相似度的分析［２】ａ 重要课题之一。这类课题研究都产生于标记资源集的数据处理中， 通常对文本数据采用向量空间标记来进行聚类描述。在这一设 对未知或者说未标记的资源集的处理研究则显得相对薄弱。其原因 计模型中，每一单词都作为特征空间中的一维坐标系，而每一文本 是因为：（１）未标记资源集特征选择是基于计算机自我学习和自我提 的数据簇作为一个向量。这种分析方法虽然简单和直接，但是在多 升处理能力的Ｉ（２）未标记资源集特征选择是利用上下文（一组带屙陛 维稀疏矩阵文本聚类中，效率和性能却很难让人满意。 的有序序列），进行自我对象认知和激活的过程，要求是自动服务，如 为了解决上述问题，我们通过特征选择来进行分级汇总进行特 同步数据到资源库、实时激活、事物的再处理的过程中充满了许多 征值的降序排序，根据标记和未标记资源集的特征选择进行分类。 不确定性，获取的结果也难以验证和解释。本文对多特征选择聚类 比如，在对文档的聚类中，文档归属于一种类型（ｔｙｐｅ），而这些聚类 算法（Ｍｕｌｔｉｐｌｅ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ）进行研究， 分析后的类型存在于索引（ｉｎｄｅｘ）中，我们对其中的字４￣（ｆｉｅｌｄｓ）进行 以降低特征空间维数、提升聚类的效果［１】。 搜索，步骤如下所示： Ｒｅｌａｔｉｏｎａｌ ＤＢ一＞Ｄａｔａｂａｓｅｓ一＞Ｔａｂｌｅｓ一＞Ｒｏｗｓ一＞ ２文本分类的相关技术 ＣｏｌｕｍｎｓＳｅａｒｃｈ一＞Ｉｎｄｉｃｅｓ一＞Ｔｙｐｅｓ一＞Ｄｏｃｕｍｅｎｔｓ一＞ 聚类在ｗｅｂ文本数据的归类中作为一种手段，利用的是计算机 Ｆｉｅ１ｄｓ 的自我分析和聚合。例如两个职员对音乐有兴趣，一个喜欢哲学，一 个喜欢运动。这些数据并没有被预先计算好，它们是实时的从匹配 ３特征选择聚类算法研究 查询语句的文档中动态计算生成的。首先将文本中挖掘的数据集分 在未标记的数据集中，数据的特征并不是孤立表现的，而是相 收稿日期：２０１７—０５—１６ 基金项目：中山市科技计划项目，项目编号：２０１５Ｂ２３８２。 作者简介：马元元（１９８２－－），女，甘肃庆阳人，硕士研究生，讲师，研究方向：数据挖掘、物联网。 芹甘天发计算 多特订七彝￡买 椭 杯记王键 漠Ｉ试 数据集 特征序歹ＩＪ类 别空区间 特征簇 群 特征子集 空间 图１多特征选择聚类算法处理流程 表１各特征选择算法在Ｋ—Ｍｅａｎｓ上分类的结果 Ｉｄ ｌ ２ ３ ４ ５ ６ ａＶｅｒ Ｒａｗ ９４．２８±０．１ｌ ４０．６３±７．６５ １０ｏ土０．０ ８０．９６±２．５２ ９６．５５±０．２３ ９２．２８士０．４４ ８４．１２±１．８３ ＴＳ ９４．３８士０．１６ ５７．５土５．５３ ９９．０２±０．０ ７０．４８士１．０８ ９５．５９±０．３ ９２．６７士０．５４ ８４．９４士１．２７ ＦＣＢＦ ９４．０３士０．０４ ５８．１３±２．７１ １００±０．０ ９５．３２士２．Ｏ５ ９６．６０±０．２５ ９１．０９土Ｏ．Ｏ ８９．２０±０．８４ ＦＳＦＣ ９４．３６士０．１７ ４８．１３士３．５６ ９９．０２土０．Ｏ ７０．４８士１．０８ ９５．５９±０．３ ９２．０８士Ｏ．Ｏ ８３．２８土０．８５ ＭＦＳＣ ９４．２６土０．０２ ５３．７５±２．６ｌ ９９．８６土０．０ ９５．３２士１．０５ ８９．０９士０．０ ９１．ｏ９±０．Ｏ ８７．２２土０．６３ 表２各特征选择算法在Ｎａ ｉｖｅ ｂａｙｅｓ上分类的结果 Ｉｄ ｌ ２ ３ ４ Ｒａｗ ９５．４０±０．０５ ４９．３８士４．６４ ９５．７３士０．０３ ７４．６８±１．９４ ＴＳ ９６．１９±０．０６ ７１．２５士１．４０ ９８．５２±０．０ ７２．５８±１．８９ ＦＣＢＦ ９４．４５士０．０２ ６１．８６士１．４０ ９８．５２士Ｏ．０ ７４．８４土１．４４ ＦＳＦＣ ９６。１９±０。０６ ６８．１３±５．１３ ９８．５２土０．０ ７２．５８±１．８９ ＭＦＳＣ ９４．７９－１－０．０ｌ ５３．１３土１．８３ ９８．３３土Ｏ．０ ７５．１６土１．０９ ５ ６ ７ ８９．９８±０．１３ ９３．６６士Ｏ．８９ ８３．１４士１．２８ ９６．０９士Ｏ．０ ９３．０７±０．Ｏ ８７．９５±Ｏ．５６ ９１．３６土０．２６ ９４．０６土０．０ ８５．８５士０．５２ ９６．０９±０．０ ９１．０９土０．０ ８７．０１±１．１８ ８６．６７土０．１５ ９６．０４士０．０ ８４．０２±０．５１ 关联的表现相似特征，这就构成了多特征的集。针对这些在区分类 则可以利使用以上公式计算每＋ｗｅｂ页面的特征向量空间，对 别时存在的冗余现象，本文提出了基于上下文多特征选择的聚类算 每个特征区间进行聚类汇总了。 ３．２多特征选择聚类算＂￣（ＭＦＳＣ） 法。主要思想是根据数据集表现的特征的相似度，对相似属性类的 在聚类的选择特征中，对特征类型的分类是—个反复进行的过 特征进行聚类汇总，然后在每个簇群中选择一个特征作为主键，簇 首先对探测到的未标记的数据集进行相关度计算并形成类别区 群中的其他特征从候选特征集中标记为外键或对依赖性弱的进行 程，剔除，这样保证特征集的相对独立性、降低高冗余度，进而对剩余的 间，基于多特征选择聚类的算法，会在此基础上进行降序特征排序， 特征进行信息筛选后特征归类。 然后通过聚类算法在不同的子空间中检索数据簇，确定标记主键， ３．１特征区问的选择 然后形成特征子集的特征簇群。其处理过程如图１所示。 我们ＰＡｗｅｂ文本为例，对于ＤｏｃＴｙｐｅ￣型的文本中的每一特征 在实际的应用中，多特征选择聚类算法充分利用文本的多特征 作为一类的特征区间。如文档内容、ＵＲＩ和ｗｅｂ的访问日志，对于文 特性，为特征类的聚集确定主键，并进行分离出具有代表性的特征 这样在得到不同类别的类集后，在各个类集上进行特征选择 档内容和ＵＲＩ我们可以用向量区间模型表示，通过对语义的划分表 子集， 示权值。但对于用户访问过的ｌｏｇ信息，如果没有定义信息来源类 并利用合并函数得到结果集。设Ｍ表示每个特征区间的数据集，别，将得不到任何关于词分类的信息。因此引入了一种从开发到用 厂（ｎ）代表一维的特征向量，钾ＬＩ弋表聚类选择的第ｉ个特征区间，ＣＦ 代表合并的函数。那么算法程序的伪代码可以表示为： 假设日志信息包含了ｍ个上下文样本记录和ｎ个查询特征，特 ｆｏｒ（ｎ ｉｔｅｒａｔｉｏｎｓ ｏｆ ｃｌｕｓｔｅｒｉｎｇ）｛ ｆｏｒ（Ｍ ｆｅａｔｕｒｅ ｃｈａｒａｃｔｅｒ）｛ 征集Ｆ可表示为： 户使用之间的关系向量。 Ｆ＝ｆ厂１．ｆ２，ｆ３，…．ｆｎ］，厂∈Ｒ（ｎ）（１≤Ｋ≤ｎ）．Ｋ指的是特征 集，Ｆ进行聚类时被划分了Ｋ个不同的特征簇。 对于特征选择后的聚类，不确定性是特征评价的指标，它也是 针对计算机信息增减变化的度量指标和依赖程度，可以理解为数据 簇之间共同相似的信息含量。如果用∞表示ｗｅｂ页面的上下文本记 录， 表示查询次的访问过的页面，ａ， 表示特征向量的空间。 ｑｏｎＶ（∞）＝ ， ｑｏ２…．， ，Ｄｏ ｃｌｕｓｔｅｒｉｎｇ ｉｎ ｆｅａｔｕｒｅ ｃｈａｒ ｍ ｝ ｆｏｒ（Ｍ ｆｅａｔｕｒｅ ｃｈａｒａｃｔｅｒ） ｛ ｆｏｒ ｆｅａｔｕｒｅ ｃｈａｒａｃｔｅｒ ｉｎ，ｄｏ ｆｅａｔｕｒｅ ｉｎｄｅｘ ｕｓｉｎｇ ｒｅｓｕｌｔｓ ｉｎ ａｌｌ ｆｒｅａｔｕｒｅ ｃｈａｒａｃｔｅｒ； ｔｈｅｎ 】下 ｔｏ ｃｏｍｂｉｎｅｄ ｓｃｏｒｅ ｆ（ｘ）＝Ｖｏｔｉｎｇ（ｖａｌｕｅ０） 欺事虹水 ？ 应用研究 并由实验结果可以看出：（１）ＭＦＳＣ算法结果正态分布的稳定性， ｝ （２）ＭＦｓＣ在未标记数据集上的分类用时是高于其他特征方法的， 其中，在程序代码的实现中利用到的算法厂ｘ，可以具体表示为： 其原因在于多特征的选择的分量，类区间内距离分量相比其他更 Ｖｏｔｉｎｇ（ｖａｌｕｅ（厂（ｎ）） 小。（３）ＭＦＳＣ在数据集上的分类上，由于特征选择的子集区间分 量较小，准确率相比其他更高和错误率更低［３】。 ｝ ｆ ＝ｆ ∑Ｍ．。ｖｏｔｅ（ｆ（ｖ）ｎ．ｎ ） １Ｌ ｖ。ｔ。（，（ ）ｎ，口 ）：ｆ【。Ｖａ ｕｅ‘厂 ｎ，。Ｙ ｌ ＜ｓ （１） １、，ａｌｕｅ（厂（、 ）ｎ．ｅ、 Ｌ） Ｓｔ ４结论 乞●ｉ｛ｐ Ｉ 囊●●●● Ｌ墨蓝毫毫鼙 慧 ｔ ｔ ｔ ｔ ｔ■ 秘一ｌＩ 舯 聃暑 ｝¨ 己学习使用多特征相关的选择聚类的方法——ＭＦＳＣ。使用这一 ｉ ２ ３ ｔ 本文提出一种在未被标记的资源集处理环境中，让计算机自 公式（１）中，ｖａｌｕｅ（厂（ｎ）可以用３．１节中标记资源集的特征选择 算法将有无标记或有无监督的特征选方法成功的运用到了聚类分 聚集函数公式来计算，ｓｔ是特征选择的阀值，可以通过以往统计的数 析，利用了上下文的多种相似特征进行主成分分析，确立主键和区 据推出设定值。从算法中，我们可以发现基于上下文进行多特征选 间内距离，并对子区间也进行了特征值降序排列，从而达到较为理 择的聚类方法在聚类时是利用主键的方式进行表示，采用分类别的 想的效果。 簇间的不同性选择特征子集。在每一次特征集簇群选择后，聚类都 参考文献 会重新降序排列汇总，得到一组高聚类的特征子集。 ［１］樊东辉．基于文本聚类的特征选择算法研究［Ｄ］．西北师范大学。 ３．３实验结果比较 对于特征选择算法的评估，我应考虑到：（１）特征分类所获的结 ［２］樊东辉，王治和，陈建华。许虎寅．基于ＤＦ算法改进的文本聚类特征 果相同时，子集的区间距离越短，其性能越优・（２）在大数据集测试 选择算法［Ｊ］．甘肃联合大学学报（自然科学版）。２０１２（１）：５１－５４． 时，特征分类的越稳定，其算法越好。 ［３］徐峻岭。周毓明。陈林．徐宝文．基于互信息的无监督特征选择［Ｊ］． 表１和表２分别对比了Ｒａｗ（特征全集）、ＴＳ、ＦＣＢＦ、ＦＳＦＣ、 计算机研究与发展．２０１２（２）：３７２－３８２． ＭＦＳＣ等算法，在Ｋ－Ｍｅａｎｓ和Ｎａ Ｙｖｅ ｂａｙｅｓ分类器的分类结果， ２０１２． Ｚ—．ｎ 工Ｐ＾ｄｄｒ日，●捌：＾Ｃ＾ｄｄｒ■■曩 口ｐ 口ｐ 土，２．１６９．２０．２／２４ 土，２．１６８．０．１／２４ ０００１．葛‘Ｂ２．８盂０１ ００ｔ０．Ａ３０Ａ．Ｏｌ●Ｃａ Ｄ０ ｌｌ 自 ＾啉 Ｄ口确 Ｄ叫ｈ 一一 一一 一－－ＯＯＯＩ．‘４Ｂ２＋Ｂ置Ｏ２ ＯＯＯ１．‘●ｌ醢．Ｂｌｏａ ０００１．“戤．口妁● ０００１．掌¨噱．吐Ｏ暑 却 玺 ・一ｏ９幢 ・’‘ｔ豫，薯 口蛋 。 ； 。 。 图２交换机为Ｌｉｎｋｓｙｓ的Ｉｎｔｅｍｅｔ口分配到的地址 ……上援第４６贞 经过上述设置，交换机为ＰＣ０分配了Ｊ＠Ａｌｌ：１９２．１６８．１０．２／２４， 无线胖ＡＰ）等类设备的统称。无线ＡＰ是使用无线设备（手机等移动设 为Ｌｉｎｋｓｙｓ的Ｉｎｔｅｒｎｅｔ口分配了地址１９２．１６８．２０．２／２４ｌＬｉｎｋｓｙｓ为 备及笔记本电脑等无线设备）用户进入有线网络的接人 ，主要用于ＰＣ１分配了地址ｌ９２．１６８．０．１００／２４。图２所示给出了交换机为 宽带家庭、大楼内部、校园内部、园区内部以及仓库、工厂等需要无Ｌｉｎｋｓｙｓ的Ｉｎｔｅｍｅｔ地址。 线监控的地方，典型距离覆盖几十米至上百米，也有可以用于远距 使用ｐｉｎｇ命令检验无线终端设备和交换机之间的连通性，以 离传送，目前最远的可以达到３０ＫＭ左右，主要技术为１ＥＥＥ８０２．１１系 及两边无线终端设备之间的连通性，结果都能连通。实验结果表明， 列。大多数无线ＡＰ还带有接人点客户端模式（ＡＰ ｃｌｉｅｎｔ），可以和其 通过ＡＰ和ＶＬＡＮ技术可以实现无线网络和有线网络的互相连接。 它ＡＰ进行无线连接，延展网络的覆盖范围。 本研究拓扑中包含了有瘦ＡＰ和胖ＡＰ（Ｌｉｎｋｓｙｓ）两种设备。 嬉蕊 ． ．通过上述的研究表明，无论是瘦ＡＰ，还是胖ＡＰ，都可以通过 ３本研究拓扑圈的设计和Ｉ Ｐ地址段的规划 ＶＬＡＮ￣￣．将无线终端设备连接到有线网络中，从而进一步实现无 ，本研究采用如图１的拓扑图设计。在如下综合网络中，共有１个 线终端设备像有线终端设备一样，利用网络中的所有资源，并通过 三层交换机，１台瘦ＡＰ，Ｉ台Ｌｉｎｋｓｙｓ。链路分配的地址段分别为： 有线网络实现广域网络的连接。本研究为局域网工程项目中，实现 ｖｌａｎ １０的地址网段为１９２．１６８．１０．０／２４、ｖｌａｎ ２０的地址网段为 无线和有线的有效互连提供了新的思路。 １９２．１６８．２０．０／２４，瘦ＡＰ－Ｖ作在二层，只需要配置ＳＳＩＤ为ＡＰ￣Ｉ］ 参考文献 可，ｌｉｎｋｓｙｓ设备使用Ｉｎｔｅｍｅｔ口和交换机相连接，连接方式为ａｕ一 ［１］唐继勇ｔｏｍａｔｉｃ ｃｏｎｆｉｇｕｒａｔｉｏｎ—ＤＨＣＰ，管理地址使用默认地址１９２．１６８． ＤＨＣＰ自动分配，ＰＣｌ的地址由Ｈｎｋｓｙｓ的ＤＨＣＰ分配，地址网段为 １９２．１６８．０．０／２４。 童均．任月辉．无线网络组件项目教程［Ｍ］．中国水利水电 山 “。ｎ１ ，。０・１／２４，且将ＤＨｃＰ设置成Ｅｎａｂｌｅｄ状态。Ｐｃ０的地址由交换机 ［２］杨军李瑛，杨章玉．无线局域网组建实战［Ｍ］．北京：电子工业出版 。ｎｎ ｆ＿ｕ・（．ｕｕｕ・ 交换机上关键配置语句如表ｌ所示。