第119章 高中課程裡有這些?

    這就是“高維np難”問題。

    所謂np難（np-hard），是指:非確定性多項式問題的大型實例，不能用精確算法求解，只能尋求有效的近似算法。

    而解決的辦法，也有很多……

    好吧，先回到一開始的問題:如何判斷數據是線性可分的？

    最簡單的情況，比如數據向量是一維、二維或者三維的，只要把圖像畫出來，直觀上就能判斷出來。

    但如果數據向量的維度變得很高，又該怎麼辦？

    答案是檢查凸包（convexhull）是否相交。

    所謂凸包，簡單的說，就是一個凸的閉合曲線（曲面），它剛好包住了所有的數據。

    以二維的情況為例，如果我們的數據訓練集有兩類:m+和m-。

    當我們畫出兩個類的凸包，如果兩者不重疊，那麼兩者線性可分，反之則線性不可分。

    靠畫出圖形，然後用眼睛來判斷是否線性可分，雖然比直接看數據更加容易了些……

    但好像依然沒有解決高維數據的問題？

    其實不是這樣的。

    判斷兩個凸包是不是有重疊，可以通過判斷兩個凸包（m+和m-）的邊是否相交來實現，而無需把凸包畫出來。

    要想高效地找到一組數據的凸包，在計算幾何中有很多現成的算法:

    窮舉法、分治法、jarvis步進法、graham掃描法、melkman算法……

    江寒在這篇論文中選擇的算法，稱之為快速凸包算法（quickhull）。

    第二個問題，如何高效地判斷出，兩個凸包的邊緣是否相交？

    也有許多可選的算法，江寒使用了所謂的掃描線算法（sweepline）。

    quickhull和sweepline的時間複雜度，都是o(nlogn)，這是它們被選中的前提條件。

    時間複雜度越低，實踐中就越有可行性。

    但寫論文不能這麼簡單的直接扔出來結論，必須將各種算法的效率和優缺點，全都分析一下。

    有必要的時候，還要逐一測試n遍，收集到足夠的數據，然後進行橫向比較，最後才能得出結論。

    江寒理清了思路後，開始打草稿。

    首先寫下標題，然後是摘要，接下來是正文……

    （此處省略2300字。）

    江寒正奮筆疾書，黃光明忽然溜溜達達地走了過來。

    “江寒，都下課了，還在做題啊？”

    黃大學霸說著，探頭探腦地瞅了一眼。

    結果一看草稿紙上書寫的標題，頓時就有點傻眼。

    “《如何高效判斷數據是否線性可分》……”