coreBugZJ

此 blog 已棄。

k-means 算法實現人口聚類

/*
2

k-means 算法實現人口聚類
4

----問題描述：
7

聚類（Cluster）分析是由若干模式（Pattern）組成的，通常，模式是一個度量（Measurement）的向量，或者是多維空間中的一個點。聚類分析以相似性為基礎，在一個聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性。
9

為了更深入了解我國人口的文化程度狀況，現利用1990年全國人口普查數據對全國30個省、直轄市、自治區進行聚類分析。分析選用了三個指標：（1）大學以上文化程度的人口占全部人口的比例（DXBZ）；（2）初中文化程度的人口占全部人口的比例（CZBZ）；（3）文盲半文盲人口占全部人口的比例（WMBZ）、分別用來反映較高、中等、較低文化程度人口的狀況，原始數據如下表：
11

Table 2. 1990年全國人口普查文化程度人口比例（%）
13

地區序號 DXBZ CZBZ WMBZ
15

北京 1 9.30 30.55 8.70
17

天津 2 4.67 29.38 8.92
18

河北 3 0.96 24.69 15.21
19

山西 4 1.38 29.24 11.30
20

內蒙 5 1.48 25.47 15.39
21

遼寧 6 2.60 32.32 8.81
22

吉林 7 2.15 26.31 10.49
23

黑龍江 8 2.14 28.46 10.87
24

上海 9 6.53 31.59 11.04
25

江蘇 10 1.47 26.43 17.23
26

浙江 11 1.17 23.74 17.46
27

安徽 12 0.88 19.97 24.43
28

福建 13 1.23 16.87 15.63
29

江西 14 0.99 18.84 16.22
30

山東 15 0.98 25.18 16.87
31

河南 16 0.85 26.55 16.15
32

河北 17 1.57 23.16 15.79
33

湖南 18 1.14 22.57 12.10
34

廣東 19 1.34 23.04 10.45
35

廣西 20 0.79 19.14 10.61
36

海南 21 1.24 22.53 13.97
37

四川 22 0.96 21.65 16.24
38

貴州 23 0.78 14.65 24.27
39

云南 24 0.81 13.85 25.44
40

西藏 25 0.57 3.85 44.43
41

陜西 26 1.67 24.36 17.62
42

甘肅 27 1.10 16.85 27.93
43

青海 28 1.49 17.76 27.70
44

寧夏 29 1.61 20.27 22.06
45

新疆 30 1.85 20.66 12.75
46

數據來源：《中國計劃生育全書》第886頁。
48

要求將上述數據分成三類。
50

參考算法（K-MEANS）
52

　　k-means 算法接受輸入量 k ；然后將n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進行計算的。
53

　　k-means 算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心；而對于所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標準測度函數開始收斂為止。一般都采用均方差作為標準測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。
55

----輸入：
58

若干行，每行為
60

字符串實數實數實數
62

表示
64

地區 DXBZ CZBZ WMBZ
66

輸入至文件結束。
68

----輸出：
71

按輸入順序，輸出若干行，每行為
73

地區類別
75

其中類別為 1，2 或 3 。
77

----分析：
80

無需贅述。
82

第一次實現，代碼好丑。
84

*/
87

#include <iostream>
90

#include <cstdio>
91

#include <cstring>
92

#include <cmath>
93

#include <cstdlib>
94

#include <ctime>
95

#include <string>
96

using namespace std;
98

const int N = 1009;
100

const double EPS = 1e-3;
101

102

int n; // n 項數據，編號為 1..n
103

double x[ N ], y[ N ], z[ N ]; // 1..n DXBZ CZBZ WMBZ
104

int bg[ N ]; // 1..n bg[ i ] 表示第 i 項數據屬于哪一類
105

string name[ N ];
106

107

int k; // 分為 k 類，編號為 1..k
108

int g[ N ][ N ]; // 1..k 1..[0]
109

double cx[ N ], cy[ N ], cz[ N ]; // center 1..k
110

111

bool md = false;
112

113

inline double sqr( double x ) {
114

return x * x;
115

}
116

117

inline double dist( int ci, int j ) {
118

return sqr(cx[ci] - x[j]) + sqr(cy[ci] - y[j]) + sqr(cz[ci]-z[j]);
119

}
120

121

inline int diff( double x, double y ) {
122

return (abs(x - y) > EPS);
123

}
124

125

inline void center() {
126

double sx, sy, sz, tx, ty, tz;
127

int i, j, p;
128

for ( i = 1; i <= k; ++i ) {
129

sx = sy = sz = 0;
130

for ( j = g[ i ][ 0 ]; j > 0; --j ) {
131

p = g[ i ][ j ];
132

sx += x[ p ];
133

sy += y[ p ];
134

sz += z[ p ];
135

}
136

j = g[ i ][ 0 ];
137

tx = sx / j;
138

ty = sy / j;
139

tz = sz / j;
140

141

if ( diff(tx, cx[i]) || diff(ty, cy[i]) || diff(tz, cz[i]) ) {
142

md = true;
143

}
144

145

cx[ i ] = tx;
146

cy[ i ] = ty;
147

cz[ i ] = tz;
148

}
149

}
150

151

inline int find( int i ) {
152

int j = 1, v;
153

double m = dist( 1, i ), tm;
154

for ( v = 2; v <= k; ++v ) {
155

tm = dist( v, i );
156

if ( tm < m ) {
157

m = tm;
158

j = v;
159

}
160

}
161

return j;
162

}
163

164

inline void add( int i ) {
165

int j = find( i );
166

bg[ i ] = j;
167

g[ j ][ ++g[j][0] ] = i;
168

}
169

170

inline void disp() {
171

int i;
172

for ( i = 1; i <= k; ++i ) {
173

g[ i ][ 0 ] = 0;
174

}
175

for ( i = 1; i <= n; ++i ) {
176

add( i );
177

}
178

}
179

180

int kmean() {
181

int i, j;
182

183

if ( (1 > n) || (k > n) ) {
184

return 0;
185

}
186

187

srand( (unsigned int)time( NULL ) );
188

189

memset( g, 0, sizeof(g) );
190

memset( bg, 0, sizeof(bg) );
191

for ( i = 1; i <= k; ++i ) {
192

j = rand() % n + 1;
193

194

g[ i ][ 0 ] = 1;
195

g[ i ][ 1 ] = j;
196

cx[ i ] = x[ j ];
197

cy[ i ] = y[ j ];
198

cz[ i ] = z[ j ];
199

bg[ j ] = i;
200

}
201

for ( i = 1; i <= n; ++i ) {
202

if ( 0 == bg[ i ] ) {
203

add( i );
204

}
205

}
206

207

md = true;
208

while ( md ) {
209

md = false;
210

center();
211

disp();
212

}
213

214

return 1;
215

}
216

217

int main() {
218

n = 0;
219

k = 3;
220

while ( cin >> name[n+1] >> x[n+1] >> y[n+1] >> z[n+1] ) {
221

++n;
222

}
223

if ( kmean() ) {
224

int i;
225

for ( i = 1; i <= n; ++i ) {
226

cout << name[ i ] << " " << bg[ i ] << endl;
227

}
228

}
229

else {
230

cout << "輸入不合法，無法分類" << endl;
231

}
232

return 0;
233

}
234

235

236

/*
237

實際輸出：
238

239

北京 2
240

天津 2
241

河北 3
242

山西 2
243

內蒙 3
244

遼寧 2
245

吉林 2
246

黑龍江 2
247

上海 2
248

江蘇 3
249

浙江 3
250

安徽 1
251

福建 3
252

江西 3
253

山東 3
254

河南 3
255

河北 3
256

湖南 3
257

廣東 3
258

廣西 3
259

海南 3
260

四川 3
261

貴州 1
262

云南 1
263

西藏 1
264

陜西 3
265

甘肅 1
266

青海 1
267

寧夏 3
268

新疆 3
269

270

*/
271

posted on 2012-06-05 15:04 coreBugZJ 閱讀(1176) 評論(0) 編輯收藏引用所屬分類: Algorithm 、課內作業、Intelligence

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 微軟2014實習生及秋令營技術類職位在線測試 LZW 編碼解碼代碼 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight k-means 算法實現人口聚類 ID3 算法實現決策樹 POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

k-means 算法實現人口聚類