聚类分析2

聚类分析主要内容基于密度的聚类模糊C均值聚类基于密度的聚类DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)含噪声的基于密度的空间聚类的应用，基于中心的方法。在基于中心的方法中，数据集中特定点的密度通过对该点Eps半径之内的点计数（包括点本身）来估计。点的密度取决于指定的半径。(扫描半径(Eps)和最小包含点数(MinPts))图1基于中心的密度图2核心点、边界点和噪声点根据基于中心的密度进行点分类核心点(corepoint)点在基于密度的簇内部（稠密区域的内部）。如果该点的给定邻域内的点的个数超过给定的阈值MinPts，则该点是核心点。点的邻域由距离函数和用户指定的距离参数Eps决定。边界点(borderpoint)稠密区域边缘上的点。边界点不是核心点，但它落在某个核心点的邻域内。边界点有可能落在多个核心点的邻域内。噪声点(noisepoint)稀疏区域中的点。噪声点既非是核心点也非边界点的任何点。基于密度的聚类DBSCAN算法将所有点标记为核心点、边界点和噪声点删除噪声点为距离在Eps之内的所有核心点之间赋予一条边每组连通的核心点形成一个簇将每个边界点指派到一个与之关联的核心点的簇中非正式的描述：任意两个足够靠近（相互之间的距离在Eps之内）的核心点将放在同一个簇中。同样，任何与核心点足够靠近的边界点也放到与核心点相同的簇中。（如果一个边界点靠近不同簇的核心点，则可能需要解决平局问题。）噪声点被丢弃。基于密度的聚类优点能够处理任意形状和大小的簇缺点当簇的密度变化很大的时候高维数据密度定义困难当邻近计算需要计算所有的点对邻近度时（对于高维数据，常常如此），DBSCAN的开销可能是很大的基于密度的聚类噪声噪声簇C簇D簇A图中包含4个埋藏在噪声中的簇。簇的密度由它们的明暗度指出。较密的两个簇A和B周围的噪声的密度和簇C和D的密度相同。如果Eps阈值足够低，可以发现簇C和D，则A、B和包围它们的点将变成单个簇。若Eps阈值足够高，可以发现簇A和B，并且包围他们的点标记为噪声，那么C、D和包围它们的点将被标记为噪声。基于密度的聚类簇B选择DBSCAN的参数基本方法是观察点到它的K个最邻近的距离（称为k-距离）的特性。对于属于某个簇的点，如果K不大于簇的大小的话，则k-距离将很小。对于不在簇中的点，K-聚类将相对很大。如果我们对于某个K，计算所有点的k-距离，以递增次序将他们排序，然后绘制排序后的值，则我们会看到k-距离的急剧变化，对应于合适的Eps值。如果我们选取该距离为Eps参数，而取Ｋ的值为MinPts参数，则k-距离小于Eps的点将被标记为核心点，而其他点被标记为噪声点或者边界点。基于密度的聚类模糊C均值聚类K均值聚类，簇中任何对象距离定义该簇的原型比离定义其他簇的原型更近，它使用簇中对象的质心作为簇的原型。模糊集合：模糊聚类技术基于模糊集合论。模糊集合论和模糊逻辑论作为一种处理不精确和不确定性的方法。模糊集合论允许对象以0和1之间的某个隶属度属于一个集合，而模糊逻辑论允许一个陈述以0和1之间的确定度为真。传统的集合论和逻辑论是对应的模糊集合论和逻辑论的特殊情况。它们限制集合的隶属度或者确定度或者为0，或者为1。基本的模糊C均值算法X={x1,x2,…,xm},xi={xi1,xi2,…，xin},C1,C2,…，Ck（1）选择一个初始模糊伪划分，即对所有的wij赋值（2）repeat使用模糊伪划分，计算每个簇的质心重新计算模糊伪划分，即wij(权值wij指明xi在簇Cj中的隶属度)until质心不发生变化（替换的终止条件是“如果误差的变化低于指定的阈值”或者“如果所有wij的变化的绝对值都低于指定的阈值”）模糊C均值聚类11kijjw以下合理的条件施加在簇上以确保簇形成模糊伪划分（fuzzypsuedo-partition）(1)给定点xi的所有权值之和为1：10mijiwm(2)每个簇Cj以非零权值至少包含一个点，但不以权值1包含所有的点：模糊C均值聚类目标函数：误差的平方和SSE(sumoftheSquaredError)计算每个数据点的误差，即它到最近质心的欧几里得距离，然后计算误差的平方和。模糊C均值聚类21(,)imiixCSSEdistcxdist是欧几里得空间中两个对象之间的标准欧几里得距离：2(,)()ijijdistxcxc21211(,,)(,)kmpkijijjiSSECCwdistxc…,C误差平方和（SSE）的定义修改为：Ｃj是第j个簇的质心。Ｐ是确定权值影响的指数。在１和正无穷大之间（模糊因子）。模糊C均值聚类计算质心：wij为0或为1时，该定义退化为传统的质心定义。随着ｐ增大，所有的簇质心都趋向于所有数据点的全局质心。换言之，划分会变得越来越模糊。11/mmppjijiijiicwxw模糊C均值聚类更新模糊伪划分模糊C均值聚类1122111(1/(,))/(1/(,))kppijijiqqwdistxcdistxcp=2，公式简化为：221(1/(,))/(1/(,))kijijiqqwdistxcdistxc点在簇中的隶属权值是点与簇质心距离平方的倒数，除以该点所有隶属权值之和。除以分母加以规范化，否则一个点的隶属权值之和不等于1。如果p2，则该指数降低赋予离点最近的簇的权值。随着P趋向于无穷大，该指数趋向于0，而权值趋向于1/k。随着p趋向于1，该指数加大赋予离点最近的簇的权值。随着p趋向于1，关于最近簇的隶属簇的隶属权值趋向于1，而关于其他簇的隶属权值趋向于0，这对应于K均值。优点和缺点产生指示任意点属于任意簇的程度的聚类。其他与K均值同，尽管他的计算密集程度更高一些。模糊C均值聚类