本系列文章對(duì)常見的機(jī)器學(xué)習(xí)面試題進(jìn)行了搜集、分類和整理，主要包括”手撕推導(dǎo)篇“、“模型比較篇”、“工程經(jīng)驗(yàn)篇”以及“基礎(chǔ)概念篇”等多個(gè)板塊，旨在幫助廣大算法工作者能夠從容應(yīng)對(duì)求職面試！

手撕邏輯回歸

image

手寫k-means算法

1. 算法原理：

(1) 初始隨機(jī)選取k個(gè)中心點(diǎn)；

(2) 遍歷每個(gè)樣本，選取距離每個(gè)樣本最近的中心點(diǎn)，歸為該類；

(3) 更新中心點(diǎn)為每類的均值；

(4) 重復(fù)(2)(3)迭代更新，直至誤差小到某個(gè)值或者到達(dá)一定的迭代步數(shù).

2. 偽代碼

image

3. 代碼實(shí)現(xiàn)(python)

def kmeans(k):
    m, n = 100, 20  # 構(gòu)造樣本：100行、20列
    x = 10 * np.random.random((m, n))
    
    # 隨機(jī)選擇k個(gè)初始中心點(diǎn)
    init_cent_sample = set()
    while len(init_cent_sample) < k:
        init_cent_sample.add(np.random.randint(0, m))
    cent = x[list(init_cent_sample)]
    
    # 記錄每個(gè)樣本的類歸屬
    cluster_assessment = np.zeros((m, 2))
    
    # 記錄每個(gè)類的中心點(diǎn)在本次迭代后是否有過改變
    cent_changed = True
    while cent_changed:
        cent_changed = False
        
        for j in range(m):
            # 記錄每個(gè)樣本距離最近的類
            min_inx = -1
            # 記錄每個(gè)樣本的最小類距
            min_dist = math.inf
            
            for i in range(k):
                d = distance(x[j], cent[i])
                if d < min_dist:
                    min_dist = d
                    min_inx = i
            
            # 記錄此樣本的中心點(diǎn)是否發(fā)生變化
            if min_inx != cluster_assessment[j][0]:
                cluster_assessment[j] = np.array([min_inx, min_dist])
                cent_changed = True
        print(cluster_assessment)
        
        # 更新每個(gè)類的中心點(diǎn)：均值
        for i in range(k):
            cent_i_samples = np.where(cluster_assessment[:, 0] == i)
            if len(cent_i_samples) > 0:
                print(cent_i_samples)
                cent[i] = np.mean(x[cent_i_samples], axis=0)


# 計(jì)算距離
def distance(a, b):
    return math.sqrt(sum(pow(a - b, 2)))

image