苹果上带有一个照片查看效果，根据地图缩放比例，点之间的距离如果小于该比例对应的值，则视为一个点，很明显是通过聚类算法实现的，聚类算法有很多种，下面主要介绍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算法的步骤来重写一下，看看效果会不会更佳，不过目前我觉得效果已经很赞了。
网友评论