算法

Python 实现 KNN 分类算法

0 条评论 算法 Python 算法 shenke

本文将详细讲述 KNN 算法及其 python 实现

1. KNN

KNN（K-Nearest Neighbour）即 K最近邻，是分类算法中最简单的算法之一。KNN 算法的核心思想是 如果一个样本在特征空间中的 k 个最相邻的样本中的大多数属于某一个类别，则将该样本归为该类别

1.1 KNN 分类算法步骤

有 N 个已知分类结果的样本点，对新纪录 r 使用 KNN 将其分类

  • 1.确定 k 值，确定计算距离的公式，如常用欧氏距离 $d(x,y)=\sqrt{\displaystyle \sum^n_{i = 1}{{(x_i-y_i)}^2}}$
  • 2.计算 r 和其他样本点之间的距离 $d_{ir}$，其中 $i\in(1,N)$
  • 3.得到与 r 最接近的 k 个样本
  • 4.将 k 个样本中最多归属类别的分类标签赋予新纪录 r，分类结束


Java 求最大子数组

0 条评论 算法 Java 算法 shenke

Background

在某天购入股票后抛出，求如何取得最大利润。已知股票趋势如图所示。


Java 分治策略实现归并排序

0 条评论 算法 Java 算法 shenke

Thought

能不能使用分治策略的关键是 子问题的最优解是否可以通过某种手段得到原问题的最优解。对于归并排序，将两个已经有序的子问题序列进行合并，就可得到一个有序序列，以此类推，最终可将所有子问题序列合并成一个有序序列，而得到的有序序列就是最终答案。

图片来自简书，链接：https://www.cnblogs.com/chengxiao/p/6194356.html


Java 分治策略实现快速排序

0 条评论 算法 Java 算法 shenke

Thought

  • Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray.
  • Conquer: Recursively sort the subarrays.
  • Combine: Trivial.

以枢轴 x 为中点，每次排序将小于枢轴 x 的元素都放在 x 左边，大于 x 的元素都放在 x 右边，然后递归以同样方式对子数组排序


Java 建立大顶堆

0 条评论 算法 Java 算法 shenke

Thought

  • 从最后一个有孩子的父节点开始调整，若父节点的值小于左右孩子结点的值（如果有的话），就与该孩子结点交换位置。若发生了交换，由于原来父节点到了他的孩子结点上，可能破坏了现在这颗以原来父节点为根节点的子树，所以需要重复以上步骤，即递归。
  • 数组的范围是从 0 ~ length - 1，设父节点的下标为 p，则：
p的左孩子下标为：2 * p + 1
p的右孩子下标为：2  *p + 2

最后一个有孩子的父节点下标为（length - 2）/ 2