資源簡(jiǎn)介

(共21張PPT)
浙教版四年級(jí)上冊(cè)
第13課 數(shù)據(jù)有關(guān)聯(lián)
目錄
CONTENTS
01
KM算法的數(shù)據(jù)關(guān)聯(lián)
02
數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)
03
匈牙利算法的數(shù)據(jù)關(guān)聯(lián)概念
04
作業(yè)布置
05
總結(jié)回顧
匈牙利算法的數(shù)據(jù)關(guān)聯(lián)概念
01
匈牙利算法（Hungarian Algorithm），也稱為Kuhn-Munkres算法，是一種解決指派問(wèn)題（Assignment problem）的優(yōu)化算法。指派問(wèn)題是在給定的任務(wù)和資源之間建立最佳的一對(duì)一分配關(guān)系的問(wèn)題。
具體來(lái)說(shuō)，匈牙利算法解決的是一個(gè)二維的代價(jià)矩陣，其中每個(gè)元素表示將一個(gè)任務(wù)分配給一個(gè)資源的成本或代價(jià)。算法的目標(biāo)是找到一種分配方式，使得總成本最小。匈牙利算法的基本思想是通過(guò)不斷尋找增廣路徑來(lái)找到最佳的分配方式。
1
代價(jià)矩陣德每一行減去改行的最小值。
2
代價(jià)矩陣德每一列減去該列的最小值。
3
用盡量少的線覆蓋矩陣中所有的0，判斷線的數(shù)量是否小于n（矩陣行數(shù)列數(shù)）
4
線的數(shù)量小于n，則需要繼續(xù)減，未被線覆蓋的行或者列繼續(xù)減掉未被覆蓋的最小值，被線覆蓋一次的不參與減，被線覆蓋兩次的反而要加這個(gè)最小值。
5
重復(fù)上面步驟4，直到找到線的個(gè)數(shù)等于n，則得到最終的匹配方案。
匈牙利算法步驟：
最后需要?jiǎng)?4 條線才能覆蓋住矩陣中所有的 0 元素，迭代終止，根據(jù)矩陣中 0 元素的位置很容易得到最終的匹配關(guān)系：目標(biāo)1→目標(biāo)D，目標(biāo)2→目標(biāo)B，目標(biāo)3→目標(biāo)A，目標(biāo)4→目標(biāo)C。這個(gè)匹配滿足構(gòu)成的二分圖上的匹配邊總權(quán)重最小，即總的匹配距離最小，代價(jià)最低。若目標(biāo)和下一幀目標(biāo)個(gè)數(shù)不一致，則需要補(bǔ)0進(jìn)行匈牙利算法。假設(shè)不用匈牙利算法進(jìn)行匹配，而是按照順序進(jìn)行局部最小值匹配。顯然不是最優(yōu)匹配。
KM算法的數(shù)據(jù)關(guān)聯(lián)
02
KM算法
現(xiàn)在常說(shuō)的以及文獻(xiàn)中常提到的匈牙利算法和 Kuhn-Munkres 算法指的是同一個(gè)東西，求解的都是有權(quán)二分圖最小權(quán)匹配問(wèn)題；James Munkres 引入了“標(biāo)星 0（starred zeros）”和“標(biāo)撇 0（primed zeros）”的概念以改進(jìn)匈牙利算法原始流程中的劃線法，在算法執(zhí)行過(guò)程中會(huì)選擇性地對(duì)代價(jià)矩陣中產(chǎn)生的 0 元素標(biāo)記星號(hào)（*）或標(biāo)記撇號(hào)（’）來(lái)輔助搜索增廣路，標(biāo)星 0 表示增廣路中的匹配邊，標(biāo)撇 0 表示增廣路中的未匹配邊。
可以說(shuō)KM算法是對(duì)匈牙利算法進(jìn)行了改進(jìn)和推廣。后來(lái)習(xí)慣將 Munkres 提出的方法稱為 Kuhn–Munkres 算法、KM 算法或 Munkres 分配算法。
有一種觀點(diǎn)認(rèn)為匈牙利算法是不帶權(quán)重的，只用于在圖中尋找最大匹配。而KM算法是用于帶權(quán)重的匹配，求解過(guò)程中包含匈牙利算法。若是此觀點(diǎn)，則上述目標(biāo)跟蹤匹配例子其實(shí)應(yīng)該叫KM算法，因?yàn)榫嚯x度量就是權(quán)重。
01
而另外一種觀點(diǎn)則是匈牙利算法（Hungarian Algorithm），也稱為Kuhn-Munkres算法，是同一種算法的不同叫法。
02
數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)
03
數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)
數(shù)據(jù)關(guān)聯(lián)神經(jīng)網(wǎng)絡(luò)（Data Association Neural Network）是一種利用神經(jīng)網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)關(guān)聯(lián)的方法。在目標(biāo)跟蹤、目標(biāo)識(shí)別和多目標(biāo)追蹤等任務(wù)中，數(shù)據(jù)關(guān)聯(lián)是指將觀測(cè)到的目標(biāo)與已知的目標(biāo)進(jìn)行關(guān)聯(lián)，以確定它們之間的對(duì)應(yīng)關(guān)系。
傳統(tǒng)的數(shù)據(jù)關(guān)聯(lián)方法通常依賴于啟發(fā)式規(guī)則、距離度量或最大后驗(yàn)概率等方法。而數(shù)據(jù)關(guān)聯(lián)神經(jīng)網(wǎng)絡(luò)通過(guò)學(xué)習(xí)數(shù)據(jù)之間的關(guān)聯(lián)模式，從數(shù)據(jù)中自動(dòng)學(xué)習(xí)和推斷目標(biāo)之間的關(guān)聯(lián)關(guān)系。
總結(jié)回顧
04
總結(jié)回顧
02
通過(guò)今天的學(xué)習(xí)有哪些收獲？請(qǐng)分享一下。
作業(yè)布置
05
logo
作業(yè)
繼續(xù)查找有關(guān)數(shù)據(jù)關(guān)聯(lián)的資料，我們下節(jié)課一起分享。
感謝聆聽(tīng)

展開(kāi)更多......

收起↑