蘋果上帶有一個照片查看效果，根據(jù)地圖縮放比例，點之間的距離如果小于該比例對應(yīng)的值，則視為一個點，很明顯是通過聚類算法實現(xiàn)的，聚類算法有很多種，下面主要介紹K-Means算法。

K-Means算法簡介

K-Means是聚類算法中的一種，其中K表示類別數(shù)，Means表示均值。顧名思義K-Means是一種通過均值對數(shù)據(jù)點進(jìn)行聚類的算法。K-Means算法通過預(yù)先設(shè)定的K值及每個類別的初始質(zhì)心對相似的數(shù)據(jù)點進(jìn)行劃分。并通過劃分后的均值迭代優(yōu)化獲得最優(yōu)的聚類結(jié)果。

步驟

• 1.從數(shù)據(jù)中隨機(jī)抽取k個點作為初始聚類的k個中心，分別代表k個聚類
• 2.計算數(shù)據(jù)中所有的點到K個中心點的距離，通常是歐式距離
• 3.將每個點歸屬到離其最近的聚類里，生成k個聚類
• 4.重新計算每類的中心點，即計算沒類中所有點的幾何中心(平均值)
• 5.如果滿足終止條件，算法將結(jié)束，否則，進(jìn)入第二步
  終止的條件通常有如下三種；
• 1.聚類的中心點不在移動
• 2.聚類的中心點移動的大小在給定閾值范圍內(nèi)
• 3.迭代次數(shù)到達(dá)上限

理論說完了現(xiàn)在談實踐，我在實踐的時候并沒有完全按照K-Means算法的步驟來做，但意思差不多。

• 1.拿到數(shù)據(jù)后首先分為K類。
• 2.計算每個數(shù)據(jù)點到上一步中得到的類族中心點的距離，如果小于給定值則，則該把點加入該類族中
• 3.檢測通過第二步計算得到類族，如果該類中的點到該類的中心點都小于給定的值，視為收斂，當(dāng)然必須是每個類都收斂才結(jié)束迭代，否則用新得到類繼續(xù)迭代。

迭代處代碼

-(void)iteratorData:(NSArray *)array limit:(int)limit length:(int)length result:(void(^)(NSArray *))result {
    
    NSMutableArray *tempArray = @[].mutableCopy;
   
    for (int i = 0; i < array.count; i ++) {
        
        [tempArray addObject:@[].mutableCopy];
    }
    [self.array enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        
        QYPersonAnnotion *anno = obj;
        CLLocation *location = [anno locationForAnnotion];
        for (int i = 0; i < array.count; i++) {
            
            NSMutableArray *info = array[i];
            CLLocation *loc = [self calculateCenterlegth:info];
            
            double distance = [self calculateTwoPointLength:location to:loc];
            if (distance < length) {
                NSMutableArray *newInfo = tempArray[i];
                [newInfo addObject:obj];
                break;
            }
  
        }
      
    }];
#ifdef DEBUG
    NSLog(@"cureent iterator count:%d on this length:%d",2000 - limit,length);
#endif
   BOOL restrain = [self checkRestrainData:tempArray length:length];
    if (restrain || limit == 0) {
        if (limit == 0) {
            
#ifdef DEBUG
            
            NSLog(@"have more than the max iterator count");
#endif
        } else {
            
#ifdef DEBUG
            
            NSLog(@"data have restrain iterator can end with iterator count:%d",2000-limit);
#endif
        }
#ifdef DEBUG
        NSLog(@"check callback count");
#endif
        
        NSMutableArray *endResult = @[].mutableCopy;
        [self.array enumerateObjectsUsingBlock:^(id<QYLocationDelegate>  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
           
            QYPersonAnnotion *annotion = (QYPersonAnnotion *)obj;
            __block BOOL find = NO;
            [tempArray enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull level_stop) {
                
                NSArray *categoryArray = obj;
                [categoryArray enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
                   
                    QYPersonAnnotion *anno = obj;
                    if (anno == annotion) {
                        
                        *stop = YES;
                        *level_stop = YES;
                        find = YES;
                    }
                }];
            }];
            
            if (!find) {
                
                [endResult addObject:@[annotion]];
            }
        }];
        [endResult addObjectsFromArray:tempArray];
        result(endResult);
        return;
    }
    NSMutableArray *reArray = [NSMutableArray arrayWithArray:tempArray];
    [self iteratorData:reArray limit:--limit length:length result:result];
}

檢測是否收斂

- (BOOL)checkRestrainData:(NSArray<id<QYLocationDelegate>> *)array length:(int)length {
    
   __block BOOL restrain = YES;
    
    [array enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
       
        NSArray *info = obj;
        CLLocation *loc = [self calculateCenterlegth:info];
        for (id<QYLocationDelegate> location in info) {
            
            double distance = [self calculateTwoPointLength:[location locationForAnnotion] to:loc];
            if (distance > length) {
                
                restrain = NO;
                *stop = YES;
                break;
            }
        }
        
    }];
    return restrain;
}

以蘋果照片的查看效果來看，1.數(shù)據(jù)會很多，2.用戶隨時都會改變當(dāng)前地圖的縮放比例，如果不進(jìn)行優(yōu)化主線程都將用來計算去了，繪制將如龜速。想到的當(dāng)然是把當(dāng)前計算放到子線程中去。我這里用隊列來完成的

- (NSOperationQueue *)calculateQueue {
    
    if (!_calculateQueue) {
        
        _calculateQueue = [[NSOperationQueue alloc] init];
        _calculateQueue.maxConcurrentOperationCount = 9;
    }
    return _calculateQueue;
}

計算操作都會丟到該隊列中，并發(fā)數(shù)可以定義為17，我的應(yīng)用中用的是高德，縮放級別我3~20，可以為每個比例都起一個線程去計算，不過考慮到用戶縮放操作頻繁，容易導(dǎo)致一個比例重復(fù)計算，因此最大并發(fā)數(shù)限制為9。

緩存計算結(jié)果也是優(yōu)化的一個重要步驟。應(yīng)用中沒有單獨設(shè)計一個緩存管理機(jī)制，直接用NSCache，耦合在該迭代器中

- (void)loadDataByScale:(float)scale result:(void (^)(NSArray *))result {
    
    NSInteger zoomScale = scale;
    self.curScale = zoomScale;
    NSArray *array = [self.cache objectForKey:@(zoomScale)];
    if (array) {
        
        result(array);
    } else {
        
        [self analyzeData:zoomScale result:result];
    }
    
}

后面有時間會把緩存邏輯提出來，具體功能，1.緩存的key交給delegate來提供；2.提供緩存超時限制
key交給delegate提供，主要為了緩存不同用戶的計算結(jié)果，更具用戶id和當(dāng)前比例作為key來緩存。
緩存超時限制，因為是對用戶的所有數(shù)據(jù)進(jìn)行聚類并緩存，可能導(dǎo)致內(nèi)存壓力，2.能夠?qū)τ脩粜聛淼臄?shù)據(jù)進(jìn)行聚類，不至于影響用戶體驗。

大致都介紹完了，整個項目都開源在github上，想看效果下載我們的App吧，??，App中關(guān)于我們有提供項目的連接。后續(xù)應(yīng)該會嚴(yán)格按照K-Means算法的步驟來重寫一下，看看效果會不會更佳，不過目前我覺得效果已經(jīng)很贊了。