資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學什麼是ROCK？
ROCK代表使用連結的魯棒聚類。這是一種層次聚類演算法，它分析連結的概念（兩個物件之間共同鄰居的數量）來處理具有類別屬性的資料。它表明，在對類別資訊進行聚類時，這種距離資料無法產生高質量的聚類。
此外，大多數聚類演算法在聚類時只建立點之間的相似性，即在每一步中，將組合成單個聚類的點。“區域性”方法容易出現錯誤。例如，兩個不同的聚類可以有一些接近的點或異常值；因此，依賴點之間的相似性來做出聚類決策可能會導致將這兩個聚類組合在一起。
ROCK透過處理單個點對的鄰域來採用更全域性的聚類方法。如果兩個相似的點也具有相同的鄰域，則這兩個點很可能屬於相同的聚類，因此可以組合在一起。
如果sim(pi, pj) ≥ θ，則存在兩點pi和pj是鄰居，其中sim是相似性函式，θ是使用者指定的閾值。可以選擇sim作為距離度量，甚至是非度量，只要將其標準化，使其值介於0和1之間，較高的值表示點越相似。
pi和pj之間的連線數表示為pi和pj之間共同鄰居的數量。如果兩點之間的連結數很高，則它們更可能屬於相同的聚類。透過處理個體點群之間關係中的相鄰資料點，ROCK比僅針對點相似性的標準聚類方法更強大。
包含類別屬性的資料例項是市場籃子資訊。此類資料包括一個事務資料庫，其中每個事務是一組專案。事務被視為具有布林屬性的資料，每個屬性對應於一個專案，例如麵包或乳酪。
在事務資料中，如果事務包含該專案，則對應於該專案的屬性為真；否則為假。可以用相同的方式管理幾個具有類別屬性的資料集。ROCK中兩點或事務Ti和Tj之間的鄰居和連結的概念用Jaccard係數表示為
$$\mathrm{sim(T_{i},T_{j})=\frac{|T_{i} \cap T_{j}|}{|T_{i} \cup T_{j}|}}$$
ROCK首先利用相似性閾值和共享鄰居的方法，從給定的資料相似性矩陣生成稀疏圖。它可以在稀疏圖上實現凝聚層次聚類。可以使用一種優度量來計算聚類。可以使用隨機抽樣來擴充套件到大型資料集。
ROCK的最壞情況時間複雜度為O(n2 + nmmma + n2logn)，其中mm和ma分別表示最大和平均鄰居數，n是物件的個數。
4K+ 次檢視
