coreBugZJ

此 blog 已弃。

k-means 算法实现人口聚类

  1/*
  2
  3k-means 算法实现人口聚类
  4
  5
  6----问题描述：
  7
  8聚类（Cluster）分析是由若干模式（Pattern）组成的，通常，模式是一个度量（Measurement）的向量，或者是多维空间中的一个点。聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。
  9
 10为了更深入了解我国人口的文化程度状况，现利用1990年全国人口普查数据对全国30个省、直辖市、自治区进行聚类分析。分析选用了三个指标：（1）大学以上文化程度的人口占全部人口的比例（DXBZ）；（2）初中文化程度的人口占全部人口的比例（CZBZ）；（3）文盲半文盲人口占全部人口的比例（WMBZ）、分别用来反映较高、中等、较低文化程度人口的状况，原始数据如下表：
 11
 12Table 2. 1990年全国人口普查文化程度人口比例（%）
 13
 14地区    序  号    DXBZ    CZBZ    WMBZ
 15
 16北  京    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
 47数据来源：《中国计划生育全书》第886页。
 48
 49要求将上述数据分成三类。
 50
 51参考算法（K-MEANS）
 52　　k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
 53
 54　　k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
 55
 56
 57----输入：
 58
 59若干行，每行为
 60
 61字符串 实数 实数 实数
 62
 63表示
 64
 65地区 DXBZ CZBZ WMBZ
 66
 67输入至文件结束。
 68
 69
 70----输出：
 71
 72按输入顺序，输出若干行，每行为
 73
 74地区 类别
 75
 76其中类别为 1，2 或 3 。
 77
 78
 79----分析：
 80
 81无需赘述。
 82
 83第一次实现，代码好丑。
 84
 85
 86*/
 87
 88
 89#include <iostream>
 90#include <cstdio>
 91#include <cstring>
 92#include <cmath>
 93#include <cstdlib>
 94#include <ctime>
 95#include <string>
 96
 97using namespace std;
 98
 99const int    N   = 1009;
100const double EPS = 1e-3;
101
102int    n;                      // n 项数据，编号为 1..n
103double x[ N ], y[ N ], z[ N ]; // 1..n   DXBZ CZBZ WMBZ
104int    bg[ N ];                // 1..n   bg[ i ] 表示第 i 项数据属于哪一类
105string name[ N ];
106
107int    k;                         // 分为 k 类，编号为 1..k
108int    g[ N ][ N ];               // 1..k  1..[0]
109double cx[ N ], cy[ N ], cz[ N ]; // center 1..k
110
111bool md = false;
112
113inline double sqr( double x ) {
114        return x * x;
115}
116
117inline 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
121inline int diff( double x, double y ) {
122        return (abs(x - y) > EPS);
123}
124
125inline 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
151inline 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
164inline void add( int i ) {
165        int j = find( i );
166        bg[ i ] = j;
167        g[ j ][ ++g[j][0] ] = i;
168}
169
170inline 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
180int 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
217int 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 阅读(1086) 评论(0)  编辑 收藏 引用 所属分类: Algorithm 、课内作业 、Intelligence


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理