湖北专业网站建设产品介绍,网站数据库连接不上的常见问题,公司网站改版设计,昆明网站建设在河科技1、基于划分的聚类算法
基于划分的聚类算法 主要通过聚类中心的迭代重置#xff0c;直到达到“簇内点足够近#xff0c;簇间点足够远”的目标效果#xff0c;完成样本集的最优化分。其算法优点是时间、空间复杂度低#xff0c;可以处理大规模数据集。缺点包括容易陷入局部…1、基于划分的聚类算法
基于划分的聚类算法 主要通过聚类中心的迭代重置直到达到“簇内点足够近簇间点足够远”的目标效果完成样本集的最优化分。其算法优点是时间、空间复杂度低可以处理大规模数据集。缺点包括容易陷入局部最优对初始聚类中心的选取十分敏感无法处理噪声和离群点不能解决非凸数据等。其代表算法包括K-means、CLARANS和 CLARA。以 K-means 为例算法流程为
步骤 1初始的类簇中心采用随机选择的方式选取一般人为设定为 K 个步骤 2对剩余对象计算其与选取的各类簇中心的距离将其分配给距离最近的簇步骤 3重新计算每个簇的平均值将其作为新的聚类中心步骤 4重复步骤 2 和 3直到聚类结果不再变化
2、基于密度的聚类算法
基于密度的聚类算法其算法原理是通过计算数据样本分布的疏密情况将高密度区域的点划分为同一个类簇。这种方式可以处理具有复杂形状的类簇和噪声数据。DBSCAN 算法是典型的基于密度的聚类算法能够有效识别任意形状的类簇。缺点是聚类的结果与参数有很大的关系对于稀疏度差异很大的数据集无法取得很好的聚类效果。其算法步骤为
步骤 1从数据集中任选一个对象 p步骤 2寻找对象 p 的直接密度可达的数据点步骤 3若对象 p 存在直接密度可达数据点则合并生成一个类簇若不存在将 p 作为一个边界点选取下一个对象步骤 4重复步骤 2 和 3直到所有点都被处理。
3、基于层次的聚类算法
基于层次的聚类算法无需预先设置类簇个数而是通过对数据集在不同层次上进行划分来获得树状聚类结构。一般分为两种类型合并的层次聚类和分裂的层次聚类。前者是一种自底向上的层次聚类算法从最底层开始每一次通过合并最相似的类簇来形成上一层次的类簇直到满足终止条件。后者则是采用自顶向下的方法从一个包含全部数据点的聚类开始然后把根节点分裂为一些子类簇每个子类簇再递归地分裂下去直到出现只包含一个数据点的类簇出现。这种算法的优点是处理速度很快仅与类簇个数有关与数据个数无关可以解决非球形簇的聚类。其缺点是算法具有明显的贪心特征一个数据点分配错误将会出现连带性错误。代表算法包括 BIRCH算法、CURE 算法和 CHAMELEON 算法等。以自底向上的层次聚类算法为例其算法步骤如下
步骤 1将每个对象看作一个类簇计算两两之间的相似性步骤 2将相似性最高的两个类簇进行合并成为一个新的类簇步骤 3重新计算新的类簇与所有类簇的相似性步骤 4重复步骤 2 和 3直到不再有可合并类簇或者类簇数满足预先设定值。
在第二步中使用到的相似性度量方法有很多算法常见的有如下 5 种方法其中 Ward 法与 Average Linkage 法比较常见
3.1 单连接算法SingleLinkage
对于类 和 选择这两个类之间的任意两个对象的最小距离作为他们合并的相似性度量方式如公式所示: 3.2 全连接算法CompleteLinkage
该算法是单连接算法的反面对于对于类 和 选取两个类中距离最远的任意两个负荷曲线对象作为两个类之间的距离度量方式如公式所示。然后选取类间距最小的类进行合并。 3.3 平均连接算法Average-linkage
该算法的计算量较大对于类和 求两个类之间所有对象两两之间的距离然后再计算平均值作为两个类的距离。然后选取所有类之间距离最小的两个进行合并具体如公式 3.4 Ward法
选择合并之后的类导致的类内离差平方和增加量最小的两个类进行合并。
3.5 质心连接CentroidLinkage
对于类类和 类之间的距离为聚类中心距离的平方作为距离度量 4、基于网格的聚类算法
基于网格的聚类算法利用多分辨率形式的网格结构将数据空间划分为一个个的网格单元并在网格单元上进行类簇划分。优点是处理速度快与数据对象个数无关。缺点是参数敏感无法处理不规则分布的数据处理精度也不高。这类算法通常与基于密度的聚类算法结合从而提高聚类准确度代表算法有 STING 算法、CLIQUE算]和 WAVE-CLUSTER 算法等。这些算法采用了不同的网格划分方法但其核心步骤差异不大如下所示。
步骤 1将数据空间划分为多个互不重叠的网格步骤 2对网格内数据进行统计步骤 3通过统计信息找到高密度网格单元步骤 4将相连的高密度网格单元合并为一个类簇步骤 5将低密度网格单元划分给距离最近的高密度网格单元所在类簇中。
5、基于模型的聚类算法
基于模型的聚类算法为每个类簇假设了一个模型然后利用一个判断机制寻找数据与给定模型的最佳拟合最后完成聚类。这一类算法主要包括基于概率的模型聚类和基于神经网络的模型聚类。基于概率的模型聚类主要采用了概率生成方法假定同一类簇中的数据按照同一种概率分布最常用的即为高斯混合模型Gaussian Mixture Models, GMM。基于神经网络的模型聚类最常见的是 SOM 模型其可以保持原始数据的拓扑特征把相似的数据分配到同一类。这类算法的优点是其对数据点所属类簇的划分以概率的形式表现每一类的特征也可用参数表达。缺点是处理效率不高特别是数据量很少时聚类效果很差。以 SOM 模型为例其算法流程如下
步骤 1先将网络初始化给输出层的每个节点权重赋值步骤 2从输入样本中随机选择一个输入向量找到与该输入向量距离最小的权重向量步骤 3定义获胜单元在获胜单元的领域内调整权重使其向输入向量靠近步骤 4提供新样本再次进行训练步骤 5使邻域半径收缩降低学习率重复步骤 2-4直到满足输出条件得到聚类结果。
