coreBugZJ

此 blog 已棄。

k-means 算法實(shí)現(xiàn)人口聚類

/*
2

k-means 算法實(shí)現(xiàn)人口聚類
4

----問題描述：
7

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

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

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

地區(qū) 序號 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

內(nèi) 蒙 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

數(shù)據(jù)來源：《中國計(jì)劃生育全書》第886頁。
48

要求將上述數(shù)據(jù)分成三類。
50

參考算法（K-MEANS）
52

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

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

----輸入：
58

若干行，每行為
60

字符串實(shí)數(shù) 實(shí)數(shù) 實(shí)數(shù)
62

表示
64

地區(qū) DXBZ CZBZ WMBZ
66

輸入至文件結(jié)束。
68

----輸出：
71

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

地區(qū) 類別
75

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

----分析：
80

無需贅述。
82

第一次實(shí)現(xiàn)，代碼好丑。
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 項(xiàng)數(shù)據(jù)，編號為 1..n
103

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

int bg[ N ]; // 1..n bg[ i ] 表示第 i 項(xiàng)數(shù)據(jù)屬于哪一類
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

實(shí)際輸出：
238

239

北京 2
240

天津 2
241

河北 3
242

山西 2
243

內(nèi)蒙 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 閱讀(1180) 評論(0) 編輯收藏引用所屬分類: Algorithm 、課內(nèi)作業(yè) 、Intelligence

只有注冊用戶登錄后才能發(fā)表評論。


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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術(shù)

開源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

問題（練習(xí)＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

k-means 算法實(shí)現(xiàn)人口聚類