比較空間群集合.doc

比較空間群集合Michael H. Coen M. Hidayath Ansari Nathanael Fillmore University of Wisconsin-Madison, 1300 University Ave, Madison, WI 53706 USA摘要本文提出了一種比較群集合，同時(shí)用了劃分與幾何的新方法。我們的做法是出于以下觀察：以前比較群集合技術(shù)絕大多數(shù)是完全劃分的，也就是說(shuō)，他們?cè)谠O(shè)置檢查點(diǎn)理論方面的任務(wù)后，他們已分區(qū)。在這樣做時(shí)，這些方法忽略了數(shù)據(jù)的空間布局，與事實(shí)相反的，這些信息在開(kāi)始的時(shí)候是用于生成群集合。我們表示這導(dǎo)致了各種各樣的失敗模式。之前的比較技術(shù)往往不能區(qū)分被聚集在數(shù)據(jù)作出重大改變。我們制定一個(gè)比較新的措施，用最優(yōu)化理論空間和劃分的信息結(jié)合群集合到一個(gè)單一的措施。這樣做消除了以前的辦法病態(tài)的狀態(tài)。它也同時(shí)刪除一些常見(jiàn)的限制，例如每個(gè)集群必須有相同數(shù)量的群集或他們?cè)谙嗤臄?shù)據(jù)集。這種方法是穩(wěn)定的，易于實(shí)現(xiàn)，具有較強(qiáng)的直觀的吸引力。1. 簡(jiǎn)介本文提出了一種比較群集合同時(shí)用了劃分與幾何的新方法。我們呼吁我們的新的比較函數(shù)聚類距離或C距離。我們認(rèn)為，這是第一個(gè)比較群集合根據(jù)其空間屬性以及它們的群集成員分配原則的做法。我們認(rèn)為，作為一個(gè)坐落在一個(gè)空間與距離相關(guān)的功能點(diǎn)集合劃分聚類。這種看法是自然的，因?yàn)榱餍械木垲愃惴?，如均值，譜聚類，親和傳播等，不僅作為輸入一個(gè)將要聚集點(diǎn)的集合，而且對(duì)空間中的點(diǎn)在于距離的函數(shù)。這個(gè)距離函數(shù)可以指定含蓄，它可能是由一個(gè)內(nèi)核改變，但它必須定義這種或那種方式，其性質(zhì)是至關(guān)重要的一個(gè)聚類算法的輸出。與此相反，幾乎所有現(xiàn)有的集群技術(shù)比較忽略兩點(diǎn)之間的距離，原子當(dāng)作具體形式表現(xiàn)出來(lái)的分區(qū)聚類。雖然這種做法在某些情況下具有一些優(yōu)點(diǎn)，他好像是很大程度上的忽略了用來(lái)構(gòu)建聚類的距離函數(shù)。這樣做似乎摒棄了在某種意義上是最基本的信息。事實(shí)上，在第3節(jié)中，我們表現(xiàn)出了群集合有威不同的空間屬性，但實(shí)質(zhì)上是幾乎所有以前的聚類技術(shù)比較難以區(qū)分?jǐn)?shù)量。其中一個(gè)例子是在圖1。只有一個(gè)現(xiàn)有的集群比較，我們發(fā)現(xiàn)可以區(qū)分最左邊的參考集群及其兩個(gè)修改到正確的技術(shù)，我們審查在第3節(jié)中有一個(gè)例外的弱點(diǎn)。本文的主要貢獻(xiàn)是一個(gè)比較群集合，考慮到他們的空間屬性需要的新技術(shù)。特別是，我們的技術(shù)回答了這個(gè)問(wèn)題：如何做兩井群集合點(diǎn)“重疊“在一個(gè)特定的空間因此，我們的技術(shù)并不只評(píng)估作業(yè)點(diǎn)的分區(qū)，它也考慮到了每個(gè)點(diǎn)的位置？集群，該集群的形狀和集群之間的空間關(guān)系。通過(guò)將空間信息，我們的方法提供了一些額外的好處。首先，我們可以比較無(wú)法被許多其他技術(shù)考慮群集合，具體而言，我們可以比較群集合：（1）不同位置的點(diǎn);（2）不同數(shù)量的點(diǎn);和（3）不同數(shù)量集群。我們不知道其他群集比較技術(shù)，允許這樣的條件下都比較同步，特別是條件（1）及（2），大部分是在文獻(xiàn)中得到解決。最后，相對(duì)于其他一些辦法，我們的工作還擴(kuò)展了一個(gè)簡(jiǎn)單的方法來(lái)軟的（非劃分的）聚類。我們briey在回顧一些應(yīng)用中，聚類距離是有益的。 （1）由于集群是一種無(wú)監(jiān)督學(xué)習(xí)技術(shù)，比較了聚類算法的輸出是困難的。在某些情況下，有可能是一個(gè)黃金標(biāo)準(zhǔn)是我們希望我們的算法同意。測(cè)出的黃金標(biāo)準(zhǔn)聚類算法的輸出提供了距離該算法是否是一個(gè)合適的定域的重要見(jiàn)解。 （2）我們可以探索通過(guò)反復(fù)抽樣DataSet和比對(duì)彼此的算法的結(jié)果的聚類算法的結(jié)果對(duì)數(shù)據(jù)集的穩(wěn)定。（3）如果兩個(gè)聚類算法的產(chǎn)出傾向于同意某些數(shù)據(jù)類型，我們可能更愿意用較低的計(jì)算復(fù)雜性算法比較算法，輸出可以讓我們這種決心。 （4）最后，在合奏聚類，我們可以采用的聚類算法，利用數(shù)學(xué)的data.Asking為不同屬性，如果它們的輸出都劃分與幾何兼容增加了一個(gè)額外的維數(shù)進(jìn)行比較等。2. 方法在本節(jié)中，我們描述新的聚類比較技術(shù)連同上計(jì)算其價(jià)值的群集合對(duì)算法。我們首先做一個(gè)精確的描述集群概念和一些需要制定我們的方法的先決條件。2.1.聚類A (hard)聚類A是一個(gè)集成集12K稱為集群（這句實(shí)在是難以翻譯） 如下我們假設(shè)，因此1K，是一個(gè)度量空間（，）的有限子集。2.2. 優(yōu)化運(yùn)輸距離運(yùn)輸問(wèn)題的最佳(Hillier & Lieberman, 1995; Rachev & Ruschendorf, 1998) 提出了什么是最便宜的方式將一個(gè)設(shè)置為從源匯的群眾，誰(shuí)是一段距離？這里的成本是指總質(zhì)量科幻移動(dòng)距離。例如，可以考慮作為源和匯的工廠作為倉(cāng)庫(kù)，使問(wèn)題具體。我們假設(shè)的來(lái)源是航運(yùn)多匯的質(zhì)量完全一樣的期待。從形式上看，在優(yōu)化運(yùn)輸問(wèn)題，我們得到的加權(quán)點(diǎn)集 ( ) 和( ), 其中=1 |A|是一個(gè)度量空間有限子集( ), = (1 |A|)是一個(gè)相關(guān)的非負(fù)權(quán)重向量總結(jié)為一個(gè)，并舉行類似的定義和。最佳的運(yùn)輸距離在( )和( )之間，定義為其中最佳流量在()和()之間是最小的線性規(guī)劃求解這是非常有用的觀點(diǎn)作為一種合作方式的最大來(lái)源之間傳輸和接收器的最佳超重群眾代表。在這里，合作意味著源“同意“一個(gè)全球最小的運(yùn)輸成本的群眾。2.3.幼稚的運(yùn)輸距離按照上文提出的優(yōu)化算法相比，在這里我們定義一個(gè)天真的解決交通問(wèn)題。在這里，所有的來(lái)源是個(gè)別群眾按比例分配給他們匯負(fù)責(zé)。這種情況下, 沒(méi)有一個(gè)合作源,導(dǎo)致運(yùn)送到各節(jié)點(diǎn)的整體質(zhì)量效率低下。從形式上看，在幼稚的運(yùn)輸距離問(wèn)題，我們得到的加權(quán)點(diǎn)集（）和（）如上。我們定義在（）和天真的運(yùn)輸距離（）為2.4. 相似距離我們的下一個(gè)最佳之間的運(yùn)輸距離和運(yùn)輸距離的關(guān)系如何界定幼稚的關(guān)注。在這里，我們感興趣的是合作程度，降低了移動(dòng)源到接收器的成本。從形式上看, 我們得到的加權(quán)點(diǎn)集（）和（）如上。我們定義在（）和相似距離（）為當(dāng)和完全重疊，沒(méi)有成本轉(zhuǎn)移到，所以無(wú)論是最佳的運(yùn)輸距離和距離的相似性，是0。另一方面，從時(shí)間和彼此非常遙遠(yuǎn)，每一個(gè)點(diǎn)更接近點(diǎn)，比所有其他的任何點(diǎn)，反之亦然。因此，在這種情況下，合作不產(chǎn)生任何明顯的好處，所以O(shè)T是幾乎和NT一樣大，S為接近1。 （此行為是如圖2，圖2PDF上顯示不出）。在這個(gè)意義上說(shuō)，兩個(gè)點(diǎn)集之間的相似距離的措施在何種程度上他們空間重疊，或者是“類似”，給對(duì)方。 （請(qǐng)注意，這種關(guān)系實(shí)際上是逆;相似距離是空間重疊度從一中減去。）另一個(gè)例證是這種行為在圖3中給出。圖中的每個(gè)面板顯示兩個(gè)重疊的點(diǎn)集是我們的重量分配均勻分布。度的空間點(diǎn)集的兩個(gè)重疊的例A是遠(yuǎn)遠(yuǎn)高于空間的點(diǎn)重疊度在例B，盡管在絕對(duì)數(shù)量方面的工作需要，以最佳移動(dòng)一個(gè)點(diǎn)上設(shè)置另一種是多在例A比例B更高。2.5. 聚類距離接下來(lái)我們定義我們的聚類距離新措施。我們的目標(biāo)是建立一個(gè)群集合之間的距離測(cè)量，抓住兩個(gè)關(guān)于群集合空間和劃分的信息。從概念上講，我們的方法如下。給定一個(gè)群集合A和B對(duì)，我們首先構(gòu)造一個(gè)新的度量空間|其中包含每個(gè)群集在A和B之間定義不同的元素，我們?nèi)魏蝺蓚€(gè)元素的距離|從度量空間，獨(dú)特的原始數(shù)據(jù)的謊言這一新的空間是對(duì)應(yīng)的最佳聚類之間交通距離。該群集合A和B可以被認(rèn)為是在這一新的空間加權(quán)點(diǎn)集，以及A和B之間的相似程度可以被認(rèn)為是對(duì)空間之間的對(duì)應(yīng)的加權(quán)點(diǎn)集在這一新的空間重疊度。從形式上看，我們得到的數(shù)據(jù)集和度量空間（）群集合A和B。我們定義集群A和B之間的距離（CDistance）作為量重量= 及 = 是成正比的點(diǎn)的群數(shù)，并在距離之間集群A且B的OT是最佳的運(yùn)輸距離均勻的 weights = (1 | | ) and = (1 | | )。一個(gè)eficient聚類算法來(lái)計(jì)算的距離是很容易派生自定義。設(shè)A B和如上。步驟 1. 對(duì)于每一個(gè)集群對(duì)（）AB, 計(jì)算最優(yōu)的運(yùn)輸距離 ，基礎(chǔ)上，根據(jù)在與點(diǎn)之間的距離。步驟 2. 相似距離計(jì)算S(A B; OT) 群集合之間的A和B，在最佳的運(yùn)輸距離OT在A和B之間在步驟1計(jì)算集群。調(diào)用此量的聚類距離（AB公司）之間的A和B群集合。讀者會(huì)發(fā)現(xiàn)，我們使用最佳的運(yùn)輸距離來(lái)衡量之間（步驟1）個(gè)別聯(lián)網(wǎng)的距離，而我們使用相似距離來(lái)衡量群集合之間作為一個(gè)整體（步驟2）的距離。此difierence原因如下。在步驟1中，我們有興趣在集群之間的絕對(duì)距離：我們想知道多少工作是需要在一個(gè)集群移動(dòng)到其他群集的所有點(diǎn)。我們將使用一本怎樣的措施“遠(yuǎn)”是一組從另一個(gè)。與此相反，在步驟2中，我們想知道在何種程度上在一個(gè)聚類簇在另一個(gè)空間與使用步驟1源性的距離聚類重疊。我們選擇在步驟1中統(tǒng)一使用權(quán)，但在第2步比例權(quán)重也有類似的動(dòng)機(jī)。在（硬）集群，集群中的每個(gè)點(diǎn)給予很大的貢獻(xiàn)，作為為集群中的其他任何點(diǎn)群的貢獻(xiàn)，所以我們?cè)诒容^重點(diǎn)均勻個(gè)別聯(lián)網(wǎng)。與此相反，第2步中按比例分配的CDistance整體計(jì)算每個(gè)群集inuence根據(jù)其相對(duì)權(quán)重，由它包含的數(shù)據(jù)點(diǎn)的數(shù)量而定。（這里圖3也是沒(méi)有的）2.5.1.計(jì)算復(fù)雜性該算法的計(jì)算復(fù)雜性上面介紹CDistance是由計(jì)算優(yōu)化運(yùn)輸距離的復(fù)雜性為主。優(yōu)化兩個(gè)點(diǎn)集的基數(shù)運(yùn)輸距離最多可以計(jì)算在最壞情況下（3 log）時(shí)間(Shirdhonkar & Jacobs, 2008). 最近的線性或次線性時(shí)間近似算法已被開(kāi)發(fā)為最優(yōu)運(yùn)輸問(wèn)題的若干變種，例如(Shirdhonkar & Jacobs, 2008; Ba et al., 2009). 為了驗(yàn)證我們的方法是在實(shí)踐中eficient，我們測(cè)試的最佳運(yùn)輸距離計(jì)算，它使用的幾百萬(wàn)元的大型點(diǎn)對(duì)運(yùn)輸單純形算法，從一個(gè)集多種采樣高斯分布我們的實(shí)現(xiàn)。平均運(yùn)行時(shí)間符合表達(dá)式具有的價(jià)值，其中是兩個(gè)點(diǎn)集進(jìn)行比較基數(shù)較大秒。對(duì)于龐大的點(diǎn)集，可以采用標(biāo)準(zhǔn)分級(jí)技術(shù)，以進(jìn)一步降低運(yùn)行(Levina & Bickel, 2001).與此相反，唯一的空間感知聚類的比較方法，我們知道需要明確列舉集群之間的匹配所有可能的排列指數(shù)在B空間到群集 (Bae et al., 2006).3. 對(duì)相關(guān)工作比較在表1中，我們提出，演示了比較流行的技術(shù)不敏感群集合之間的空間difierences簡(jiǎn)單的例子。我們的方法很簡(jiǎn)單：每個(gè)技術(shù)，我們提出了一個(gè)基準(zhǔn)參考集群。然后，我們把它比作另外兩個(gè)群集合，它不能區(qū)分，即比較法分配給這些群集合每個(gè)從基線相同的距離。然而，在每種情況下，與基準(zhǔn)相比群集合顯著彼此威不同，從空間，既直觀的角度，根據(jù)我們的測(cè)量，CDistance。我們?cè)诒?的目的是要顯示，相互競(jìng)爭(zhēng)的方法是無(wú)法檢測(cè)的改變，即使出現(xiàn)時(shí)明確指出，不平凡的變化已經(jīng)發(fā)生。這些例子的本意是說(shuō)教，因此，只有足夠的積分是要說(shuō)明組成。由于在這些方法中最限制，所有，但在表1顯示了相同的套群集合點(diǎn)的一個(gè)例子。更復(fù)雜的數(shù)據(jù)集和其他技術(shù)進(jìn)行比較群集合更多的討論在第4節(jié)進(jìn)行檢查。我們briey審查表1所示的技術(shù)。其中群集合進(jìn)行比較的方法，是已知最早的Jaccard指數(shù)(Ben-Hur et al., 2002). 它衡量的是不同的分區(qū)分配上同意的部分. 蘭德指數(shù)(Rand,1971)，在已知的技術(shù)中最好的是，基于點(diǎn)分配的變化。計(jì)算方法是由點(diǎn)分?jǐn)?shù)-采取成對(duì)- 他的任務(wù)是兩個(gè)群集合是一致的。這種方法已建立在許多人。比如， (Hubert & Arabie, 1985) 地址蘭德指數(shù)的高估數(shù)據(jù)集上隨機(jī)聚集相似人所共知的問(wèn)題。這三項(xiàng)措施是元組的聚類計(jì)算或基于集合的成員基礎(chǔ)的比較技術(shù)的一般類的一部分。在這個(gè)類別中的其他措施包括Mirkin, van Dongen, Fowlkes-Mallows,和Wallace indices, 其中一個(gè)在討論中可以發(fā)現(xiàn)(Ben-Hur et al., 2002; Meilfia, 2005).變化的信息的方法是由(Meilfia, 2005)，定義了信息理論群集合之間的度量。它的措施的信息丟失，在移動(dòng)到另一個(gè)從一個(gè)聚類在同一組點(diǎn)，上漲。在工作中提出(Zhou et al., 2005) 我們的股票納入一些距離比較群集合概念的動(dòng)力。然而，距離超過(guò)指標(biāo)計(jì)算每個(gè)集群載體空間，每個(gè)數(shù)據(jù)點(diǎn)代表是否是它的一個(gè)成員。因此，隨著集群相似的測(cè)量只在它們的共同點(diǎn)的身份條件，不考慮到這些點(diǎn)的空間位置。最后，我們研究ADCO (Bae et al., 2006)，其中介紹了唯一的方法，直接雇用的空間信息。這種方法垃圾箱所有點(diǎn)，然后確定每個(gè)群集在垃圾箱密度。兩群集合之間的距離被定義為兩兩集群密度最小的點(diǎn)產(chǎn)品的總和（從分級(jí)派生），比相匹配的集群采取所有可能的排列。這一般不是一個(gè)可行的計(jì)算，箱的數(shù)目呈指數(shù)增長(zhǎng)的空間維度，檢查所有集群之間的匹配需要O（?。r(shí)間復(fù)雜度，是集群數(shù)量。4. 再評(píng)價(jià)在本節(jié)中，我們考察一個(gè)數(shù)據(jù)集的范圍更廣CDistance。我們的目標(biāo)是要了解它的動(dòng)態(tài)行為，以及如何在集成方法和評(píng)價(jià)的穩(wěn)定使用。4.1.例子比較圖4說(shuō)明了CDistance.In一些示例輸出每個(gè)子圖，我們是在比較兩個(gè)群集合，其中一個(gè)已被翻譯為可視化的目的。例如，在圖4（a），兩群集合空間重疊好極了，他們的群集的距離是零。匹配集群是連接線，以說(shuō)明他們的信件。 （這些行drawnsolely可視化的目的。）最有趣的面板圖4（d），這表明在一個(gè)形狀對(duì)稱生產(chǎn)與使用的算法不穩(wěn)定的聚類。譜聚類對(duì)這些數(shù)據(jù)的重復(fù)使用產(chǎn)生非常威不同的結(jié)果。乘聚類數(shù)據(jù)集可以讓我們衡量是否算法/數(shù)據(jù)集的結(jié)合是相互兼容。4.2. 連續(xù)性和穩(wěn)定性的CDistance圖5說(shuō)明了CDistance為小群集合增量變化的平滑度。圖5（d）是一個(gè)參考之間的CDistance聚類圖，繪制在圖5（a）和聚類輪換由0 2弧度。考慮圖6聚類（一），其中包含從表1（A）與例4相同的數(shù)據(jù)集。假設(shè)我們逐步增加，對(duì)藍(lán)色三角形組成的集群坐標(biāo)。在每一步中，我們修改后的數(shù)據(jù)集之間計(jì)算和參考圖6聚類都ADCO和CDistance（一）。其結(jié)果是繪制在圖6（b）項(xiàng)。我們看到，從搖擺和不連續(xù)性由于移動(dòng)數(shù)據(jù)之間的離散垃圾箱突然轉(zhuǎn)變ADCO sufiers。由于這種行為的結(jié)果，ADCO的價(jià)值觀是難以直觀解釋的。4.3. 子采樣和穩(wěn)定性在本小節(jié)，我們說(shuō)明如何CDistance可以用來(lái)比較來(lái)自子采樣數(shù)據(jù)集的聚類。Ben-Hur 等人(2002) 提出了一個(gè)穩(wěn)定的群集可以通過(guò)反復(fù)的數(shù)據(jù)集的聚類子樣品確定。查找一致群集合很高的相似性表明在尋找類似的一致性數(shù)據(jù)集中的子結(jié)構(gòu)。這可以增加一個(gè)算法的適用性信心特定的數(shù)據(jù)分布。換句話說(shuō)，通過(guò)比較產(chǎn)生的群集合，可以得到一