大热的算法

1. 哪个编程语言最好学

目前通用排名如下：
1、Java、C、C++！
从2001年Tiobe编程语言排行榜开始发布至今，Java、C、C++几乎一直占据着前三名。虽然Perl、Visual Basic、Objective-C、PHP曾经也排到第3名，但和C++相比，他们就显得不值一提了，因为他们最多只能保持几个月而已。
2、曾经大热的语言：
Perl：像C一样强大，像awk、sed等脚本描述语言一样方便。

PHP：世界上最好的编程语言。

C#：有人认为C#势必会取代C++，C++是垃圾语言，因为微软的大力推广，使用C#的人越来越多，C++却正在被人遗忘。

Delphi：真正的程序员用C++，聪明的程序员用Delphi，Delphi简单、高效、强大。

3、现在使用很广泛的
Python：当今大学教授的第一语言，在统计领域排名第一，在人工智能编程领域排名第一，在脚本编写方面排名第一，在系统测试方面排名第一。

培训机构说：Python已经超过Java了，世界第一了。

4、很久很久以前的编程语言
Foxpro： 曾经最流程的编程语言，市场上的霸主，2015年消失。

PowerBuilder：史上最强大的数据窗口，如果程序员不会PowerBuilder，都不好意思说自己是程序员。

Foxpro是我的第一编程语言，我用它开发了第一个项目。我最喜欢书是《二十一天PowerBuilder从入门到精通》，面试过纺织厂的程序员职位，没被录用。我最后一次用Delphi开发是十五年前。我最不喜欢的是C语言，第一次写的C语言代码是：

char str;

str="hello world";

5、C与C++的关系
C++是C的增强版吗？就像iPhone7和iPhone7 plus的关系吗？那为什么国外的C程序员远远超过C++程序员呢？

最顶级的工程师用C语言开发出Java、Python等语言给程序员使用。

我们是程序员，所以用C++。

2. K-Means 聚类算法

问题导入

    假如有这样一种情况，在一天你想去某个城市旅游，这个城市里你想去的有70个地方，现在你只有每一个地方的地址，这个地址列表很长，有70个位置。事先肯定要做好攻略，你要把一些比较接近的地方放在一起组成一组，这样就可以安排交通工具抵达这些组的“某个地址”，然后步行到每个组内的地址。那么，如何确定这些组，如何确定这些组的“某个地址”？答案就是聚类。而本文所提供的k-means聚类分析方法就可以用于解决这类问题。

一，聚类思想

        所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，属于无监督学习方法，这个方法要保证同一类的数据有相似的特征，如下图：

        根据样本之间的距离或者说相似性，把越相似，差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。

二，K-Means聚类分析算法

        K-Means是一种基于自下而上的聚类分析方法，基本概念就是空间中有N个点，初始选择K个点作为中心聚类点，将N个点分别与K个点计算距离，选择自己最近的点作为自己的中心点，不断地更新中心聚集点。

相关概念：

        K值：要得到的簇的个数

        质心：每个簇的均值向量，即向量各维取品军即可

        距离度量：常用欧几里得距离和余弦相似度(先标准化)

        两点之间的距离：

算法流程：

        1    首先确定一个K值，即我们希望将数据集经过聚类得到 K个集合；

        2    从数据集中随机选择K个数据点作为质心；

        3    对数据集中每一个点，计算其与每个质心的距离(如欧式距离)，离哪个质心近，就划分到哪个质心所属的集合

        4    把所有数据归好集合，一共有K个集合，然后重新计算每个集合的质心；

        5    如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，我们可以认为聚类已经达到期望的结果，算法终止。

        6    如果新质心和原质心距离变化大，需要迭代3-5步骤

K-means实现过程

K-means 聚类算法是一种非监督学习算法，被用于非标签数据（data without defined categories or groups）。该算法使用迭代细化来产生最终结果。算法输入的是集群的数量 K 和数据集。数据集是每个数据点的一组功能。

算法从 Κ 质心的初始估计开始，其可以随机生成或从数据集中随机选择 。然后算法在下面两个步骤之间迭代：

1.数据分配：

每个质心定义一个集群。在此步骤中，基于平方欧氏距离将每个数据点分配到其最近的质心。更正式一点， ci 属于质心集合 C ，然后每个数据点 x 基于下面的公式被分配到一个集群中。

其中 dist（·）是标准（L2）欧氏距离。让指向第 i 个集群质心的数据点集合定为 Si 。

2. 质心更新：

在此步骤中，重新计算质心。这是通过获取分配给该质心集群的所有数据点的平均值来完成的。公式如下：

K-means 算法在步骤 1 和步骤 2 之间迭代，直到满足停止条件（即，没有数据点改变集群，距离的总和最小化，或者达到一些最大迭代次数）。

K 值的选择

上述算法找到特定预选 K 值和数据集标签。为了找到数据中的集群数，用户需要针对一系列 K 值运行 K-means 聚类算法并比较结果。通常，没有用于确定 K 的精确值的方法，但是可以使用以下技术获得准确的估计。

Elbow point 拐点方法

通常用于比较不同 K 值的结果的度量之一是数据点与其聚类质心之间的平均距离。由于增加集群的数量将总是减少到数据点的距离，因此当 K 与数据点的数量相同时，增加 K 将总是减小该度量，达到零的极值。因此，该指标不能用作唯一目标。相反，绘制了作为 K 到质心的平均距离的函数，并且可以使用减小率急剧变化的“拐点”来粗略地确定 K 。

DBI（Davies-Bouldin Index）

DBI 是一种评估度量的聚类算法的指标，通常用于评估 K-means 算法中 k 的取值。简单的理解就是：DBI 是聚类内的距离与聚类外的距离的比值。所以，DBI 的数值越小，表示分散程度越低，聚类效果越好。

还存在许多用于验证 K 的其他技术，包括交叉验证，信息标准，信息理论跳跃方法，轮廓方法和 G 均值算法等等。

三，数学原理

K-Means采用的启发式很简单，可以用下面一组图来形象的描述：

上述a表达了初始的数据集，假设 k=2 。在图b中，我们随机选择了两个 k 类所对应的类别质点，即图中的红色质点和蓝色质点，然后分别求样本中所有点到这两个质心的距离，并标记每个样本类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心大热位置已经发生了变化。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求出新的质心。最终我们得到的两个类别如图f.

四，实例

坐标系中有六个点：

1、我们分两组，令K等于2，我们随机选择两个点：P1和P2

2、通过勾股定理计算剩余点分别到这两个点的距离：

3、第一次分组后结果：

        组A：P1

        组B：P2、P3、P4、P5、P6

4、分别计算A组和B组的质心：

        A组质心还是P1=（0，0）

        B组新的质心坐标为：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）

5、再次计算每个点到质心的距离：

6、第二次分组结果：

        组A：P1、P2、P3

        组B：P4、P5、P6

7、再次计算质心：

        P哥1=（1.33，1） 

        P哥2=（9，8.33）

8、再次计算每个点到质心的距离：

9、第三次分组结果：

        组A：P1、P2、P3

        组B：P4、P5、P6

可以发现，第三次分组结果和第二次分组结果一致，说明已经收敛，聚类结束。

五、K-Means的优缺点

优点：

1、原理比较简单，实现也是很容易，收敛速度快。

2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。

3、主要需要调参的参数仅仅是簇数k。

缺点：

1、K值需要预先给定，很多情况下K值的估计是非常困难的。

2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。

3、对噪音和异常点比较的敏感。用来检测异常值。

4、采用迭代方法， 可能只能得到局部的最优解，而无法得到全局的最优解 。

六、细节问题

1、K值怎么定？

答：分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。或者可以把各种K值算出的 E 做比较，取最小的 E 的K值。

2、初始的K个质心怎么选？

        答：最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更reasonable，就用哪个结果。      当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法（如层次聚类）得到聚类结果，从结果中每个分类选一个点。

3、关于离群值？

        答：离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离群值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。

4、单位要一致！

        答：比如X的单位是米，Y也是米，那么距离算出来的单位还是米，是有意义的。但是如果X是米，Y是吨，用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方，最后算出的东西没有数学意义，这就有问题了。

5、标准化

        答：如果数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么，在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里德距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化（normalization），即将数据按比例缩放，使之落入一个小的特定区间。

3. 挖矿算力怎么计算

首先，算力代表的是矿机每秒的运算次数，如达到 1 次 /s ，则对应算力为 1H 。因此知道挖币矿机的运作时间与运算次数即可计算其算力。算力的单位是每千位一变化，最小单位 H 为 1 次， 1K=1000H,1G=1000K,1T=1000G,1P=1000T,1E=1000P 。大热币种比特币在各地的挖矿算力不完全一致，但基本保持在 24.5E 上下，至少要拥有 150 万台计算机才能达到这一算力。并且不同的数字货币对挖矿方式（算法）的选择也有所区分，因此比较不同货币的算力是不可比的。

不同币种间的算力

不同的币种挖矿选择的算法可能会有所不同，如以太坊使用 Ethash 算法，比特币是 sha256 算法，莱特币是 scrypt 算法等。不同算法对算力的影响就像 6 位数字密码与 12 位字母和数字密码解码的区别，实际情况还要比这个要复杂的多。两种密码的解码要求不同，那么尝试解码的速度也会有较大差距。因此，不同的币种间的算力是没有任何关系的。

4. ECC椭圆曲线加密算法(一)

btc address:
eth address:

随着区块链的大热，椭圆曲线算法也成了密码学的热门话题。在Bitcoin 生成地址 中使用到了椭圆曲线加密算法。

椭圆曲线的一般表现形式：

椭圆曲线其实不是椭圆形的，而是下面的图形：

Bitcoin使用了 secp256k1 这条特殊的椭圆曲线，公式是：

这个东西怎么加密的呢？

19世纪挪威青年 尼尔斯·阿贝尔 从普通的代数运算中，抽象出了加群（也叫阿贝尔群或交换群），使得在加群中，实数的算法和椭圆曲线的算法得到了统一。是什么意思呢？

我们在实数中，使用的加减乘除，同样可以用在椭圆曲线中！
对的，椭圆曲线也可以有加法、乘法运算。

数学中的群是一个集合，我们为它定义了一个二元运算，我们称之为“加法”，并用符号 + 表示。假定我们要操作的群用𝔾表示，要定义的 加法 必须遵循以下四个特性：

如果在增加第5个条件：
交换律：a + b = b + a

那么，称这个群为阿贝尔群。根据这个定义整数集是个阿贝尔群。

岔开一下话题， 伽罗瓦 与 阿贝尔 分别独立的提出了群论，他们并称为现代群论的创始人，可惜两位天才都是英年早逝。

如上文所说，我们可以基于椭圆曲线定义一个群。具体地说：

在椭圆曲线上有 不重合且不对称的 A 、B两点，两点与曲线相交于X点, X与 x轴 的对称点为R，R即为 A+B 的结果。这就是椭圆曲线的加法定义。

因为椭圆曲线方程存在 项，因此椭圆曲线必然关于x轴对称

曲线： ，
坐标：A=(2,5)，B=(3,7)
A、B正好在曲线上，因为坐标满足曲线公式


那如何找到相交的第三个点呢？

通过 A、B两点确定直线方程，
设直线方程： ，m为直线的斜率

进一步得到c=1。

联立方程：

X(-1,-1)的x坐标-1代入方式正好满足方程，所以A、B两点所在直线与曲线相交于 X(-1,-1)，则点X的关于x轴的对称点为R(-1,1)，即A(2,5)+B(3,5)=R(-1,1)。

根据椭圆曲线的 群律(GROUP LAW) 公式，我们可以方便的计算R点。

曲线方程：
当A=(x1,y1)，B=(x2,y2) ，R=A+B=(x3,y3)，x1≠x2时,
， m是斜率
x3=
y3=m(x1-x3)-y1

A=(2,5), B=(3,7) , R=(-1,1) 符合上面的公式。

椭圆曲线加法符合交换律么？

先计算(A+B)，在计算 A+B+C

先计算B+C， 在计算 B+C+A

看图像，计算结果相同，大家手动算下吧。

那 A + A 呢， 怎么计算呢？

当两点重合时候，无法画出 “过两点的直线”，在这种情况下，
过A点做椭圆曲线的切线，交于X点，X点关于 x轴 的对称点即为 2A ，这样的计算称为 “椭圆曲线上的二倍运算”。

下图即为椭圆曲线乘法运算：

我们将在 ECC椭圆曲线加密算法(二) 介绍有限域，椭圆曲线的离散对数问题，椭圆曲线加密就是应用了离散对数问题。

参考：

https://eng.paxos.com/blockchain-101-foundational-math
https://eng.paxos.com/blockchain-101-elliptic-curve-cryptography
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introction/