- 浏览: 73877 次
最新评论
层次聚类算法:
前面介绍的 K-means 算法和 K 中心点算法都属于划分式( partitional )聚类算法。层次聚类算法是将所有的样本点自底向上合并组成一棵树或者自顶向下分裂成一棵树的过程,这两种方式分别称为凝聚和分裂。
凝聚层次算法 :
初始阶段,将每个样本点分别当做其类簇,然后合并这些原子类簇直至达到预期的类簇数或者其他终止条件。
分裂层次算法 :
初始阶段,将所有的样本点当做同一类簇,然后分裂这个大类簇直至达到预期的类簇数或者其他终止条件。
两种算法的代表:
传统的凝聚层次聚类算法有 AGENES ,初始时, AGENES 将每个样本点自为一簇,然后这些簇根据某种准则逐渐合并,例如,如果簇 C1 中的一个样本点和簇 C2 中的一个样本点之间的距离是所有不同类簇的样本点间欧几里得距离最近的,则认为簇 C1 和簇 C2 是相似可合并的。
传统的分裂层次聚类算法有 DIANA ,初始时 DIANA 将所有样本点归为同一类簇,然后根据某种准则进行逐渐分裂,例如类簇 C 中两个样本点 A 和 B 之间的距离是类簇 C 中所有样本点间距离最远的一对,那么样本点 A 和 B 将分裂成两个簇 C1 和 C2 ,并且先前类簇 C 中其他样本点根据与 A 和 B 之间的距离,分别纳入到簇 C1 和 C2 中 , 例如,类簇 C 中样本点 O 与样本点 A 的欧几里得距离为 2 ,与样本点 B 的欧几里得距离为 4 ,因为 Distance(A , O)<Distance(B,O) 那么 O 将纳入到类簇 C1 中。
如图所示:
算法: AGENES 。传统凝聚层次聚类算法
输入: K :目标类簇数 D :样本点集合
输出: K 个类簇集合
方法: 1) 将 D 中每个样本点当做其类簇;
2) repeat
3) 找到分属两个不同类簇,且距离最近的样本点对;
4) 将两个类簇合并;
5) util 类簇数 =K
算法: DIANA 。传统分裂层次聚类算法
输入: K :目标类簇数 D :样本点集合
输出: K 个类簇集合
方法: 1) 将 D 中所有样本点归并成类簇;
2) repeat
3) 在同类簇中找到距离最远的样本点对;
4) 以该样本点对为代表,将原类簇中的样本点重新分属到新类簇
5) util 类簇数 =K
缺点:
传统的层次聚类算法的效率比较低 O(tn2 ) t: 迭代次数 n: 样本点数,最明显的一个缺点是不具有再分配能力,即如果样本点 A 在某次迭代过程中已经划分给类簇 C1 ,那么在后面的迭代过程中 A 将永远属于类簇 C1 ,这将影响聚类结果的准确性。
改进:
一般情况下,层次聚类通常和划分式聚类算法组合,这样既可以解决算法效率的问题,又能解决样本点再分配的问题,在后面将介绍 BIRCH 算法。首先把邻近样本点划分到微簇 (microcluseters) 中,然后对这些微簇使用 K-means 算法。
----------------贴上本人实现的AGENES算法,大家有兴趣可以把DIANA算法自己实现下-------------- -
package com.agenes;
public class DataPoint {
String
dataPointName; // 样本点名
Cluster
cluster; // 样本点所属类簇
private
double dimensioin[]; // 样本点的维度
public
DataPoint(){
}
public
DataPoint(double[] dimensioin,String dataPointName){
this.dataPointName=dataPointName;
this.dimensioin=dimensioin;
}
public
double[] getDimensioin() {
return
dimensioin;
}
public void
setDimensioin(double[] dimensioin) {
this.dimensioin = dimensioin;
}
public
Cluster getCluster() {
return
cluster;
}
public void
setCluster(Cluster cluster) {
this.cluster
= cluster;
}
public
String getDataPointName() {
return
dataPointName;
}
public void
setDataPointName(String dataPointName) {
this.dataPointName = dataPointName;
}
}
package com.agenes;
import java.util.ArrayList;
import java.util.List;
public class Cluster {
private
List<DataPoint> dataPoints = new
ArrayList<DataPoint>(); //
类簇中的样本点
private
String clusterName;
public
List<DataPoint> getDataPoints()
{
return
dataPoints;
}
public void
setDataPoints(List<DataPoint>
dataPoints) {
this.dataPoints = dataPoints;
}
public
String getClusterName() {
return
clusterName;
}
public void
setClusterName(String clusterName) {
this.clusterName = clusterName;
}
}
package com.agenes;
import java.util.ArrayList;
import java.util.List;
public class ClusterAnalysis {
public
List<Cluster>
startAnalysis(List<DataPoint>
dataPoints,int ClusterNum){
List<Cluster> finalClusters=new
ArrayList<Cluster>();
List<Cluster>
originalClusters=initialCluster(dataPoints);
finalClusters=originalClusters;
while(finalClusters.size()>ClusterNum){
double min=Double.MAX_VALUE;
int mergeIndexA=0;
int mergeIndexB=0;
for(int
i=0;i<finalClusters.size();i++){
for(int
j=0;j<finalClusters.size();j++){
if(i!=j){
Cluster clusterA=finalClusters.get(i);
Cluster clusterB=finalClusters.get(j);
List<DataPoint>
dataPointsA=clusterA.getDataPoints();
List<DataPoint>
dataPointsB=clusterB.getDataPoints();
for(int m=0;m<dataPointsA.size();m++){
for(int
n=0;n<dataPointsB.size();n++){
double
tempDis=getDistance(dataPointsA.get(m),dataPointsB.get(n));
if(tempDis<min){
min=tempDis;
mergeIndexA=i;
mergeIndexB=j;
}
}
}
}
} //end for j
}// end for i
//合并cluster[mergeIndexA]和cluster[mergeIndexB]
finalClusters=mergeCluster(finalClusters,mergeIndexA,mergeIndexB);
}//end while
return finalClusters;
}
private
List<Cluster>
mergeCluster(List<Cluster>
clusters,int mergeIndexA,int mergeIndexB){
if
(mergeIndexA != mergeIndexB) {
//
将cluster[mergeIndexB]中的DataPoint加入到 cluster[mergeIndexA]
Cluster
clusterA = clusters.get(mergeIndexA);
Cluster
clusterB = clusters.get(mergeIndexB);
List<DataPoint> dpA =
clusterA.getDataPoints();
List<DataPoint> dpB =
clusterB.getDataPoints();
for
(DataPoint dp : dpB) {
DataPoint
tempDp = new DataPoint();
tempDp.setDataPointName(dp.getDataPointName());
tempDp.setDimensioin(dp.getDimensioin());
tempDp.setCluster(clusterA);
dpA.add(tempDp);
}
clusterA.setDataPoints(dpA);
//
List<Cluster>
clusters中移除cluster[mergeIndexB]
clusters.remove(mergeIndexB);
}
return
clusters;
}
// 初始化类簇
private
List<Cluster>
initialCluster(List<DataPoint>
dataPoints){
List<Cluster> originalClusters=new
ArrayList<Cluster>();
for(int
i=0;i<dataPoints.size();i++){
DataPoint
tempDataPoint=dataPoints.get(i);
List<DataPoint> tempDataPoints=new
ArrayList<DataPoint>();
tempDataPoints.add(tempDataPoint);
Cluster tempCluster=new Cluster();
tempCluster.setClusterName("Cluster "+String.valueOf(i));
tempCluster.setDataPoints(tempDataPoints);
tempDataPoint.setCluster(tempCluster);
originalClusters.add(tempCluster);
}
return originalClusters;
}
//计算两个样本点之间的欧几里得距离
private double
getDistance(DataPoint dpA,DataPoint dpB){
double
distance=0;
double[]
dimA = dpA.getDimensioin();
double[]
dimB = dpB.getDimensioin();
if
(dimA.length == dimB.length) {
for (int i =
0; i < dimA.length; i++) {
double temp=Math.pow((dimA[i]-dimB[i]),2);
distance=distance+temp;
}
distance=Math.pow(distance, 0.5);
}
return distance;
}
public static void
main(String[] args){
ArrayList<DataPoint> dpoints = new
ArrayList<DataPoint>();
double[] a={2,3};
double[] b={2,4};
double[] c={1,4};
double[] d={1,3};
double[] e={2,2};
double[] f={3,2};
double[] g={8,7};
double[] h={8,6};
double[] i={7,7};
double[] j={7,6};
double[] k={8,5};
//
double[] l={100,2};//孤立点
double[] m={8,20};
double[] n={8,19};
double[] o={7,18};
double[] p={7,17};
double[] q={8,20};
dpoints.add(new DataPoint(a,"a"));
dpoints.add(new DataPoint(b,"b"));
dpoints.add(new DataPoint(c,"c"));
dpoints.add(new DataPoint(d,"d"));
dpoints.add(new DataPoint(e,"e"));
dpoints.add(new DataPoint(f,"f"));
dpoints.add(new DataPoint(g,"g"));
dpoints.add(new DataPoint(h,"h"));
dpoints.add(new DataPoint(i,"i"));
dpoints.add(new DataPoint(j,"j"));
dpoints.add(new DataPoint(k,"k"));
//
dataPoints.add(new DataPoint(l,"l"));
dpoints.add(new DataPoint(m,"m"));
dpoints.add(new DataPoint(n,"n"));
dpoints.add(new DataPoint(o,"o"));
dpoints.add(new DataPoint(p,"p"));
dpoints.add(new DataPoint(q,"q"));
int clusterNum=3; //类簇数
ClusterAnalysis ca=new ClusterAnalysis();
List<Cluster>
clusters=ca.startAnalysis(dpoints, clusterNum);
for(Cluster cl:clusters){
System.out.println("------"+cl.getClusterName()+"------");
List<DataPoint>
tempDps=cl.getDataPoints();
for(DataPoint
tempdp:tempDps){
System.out.println(tempdp.getDataPointName());
}
}
}
}
发表评论
-
话题监测与发现之热点新闻发现技术
2013-01-25 09:51 3706最近在帮朋友做一 ... -
【转载】推荐几个数据分析网站
2013-01-04 09:45 1275From http://blog.sina.com.cn/ ... -
数据挖掘只言片语
2013-01-04 09:44 1911写了好几篇关于数据挖掘算法的帖子,都属于技术上的细节贴。这篇文 ... -
【转载】如何预测用户query意图
2013-01-03 17:57 1350From http://www.searchtb.com/20 ... -
关联规则(二)强关联规则一定就是用户感兴趣的规则吗
2012-12-28 08:58 2413关联规则算法 Apriori 表明 , 当蕴含式 A ... -
关联规则(一)Apriori算法
2012-12-28 08:58 78041. 挖掘关联规 ... -
聚类分析(七)离群点分析
2012-12-28 08:57 4983一、 ... -
聚类分析(六)基于密度的聚类算法 — OPTICS
2012-12-28 08:57 15861 什么是 OPTICS 算法 在前面介绍的 ... -
数据分布倾斜性风险浅析
2012-12-28 08:56 944数据分布倾斜性指的是数据分布过度集中于数据空间的某端, ... -
聚类分析(五)基于密度的聚类算法 — DBSCAN
2012-12-27 15:35 6003一 什么是基于密度的聚类算法 由于层次聚类算法和划分式 ... -
聚类分析(三) K中心点算法(k-mediods)
2012-12-27 15:28 4994K 中心点算法( K-medoids ) ... -
聚类分析(二) K-MEANS
2012-12-27 15:24 2107K-means 算法 一般情况,聚类算法可以划分为 ... -
聚类分析(一) 什么是聚类分析
2012-12-27 15:22 1897将一群物理对 ...
相关推荐
本文实例讲述了Python实现的KMeans聚类算法。分享给大家供大家参考,具体如下: 菜鸟一枚,编程初学者,最近想使用Python3实现几个简单的机器学习分析方法,记录一下自己的学习过程。 关于KMeans算法本身就不做介绍...
主要介绍了Python聚类算法之凝聚层次聚类的原理与具体使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
了一个基于重叠度的层次聚类算法(CCSLM),该算法基于重叠度的衡量,而且不需要预先指定聚类数, 能够很好地解决以上两个问题.算法根据每两簇之间的重叠情况自动运行或停止,从而准确划分簇间 重叠的数据,并自动...
无监督学习-kmeans聚类算法及手动实现jupyter代码.ipynb
这个是一个简单的聚类分析matlab代码实现,通过matlab对数据进行了简单的层次聚类分析
针对点云数据进行Mean shift聚类,可以通过调整聚类算法的阈值以及搜索半径,来达到不同的聚类效果,内附有示例,运行test.m即可。
层次聚类算法java数据挖掘算法源码 数据挖掘算法是根据数据创建数据挖掘模型的一组试探法和计算。 为了创建模型,算法将首先分析您提供的数据,并查找特定类型的模式和趋势。概念描述算法使用此分析的结果来定义用于...
聚类分析原理 聚类分析常用算法分类 划分聚类方法 层次聚类方法 基于密度的聚类方法 基于网格的聚类方法 基于模型的聚类方法 高维数据的聚类方法 模糊聚类FCM 应用实例分析
主要为大家详细介绍了Python实现简单层次聚类算法以及可视化,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
一般而言,能将无标签的样本点聚为若干个簇的算法都可以称为聚类算法,人们常根据这些算法的基本思想或基本假设将其分为几个常见的类型:分割聚类法、层次聚类法、密度聚类法、网格聚类法、模型聚类法等。
层次聚类分析算法研究.doc
随着煤炭系统中收集的煤炭数据数量的增多,层次聚类算法由于需要计算大量的相似性矩阵需要大量的内存,原有的层次聚类算法不能有效地处理海量规模数据。文章针对煤炭数据中生成的大规模数据,提出基于云计算平台的...
用R语言实现多种聚类方法,包括k-means聚类,pamk聚类,层次聚类,基于密度的dbscan算法的聚类。
层次聚类的matlab程序,数据来源为80个平面点坐标。
Birch聚类算法分析与改进,杨阳,黄炳洁,Birch算法是典型的层次聚类算法,适用于大规模数据集的处理,本文分析了Birch算法的具体实现过程,着重对其核心CF和CF Tree作了讨论,��
详细介绍聚类分析的一些基本概念和主要的方法,并给出了一些示例进行分析。包括k-均值算法、BIRCH算法、Chameleon算法、概率层次聚类、距离度量等。适合教学和复习使用。
然后定义了新的个体间不可区分度、 类间不可区分度、聚类结果的综合近似精度等概念,提出了新的混合数据类型层次聚类算法。该算法不仅能处 理数值型数据,而且能处理大多数聚类算法不能处理的字符型数据和混合型数据...
k均值、合并聚类和DBSCAN聚类算法对鸢尾花数据集聚类代码.zip
分析在有效 性、快速性等性能指标方面,与模糊 C 均值聚类算法、基于遗传的模糊 C-均值聚类算法相 比,模拟退火算法与遗传算法相结合后用于模糊 C-均值聚类的算法所带来的优越性。 3、理解混合粒子群算法(基于自然...
基于matlab软件设计的层次聚类算法,进行数据的聚类分析