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

K-Means算法簡(jiǎn)介

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

步驟

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

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

• 1.拿到數(shù)據(jù)后首先分為K類。
• 2.計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到上一步中得到的類族中心點(diǎn)的距離，如果小于給定值則，則該把點(diǎn)加入該類族中
• 3.檢測(cè)通過(guò)第二步計(jì)算得到類族，如果該類中的點(diǎn)到該類的中心點(diǎn)都小于給定的值，視為收斂，當(dāng)然必須是每個(gè)類都收斂才結(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];
}

檢測(cè)是否收斂

- (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;
}

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

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

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

緩存計(jì)算結(jié)果也是優(yōu)化的一個(gè)重要步驟。應(yīng)用中沒(méi)有單獨(dú)設(shè)計(jì)一個(gè)緩存管理機(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];
    }
    
}

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

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