k-means算法实践-苹果照片查看效果实现

苹果上带有一个照片查看效果，根据地图缩放比例，点之间的距离如果小于该比例对应的值，则视为一个点，很明显是通过聚类算法实现的，聚类算法有很多种，下面主要介绍K-Means算法。

K-Means算法简介

K-Means是聚类算法中的一种，其中K表示类别数，Means表示均值。顾名思义K-Means是一种通过均值对数据点进行聚类的算法。K-Means算法通过预先设定的K值及每个类别的初始质心对相似的数据点进行划分。并通过划分后的均值迭代优化获得最优的聚类结果。

步骤

• 1.从数据中随机抽取k个点作为初始聚类的k个中心，分别代表k个聚类
• 2.计算数据中所有的点到K个中心点的距离，通常是欧式距离
• 3.将每个点归属到离其最近的聚类里，生成k个聚类
• 4.重新计算每类的中心点，即计算没类中所有点的几何中心(平均值)
• 5.如果满足终止条件，算法将结束，否则，进入第二步
  终止的条件通常有如下三种；
• 1.聚类的中心点不在移动
• 2.聚类的中心点移动的大小在给定阈值范围内
• 3.迭代次数到达上限

理论说完了现在谈实践，我在实践的时候并没有完全按照K-Means算法的步骤来做，但意思差不多。

• 1.拿到数据后首先分为K类。
• 2.计算每个数据点到上一步中得到的类族中心点的距离，如果小于给定值则，则该把点加入该类族中
• 3.检测通过第二步计算得到类族，如果该类中的点到该类的中心点都小于给定的值，视为收敛，当然必须是每个类都收敛才结束迭代，否则用新得到类继续迭代。

迭代处代码

-(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.数据会很多，2.用户随时都会改变当前地图的缩放比例，如果不进行优化主线程都将用来计算去了，绘制将如龟速。想到的当然是把当前计算放到子线程中去。我这里用队列来完成的

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

计算操作都会丢到该队列中，并发数可以定义为17，我的应用中用的是高德，缩放级别我3~20，可以为每个比例都起一个线程去计算，不过考虑到用户缩放操作频繁，容易导致一个比例重复计算，因此最大并发数限制为9。

缓存计算结果也是优化的一个重要步骤。应用中没有单独设计一个缓存管理机制，直接用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提供，主要为了缓存不同用户的计算结果，更具用户id和当前比例作为key来缓存。
缓存超时限制，因为是对用户的所有数据进行聚类并缓存，可能导致内存压力，2.能够对用户新来的数据进行聚类，不至于影响用户体验。

大致都介绍完了，整个项目都开源在github上，想看效果下载我们的App吧，😀，App中关于我们有提供项目的连接。后续应该会严格按照K-Means算法的步骤来重写一下，看看效果会不会更佳，不过目前我觉得效果已经很赞了。