《数据挖掘:概念与技术》读书笔记(五)

大数据 2017-08-31

  1. 聚类是将数据分组成类或集群的过程,并且集群中的对象彼此之间具有高相似性,但与其他集群中的对象不相似。聚类方法有以下几种:(1)分区方法:给定n个对象或数据元组的数据库,分区方法构造k个数据分区,其中每个分区表示一个集群,k≤n。 给定k,构造的分区数,它创建一个初始分区。 然后,它使用迭代重定位技术,尝试通过将对象从一个组移动到另一个组来改进分区。良好分区的一般标准是同一集群中的对象彼此“接

近”或相关,而不同集群的对象“远离”。 k-means算法是一种常用的分区方法。(2)分层方法:分层方法创建给定的一组数据对象的分层分解。它可以是聚集的或分裂的。聚集(自下而上)方法从每个对象形成一个单独的组开始。它连续地合并彼此接近的对象,直到所有组合并为一个,或直到终止条件成立。分裂(自上而下)的方法从同一个集群中的所有对象开始。在每个连续的迭代中,一个群集被分解成更小的簇,直到最终每个对象形成自己的簇或直到终止条件成立 AGNES和DIANA是层次聚类的示例。BIRCH将层次聚类与迭代(基于距离)重定位相结合。(3)基于密度的方法:这些方法是基于密度的概念。只要“邻里”的密度超过某个阈值,主要思想就是继续增长给定的群集。也就是说,对于给定簇内的每个数据点,给定半径的邻域必须至少包含最小点数。 该方法可用于滤除噪声并发现任意形状的簇。DBSCAN和OPTICS是基于密度的聚类的典型例子。(4)基于网格的方法:这种方法将对象空间量化为形成网格结构的有限数量的单元格,所有的聚类操作都在网格结构上执行。这种方法的主要优点是其快速处理时间,其通常与数据对象的数量无关,并且仅依赖于量化空间中每个维度中的单元数量。STING是基于网格的聚类的一个例子。(5)基于模型的方法:该方法假设每个集群的模型,并找到数据与给定模型的最佳拟合。基于模型的算法可以通过构建反映数据点的空间分布的密度函数来定位聚类。它还导致基于标准统计信息自动确定群集数量的方法。它考虑到“噪音”或异常值,从而有助于方法的鲁棒性。COBWEB和自组织特征映射是基于模型的聚类的示例。(6)高维数据的方法:高维数据通常可以有许多不相关的维度。随着维度的增加,数据通常变得越来越稀疏,因为数据点可能位于不同的维度子空间中。点对之间的距离测量变得无意义,数据中任何地方的点的平均密度可能很低。因此,基于距离和密度的聚类方法对聚类高维数据无效。已经提出了替代方法,例如子空间聚类方法,其在数据的子空间(或维度的子集)中搜索簇,而不是在整个数据空间上搜索。CLIQUE和PROCLUS是子空间聚类方法的示例。频繁的基于模式的聚类是另一种聚类方法,其提取频繁发生的维度子集中的不同频繁模式。 pCluster是频繁基于模式的聚类的一个例子,它们基于它们的模式相似性对对象进行分组。(7)基于约束的方法:这些方法通过结合用户指定或面向应用的约束来执行群集 约束可以表达用户的期望或描述所需聚类结果的“属性”,并提供与聚类过程进行通信的有效手段。使用基于约束的方法用于与障碍物物体聚类的空间聚类(例如,在计划自动银行机器的布置时考虑诸如河流和高速公路之类的障碍物)和用户约束的聚类分析(例如,在确定时考虑关于客户群体的具体约束 一个新的服务站的最佳位置,如“必须服务至少100个高价值客户”)。此外,半监督聚类使用例如成对约束(例如标记为属于相同或不同簇的实例对),以便提高所得聚类的质量。

  1. EM聚类基本上使用底层混合模型进行聚类。由于这种模型的概率性质,EM聚类可以很容易地扩展,以处理具有数值属性和分类属性的数据。在每个属性彼此独立的假设下,我们可以通过使用密度函数(如泊松,高斯等)来建模数值属性;可以通过将这些属性上的离散分布相关联来建模分类属性,例如多项式,二项式等。总分量密度可以分解为每个属性上的密度函数的乘积。通过具有这样的组件密度函数,我们可以轻松地使用EM聚类来将数据与数字属性和分类属性进行聚类。

  2. 与其余数据集完全不同或不一致的数据对象称为“异常值”。异常挖掘对于检测欺诈活动(如信用卡或电信欺诈)以及客户细分和医学分析很有用。基于计算机的异常值分析可以是基于统计的,基于距离的或基于偏差的。基于统计的方法假设给定数据集的分布或概率模型,然后使用不一致性测试来识别关于模型的异常值。不一致测试基于数据分布,分布参数(例如,均值,方差)和预期异常值的数量。这种方法的缺点是大多数测试都是针对单一属性的,在许多情况下,数据分布可能不知道。采用基于距离的方法来对付基于统计的方法的局限性。DB(p,dmin)-outlier是数据集D中的对象o,使得D中的对象的至少一部分p位于距离o大于dmin的距离处。与基于统计的方法相比,基于距离的方法概括了各种标准分布的不一致测试背后的想法。此外,基于距离的异常值检测避免了可以将观察到的分布拟合到某些标准分布和选择不一致性测试中的过度计算。基于偏差的异常值检测不使用统计测试或基于距离的测量来识别异常对象。相反,它通过检查组中对象的主要特征来识别异常值。“偏离”这个描述的对象被认为是异常值。这种方法的两种技术包括顺序异常技术和OLAP数据立方体技术。

  3. 大型社交网络具有不同于单一数据关系的特征,因此在分类任务中引入不同的挑战。首先,大型社交网络不是静态的。因此,必须动态更新分类器中的功能才能应对这一挑战。第二,大型社交网络中的节点连接在一起。这些链接包含分类器需要分析和使用的语义。最后,大型社交网络中的节点是异构和嘈杂的(它们可能属于不同的社区用于不同的目的),因此并不是全部都与分类器的训练数据相关。 分类方案:在传统的单一数据关系专用分类方法中,对象根据描述的对象进行分类。然而,当在大型社交网络中进行分类时,我们必须考虑网络的链路结构。基于链接的分类不仅基于其属性,而且基于其链接以及链接对象的属性来预测对象的类别。以网页分类为例。它基于词出现和锚文本来预测网页的类别,两者都用作属性。此外,分类是基于页面和页面和链接的其他属性之间的链接。这使我们深入了解引文数据的分类。社交网络中的分类包括两个方案:分类对象(节点)和分类链接(边)。在引用领域,对高度评价的论文进行分类被认为是对象的分类。具体来说,论文(即节点)具有自己的属性,如作者,主题,关键字,抽象和全文。此外,它还通过引用与其他论文相关联。为了对特定主题的高度评价的论文进行建模,我们可以首先选择所有关于此主题的论文,形成整个网络的子图。然后,我们可以对该子网上的一般社交网络(如PageRank,HITS等)应用任何对象排名/分类方法,以获得高度评价的论文。请注意,如果培训数据不可用,我们可以依靠PageRank和HITS。如果我们有培训数训练据,我们构建的分类器也可以适应对象属性,如内容和作者。

  4. 垃圾邮件分类可以被认为是文本分类问题或半监督学习问题。我们分析这两种情况。在第一种情况下,数据挖掘系统将从标记的电子邮件消息中提取特征,并使用特征训练分类器。这些特征不仅可以包含内容特征(例如,关键词,部分语音标签等)和文本模式(例如,频繁的顺序模式,短语),还包含来自其他属性(诸如作者,主题,线程ID)的特征,和时间戳。然后可以对这些特征进行分类器(例如,支持向量机,决策树,神经网络)的训练。所得到的分类器可用于对先前未看到的电子邮件进行分类。在另一种情况下,我们假设我们只有一小部分标签的电子邮件。半监督学习方法用于标记未标记或新的电子邮件。一种方法是设计生成模型(混合模型),并使用EM算法使用与标记的电子邮件消息相同的约束来估计模型参数。估计的模型可以用于进一步提供以前看不见的电子邮件的标签。另一个策略是建立电子邮件的连接网络表示,并将类标签从小型培训数据传播到大多数未标记的电子邮件。

  5. 对于数据挖掘,有许多数据挖掘应用可以使用的一般原理和算法。还有一些具体的算法旨在解决特定的实际问题,如搜索生物序列模式。即使对于一般原则,由于不同的数据特征和不同的开采类型,通常需要更具体的开发。 因此,研究和发展应该有两条轨道。一个是开发与领域无关的数据挖掘方法和系统,而另一个是开发面向领域的数据挖掘解决方案。 预计这两个都有很好的应用。由于数据和挖掘请求的多样性,将来可能会生成许多依赖域的数据挖掘系统。然而,这种系统的许多功能可能共享一些核心原理和方法。生物信息学文本挖掘网络和多媒体数据挖掘以及挖掘时空数据库的数据挖掘也是有趣的研究领域。例如,生物信息学提出了许多有趣和具有挑战性的问题,包括基因和蛋白质序列的分析,生物网络的分析等。采集生物数据需要处理数据和模式中的噪声和不准确性,而且发现的模式通常是大而复杂的。 挖掘这些数据集可能需要多年的研究,才能实现显着的进步,从而产生有价值的应用。

本文由 Tony 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

赏个馒头吧