DBSCAN算法和數據挖掘聚類算法

Question

如何在分類數據（蘑菇數據集）上實現DBSCAN算法？

什麼是單程聚類算法？

你能提供一個單程聚類算法的僞代碼嗎？

Answer 1

閱讀前k項並按住它們。計算它們之間的距離。

對於每個剩餘的項：

• 找出第k項目的，它是最接近，而這兩個項之間的距離。

• 如果這比k個項目中任意兩個之間的最近距離更長，那麼可以將新項目與這兩個項目中的一個交換，並且至少不會減少任何兩個新k項目之間的最近距離。儘可能地增加這個距離。

假設集合中的所有項目可以被分成升< = k個簇，使得同一集羣中的任何兩個點之間的距離比在不同的簇的任何兩個點之間的距離更小。然後在運行此算法後，您將保留每個羣集至少一個點。

Answer 2

您可以使用任意距離函數運行DBSCAN而不做任何更改。索引部分將更加困難，因此您可能只會獲得O(n^2)的複雜性。

但是，如果仔細觀察DBSCAN，它所做的只是計算距離，將它們與閾值進行比較並計算對象。這是它的一個關鍵優勢，它可以很容易地應用於各種數據，所有你需要的是定義一個距離函數和閾值。

我懷疑有一個DBSCAN版本，因爲它依賴於成對距離。你可以修剪這些計算中的一部分（這是索引起作用的地方），但基本上你需要將每個對象與其他對象進行比較，所以它在O(n log n)而不是一遍。

單程：我相信最初的k-means是一個一遍算法。前k個對象是你的初始手段。對於每個新對象，您選擇關閉平均值並用新對象更新（增量）。只要你不對數據集做另一次迭代，這就是「一次通過」。 （雖然結果會比勞埃德風格的K-means更糟糕）。