簡述

最近發現一篇有趣的論文。關于限制性的kMeans. 主要思想是基于boosting principle的COP-kMeans。所以，我就先研究了下COP-kMeans。

COP-kMeans

是一種限制性聚類算法。限制性的含義很簡單，就是需要考慮到有些節點在聚類前，我們就知道了這個兩個節點是應該放在一起，還是應該分開。

所以，這里有兩類。最簡單的想法，就是這里用一個二維矩陣來存儲這個信息。
COP-kMeans，從名字上看，就知道這是一個基于kMeans的算法。

Python實現

• 比較奇怪的點，這里我使用了一個函數內的函數定義。主要是考慮到了封閉性所以這樣實現~
• 關于使用： 在策略上，我用了最簡單的策略。而且還存在有病態初始化的可能。所以，可能會出現一只被報錯的情況~ 不用擔心，多進行幾次測試就好了，或者，你也可以直接改我的代碼~
• 代碼實現上，基于我之前寫過的k-Means. 只是加了一個驗證的部分而已~
• 耗時上也比kMeans要高，畢竟每次都需要檢查兩個表~

補充說明

在評論區的小哥提示下，我做了con的補充。意外發現代碼有些小問題。這里補充下。

• Con1和Con2是兩個限制矩陣，大小規模為n*n，n為X的長度，即元素數量。
• Con1是要保證在一個組的限制，Con2是要保證不在一個組的限制
• 沒有限制就為0，存在限制就非0.

def COP_K_means(X, n_clusters=3, Con1=None, Con2=None):clusters = np.random.choice(len(X), n_clusters)clusters = X[clusters]labels = np.array([-1 for i in range(len(X))])def validata_constrained(d, c, Con1, Con2):for dm, value in enumerate(Con1[d]): # should in the same groupif value == 0: continueif labels[dm] == -1 or labels[dm] == c: # has not allocated or ...continueif labels[dm] != -1 and labels[dm] != c: # has allocatedreturn Falsefor dm, value in enumerate(Con2[d]): # cannot in the same groupif value == 0: continueif labels[dm] == -1 or labels[dm] != c: # has not allocated or ...continueif labels[dm] != -1 and labels[dm] == c: # has allocatedreturn Falsereturn Truewhile True:labels_new = np.array([-1 for i in range(len(X))])for i, xi in enumerate(X):close_list = np.argsort([np.linalg.norm(xi - cj) for cj in clusters])unexpect = Truefor index in close_list:if validata_constrained(i,index, Con1, Con2):unexpect = Falselabels_new[i] = indexbreakif unexpect:raise Exception("Can not utilize COP-k-Means algorithm inside the dataset.")if sum(labels != labels_new) == 0:breakfor j in range(n_clusters):clusters[j] = np.mean(X[np.where(labels_new == j)], axis=0)labels = labels_new.copy()return labels

• 效果~ 可以跟之前的kMeans進行對比
  

總結

以上是生活随笔為你收集整理的COP-kMeans限制性--kMeans变体算法研究的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。