最大最小距离算法

课程设计

使用最大最小距离算法做聚类分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
/*
使用最大最小距离法做聚类分析
1. 任选一个样本作为聚类中心z1
2. 选择离z1距离最大的样本作为第二个聚类中心z2
3. 计算其余样本与{z1,z2}之间的距离,Di1=|Xi-z1|, Di2=|Xi-z2|,Di=min(Di1,Di2)
4. 若max(Di,{i=1..2..}) >
θ|z1-z2|,即样本离两个中心太远,则取max(Di)中的Xi为新的聚类中心z3,
若没有新的聚类中心,则找聚类中心过程结束,直接将样本分到最近的中心。
5. 重新回到第3步计算最小距离,
*/
/*
距离测度:
欧式距离 绝对值距离 切氏距离 闵氏距离
*/
/*
类内距离
*/
/*
二值特征还有匹配测度
*/
/*
1. 输入比例系数
2. 输入样本数和样本维度
3. 输入样本
4. 确定距离测度
5. 第一个样本作为第一个聚类中心
6. 找到离第一个样本最远的样本作为第二个聚类中心
7. 找到离这两个聚类中心都很远的样本作为其他可能的中心
8. 将所有样本分到最近的聚类中心
9. 计算类间距离
*/
#include "algorithm"
#include "cmath"
#include "cstring"
#include "iostream"
#include "vector"
using namespace std;
int z[30]; //聚类中心
int zn; //聚类中心的个数
double a[30][6]; //样本,最多30个样本,每个样本最多6个维度
double d[33]; //样本到z1的距离
double mind[33]; //样本到最近聚类中心的距离
int n; //样本数量
int D; //样本维数
//初始化分类向量,最多30个类
vector<vector<int>> v(30);
int DistanceMeasure; //距离测度
//计算两点间欧式距离
double Euclidean(double x[], double y[]) {
int sum = 0;
for (int i = 1; i <= D; i++)
sum = sum + (x[i] - y[i]) * (x[i] - y[i]);
return sqrt(sum);
}
//绝对值距离
double Manhattan(double x[], double y[]) {
int sum = 0;
for (int i = 1; i <= D; i++)
sum += abs(x[i] - y[i]);
return sum;
}
//切氏距离
double Chebyahev(double x[], double y[]) {
double ans = 0;
for (int i = 1; i <= D; i++) {
ans = max(ans, abs(x[i] - y[i]));
}
return ans;
}
//闵氏距离
double Minkowski(double x[], double y[], int m) {
int sum = 0;
for (int i = 1; i <= D; i++) {
sum += pow(abs(x[i] - y[i]), m);
}
return pow(sum, 1.0 / m);
}
//用DistanceMeasure选择不同的距离测度
double Distan(double x[], double y[]) {
if (DistanceMeasure == 1) //欧式距离
return Euclidean(x, y);
else if (DistanceMeasure == 2) //绝对值距离
return Manhattan(x, y);
else if (DistanceMeasure == 3) //切氏距离
return Chebyahev(x, y);
else if (DistanceMeasure == 4) { //闵氏距离
static int m;
if (!m) {
cout << "请输入闵氏距离的参数m: ";
cin >> m;
}
return Minkowski(x, y, m);
} else {
cout << "参数错误!!\n";
return -1;
}
}
/*
类间距离:
最近距离法 最远距离法 中间距离法 重心距离法 平均距离法
*/
//最近距离
//计算第x个类别和第y个类别的元素间的最小距离
double ClusterMin(int x, int y) {
double MinDistan = 1 << 30;
for (auto i = v[x].begin(); i != v[x].end(); i++) {
for (auto j = v[y].begin(); j != v[y].end(); j++) {
double tempd = Distan(a[*i], a[*j]);
MinDistan = min(MinDistan, tempd);
}
}
return MinDistan;
}
//最远距离
double ClusterMax(int x, int y) {
double MaxDistab = 0;
for (auto i = v[x].begin(); i != v[x].end(); i++)
for (auto j = v[y].begin(); j != v[y].end(); j++) {
double tempd = Distan(a[*i], a[*j]);
MaxDistab = max(MaxDistab, tempd);
}
return MaxDistab;
}
//重心距离
//以样本均值作为类的重心
double ClusterCentroid(int x, int y) {
double CenterX[33], CenterY[33];
memset(CenterX, 0, sizeof(CenterX));
memset(CenterY, 0, sizeof(CenterY));
for (auto i = v[x].begin(); i != v[x].end(); i++) {
for (int j = 1; j <= D; j++) {
CenterX[j] += a[*i][j];
}
}
for (auto i = v[y].begin(); i != v[y].end(); i++) {
for (int j = 1; j <= D; j++) {
CenterY[j] += a[*i][j];
}
}
//求得中心位置
for (int i = 1; i <= D; i++) {
CenterX[i] /= v[x].size();
CenterY[i] /= v[y].size();
}
//计算中间距离
double ans = Distan(CenterX, CenterY);
return ans;
}
//中心距离
// double ClusterMedian(int x, int y) { return 0; }
//平均距离
double ClusterAverage(int x, int y) {
double sum = 0, tempd;
for (auto i = v[x].begin(); i != v[x].end(); i++) {
for (auto j = v[y].begin(); j != v[y].end(); j++) {
tempd = Distan(a[*i], a[*j]);
sum += tempd;
}
}
sum /= (v[x].size() * v[y].size());
return sqrt(sum);
}
//类内距离
//输入x为类别,z[x]为x的类心,v[x]为类内样本
double ClusterInDistance(int x) {
//定义为类内样本到类中心的距离和
double sum = 0;
int t = z[x];
double d;
for (auto i = v[x].begin(); i != v[x].end(); i++) {
d = Distan(a[t], a[*i]);
sum += d;
}
return sum;
}
int main() {
freopen("in.txt", "r", stdin);
double k; //阈值
cout << "请输入阈值:\n";
cin >> k;
cout << "请输入样本数量和样本维数:\n";
cin >> n >> D;
cout << "输入样本:\n";
int i, j;
//录入样本
for (i = 1; i <= n; i++)
for (j = 1; j <= D; j++)
cin >> a[i][j];
// 选择距离测度
cout << "选择距离测度: \n";
cout << "1. 欧氏距离\n";
cout << "2. 绝对值距离\n";
cout << "3. 切氏距离\n";
cout << "4. 闵氏距离\n";
cin >> DistanceMeasure;
//选择第一个样本点为初始聚类中心
z[1] = 1;
//选择距离z1最远的样本作为第2个聚类中心
double t = 0; //最大距离
for (i = 2; i <= n; i++) {
d[i] = Distan(a[1], a[i]); //样本i距z1的距离
// cout << i << "到x1距离: " << d[i] << endl;
if (d[i] > t) {
t = d[i];
z[2] = i;
}
}
zn = 2;
//查找聚类中心
while (1) {
//计算其余样本到最近聚类中心的距离
//聚类中心数量>=2
for (i = 1; i <= n; i++) {
double t = 1 << 30; //临时作为最小距离
for (j = 1; j <= zn; j++) {
t = min(t, Distan(a[z[j]], a[i]));
}
mind[i] = t;
}
//选出最小距离中的最大距离
int tempZ; //可能的新聚类中心
double tempD = 0; //最小距离中的最大距离
for (int i = 1; i <= n; i++) {
if (mind[i] > tempD) {
tempD = mind[i];
tempZ = i;
}
}
if (tempD > k * Distan(a[1], a[z[2]])) { //增加新聚类中心
z[++zn] = tempZ;
} else {
//查找聚类中心结束
break;
}
}
//输出聚类中心
/* cout << "聚类中心: \n";
for (i = 1; i <= zn; i++)
cout << z[i] << ' ';
cout << endl;*/
//将样本分配到最近的聚类中心
for (i = 1; i <= n; i++) { //遍历所有的样本
vector<int> v1;
double d; //距离
t = 1 << 30; //最小距离
int tempNo; //临时分组
for (j = 1; j <= zn; j++) { //遍历所有的中心
d = Distan(a[z[j]], a[i]);
if (d < t) { //距离更近,更新分组
t = d;
tempNo = j;
}
}
// cout << "push" << tempNo << endl;
v[tempNo].push_back(i); //将样本i加到第tempNo个分组中
}
//for (auto x = v[3].begin(); x != v[3].end(); x++)
//cout << *x;
//cout << endl;
//输出分组信息
for (i = 1; i <= zn; i++) {
cout << "分组中心: " << z[i] << endl;
cout << "分组成员: ";
for (auto x = v[i].begin(); x != v[i].end(); x++)
cout << *x << ' ';
cout << endl;
}
//计算类间距离
cout << "类间距离: \n";
for (i = 1; i <= zn; i++) {
for (j = i + 1; j <= zn; j++) {
cout << " " << i << " --- " << j << endl;
cout << "最近距离: " << ClusterMin(i, j) << endl;
cout << "最远距离: " << ClusterMax(i, j) << endl;
// cout << "中间距离: " << ClusterMedian(i, j) << endl;
cout << "重心距离: " << ClusterCentroid(i, j) << endl;
cout << "平均距离: " << ClusterAverage(i, j) << endl;
}
}
//类内距离
//定义为类内样本到类心的距离和
cout << "\n类内距离: \n";
for (i = 1; i <= zn; i++) {
cout << "第" << i << "类: ";
cout << ClusterInDistance(i) << endl;
}
return 0;
}

测试输入文件
in.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
0.5
10 2
0 0
3 8
2 2
1 1
5 3
4 8
6 3
5 4
6 4
7 5
1

本文标题:最大最小距离算法

文章作者:admin

发布时间:2017年12月16日 - 17:12

最后更新:2017年12月16日 - 17:12

原始链接:https://kxp555.coding.me/2017/12/16/最大最小距离算法/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。