柚子快報激活碼778899分享：聚類 算法 多示例學習回顧
文章目錄
1、聚類：· K-Means· Bamic· Density Peak· SMDP· MIDIE
2、嵌入· Bamic· SMDP· MIDIE· ELDB· miGraph
3、距離度量
1、聚類：
剛接觸的聚類算法就是K-Means，當時也通過復現了算法代碼來理解了原理。在后面的許多論文中，都利用了聚類的思想。聚類的最主要思想為：找到一簇數據中的最具代表性的數據作為代表，并以此來代表某一類別的數據。再通過度量其他數據與這些代表的相似性實現分類。
· K-Means
主要原理見這篇文章，主要是通過這個算法來理解聚類的意義。
· Bamic
該算法是基于包，距離度量方式為豪斯多夫距離。論文閱讀見這一篇，代碼見這一篇。
這個算法與K-Means有一定關聯，因為算法利用K-Medoids算法進行聚類：隨機選出K個點作為中心，計算每個簇的平均距離，并通過平均距離找到新的中心，依次迭代，直到中心不再變化為止。
在嵌入方面，Bamic通過計算每個包與k個中心的距離，將包映射為k維的特征向量，每一維都是該包與第k個中心的間距。得到映射向量后，再進行分類處理。
· Density Peak
參考這篇文章，算法的核心思想是：密度比鄰居節(jié)點高、與比其密度大的點的距離相對大的點是聚類中心。目的是為了找到最具代表性的點 算法中的一些具體細節(jié)會在SMDP中提到。
DP算法將密度
ρ
\rho
ρ與距離
δ
\delta
δ組合成為
(
ρ
,
δ
)
(\rho, \delta)
(ρ,δ)并映射到二維空間中進行決策。
· SMDP
該算法是基于包，距離度量方式為豪斯多夫距離。論文閱讀見這一篇，代碼在這一篇。 算法以Density Peak為基礎，找出數據集中的代表包，并將其利用到多示例學習中。SMDP的算法思想為：通過計算密度選出那些周圍包數量多的包作為master，這樣的master最具代表性，能夠代表周圍一圈的包。 然后計算每一個包到它們所屬master的距離并映射。最終對映射的向量通過svm等分類器進行分類得到預測結果 。
算法流程圖： 由于cutoff kernel得到的是整數，得到的結果是整數，會出現密度相同的情況，而Gaussian kernel很少出現這種情況。因此常選用高斯核為核函數。下面的MIDIE也同樣使用了高斯核。
之所以求每個包距其master的距離，就是來度量包與每個代表包的相似度，從而判斷這個包的類型。通過距離來側面體現每個包的特征。
該算法在DP的基礎上增加了嵌入，得到每個包的映射向量。最后再對這些向量通過SVM等分類器進行分類。算法利用了聚類的思想，關鍵就是如何找到最具代表性的包。
· MIDIE
該算法是基于實例 ，距離度量方式為歐氏距離。論文閱讀見這一篇，代碼見這一篇。算法沿用了SMDP中的聚類思想來找出代表實例 ，且也包含miGraph中的一些方法。
同樣，MIDIE通過聚類選出了每個包中最能夠代表這個包的實例原型，其中加入了關聯性，在miGraph中也有用同樣的方式來構建affinity matrix。關聯性體現了某個實例與其他實例的關聯程度，若某個實例與周圍實例的關聯性高（距離小于包內實例平均距離），則該實例稱為實例原型的幾率越大。 MIDIE同時考慮了密度與關聯性，從兩個角度綜合起來選出了一個包中最具代表性的那一個實例原型，構成了實例原型池。
在代表實例選擇階段，則依舊沿用了SMDP中的思想來選出實例原型中的代表實例。這一階段與SMDP差別不大，同樣考慮了每個實例原型的重要性與獨立性，都是通過計算密度與距離來計算得分，并選出實例原型。從實例原型池中選出代表實例，更能凸顯出代表實例的代表性。
算法流程圖：
在映射部分，與SMDP不同，MIDIE是通過差值來體現每個包的特征。若差值較小，則說明該實例與其代表實例差別不大，則為同一類別的可能性越大；反之則越小。
2、嵌入
· Bamic
通過Bamic算法得到k個簇與中心后，通過計算N個包與k個中心的距離，將每個包映射為k維向量，最后再通過預測算法對嵌入后的向量進行處理。
由于每個中心都能夠代表一種特征，因此計算每個包與中心的距離就能夠體現每個包的所屬特征，就能夠對該包的向量進行預測。
· SMDP
通過DP聚類得到每個包的master以及它們的距離后，通過計算每個包到
n
c
n_{c}
nc?個中心的距離，映射為
n
c
n_{c}
nc?維特征向量 。最后再通過預測算法對嵌入后向量進行分類處理。
這里的嵌入方式與Bamic類似。
· MIDIE
MIDIE是通過差值來體現每個包的特征。若差值較小，則說明該實例與其代表實例差別不大，則為同一類別的可能性越大；反之則越小。計算每個包中的實例與其對應的實例代表作差值處理，并將每個包中差值處理后的實例疊加，得到這個包的映射向量。
· ELDB
論文閱讀在這一篇，代碼在這一篇。
算法的映射方式為：計算每個包
B
i
B_{i}
Bi?與判別包集合
T
e
\mathcal{T}_{e}
Te?中之間的平均豪斯多夫距離來度量關聯性：
f
b
(
B
i
,
T
e
)
?
b
i
=
[
b
i
ζ
1
,
.
.
.
,
b
i
ζ
ψ
]
f_(\mathbf B_{i},\mathcal{T}_{e})\mapsto \mathbf b_{i}=[b_{i\zeta_{1}},...,b_{i\zeta_{\psi }}]
fb?(Bi?,Te?)?bi?=[biζ1??,...,biζψ??] 其中，
b
i
k
=
∣
∣
x
i
ˉ
?
x
k
ˉ
∣
∣
b_{ik}=||\bar{\mathbf{\mathit{x}}_{i} }-\bar{\mathbf{\mathit{x} }_{k}} ||
bik?=∣∣xi?ˉ??xk?ˉ?∣∣，
x
i
ˉ
=
∑
j
=
1
n
i
x
i
j
/
n
i
\bar{x_{i}}=\sum_{j=1}^{n_{i}}x_{ij}/n_{i}
xi?ˉ?=∑j=1ni??xij?/ni?。
判別包集合就是包集合中最具區(qū)分度的包 ，也就是代表包集合，與其他包差別大的包。通過映射，能夠得到每個包與代表包之間的差別，映射為向量
b
i
\mathbf b_{i}
bi?。
此外，ELDB擁有判別性分析技術，即使得
T
d
\mathcal{T}_3ih7pjjnjzpn
Td?中任意兩個不同標簽的包之間距離累積之和最大；任意兩個相同標簽的包之間距離累積之和最?。?/p>
max
?
T
e
?
T
d
?
T
J
(
T
d
,
T
e
)
=
1
2
∑
B
ξ
i
,
B
ξ
j
∈
T
d
d
i
j
δ
i
j
\max_{\mathcal{T} _{e}\subseteq \mathcal{T} _3ih7pjjnjzpn\subset \mathcal{T}}\mathcal{J}(\mathcal{T}_3ih7pjjnjzpn,\mathcal{T}_{e})=\frac{1}{2} \sum_{B_{\xi _{i}},B_{\xi _{j}}∈\mathcal{T}_3ih7pjjnjzpn}^{} d_{ij}\delta _{ij}
Te??Td??Tmax?J(Td?,Te?)=21?Bξi??,Bξj??∈Td?∑?dij?δij? 其中，
d
i
j
d_{ij}
dij?為包間距離，
δ
i
j
\delta _{ij}
δij?為bag-link矩陣中對應位置的值。若兩個包對應標簽相同，則為
λ
\lambda
λ，否則為
?
λ
-\lambda
?λ。意味著標簽不同的包之間區(qū)別越大，這個矩陣也能夠凸顯包與包之間的區(qū)別：
δ
i
j
=
{
λ
i
j
,
y
ξ
i
≠
y
ξ
j
?
λ
i
j
,
y
ξ
i
=
y
ξ
j
\delta _{ij}=\begin{cases} \lambda _{ij}, y_{\xi _{i}}\ne y_{\xi _{j}}\\ -\lambda _{ij}, y_{\xi _{i}}= y_{\xi _{j}} \end{cases}
δij?={λij?,yξi??=yξj???λij?,yξi??=yξj???
· miGraph
論文閱讀在這一篇。miGraph提供了一種全新的思路，將包映射為一個affinity matrix：若包內實例間距大于閾值，矩陣對應位置的值置為1，否則為0。這也是MIDIE算法在衡量實例關聯性時的做法。
映射部分，miGraph設計了一個Graph Kernel來度量包與包之間的相似性（關聯性）。計算每一個包與其他包之間的相似性并映射為向量。該方法依然離不開距離度量，因為核函數中處理了affinity matrix，而affinity matrix中數據是通過距離計算得到的。
3、距離度量
在多示例學習中，常通過距離來衡量相似性，計算包與包、實例與實例、包與實例的距離。但距離函數又不等同于相似度函數。
所以，要度量包間相似度，距離度量是關鍵一步。距離越近，兩個包就越相似。正如疫情期間，那些接觸過患者的人往往患病幾率就愈大。常通過
d
=
1
?
s
d=1-s
d=1?s、
d
=
?
l
n
(
s
)
d=-ln(s)
d=?ln(s)等來將距離轉換為相似度。因為距離
s
s
s越小，相似度
s
s
s就越大，代表越相似。
在機器學習中有許多距離度量方式，這篇文章很好的總結了各自距離度量方法。在目前已經閱讀的論文中，最常見的距離公式為Hausdorff Distance與Euclidean Distance 。前者用于度量包間的距離，后者用于度量實例間的距離。在miGraph中使用了Gaussian Distance。
算法SMDPMIDIEELDBBamicmiGraph度量方式豪斯多夫歐氏豪斯多夫豪斯多夫高斯
歐式距離計算公式：
d
(
x
,
y
)
=
∑
i
=
1
n
(
x
i
?
y
i
)
2
d(x,y)=\sqrt{\sum_{i=1}^{n}(x_{i}-y_{i})^{2}}
d(x,y)=i=1∑n?(xi??yi?)2
?
豪斯多夫距離是基于歐式距離的，用于描述兩個集合之間的相似程度，因此也適用于度量多示例學習中包間相似度。又分為：最小Hausdorff距離、平均Hausdorff距離、最大Hausdorff距離。選用哪一種通常是通過做實驗后，找出性能最佳的一個作為最終的算法距離度量方式。
由于不同數據集包中的實例分布的不同，需要選擇不同的距離度量方式。一般分為：1）數據相關型；2）數據不相關型。
1）數據相關型：指的是計算距離時需要依據其他對象來計算，公式一般為
d
i
s
t
a
n
c
e
(
A
,
B
,
媒介
)
distance(A,B,媒介)
distance(A,B,媒介)
2）數據不相關型：指的是直接計算距離而不需要其他對象作為媒介，如豪斯多夫距離，公式一般為
d
i
s
t
a
n
c
e
(
A
,
B
)
distance(A, B)
distance(A,B)
由于距離能夠計算包與包的特征值之間的關系，而包的特征值往往能夠代表這個包的類別、性質。對于不同的數據分布。這一切都與數據分布有關?？梢酝ㄟ^對不同的算法試驗不同的距離度量方式，找出最適合算法的距離。
柚子快報激活碼778899分享：聚類 算法 多示例學習回顧
推薦文章
本文內容根據網絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉載請注明，如有侵權，聯系刪除。
Roku跨境娛樂坊
