|
terList);
} else {
clusterList.remove(cluster);
remainClusters = clusterList;
resultClusters.add(cluster);
}
return remainClusters;
}
/**
* 将2个簇进行边的连接
*
* @param c1
* 聚簇1
* @param c2
* 聚簇2
*/
private void connectClusterToCluster(Cluster c1, Cluster c2) {
ArrayList connectedEdges;
connectedEdges = c1.calNearestEdge(c2, 2);
for (int[] array : connectedEdges) {
edges[array[0]][array[1]] = 1;
edges[array[1]][array[0]] = 1;
}
}
/**
* 算法第一阶段形成局部的连通图
*/
private void connectedGraph() {
double distance = 0;
Point p1;
Point p2;
// 初始化权重矩阵和连接矩阵
weights = new double[pointNum][pointNum];
edges = new int[pointNum][pointNum];
for (int i = 0; i < pointNum; i++) {
for (int j = 0; j < pointNum; j++) {
p1 = totalPoints.get(i);
p2 = totalPoints.get(j);
distance = p1.ouDistance(p2);
if (distance == 0) {
// 如果点为自身的话，则权重设置为0
weights[i][j] = 0;
} else {
// 边的权重采用的值为距离的倒数,距离越近，权重越大
weights[i][j] = 1.0 / distance;
}
}
}
double[] tempWeight;
int[] ids;
int id1 = 0;
int id2 = 0;
// 对每个id坐标点，取其权重前k个最大的点进行相连
for (int i = 0; i < pointNum; i++) {
tempWeight = weights[i];
// 进行排序
ids = sortWeightArray(tempWeight);
// 取出前k个权重最大的边进行连接
for (int j = 0; j < ids.length; j++) {
if (j < k) {
id1 = i;
id2 = ids[j];
edges[id1][id2] = 1;
edges[id2][id1] = 1;
}
}
}
}
/**
* 权重的冒泡算法排序
*
* @param array
* 待排序数组
*/
private int[] sortWeightArray(double[] array) {
double[] copyArray = array.clone();
int[] ids = null;
int k = 0;
double maxWeight = -1;
ids = new int[pointNum];
for (int i = 0; i < pointNum; i++) {
maxWeight = -1;
for (int j = 0; j < copyArray.length; j++) {
if (copyArray[j] > maxWeight) {
maxWeight = copyArray[j];
k = j;
}
}
ids[i] = k;
// 将当前找到的最大的值重置为-1代表已经找到过了
copyArray[k] = -1;
}
return ids;
}
/**
* 根据边的连通性去深度优先搜索所有的小聚簇
*/
private void searchSmallCluster() {
int currentId = 0;
Point p;
Cluster cluster;
initClusters = new ArrayList<>();
ArrayList pointList = null;
// 以id的方式逐个去dfs搜索
for (int i = 0; i < pointNum; i++) {
p = totalPoints.get(i);
if (p.isVisited) {
continue;
}
pointList = new ArrayList<>();
pointList.add(p);
recusiveDfsSearch(p, -1, pointList);
cluster = new Cluster(currentId, pointList);
initClusters.add(cluster);
currentId++;
}
}
/**
* 深度优先的方式找到边所连接着的所有坐标点
*
* @param p
* 当前搜索的起点
* @param lastId
* 此点的父坐标点
* @param pList
* 坐标点列表
*/
private void recusiveDfsSearch(Point p, int parentId, ArrayList pList) {
int id1 = 0;
int id2 = 0;
Point newPoint;
if (p.isVisited) {
return;
}
p.isVisited = true;
for (int j = 0; j < pointNum; j++) {
id1 = p.id;
id2 = j;
if (edges[id1][id2] == 1 && id2 != parentId) {
newPoint = totalPoints.get(j);
pList.add(newPoint);
// 以此点为起点，继续递归搜索
recusiveDfsSearch(newPoint, id1, pList);
}
}
}
/**
* 计算连接2个簇的边的权重
*
* @param c1
* 聚簇1
* @param c2
* 聚簇2
* @return
*/
private double calEC(Cluster c1, Cluster c2) {
double resultEC = 0;
ArrayList connectedEdges = null;
connectedEdges = c1.calNearestEdge(c2, 2);
// 计算连接2部分的边的权重和
for (int[] array : connectedEdges) {
resultEC += weights[array[0]][array[1]];
}
return resultEC;
}
/**
* 计算2个簇的相对互连性
*
* @param c1
* @param c2
* @return
*/
private double calRI(Cluster c1, Cluster c2) {
double RI = 0;
double EC1 = 0;
double EC2 = 0;
double EC1To2 = 0;
EC1 = c1.calEC();
EC2 = c2.calEC();
EC1To2 = calEC(c1, c2);
RI = 2 * EC1To2 / (EC1 + EC2);
return RI;
}
/**
* 计算簇的相对近似度
*
* @param c1
* 簇1
* @param c2
* 簇2
* @return
*/
private double calRC(Cluster c1, Cluster c2) {
double RC = 0;
double EC1 = 0;
double EC2 = 0;
double EC1To2 = 0;
int pNum1 = c1.points.size();
int pNum2 = c2.points.size();
EC1 = c1.calEC();
EC2 = c2.calEC();
EC1To2 = calEC(c1, c2);
RC = EC1To2 * (pNum1 + pNum2) / (pNum2 * EC1 + pNum1 * EC2);
return RC;
}
/**
* 计算度量函数的值
*
* @param c1
* 簇1
* @param c2
* 簇2
* @param alpha
* 幂的参数值
* @return
*/
private double calMetricfunction(Cluster c1, Cluster c2, int alpha) {
// 度量函数值
double metricValue = 0;
double RI = 0;
double RC = 0;
RI = calRI(c1, c2);
RC = calRC(c1, c2);
// 如果alpha大于1，则更重视相对近似性，如果alpha逍遥于1，注重相对互连性
metricValue = RI * Math.pow(RC, alpha);
return metricValue;
}
/**
* 输出聚簇列
*
* @param clusterList
* 输出聚簇列
*/
private void printClusters(ArrayList clusterList) {
int i = 1;
for (Cluster cluster : clusterList) {
System.out.print("聚簇" + i + ":");
for (Point p : cluster.point |