数据挖掘十大算法

《数据挖掘十大算法》由会员分享，可在线阅读，更多相关《数据挖掘十大算法（3页珍藏版）》请在装配图网上搜索。

1、数据挖掘十大算法数据挖掘十大算法 K 近邻算法k -近邻算法是基于实例的学习方法中最基本的，先介绍基于实例学习的相关概 念。一、基于实例的学习。 1 、已知一系列的训练样例，很多学习方法为目标函数 建 立起明确的一般化描述；但与此不同，基于实例的学习方法只是简单地把训练样 例存储 起来。从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个 新的 查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给 新实例。 2 、基于实例的方法可以为不同的待分类查询实例建立不同的目 标函数逼 近。事实上，很多技术只建立目标函数的局部逼近，将其应用于与新查询实例邻近的实

2、例，而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂，但它可用不 太复杂的局部逼近描述时，这样做有显著的优势。3、基于实例方法的不足：(1)分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类 时，而不 是在第一次遇到训练样例时。所以，如何有效地索引训练样例，以减少查询时所需计算 是一个重要的实践问题。 (2 )当从存储器中检索相似的训练样例 时，它们一般考虑实 例的所有属性。如果目标概念仅依赖于很多属性中的几个时， 那么真正最“相似”的实 例之间很可能相距甚远。二、k-近邻法基于实例的学习方法中最基本的是k -近邻算法。这个算法假定所 有的实例对应于 n 维欧氏空间 ?n

3、 中的点。一个实例的最近邻是根据标准欧氏 距离定义 的。更精确地讲，把任意的实例 x 表示为下面的特征向量： 其中 a r(x )表示实例x的第r个属性值。那么两个实例x i和x j间的距离定义为d (x i ,x j ) ，其中：说明：1、在最近邻学习中，目标函数值可以为离散值也可以为实值。2、我们先考虑学习以下形式的离散目标函数。其中 V 是有限集合v 1，. v s 。下表给出了逼近离散目标函数的 k- 近邻算法。 3、正如下表中 所 指出的，这个算法的返回值f (x q )为对f (x q )的估计，它就是距离x q最近的k个 训练样例中最普遍的f值。4、如果我们选择k =1，那么“1

4、 -近邻算法”就把f (x i )赋给(x q )，其中x i是最靠近x q的训练实例。对于较大的k值，这个算法返回前k个最靠 近的训练实例中最普遍的 f 值。逼近离散值函数f : ?n_Vk的-近邻算法下图图解了一种简单情况下的 k - 近邻算法，在这里实例是二维空间中的点， 目标 函数具有布尔值。正反训练样例用“-”+分”别和表“示。图中也画出了一个查询点 x q 。注意在这幅图中， 1- 近邻算法把 x q 分类为正例，然而 5- 近邻算 法 把 x q 分类为反例。图解说明：左图画出了一系列的正反训练样例和一个要分类的查询实例 x q 。 1-近邻算法把 x q 分类为正例，然而 5-

5、近邻算法把 x q 分类为反例。右图是对于一个典型的训练样例集合 1- 近邻算法导致的决策面。围绕每个训 练样 例的凸多边形表示最靠近这个点的实例空间(即这个空间中的实例会被 1-近 邻算法赋予 该训练样例所属的分类)。对前面的 k - 近邻算法作简单的修改后，它就可被用于逼近连续值的目标函 数。为 了实现这一点，我们让算法计算 k 个最接近样例的平均值，而不是计算其中的 最普 遍的值。更精确地讲，为了逼近一个实值目标函数，我们只要把算法中的公式 替换为：三、距离加权最近邻算法对k -近邻算法的一个显而易见的改进是对k个近 邻的贡献加权，根据它们相对查询点x q 的距离，将较大的权值赋给较近的

6、近邻。 例如，在上表逼近离散目标函 数的 算法中，我们可以根据每个近邻与 xq 的距离平方的倒数加权这个近邻的“选举权”。方法是通过用下式取代上表算法中的公式来实现： 其中为了处理查询点 x q 恰好匹配某个训练样例 x i ，从而导致分母为 0的情况， 我 们令这种情况下的 f (xq ) 等于 f (x i ) 。如果有多个这样的训练样例，我们使用 它们中 占多数的分类。我们也可以用类似的方式对实值目标函数进行距离加权，只要用下式替换上表 的公 式：其中 w i 的定义与之前公式中相同。 注意这个公式中的分母是一个常 量，它 将不同权值的贡献归一化(例如，它保证如果对所有的训练样例 x i

7、 ， f (xi )=c ，那么 (x q )-c )。 注意以上 k- 近邻算法的所有变体都只考虑 k 个近邻以分类查询点。如果使用按距离加权，那么允许所有的训练样例影响xq的分类事实上没有坏处，因为非常远的实例对 (x q )的影响很小。考虑所有样例的惟一不足是 会使 分类运行得更慢。如果分类一个新的查询实例时考虑所有的训练样例，我们称 此为全局 (global )法。如果仅考虑最靠近的训练样例，我们称此为局部(local)法。四、对 k - 近邻算法的说明按距离加权的 k - 近邻算法是一种非常有效的归纳推理方法。它对训练数据中的噪 声有很好的鲁棒性，而且当给定足够大的训练集合时它也非常

8、有效。注意通过取k个近 邻的加权平均，可以消除孤立的噪声样例的影响。1、问题一：近邻间的距离会被大量的不相关属性所支配。应用 k - 近邻算法的一个实践问题是，实例间的距离是根据实例的所有属性 (也就 是包含实例的欧氏空间的所有坐标轴)计算的。这与那些只选择全部实例属 性的一个子 集的方法不同，例如决策树学习系统。 比如，这样一个问题：每个实 例由 20 个属性 描述，但在这些属性中仅有 2 个与它的分类是有关。在这种情况 下，这两个相关属性 的值一致的实例可能在这个 20 维的实例空间中相距很远。结 果，依赖这 20 个属性的 相似性度量会误导 k -近邻算法的分类。近邻间的距离会 被大量的

9、不相关属性所支配。 这种由于存在很多不相关属性所导致的难题，有时被 称为维度灾难( curse of dimensionality )。最近邻方法对这个问题特别敏感。2、解决方法：当计算两个实例间的距离时对每个属性加权。 这相当于按比例缩 放欧氏空间中的坐标轴，缩短对应于不太相关属性的坐标轴，拉长对应于更相关的属性的坐标轴。每个坐标轴应伸展的数量可以通过交叉验 证的 方法自动决定。3、问题二：应用 k - 近邻算法的另外一个实践问题是如何建立高效的索引。因为 这个算法推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可 能需要大 量的计算。4、解决方法：目前已经开发了很多方法用来对存储的训练样例进行索引，以 便 在增加一定存储开销情况下更高效地确定最近邻。一种索引方法是 kd -tree (Bentley 1975 ；Friedman et al. 1977 )，它把实例存储在树的叶结点内，邻近 的实例存储在同 一个或附近的结点内。通过测试新查询 x q 的选定属性，树的内部 结点把查询 x q 排列 到相关的叶结点。