mysql - 试图理解/开始使用 MySQL 中的 k-means 聚类算法

Question

我是第一次接触 MySQL，一直在研究我在 http://jonisalonen.com/2012/k-means-clustering-in-mysql/ 找到的 sql 位置聚类算法。 .我发现聚类很有趣，并试图弄清楚它是如何工作的，但遇到了一些麻烦。

这是我输入的代码(我一直在使用sqlfiddle.com)

create table km_data (id int primary key, cluster_id int,
    lat double, lng double);

create table km_clusters (id int auto_increment primary key,
    lat double, lng double
);


INSERT INTO km_data 
VALUES(1,0,88.3324,56.343);

INSERT INTO km_data 
VALUES(2,0,88.3324,56.342);

INSERT INTO km_data 
VALUES(3,0,83.234,54.234);

INSERT INTO km_data 
VALUES(4,0,88.33,57.234);

INSERT INTO km_data 
VALUES(5,0,88.234,86.654);

INSERT INTO km_data 
VALUES(6,0,78.673,56.854);

INSERT INTO km_data 
VALUES(7,0,83.136,46.958);


INSERT INTO km_clusters (lat, lng) SELECT lat, lng FROM km_data LIMIT 10;

UPDATE km_data d SET cluster_id = 
(SELECT id FROM km_clusters c ORDER BY POW(d.lat-c.lat,2)+POW(d.lng-c.lng,2) ASC LIMIT 1);

UPDATE km_clusters C, (SELECT cluster_id, AVG(lat) AS lat, AVG(lng) AS lng 
FROM km_data GROUP BY cluster_id) D SET C.lat=D.lat, C.lng=D.lng WHERE C.id=D.cluster_id;  

这编译得很好，但是当我把更新部分放入循环中时，因为网站有它所以它不断更新集群 SQL fiddle 提示，

“您的 SQL 语法有错误；请检查与您的 MySQL 服务器版本对应的手册，了解在‘UPDATE km_data d SET cluster_id = (SELECT id FROM km_clusters c ORDER BY POW(' at line 2"

我注意到“UNTIL”没有加粗，想知道这是否不适合用于这样的循环:

 BEGIN
 UPDATE km_data d SET cluster_id = 
(SELECT id FROM km_clusters c ORDER BY POW(d.lat-c.lat,2)+POW(d.lng-c.lng,2) ASC LIMIT 1);

UPDATE km_clusters C, (SELECT cluster_id, AVG(lat) AS lat, AVG(lng) AS lng 
FROM km_data GROUP BY cluster_id) D SET C.lat=D.lat, C.lng=D.lng WHERE C.id=D.cluster_id;  

UNTIL ROW_COUNT() = 0 
END REPEAT;

此外，该算法似乎只适用于大量数据(不适用于我拥有的这对数据)，这种假设是否正确？我唯一一次在同一集群中获得 2 条数据，它们具有相同的确切位置。也许这是一个错误，因为我没有让循环正常运行，尽管我已经通过连续 10 次运行相同的代码块来模拟循环。任何帮助表示赞赏!

Answer 1

不要这样做。

将数据简单地加载到聚类工具包(例如 ELKI)会快很多倍或 sklearn，将其聚集在那里，然后将结果加载回您的数据库。

原因是这些工具针对此用例进行了更好的优化。 SQL 数据库适用于通用查询，但不适用于优化的学习算法。

附带说明，不要在 GPS 坐标上使用 k-means。 K-means 是一种方差最小化技术。对于此类数据，可以使用 Haversine 距离的 DBSCAN 和 OPTICS 等方法效果更好。以下是一些示例:

https://doublebyteblog.wordpress.com/2016/02/20/spatial-data-mining/

这个还显示了此类数据的 k-means 结果是多么糟糕(底部的“长颈鹿”图案图像):

http://www.vitavonni.de/blog/201410/2014102301-clustering-23-mio-tweet-locations.html