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





            
	    
    




            






            

				

            


    
    







            
	   
	



丁香五月综合久久激情|
久久久久久免费视频|
久久av无码专区亚洲av桃花岛|
日韩va亚洲va欧美va久久|
人妻无码精品久久亚瑟影视|
久久久久久久久久久|
91精品久久久久久无码|
欧美激情一区二区久久久|
99久久久精品免费观看国产|
久久亚洲国产成人精品无码区|
亚洲精品乱码久久久久久按摩
|
色偷偷88888欧美精品久久久|
久久伊人精品青青草原高清|
中文国产成人精品久久亚洲精品AⅤ无码精品
|
国内精品久久久久影院免费|
精品久久久久久久久久中文字幕
|
99久久精品国产一区二区蜜芽|
性做久久久久久久久老女人|
国产Av激情久久无码天堂|
日日狠狠久久偷偷色综合免费
|
久久只有这精品99|
国内精品久久久久久久久电影网|
亚洲欧美成人综合久久久|
亚洲欧洲久久久精品|
久久久久一本毛久久久|
久久这里只有精品首页|
97精品国产91久久久久久|
日韩精品久久无码中文字幕|
日本久久中文字幕|
欧美麻豆久久久久久中文|
久久93精品国产91久久综合|
国产成人久久精品一区二区三区|
欧美精品国产综合久久|
久久国产AVJUST麻豆|
久久亚洲AV无码精品色午夜|
武侠古典久久婷婷狼人伊人|
久久久久久一区国产精品|
久久精品国产一区二区电影|
国产精品九九久久精品女同亚洲欧美日韩综合区
|
色妞色综合久久夜夜|
久久超乳爆乳中文字幕|