http://blog.csdn.net/u013300875/article/details/44081067

很多機器學習分類算法，比如支持向量機（svm），假設數據是要線性可分。

如果數據不是線性可分的，我們就必須要采用一些特殊的方法，比如svm的核技巧把數據轉換到更高的維度上，在那個高維空間上數據可能會變得線性可分。

?

那么，我們如何判斷數據是不是線性可分的？

最簡單的情況是數據向量是一維二維或者三維的，我們可以把圖像畫出來，直觀上就能看出來。

比如H?vard Geithus網友的圖，非常簡單就看出兩個類的情形下X和O是不是線性可分。

?

但是數據向量維度一旦變得很高，我們怎么辦？

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

?

什么是凸包呢？

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

舉個例子，下圖的藍色線就是一個恰好包住所有數據的閉合凸曲線。

?

知道了什么是凸包，我們就能檢查我們的數據是不是線性可分了。

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

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

下圖就是個線性可分的情況。

雖然現在我們比直接看數據判斷是不是線性可分進了一步，但是好像還是靠畫出圖來人眼判斷，這對高維度數據依然無效。

是這樣么？當然不是。

因為判斷兩個凸包是不是有重疊可以通過判斷凸包M+的邊和凸包M-的邊是否相交來實現，這就無需把凸包畫出來了。

?

如何高效的找到一組數據的凸包？

如何高效的判斷兩個凸包是否重合？

網友Darren Engwirda?給出了很好的建議：

?

There are efficient algorithms that can be used both to find the convex hull (theqhull?algorithm is based on anO(nlog(n))?quickhull?approach I think), and to perform line-line intersection tests for a set of segments (sweepline?atO(nlog(n))), so overall it seems that an efficient?O(nlog(n))?algorithm should be possible.

This type of approach should also generalise to general?k-way?separation tests (where you havek?groups of objects) by forming the convex hull and performing the intersection tests for each group.

It should also work in higher dimensions, although the intersection tests would start to become more challenging...

簡單說，他的建議就是用quickhull算法來找到數據的凸包，sweepline算法判斷凸包邊緣是否有相交，兩個步驟的復雜度都是O(nlogn)。

其中quickhull已經在軟件包qhull(http://www.qhull.org/)實現了。

?

?

?

?

?

?

http://www.tuicool.com/articles/ERJVZv

轉載于:https://www.cnblogs.com/lgdblog/p/6858832.html

總結

以上是生活随笔為你收集整理的线性可分 与线性不可分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。