AP算法誕生于2007年，由于其算法的簡單性以及性能的優越性，得以廣泛應用，成為K-Means外的又一大常用聚類算法；
K-Means聚類自身的缺陷在于要人為選取聚類數量以及初始點，算法的性能也完全依賴于上述選擇，與K-Means相比，AP避免了此類人工選擇，将資料點對之間的相似性度量作為輸入，它的核心在于“message passing資訊傳播”，主要目的為了找到一個樣例的典型，即能夠代表每一個聚類的樣本。
首先給出兩個定義：
1）資料點之間的相似度表示；它表示兩個點之間的比對程度，如果兩個點差别很大，比如不屬于同一個聚類，那麼這個相似度可以忽略或者直接置為-Inf；
2）偏好程度；它表示一個資料點對于某個樣例适用性的依賴程度，通常可以通過先驗知識來設定；
設有n個資料點：
每兩個點之間的相似度：S(i,j);
AP算法同樣利用多次疊代，并且每一次疊代都進行兩個資訊傳播的過程，來更新兩個矩陣：
1）矩陣R，元素為r(i,k)，這個值用來反映相對于點i的其他樣例，資料點k充當i的樣例的适合程度；
傳播方向：i -> k
2）矩陣A，元素為a(i,k)，這個值用來反映，在其他點都偏好樣例k的條件下，選擇k作為資料點i的樣例的可靠性；
傳播方向：k -> i
初始化：兩個矩陣都設為全零矩陣，按照如下方式更新：
首先，更新矩陣R：
然後，更新矩陣A：
.
具體請看下圖：
關于疊代終止條件，可以有多種不同的選擇，比如可以當小于某一個門檻值或者達到疊代最大次數等等；另外我們可以通過對兩個矩陣求和得到很多有用資訊：對于點i，當r(i,k)+a(i,k)有最大值時，表明k是i的樣例；或者可以利用矩陣主對角線上的元素值資訊，如果r(i,i)+a(i,i)>0，則點i就是一個樣例。
AP算法中，我們無需指定聚類數量，但是當我們得到的聚類達不到最優時，就需要對參數作出調節；幸運的是，在AP算法中，隻需要調節偏好程度就可以改變聚類數量，偏好程度高聚類數就多，因為一個資料點對于一個确定樣例适用的依賴性越高，其被其他樣例介入的可能性就越低，也就不會被其他樣例的聚類所吸收；反之，偏好程度越低，就會導緻聚類數越少，就好比許多資料點都在對同一個樣例說“不，不，你已經是一個很好的榜樣了，我要加入到你的聚類中去”。一般來說，如果希望聚類數偏大，可以把偏好程度設為中等相似度，如果希望聚類數适中，那麼久把偏好程度設為最小相似度，但是具體情況，還需要多次調參以滿足需要。
參考：Clustering by passing messages between data points