視頻有哪幾種——大量高維稀疏數據聚類分析實戰

問題描述

有的時候我會胡亂搜索一些TAG比如BISEXUAL之類的，或者老包（OLD-BAG我不知道怎麼翻譯），往往能搜出一些讓人大開眼界的東西。發現一些新的世界，有的時候發現了能幾天吃不下飯……

以我一己之力抗整個網站近3000000視頻（可能還不止）實在是無力，所以乾脆用機器學習進行分析。 和之前不一樣，這是一個無監督學習的問題，而且之前只有300000視頻，2000種TAG，現在有3000000視頻，50000種TAG，所以直接應用別人寫好的輪子的結果就是————崩潰。

如果使用稠密矩陣，就算是用Int8類型也需要139GB內存才能存下，事實上，用於分析的矩陣往往是float64類型的，這個時候需要1TB內存才能分析。

我要是買的起1TB內存我直接給錢讓他們給我分析不就完了嗎？

我現在的PC是12GB，我們的任務就是在有限的內存中，在有限的計算時間內完成需要分析的任務。

同時吐槽sklearn的實現，對於稍微大規模一些的問題，不但慢，而且很消耗內存。

最快的方法肯定是使用C/C++開發以後給Python調用，但是我又懶得寫。

SO，我們儘可能使用Python來完成這個任務。

代碼在：TsingJyujing/xhamster_analysis中的3M-video-analysis中。

解決問題的思路

首先考慮，我們是不是需要分析這麼多數據，鑒於網站上有很多沒誠意的小視頻（大多在3min以內），胡亂拍攝了一些就上傳，我們首先過濾掉時間過短（少於3min）的視頻，這樣還剩160多萬條數據。

隨後我們發現，很多標籤是重複的：

我們考慮降維，降維的作用就是刪去不需要的維度，合併相似的維度（註：只能淺顯的這麼理解，事實上，某些降維方法已經和「維度」沒有關係了）。 無監督的降維，我們最常使用的是PCA，但是這裡不能直接使用，因為PCA演算法中，矩陣首先要去均值化，去了均值以後，就不稀疏了，這個時候內存瞬間爆炸。

所以我們考慮使用SVD（事實上，你上Google學術搜一下，所謂Sparse PCA，本質也就是SVD）。

稀疏矩陣的SVD還是很消耗內存的，一般來說，我們也不會降特別多的維度，取64~128是比較合理的數字，這個降維之後會用於我們的可視化。

降維之後我們得到三個矩陣，不妨記其為[U,S,V]，如果分解的足夠完美，那麼M=USV。這裡我們取用US作為降維後的結果（近似的，也就是 ），原因是：U和V中每個向量都已經是單位向量了，該方向的範數被保存在了矩陣S中，要想真實的還原距離，那就需要將S乘上。

這個時候我們應用K-Means方法對其進行聚類。

下面我們可以用LDA展示一下聚類的結果，用聚類的結果為標籤y，來對X做降維，降到2~3維，

下面我需要對這K類做解釋，最直接的解釋就是將標籤打出來。但是每一類中，少的有幾千個視頻，多的有幾萬個視頻。如何展現每一類的特性呢？

首先我們考慮打出該類視頻中最常見的N個標籤，其次我們也列印出其出現的概率/次數，第三我們最好能展現每個標籤之間的關係，比如經過調查發現Gangbang和Anal標籤之前存在較強的相關性，那麼我們可以把兩個標籤靠近一點。

那我們如何評價兩個標籤的相似度呢？我們考慮Jaccard相似度。

我們決定了Jaccard評估相似度，如何求得坐標？對於已經有了距離/相似度，不知道坐標的情況，我們可以採用Metric MDS演算法將其變換回歐氏空間（如果僅僅服從局部歐氏的特性，請用ISOMAP/LLE演算法）。

最後我們用MDS將距離矩陣描述的關係映射到2維歐氏空間去看，得到我們的分析結果。

最終結果

在初次聚類以後，我們採用LDA對數據進行了降維並且可視化，得到了「喜人」的結果：

除了左側的一個大團簇以外，其它三個團簇都是Gay片。

說明這樣的可視化不行啊，雖然展示了一部分結果，但是還不夠，而且我還是沒弄清楚這三個Gay團簇之間究竟是什麼關係。

我們還是需要展示每一類的內容。最終我聚類了127類，完整版可以在Github上看到，我就隨意展示幾類給大家看一下。有一些類是相似的，這個說明我們聚類的K選的偏多了。

附錄

JACCARD

Jaccard的公式：

其中，A,B分別代表出現了a標籤和b標籤的視頻的集合。絕對值符號求的是視頻的數量。

定好了實驗方案，下一步我們就要動手了。

實踐中我挑選一些用於加速的點說一下：

如何不用FOR循環求取JACCARD距離矩陣

M = numpy.matrix(M)nNOT_M = 1-MnDM = 1.0 - ((M.transpose()*M) / (len(labels_data) - NOT_M.transpose()*NOT_M))n

DM就是我們要求的Jaccard距離矩陣，Jaccard相似度要變為Jaccard距離，需要一個定義域包含0~1，值域包含於R^+的單調遞減函數，我們取f(x)=1-x。

再說一下M.transpose()*M，這個就求取了Jaccard相似度的上半部分。 我們考慮：

0*1->0n1*1->1n1*0->0n0*0->0n

和AND的規則一模一樣，那我們把M看成向量組的話，只需要對每兩個向量求內積即可求出AND之後1的個數，轉化為矩陣的語言就是：

類似的方法我們可以求出OR，但是需要注意的是，求出之後需要用維度去減一下，原因是我們求的是0的個數，但是

求出來的是dim-0的個數。

Sparse K-Means ++ 的黑科技

如何直接對大規模的稀疏矩陣進行直接的聚類？為什麼我們一定要降維呢？兩個稀疏向量之間求取距離 為了解決大規模稀疏數據的分析問題，我們使用了Sparse K-means++。

這個名字是我胡謅的，首先是應用於大規模稀疏矩陣的K-means，點的初始化方法使用的是K-Means++。

但是該實現更加適合處理稀疏的數據集，而且到現在我並沒有看到一個比較好的稀疏K-Means庫。 （回頭看能不能提給sklearn）。

多重共線性的診斷問題

數據其實存在比較嚴重的共線性問題，這個主要是因為某些標籤的粒度不夠細，意義存在冗餘造成的。這樣就會導致對距離的測度不準確，但是如果做診斷，將需要求取一個50k維的方陣，太大了。

不論用SVD也好，還是直接用Sparse K-Means也好，只要你做的變換（不變換默認用單位矩陣做變換）是等距的，那就不嚴格適用此方法， 大概是我太呆了吧，寫到一半才想起不能用，所以索性就寫完了。

這個時候也考慮對標籤的意義進行分析來做，但是沒有多年經驗的老司機是沒法知道這50k個標籤究竟哪些意義比較相近，況且還有一些標籤有微妙的區別，最後還是考慮用SVD，犧牲在距離測度上的一些穩定性來彌補我在讀標籤經驗上的不足。

所以說，做機器學習系統，如果要得到最好的結果，你首先得是業務上的專家。