数据仓库与数据挖掘整理.docx

K_Means初始点选取KMeans算法本身思想比较简单，但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。? 1. 确定K个初始类簇中心点? 最简单的确定初始类簇中心点的方法是随机选择K个点作为初始的类簇中心点，但是该方法在有些情况下的效果较差，如下(下图中的数据是用五个二元正态高斯分布生成的，颜色代表聚类效果)：? 《大数据》一书中提到K个初始类簇点的选取还有两种方法：1)选择彼此距离尽可能远的K个点 2)先对数据用层次聚类算法或者Canopy算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。? 1) 选择批次距离尽可能远的K个点? 首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点。? 该方法经过我测试效果很好，用该方法确定初始类簇点之后运行KMeans得到的结果全部都能完美区分五个类簇：? 2) 选用层次聚类或者Canopy算法进行初始聚类，然后利用这些类簇的中心点作为KMeans算法初始类簇中心点。? 常用的层次聚类算法有BIRCH和ROCK，在此不作介绍，下面简单介绍一下Canopy算法，主要摘自Mahout的Wiki：? 首先定义两个距离T1和T2，T1>T2.从初始的点的集合S中随机移除一个点P，然后对于还在S中的每个点I，计算该点I与点P的距离，如果距离小于T1，则将点I加入到点P所代表的Canopy中，如果距离小于T2，则将点I从集合S中移除，并将点I加入到点P所代表的Canopy中。迭代完一次之后，重新从集合S中随机选择一个点作为新的点P，然后重复执行以上步骤。? Canopy算法执行完毕后会得到很多Canopy，可以认为每个Canopy都是一个Cluster，与KMeans等硬划分算法不同，Canopy的聚类结果中每个点有可能属于多个Canopy。我们可以选择距离每个Canopy的中心点最近的那个数据点，或者直接选择每个Canopy的中心点作为KMeans的初始K个类簇中心点。K-d tree总结一k-d树（k-dimensional树的简称），是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。应用背景　　SIFT算法中做特征点匹配的时候就会利用到k-d树。而特征点匹配实际上就是一个通过距离函数在高维矢量之间进行相似性检索的问题。针对如何快速而准确地找到查询点的近邻，现在提出了很多高维空间索引结构和近似查询的算法，k-d树就是其中一种。　　索引结构中相似性查询有两种基本的方式：一种是范围查询（range searches），另一种是K近邻查询（K-neighbor searches）。范围查询就是给定查询点和查询距离的阈值，从数据集中找出所有与查询点距离小于阈值的数据；K近邻查询是给定查询点及正整数K，从数据集中找到距离查询点最近的K个数据，当K=1时，就是最近邻查询（nearest neighbor searches）。　　特征匹配算子大致可以分为两类。一类是线性扫描法，即将数据集中的点与查询点逐一进行距离比较，也就是穷举，缺点很明显，就是没有利用数据集本身蕴含的任何结构信息，搜索效率较低，第二类是建立数据索引，然后再进行快速匹配。因为实际数据一般都会呈现出簇状的聚类形态，通过设计有效的索引结构可以大大加快检索的速度。索引树属于第二类，其基本思想就是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠，其代表就是k-d树；后者划分空间相互有交叠，其代表为R树。（这里只介绍k-d树）1.实例? ? ? ?先以一个简单直观的实例来介绍k-d树算法。假设有6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内（如图2中黑点所示）。k-d树算法就是要确定图2中这些分割空间的分割线（多维空间即为分割平面，一般为超平面）。下面就要通过一步步展示k-d树是如何确定这些分割线的。? ? ? ?k-d树算法可以分为两大部分，一部分是有关k-d树本身这种数据结构建立的算法，另一部分是在建立的k-d树上如何进行最邻近查找的算法。2.构造kd树? ? ? ? kd树是一种对k维空间中的实例点进行存储以便对其进行快速搜索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间进行切分，构成一系列的k维超矩形区域。kd树的每一个节点对应于一个k维超矩形区域。k-d树是一个二