本系列文章对常见的机器学习面试题进行了搜集、分类和整理，主要包括”手撕推导篇“、“模型比较篇”、“工程经验篇”以及“基础概念篇”等多个板块，旨在帮助广大算法工作者能够从容应对求职面试！
手撕逻辑回归
image
手写k-means算法
- 算法原理：
(1) 初始随机选取k个中心点；
(2) 遍历每个样本，选取距离每个样本最近的中心点，归为该类；
(3) 更新中心点为每类的均值；
(4) 重复(2)(3)迭代更新，直至误差小到某个值或者到达一定的迭代步数.
- 伪代码
image
- 代码实现(python)
def kmeans(k):
m, n = 100, 20 # 构造样本：100行、20列
x = 10 * np.random.random((m, n))
# 随机选择k个初始中心点
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)]
# 记录每个样本的类归属
cluster_assessment = np.zeros((m, 2))
# 记录每个类的中心点在本次迭代后是否有过改变
cent_changed = True
while cent_changed:
cent_changed = False
for j in range(m):
# 记录每个样本距离最近的类
min_inx = -1
# 记录每个样本的最小类距
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
# 记录此样本的中心点是否发生变化
if min_inx != cluster_assessment[j][0]:
cluster_assessment[j] = np.array([min_inx, min_dist])
cent_changed = True
print(cluster_assessment)
# 更新每个类的中心点：均值
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)
# 计算距离
def distance(a, b):
return math.sqrt(sum(pow(a - b, 2)))
image
