如何評價 SIGMOD 2015 最佳論文《DBSCAN Revisited》？

12-27

今年的 SIGMOD 最佳論文頒給了陶宇飛和其學生合作的《DBSCAN Revisited:
Mis-Claim, Un-Fixability, and Approximation》。

這篇文章有意思的地方是證明了著名的 DBSCAN 原始論文《A density-based algorithm for discovering clusters in large spatial databases with noise》存在錯誤，後者 claim 的一個 O(n log n) 的演算法，實際上是基於錯誤的分析，因為那個問題有 $Omega(n^{4/3})$ 的 lower bound。要知道 DBSCAN 的原始論文有 7000+ 的引用量，去年剛剛被KDD頒發 test of time award，從論文發表到現在 17 年的時間裡，居然沒有一個人發現錯誤。（有人提到最開始的論文只是 claim average running time, 後面的論文才 misclaim。感謝指出！抱歉，我應該去查閱一下原始的論文再評論。）

論文里出現錯誤確實非常正常, 我個人也覺得 DBSCAN 的原作者雖然可能會因為此事感到尷尬, 但是並沒有可以指責的地方, 他們的貢獻還是很大的。

我覺得比較尷尬的應該是 KDD, 剛剛給 DBSCAN 非常高的獎, 馬上就被人揪出錯了。陶宇飛說到這個錯誤已經彌散到整個社區，甚至被寫進了教科書和維基百科。此外我覺得陶宇飛的評論：

which perhaps explains why the previous evaluation was done only on small datasets.

其實非常明顯地在說，後續的工作者中應該有不少試過大的數據集，應該已經注意到 DBSCAN 的原始論文里有點問題，他們不是去研究為什麼會有這樣的問題，而是轉而用小數據跑實驗賣自己的文章，以至於讓這個錯誤存在了 17 年。這些人應該才是最尷尬的。

大家對此次事件怎麼看？

不太贊同上面的一些說法。我覺得這不存在尷尬的問題。學術圈最好的地方正是提供了一個開放的討論環境，沒有人總是對的，公開的討論能使學術圈變得更好。

說回dbscan和yufei的這篇paper。

dbscan是個非常實用的演算法，正是因為它的實用性導致了它廣泛的影響力，這是一篇很好的paper。它的問題是作者在分析時只考慮了2-dimensional space，在推論到高維空間時錯誤的認為會有相同的複雜度。

這個問題在工業界和學術界對大數據進行實驗時已有察覺，只是沒有人認真的研究過到底是怎麼回事，而我們應該怎麼補救。yufei的paper很好的闡述和分析了在dbscan在高維空間的lower bound，並提出了解決方案（一個線性近似演算法），這才是最大的貢獻，而不是要打誰的臉。

這兩篇論文都是值得我們學習的好文章，best paper award和test of time award實至名歸。

junhao 他們的 work 很棒，大家也討論的差不多了，關於論文本身我就不多說。
不過，我很反對「庸人的樂趣是看天才摔跤」的觀點套用在這裡。

首先，做研究的或者能在頂級會議上發論文的人和天才之間不能劃等號。天才只是眾多研究人員（包括教授，研究生，研究機構工作人員等）中很小很小的一部分。我接觸過的大部分人，他們能發頂級會議上的論文，是因為他們對所研究的領域有足夠深入的了解。在這種了解的基礎上，加上好的 idea 和流暢的 writing，就有機會發頂級會議的論文。天才和其他人的區別，在於他們了解一個領域的速度和學習有難度的知識的速度。換句話說，你可以覺得只用一年時間就從「對領域的研究幾乎不了解」到「能夠發最頂級的論文」的人是天才。

犯錯總是不可避免的，很多人都這樣認為。確實，科學總在吵吵鬧鬧你推翻我我推翻你之中前進。但這並不代表研究者不知道自己論文中的錯誤與不嚴謹。研究者為了發論文，刻意隱藏自己論文中的紕漏與弱點，是很常見的（當然因人而異）。你很難說清楚一篇論文的作者這樣做到底是有意還是無意。也有研究者覺得自己做的研究根本沒什麼用（我們所說的灌水），但為了能發論文，還是「不得不」去增加學術垃圾。那幾千篇引用了dbscan的論文里，有多少是沒發現錯誤，有多少是發現了錯誤但故意繞開了，這就不得而知了

其實研究人員也是人，發論文說得俗一點其實就是一份工作。有沒有自己的工作原則，有沒有託付自己的夢想，這個因人而異。我不覺得這種職業應該帶來太多的「高高在上」的錯覺。我們不要先入為止，犯錯就是犯錯，和天不天才沒關係。

題外話：聽說他們在做這篇論文的時候，把7000多篇引用了dbscan的論文都下載了下來，一篇篇地看，看是否有論文已經發現了這個問題。這是很難得的。在學術界里，大家發論文都喜歡聲稱自己是第一個發現問題的，但很少有人會真的花那麼多時間去嚴格地檢查這一點。很多的人都直接用一個「據我們所知」就帶過了。

學術進步當然離不開犯錯和糾錯，正常的一件事情
別用「打臉」、「弱菜」這些小學生辭彙來形容他們

這個論文是Yufei在bar里給我講的。所以我可以clarify幾個點。
DBSCAN原文有錯在Yufei的文章以前就有人發現了。（當然無數人還是亂引用nlogn）。
大家不知道的是這個能不能做到nlogn
當然，如果一個seriously搞computational geometry的人馬上能發現這個問題是個叫hopcroft問題的推廣，是不太可能能做到nlogn的（在一個比較general的意義下）。
Surprisingly這篇文章這麼多人引用，這麼多年過去，卻沒有一個真正搞計算幾何的人看過這個問題（Yufei是第一個）。
Yufei這些年做了不少bridging theory and practice的漂亮工作。好像去年還是前年sigmod bestpaper也是他的。

贊一下Yufei Tao，打的漂亮。

計算機的會議論文證明常常有錯（期刊會好一些），很多錯都fix不了。很多人直接把別人會議論文的結論引過來用，根本不檢查對錯。這樣的事見得太多了。

反對最高的那個答案

當然這個錯的有點大，但是沒什麼了不起的……尤其考慮到是DB界的paper……對吧……數學碉堡好的人應該不會來這一行。

DB和理論計算機有交集，還是有很多理論證明的。

再多說幾句。做數學證明，對就是對，錯就是錯，不存在半對半錯。文章發出去，過幾年被人寫個「Comment on XXX」是一件非常丟人的事。CS領域還好，錯了也沒太大代價。要是搞理論數學的人發表幾篇paper 後來被人指出是錯的，這人這輩子就別想再接著發paper了。
（解釋一下，純數學的一篇文章起碼半把月才能讀懂。你發表文章證明了XXX猜想，別人大佬整個group花了3個月看懂，發現尼瑪是錯的；你浪費別人幾個月生命，人家能不發飆么。你這種事犯2次，沒人再去看你paper；你投期刊，你的小領域同行根本不樂意給你審稿）。

所以大家做證明要嚴謹一些，寧可不發表，也不要發出去一篇錯的。

請看清楚dbscan演算法中有兩個關鍵的參數是 EPS, and Min group threshold. 直觀的想法是，如果你的eps很大，min-group-threshold 也很大的時候，那你得到的聚類的類數目就會少很多，那你搜索的時候就可能很快收斂。反之，你就要不斷去search，這樣的話，你的複雜度就上來了的。很可能變成了n^2. 所以說，average 的複雜度在有spatial index的幫助下，是n logn 是可以站的住腳的。

就我自己的感受來看，聚類演算法的running time performance 取決於你的數據分布，聚類參數，以及你是否使用了spatial index.

我就是樓主說的哪一類發現dbscan 很慢而沒有去研究為什麼的人。其實你如果比較了多種聚類演算法的時候，你會發現，其實後面的birch這個演算法就比dbscan+r-tree index 快不少的。但是dbscan的結果比較直觀。追蹤根源，dbscan演算法其實只是很早之前一個圖像處理的演算法裡面的改進的。但是不妨礙dbscan演算法得到大量的應用。為什麼啊？因為簡單啊，因為直觀啊。

yufei tao 是厲害的，人家可以改論文可以到吐血。我用過他的一個演算法，建index的過程就花了一天，幾十個G的空間，這還只是針對小數據。他這個工作後來也被別人反覆批判，反覆作為baseline。所以學術研究都是互相critical的！！

最後補個八卦，今天和組裡面的大牛們討論，今年的sigmod best paper，他們都表示很吃驚的。都說沒看懂commit 怎麼討論的。前年 yufei tao 他們組的 triangle count 的論文，拿了best paper 還可以說說。今年真沒看懂。

在sigmod上聽yufei tao的presentation，這個錯誤最早是由一篇碩士畢業論文指出來的，但是這篇碩士論文沒有引起其他人的注意，最後yufei tao是第二個引用這篇碩士paper的，我覺得有錯誤其實挺正常的。

實在是搞不懂，為什麼有好幾個答案居然覺得DBSCAN是DB界的paper，這到底是有沒有常識？
----
我想說，其實打臉正是research paper的常態，有的打得輕有的打得重而已，paper看多了就習慣了。當你看著看著文章突然一個however出來，往往後面打臉就要開始了。。。

今天和朋友突然又談到這事情，又有了一點新的看法。

的確，就像前面回答說的學術進步當然離不開犯錯和糾錯，這本身是一件很正常的事情。
但這事情也要多方面來看。
如果只是單純的犯錯和糾錯，那麼SIGMOD委員會錄用《DBSCAN Revisited》就行了，為什麼要將這篇文章評選成best paper呢？
我個人感覺，這其實SIGMOD委員會希望借這篇文章讓大家對這些年來資料庫領域的發展有一些反思。

由於工業界重視，這些年來資料庫領域，特別是數據挖掘領域，有了極大地發展與進步，湧現了大量優秀的工作。
但是伴隨著資料庫領域本身的日漸繁榮，這其中的研究工作的質量也在江河日下，有很多工作有灌水的嫌疑。
像IJCAI 2015、AAAI 2015，一年都能錄上五六百篇文章了，而香港有些組一年能中10多篇。
文章一多起來，質量也就難以保證；一個人一次同時做兩三個工作，其中很多工作難免不夠紮實。

的確，DBSCAN本身有錯不是什麼大不了的，被糾錯了也沒正常。
但這個錯被維持10多年、引用上千次才被發現有問題，那麼不禁人懷疑這上千次的引用中有多少水分。
想必是大家都想著多拉快跑，儘可能發論文，也就顧不上檢驗其中細節了。

SIGMOD委員會很可能是希望借這次《DBSCAN Revisited》給大家澆一下冷水，讓大家好好冷靜一下。
讓大家好好想想，我們資料庫領域這些年做出來的這些論文工作是否真禁得起時間的考驗？？？

擼主真是涉世未深啊。

paper有錯的太多了，我可以list給你一波類似級別的論文有錯誤的且大家默認的也沒改的。一篇理論一點的論文幾十頁證明，有錯太正常了，能fix或者能用就行了。

（今天隨手翻看的一個paper中的。）

當然這個錯的有點大，但是沒什麼了不起的……尤其考慮到是DB界的paper……對吧……數學碉堡好的人應該不會來這一行。至少我讀過的不多的DB的paper裡面好多真的是瞎XX寫的……你問我為啥還要讀？因為他們claim他們幹了很多牛逼的事情呀，我們只好引用然後說你們別真當回事啊！哪怕理論圈有的時候要寫實驗，一般也會ignore貴圈的結果的……

（凡是不要走極端，DB界當然也有牛人啊，今年Turing Award Winner就是，但是你想想7000的引用，大多數都是質量不行的我看過的那些paper吧。作為對比，59年quicksort的paper才勉強1k的引用，而且估計不少還都是DB圈引用的。DB圈實在是太臃腫，良莠不齊。）

我掃了一眼這篇paper，挺正常的……再說作者就是學術圈的人，你的意思是他自己扇自己？

因為在亞琛(RWTH)上2012年冬季學期data mining的時候，學過DBSCAN，所以看到這個問題，秉著八卦的和瞻仰大神的精神，就去看了看當時的課件，課件是2012年冬季學期的，教授Seidl在他的課件里說DBSCAN的複雜度是O(n^2)，沒想到Seidl教授這麼超前啊，不過他沒發聲糾正，是因為不能像上面答案里寫的，沒能提出一個更為優化的方法，還是因為德國人不願意糾正別人的錯誤？
上課件截圖，

最開始的那個paper只是claim了

the average run time complexity of DBSCAiNs
O(n* log n).

人家什麼時候說是最壞情況了? 這個n^2的worst case很顯然的吧

所謂的misclaim都是後面那7000多人乾的事好吧...

哪個是老師呢。。。

好多所謂頂會並不提供源代碼實驗結果無法重現

學術界就是在不斷打前人臉的過程中發展的，越打臉越發展。

剛看完這篇文章，感覺還是沒解決維數d過高（比如100甚至更高）時複雜度隨d的增加指數級增長的問題。所謂的迎接大數據，感覺還是做不到。。

其實大家也都清楚，就是在這樣一個反反覆復，大家互相學習的氛圍下，才能相互進步，或者推動行業進步。要說一個論文裡面存在一點錯誤也是正常的吧，至少不是不可饒恕的吧。我也看過一些論文，有時候確實存在這樣的情況。一個重要的事實是，前人做的工作可能總是會存在一些不足，但是他們做的開創性的工作卻是非常重要的。這個論文裡面有錯，很長時間都沒人指出來，只能說是大家沒有用心看或者沒有向權威發出挑戰的勇氣，現在有人經過縝密的思考，發現這裡存在一些問題，然後提出來，進行校正，做出的工作也應該是很有價值的。用通俗的話說，科學有時候不就是在大家相互挑刺中不斷前進的么

投稿到SIGMOD真是不可思議。

看了這麼多答案說論文出錯是正常的，說明我對學術界的判斷還是沒錯的，不要臉的人太多了。
理工科的東西，對的就是對的，錯的就是錯的。
上學的時候做題，很多東西不用交卷子你就知道自己是對是錯，這完全是一個態度問題。
這種事情正好說明了學術界的一些常態：
1、自己為了「證明」自己拍腦殼想出來的東西，有些數學不嚴謹，實驗甚至不支持的東西，先騙了自己，再騙了審稿人。
2、別人的東西很少自己驗證，盲目崇拜頂會。

就這些吧。

有錯誤指正出來當然是好事，學術不就是這樣一步步往前走的么。
不混學術圈，但是道理應該想通。工作中代碼里也有很多隱藏的大型bug是過了半年一年才發現的，但是都不會有什麼，改完回歸上線即可。人不是完美的，犯錯是必然的。有的人看到不是自己犯錯就想搞個大新聞，哪天這件事情落到自己頭上了，你會作何感想呢？