我在R^3中有n個要用k個橢圓體或圓柱體覆蓋的點（我並不在乎，哪個更容易）。我想盡量減少卷的聯合。假設n是數萬，k是少數。開發時間（即簡單性）比運行時更重要。帶有橢圓體的k-means
很明顯，我可以運行k-means並使用完美的球體作爲我的橢球體。或者我可以運行k-means，然後使用每個簇的最小封閉橢球而不是用球覆蓋，儘管在最壞的情況下這並不好。我已經看過用k-means來處理各向異性的討論，但我看到的鏈接似乎認爲我手中有張量;我不知道，我只知道這些數據將是橢球體的聯合體。有什麼建議麼？
[編輯：有幾個選票適合多元高斯混合，這似乎是一個可行的事情嘗試。啓動一個EM代碼來做到這一點不會使工會的體積最小化，但當然k-means並不會使體積最小化。]
所以你可能知道k-means是NP-hard，而這個問題更加普遍（更難）。因爲你想要做橢球體，所以適合k個多變量高斯分佈的混合可能會很有意義。你可能會想嘗試找到一個最大似然解，這是一個非凸優化，但至少它很容易制定，並且有可能的代碼可用。
除此之外，您可能需要從頭編寫自己的啓發式搜索算法，這只是一個巨大的任務。
我使用this method做了與多變量高斯相似的事情。作者使用峯度作爲分裂度量，並且我發現它是我的應用的一個令人滿意的方法，從激光測距儀（即計算機視覺）獲得聚類點。
謝謝。我沒有擔心自動選擇k，但這可能會訣竅。 – bhudson
如果橢球可以重疊很多， 然後像K-手段，方法，是儘量點分配到單集羣 將不能很好地工作。 每個橢球的一部分必須適合物體的表面， 但其餘的可能在其內部，不關心。 也就是說，覆蓋算法 在我看來與聚類/分裂算法有很大不同; 工會不是分裂。
有很多重疊的高斯混合？ 不知道，但看到Numerical Recipes p. 845上的圖片和代碼。
即使在2d也很難覆蓋，見 find-near-minimal-covering-set-of-discs-on-a-2-d-plane。
NP-hard不會嚇到我;我只需要一個近似值，而我的數據不是由小工具組成的。或者如果是這樣，我可以指責用戶。 EM計算高斯混合並不真正減少我想盡量減少。它可能工作得很好，所以我會嘗試一下--k-means不會使它最小化。 – bhudson