• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            


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





            
	    
    




            






            

				

            


    
    







            
	   
	



久久精品国产精品亚洲精品|
AAA级久久久精品无码区|
久久青青草视频|
亚洲午夜无码AV毛片久久|
久久综合九色综合网站|
无码日韩人妻精品久久蜜桃|
久久精品无码专区免费东京热|
亚洲综合久久综合激情久久|
久久久WWW免费人成精品|
欧美成人免费观看久久|
久久精品国产亚洲av水果派
|
人人狠狠综合久久亚洲|
18岁日韩内射颜射午夜久久成人
|
久久久精品免费国产四虎|
久久午夜福利电影|
久久青青草原亚洲av无码app|
91精品观看91久久久久久|
亚洲精品无码专区久久久|
精品久久综合1区2区3区激情|
亚洲国产精品无码久久SM|
国产精品亚洲综合专区片高清久久久|
伊人色综合久久天天网|
国产精品久久久久AV福利动漫|
欧美国产精品久久高清|
久久免费线看线看|
精品无码久久久久久午夜|
久久久久国产精品嫩草影院|
狠狠色综合久久久久尤物|
国产精品久久久福利|
久久婷婷激情综合色综合俺也去|
久久精品二区|
精品国产一区二区三区久久蜜臀|
99久久er这里只有精品18|
97久久国产综合精品女不卡
|
久久综合色区|
国产精品免费看久久久香蕉|
国产成人精品白浆久久69|
99久久成人国产精品免费|
97久久国产亚洲精品超碰热|
欧美亚洲色综久久精品国产|
国产成人精品三上悠亚久久|