有效的算法來在集羣組點由每兩個點

Question

我尋找一種有效的算法爲以下的問題之間的距離：

給定一組在二維空間，其中每個點由它的X和定義的點的Y座標。需要這組點分裂成一組集羣，使得如果兩個任意點之間的距離小於某一閾值，這些點必須屬於同一羣集：

換句話說，例如簇是一組相互「足夠接近」的點。

天真的算法是這樣的：

1. 讓[R是導致集羣名單，初始爲空
2. 讓P是點的列表，最初包含的所有點
3. 從P中挑選隨機點並創建一個羣集C其中只包含這一點。從P 4a中刪除從P
4. 這一點對於每一個點裨。對於每個點Pc from C 4aa。如果距離（PI，PC）<閾然後添加裨到Ç和如果加入在步驟4到簇Ç的至少一個點從P集合中刪除它
5. ，轉到步驟4
6. 添加簇C至列表R。如果P不爲空，請轉至步驟3

但是，天真的方法效率非常低。我想知道這個問題是否有更好的算法？

P.S.我不知道集羣的數量先驗

Answer 1

1. 分手了點的空間劃分爲一個網格。這個網格的單位長度等於threshhold/sqrt（8）。

2. 通過迭代點列表P，將每個點添加到它佔據的平方和新簇。如果一個點被添加到已經包含點的正方形中，則將其添加到其他點的羣集中。我會打電話給所有佔用的方位列表S。

3. 立即採取任何方從小號和其羣集Ç。對於每個相鄰或對角線方塊，將該方塊的羣集與c組合起來，並從S中刪除方塊。對剛剛添加的所有方塊重複該過程。

4. 一旦找不到更多相鄰的sqaures，則羣集已完成並可添加到C。用S中的任何剩餘方塊重複步驟3。當S爲空時，表示完成。

Answer 2

有一些經典算法在這裏：

• 分層合併聚類
• DBSCAN

，你應該閱讀和理解。