clustering聚類(lèi)分析(編輯修改稿)
2024-11-23 03:49 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 標(biāo)準(zhǔn) ? 通常是 NPHard ? 多項(xiàng)式算法 并非精確的最優(yōu)解，而是相對(duì)優(yōu)的解或者局部的最優(yōu)解 算法一 ? 判斷標(biāo)準(zhǔn)： kcenter criterion 最小化任意點(diǎn)到所分的類(lèi)中心的最大距離 ? 基本思想： 存在 k個(gè)半徑為 r的球體覆蓋所有點(diǎn) ? 存在最大距離為 r的劃分 算法一 ? 步驟 每次選取一個(gè)未被覆蓋的 數(shù)據(jù) 點(diǎn)作為一個(gè)類(lèi)的中心，作半徑為 r的球體，覆蓋某些點(diǎn)。重復(fù) k次得到 k個(gè)類(lèi)。 算法一 ? 不靠譜？有點(diǎn) …… ? 但是： 若存在最大距離為 r/2的劃分，這個(gè)算法一定能找到最大距離不超過(guò) r的劃分。 證明：反證法 假設(shè)無(wú)法找到最大距離為 r的劃分 ?至少一個(gè)點(diǎn)不在 k個(gè)半徑為 r的球體中 ?存在 k+1個(gè)點(diǎn)兩兩的距離大于 r ?k個(gè)半徑為 r/2的球體無(wú)法覆蓋這 k+1個(gè)點(diǎn) ?不存在最大距離為 r/2的劃分（矛盾） 類(lèi)中心 ? 要求類(lèi)中心必須是數(shù)據(jù)點(diǎn) 類(lèi)的劃分有限，可窮舉 ? 類(lèi)中心可以是空間中的任意點(diǎn)（使距離函數(shù)最小的點(diǎn)） 結(jié)果精確 ? 某
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1