因为之前我一直在用的Fedora22系统失效了，想重装一下Linux，于是我脑子一热，在windows中直接把Linux的/boot所在分区给删了，后来发现这会导致重启后grub无法通过原来Linux的/boot下的grub配置文件找到Windows，进而将无法启动Windows，好在当时还没有重启计算机，于是赶紧把电脑上的数据备份了一下，然后开始查询解决的办法。

Windows下使用MbrFix重建MBR

删除Linux分区后导致重启无法进入Windows是因为，MBR中的grub需要从Linux的/boot目录中读取配置文件找到windows，但是当我们删除Linux分区之后，/boot目录下的配置文件也一并被删除了，所以无法进入windows。于是我们可以设法把grub替换掉，换成windows自己的引导程序。

能使用这个方法的前提是，你准备删除或已经删除了Linux系统，但是还没有重启，这样比较简单，我们可以通过一个MbrFix工具将Windows引导程序写入MBR。

下载MbrFix：http://7xo792.com1.z0.glb.clouddn.com/MbrFix.rar

解压文件，其中”MbrFix.exe”是适用于32位系统的程序，”MbrFix64.exe”是适用于64位系统的程序。将适用于当前系统的程序复制到C盘根目录下，然后打开cmd(注意必须以管理员身份运行)，依次输入以下命令：

1
2
3

cd /
MbrFix /drive 0 fixmbr /yes
/*如果是64位系统则是MbrFix64 /drive 0 fixmbr /yes*/

至此MBR重建完成，重启后系统直接进入windows。

使用Windows安装光盘重建MBR

如果已经重启，无法进入windows，解决方法如下：

我们需要一张windows的安装光盘，以Win7安装光盘为例，在选择完语言等设置后，点击下一步进入下一个界面，不要点击“继续安装”而是点击下面的“修复计算机”。接着在出现的界面中选择第一项，点击“下一步”，然后点击“命令提示符”，输入以下命令重建MBR：

1

bootrec /fixmbr

　　
重建完成后，输入exit即可退出命令提示符，然后点击”重新启动”即可进入Windows系统。

主引导记录——MBR(Master Boot Recoder)

MBR通常存在于磁盘的第一扇区，大小为512Byte。MBR主要包括两部分：1.引导程序或者指向”分区引导记录”中引导程序的指针；2.分区表。Linux目前最常用的引导程序是”grub”，WinXP的引导程序是”NTLDR”，WinVista 和Win7的引导程序是”BCD”。

如果我们在电脑上先装了Win7后又装Linux，并且装Linux时将grub引导程序选择安装在了MBR里，那么我们每次启动进入Windows时，引导的顺序是：

[1].从MBR启动grub，grub读取Linux的boot数据(保存在“/boot”);

[2].让用户选择是进入Linux还是Windows，如果选择Linux则开始[3],如果选择Windows则开始[4];

[3].根据boot数据直接启动Linux，结束；

[4].根据boot数据找到BCD/NTLDR；

[5].BCD或NTLDR再根据自己的设置，直接启动Windows或是进行其它的引导。

反之，如果我们先安装了Linux后再装Windows，由于Windows在安装时会将原来存在于MBR中的grub覆盖，故我们在装完Windows后重启，也会进不去Linux。(补充：Linux安装设置grub时能自动识别到Windows系统，并写入boot文件中；而Windows在安装时却不会理会已存在的Linux，而直接忽略之)

正式进入2016年的8月份，校招也即将开始了。之前一直在考虑出国读博还是国内工作的问题，但是一直得不到内心坚定的回答，究其原因，应该是没有找到自己的兴趣和努力的方向。7月份去北京待了3周，远离学校的环境之后我顿时感受到自身的渺小和无助，于是陷入了一种无尽的思索人生的状态，比如说：我们最终在追求什么？人生的价值和意义究竟是什么？我付出了努力但是最终没有回报怎么办？..当然这种思考是丝毫没有用的，无非是想得太多而书读的太少，直到今天浏览到Byvoid的博客，突然得到了解答，人生的意义不就是在于追求自己喜欢的，创造自己所想的，和有意思的人分享感悟，知道自己是谁，并知道自己要成为谁。

写博客确实是必须坚持的习惯，和健身一样必不可少。健身保证的是身体的健康，而坚持写作保证了心灵的健康，让我们成为一个有思想的人。没有奋斗目标的生活是灰色的，它会让人在碌碌无为中迷失自己。Byvoid从高中开始就坚持记录生活感悟和奋斗历程，世界上有如此优秀的人在不停的努力，我们又有什么理由不去奋斗呢?

一直以来，我好像一直生活在别人的眼光之中，期待的是得到别人的赞赏，可是回头想想，难道这些真的是我想要的吗？人生很长，我不可能一辈子当学生，以后的路需要我自己用心去规划。即将从学校踏入社会，面临如此多机遇和挑战，我要做到脚踏实地，不忘初心。

接下来的日子，既然选择了远方，必定要风雨兼程。

短期目标：

1. 充分准备校招，多投简历，多总结经验；

2. 坚持英语练习，准备TOEFL考试；

3. 坚持写博客，记录学习过程和生活感悟；

这篇论文是2010年Anil K.Jain在《Pattern Recognition Letters》上发表的，作者主要论述了50年来K-means算法的发展及演变。K-means算法是机器学习领域的十大经典算法，其应用非常广泛。通过自己的理解，我将这篇论文翻译如下，如不当之处请各位指正。

摘要

将数据有效地分类是理解和学习的最基本的形式之一。比如，科学分类的常用形式是将物体放入分类系统进行分类：区域，界，系或者类等。聚类分析是一种正式的研究方法和分类算法，它根据测量(或感知)对象之间的内在特征(或者相似性)。聚类分析没有识别对象的类别标签，如类标签。相比于监督学习，非监督学习缺乏聚类数据的类别信息。聚类的目标是找到数据中的结构，然后将此结构扩展成自然形式。聚类在各种科学领域中具有漫长而丰富的历史，其中最简单常用的聚类算法是在1955年提出的K-means算法。尽管距离K-means算法的提出已经50多年，并且在它之后也提出了很多新算法，K-means算法仍然得到了广泛的应用。一般来说，设计一个通用的聚类算法是困难的，并且聚类算法存在不适定问题。我们对聚类进行了一个简要的概述，总结了一些常见的聚类方法。我们讨论了设计聚类算法时的主要挑战和关键问题，然后指出一些新的和有用的研究方向，其中包括半监督聚类(semi-supervised clustering)，整体聚类(ensemble clustering)，聚类过程中的特征选择和大尺度的数据聚类。

1. 引言

随着传感和存储技术的进步，网络搜索、数字图像以及视频监控产生了很多大容量和高维的数据集。据估计，2007年数字宇宙大约消耗了281 exabyte，预计2011年的数量大约是这个数据的10倍(1 exabyte是$10^{18}$ bytes或者1,000,000 TB)(Gantz, 2008) 。大部分数据按位存储在电子媒介中，这为自动数据分析的发展、分类和检索提供了巨大的潜力。随着数据量的大量增长，各种各样的可用数据(文本、图像和视频)也随之增加。便宜的数码相机和视频设备产生了巨大数量的图像和视频。由于RFID标签和调制器的低成本和小尺寸，使得数以百万计的传感器有规律地传输数据。每天邮件、博客、事务数据以及数十亿的网页将产生巨大数量的新数据。很多数据流是松散的，这增加了分析他们的难度。

我们需要通过改进自动理解、过程以及归纳数据的方法来应对数据的数量和多样性的增加。数据分析技术能够广泛地分为主要两类(Tukey, 1977)：(1)探索或描述，就是说研究者不需要预先指定的模型或者假设，希望去理解高位数据的一般特征或者结构。(2)确认或推论，就是说研究者希望确定假设/模型或者一组给定的数据假设的可靠性。很多统计方法已经被提出用于分析数据，例如方差分析、线性回归、判别分析、典型相关分析、多维定标、因子分析、主成分分析、聚类分析等。更多概述可以参考(Tukey, 1977)。

在模式识别中，数据分析关注于预测建模：给定一些训练数据，我们希望预测未知的测试数据的行为。这个任务也被称为learning。通常来说，在学习问题中的一个明确的区分：(1).有监督(supervised)学习,例如分类(2).无监督(unsupervised)学习,例如聚类(Duda et al., 2001 )。有监督的学习只包含有标签的数据(具有已知分类标签的训练集)，而无监督的学习只包含未标签的数据。聚类问题相比于分类问题更加具有挑战性。现在一种混合模式越来越受到关注，即半监督学习(semi-supervised learning)(Chapelle et al.,2006))。在半监督分类中，只有一小部分的训练数据是有标签的。未标记的数据(包括被忽略的数据)也在学习过程中运用到。在半监督聚类中，不是通过指定类别标签，而是指定成对约束，即先验知识中的弱编码。一对连接约束(must-link)相当于两个对象之间应该具有相同的聚类标签，而一对非连接约束(cannot-link)相当于两个对象之间具有不同的聚类标签。约束在数据聚类中非常有用 (Lange et al., 2005; Basu et al., 2008), 尤其是在底层聚类缺乏精确定义的情况下。在寻找好的模型中，我们会包括所有提供的信息，无论是被标记的数据、被约束的数据或者标记的数据。Fig.1说明了模式识别和机器学习中感兴趣的各类学习问题。

2. 数据聚类

数据聚类(聚类分析)指的是发现一组模式、点或者对象的自然分类。Webster(Merriam-Webster Online Dictionary, 2008)将聚类分析定义为”在多个特征中通过定量比较来寻找一群个体中单个个体所属类别的统计分类技术”。Fig.2表示了聚类的一个例子。目标是在未标记数据(Fig.2a)中创建一个能够发现自然分类(Fig.2b)的自动算法。

2.1 为什么用聚类

聚类分析是一种涉及任何学科的多变量分析。Google Scholar(2009)在2007年的词目中查询到1660条关于“data clustering”的词目。这个巨大的文献库说明了聚类在数据分析中的重要性。详尽地列出在众多科学领域和应用中运用的聚类技术以及成千上万的算法是非常困难的。图像分割是计算机视觉当中的重要问题，能够表示为一个聚类问题(Jain and Flynn, 1996; Frigui and Krishnapuram, 1999; Shi and Malik, 2000)。文档也可以被聚类(Iwayama and Tokunaga, 1995)，产生局部层次用来有效地信息评估(Sahami, 1998)或者检索(Bhatia and
Deogun, 1998)。聚类也用来消费者分类，进行有效地市场营销(Arabie and Hubert, 1994)，或者服务交付项目分类，用来劳动力管理和计划(Hu et al., 2007)，同时也可以在生物领域中研究基因组计划(Baldi and Hatfield, 2002)。

数据聚类已经被应用到以下三个主要的用途：

1.底层结构(Underlying structure)： 用来理解数据，生成假设，检测异常和识别特征。
2.自然分类(Natural classification)： 用来识别形式或者生物之间的相似度(系统发育关系)。
3.压缩(Compression)： 作为通过集群原型来组织数据和归纳的一种方法。

关于类别发现的一个例子如Fig.3所示。在手写字符识别应用程序，聚类被用来识别子类 (Connell and Jain, 2002)。不同的用户书写相同数字的方式是不同的，从而增加了类中方差。从一个类别中对训练集进行聚类可以得到新的子类，称为手写字符的词位(lexemes)。相比对每一个字符采用单一模式，基于子类数量的多模式提高了识别效率。

2.2 发展历史

聚类方法已经成为一个真正的跨学科方法。分类学、社会学、心理学、生物学、统计学、数学、工程学、计算机科学、医学研究和其他收集数据的学科都涉及到聚类方法。根据JSTOR(2009)，data clustering首次出现在1954年的一篇处理人类学数据的论文标题当中。根据不同的领域，数据聚类也被称为Q-分析、类型学、聚合和分类学(Jain and Dubes, 1988)。有几本关于数据聚类的经典书籍的作者有：Sokal and Sneath (1963), Anderberg (1973), Hartigan (1975), Jain and Dubes (1988), and Duda et al. (2001). 聚类算法也在数据挖掘中被广泛地运用，可以参考Han and Kamber (2000) and Tan et al. (2005)的书籍以及机器学习(Bishop, 2006)。

聚类算法可以大致分为两类：基于层次的(hierarchical)和基于划分的(partitional)。 层次聚类算法在聚集的模式中递归地找到嵌套模式(从找到每个数据点的类别开始，融合最相似的一对类别从而相继形成聚类的层次结构)或者分裂(自顶向下)模式(从找到每个数据点的类别开始，递归地将每一个聚类分裂为更小的聚类)。相比基于层次聚类算法，基于划分的算法同时找到所有的聚类来作为数据的一个划分，没有强行形成一个层次结构。在层次聚类算法中，输入n$\times$n的相似度矩阵，其中n是集群中的对象数量。而在划分聚类算法中，能够输入n$\times$d的模式矩阵，其中n个对象嵌入了d维的特征空间中；同时也能够输入n$\times$n的相似度矩阵。注意相似度矩阵很容易从模式矩阵中推导，但是从相似度矩阵中推导模式矩阵则需要排序方法(比如多维标度测量(MDS))。

最常用的层次聚类算法是单链接(single-link)和全连接(complete-link);最常用和最简单的划分聚类算法是K-means。基于可用数据的自然性质，划分聚类算法在模式识别当中是首选的，我们这里主要关注于此类算法。K-means算法具有丰富并多样的历史，因为它是在不同科学领域中独立被发现的，包括Steinhaus (1956), Lloyd (proposed in 1957, published in 1982), Ball and Hall (1965), and MacQueen (1967)。尽管K-means方法是在50多年前被提出的，它仍然是使用最为广泛的聚类算法。K-means算法实现简单、有效并且具有成功经验，这都是它如此受欢迎的原因。下面，我们首先总结K-means算法的发展，然后讨论在数据聚类中应用的主要方法。

2.3 K-means算法

令$X={x_i},i=1,…,n$是n维数据点，要将这些数据点聚成K个聚类，$C={c_k,k=1,…,K}$.K-means算法找到一个划分，使得每个聚类中的均值与该聚类中的数据点的平方误差是最小的。令$\mu_k$是聚类$c_k$的均值，$\mu_k$与$c_k$中的数据点之间的平方误差定义为：

1.引言

谱聚类是一种在探索性数据分析中使用最为广泛的技术，其应用涉及到统计、计算科学、生物学、社会科学或者心理学。几乎每个科学领域在处理实验数据过程中，人们都尝试通过识别数据中具有“相似特征”的类别来获取该数据的第一印象。本文将为读者介绍谱聚类方法。相比于传统算法如k-means或者最短距离法(single linkage)，谱聚类具有很多基本的优点。通过谱聚类获得的结果通常要比传统聚类获得的结果要好，并且谱聚类非常易于实现，能够通过标准线性代数方法有效地求解。

本文主要介绍谱聚类方法。我们分析了关于谱聚类不同的观点和谱聚类的工作机制。除了基本的线性代数，读者不需要具有特定的数学背景。同时，由于关于谱聚类的文献数量太多，我们不再赘述关于谱聚类的所有文献。本文前两个部分主要是逐步介绍关于谱聚类所使用的数学对象：相似图在第二部分，图的拉普拉斯矩阵在第三部分。谱聚类算法的介绍在第四部分。接下来的三个部分将解释为什么这些算法有作用：第五部分描述了图的划分方法，第六部分是随机游走(random walk)的观点, 第七部分是扰动理论(perturbation theory)。在第八部分中，我们研究了一些与谱聚类相关的实际问题，第九部分讨论了一些谱聚类的扩展和关于谱聚类文献。

2.相似图

给一组数据点$x_1,…,x_n$,在每一对数据点$x_i$ 和 $x_j$之间定义相似度$s_{ij}$,聚类的直接目标是把数据点分为几个不同的类别，使得同一类别中数据点的相似度最大，不同类别中数据点的相似度最小。如果我们只知道数据点之间的相似度信息，一个表示这些数据点比较好的方法是相似图的形式(similarity graph)$G=(V,E)$。 相似图中每一个顶点$v_i$表示一个数据点$x_i$。如果两个顶点$x_i$和$x_j$之间的相似度$s_{ij}$为正并且大于某个确定的阈值，那么这两个顶点是以$s_{ij}$为权重的边连接的。现在，聚类问题可以重新定义为相似图问题：我们需要找到一个这样的分割，不同类别之间的边具有非常低的权重，而同一类别中的边具有比较高的权重(这意味着在同一类中的数据点是相似的)。为了能够形式化这样的表示，我们首先介绍一些图的基本定义，简要讨论一下我们将要研究的图的种类。

2.1 图的定义

$G=(V,E)$是一个无向图，顶点集为$V={v_1,…,v_n}$. 下面我们假定图$G$是有权的，也就是说每两个顶点$v_i$和$v_j$有一个非负的权重$w_{ij}>=0$。图的加权邻接矩阵是$W=(w_{ij}). i,j=1,…,n$。如果$w_{ij}=0$意味着顶点$v_i$和$v_j$之间没有边连接。因为$G$是无向图，我们令$w_{ij}=w_{ji}$。顶点$v_i \in V$的度定义如下：

$$d_i=\sum^{n}_{j=1}w_{ij}.$$

请注意，事实上，上式只计算了与$v_i$邻接的所有顶点，其他顶点的权重都为0。度矩阵$D$是对角矩阵，其对角线上的度为$d_i,…,d_n$。给定一个顶点子集$A \subset B$，我们用

关于在Code blocks中配置OpenGL的方法，在网上一直没有找到实用的方法，后来在实验室师兄的帮助下终于配置成功了，现把配置过程记录如下。

(1)下载codeblocks，最好是带mingw的版本，不然则要自己配置mingw；

(2)下载GLUT bin文件，最好在OpenGL官网上下载最新版本，解压.
将glut32.dll复制到C:\windows\system目录;
将glut32.lib复制到mingw\lib目录;
将glut.h复制到mingw\include\GL目录;
mingw为你的mingw目录，如果是codeblocks自带的，则在codeblocks安装目录下；

(3) 新建一个空工程 empty project;

(4) 配置工程，右键单击新建的工程，打开Build Options->Linker Settings，在Link libraries中添加MinGW\lib\glut32.lib,MinGW\lib\libopengl32.a,MinGW\lib\libglu32.a，点击OK;

(5) 在工程中新建test.c测试文件，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <GL/gl.h>
#include <GL/glut.h>

void myDisplay(void)
{
 glClear(GL_COLOR_BUFFER_BIT);
 glRectf(-0.5f, -0.5f, 0.5f, 0.5f);
 glFlush();
}

int main(int argc, char *argv[])
{
 glutInit(&argc, argv);
 glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);
 glutInitWindowPosition(100, 100);
 glutInitWindowSize(400, 400);
 glutCreateWindow("first OpenGL program");
  glutDisplayFunc(&myDisplay);
 glutMainLoop();
 return 0;
}

(6)编译运行程序，效果如下：

1. 问题描述

有一个梵塔，塔内有三个座A、B、C，A座上有诺干个盘子，盘子大小不等，大的在下，小的在上(如图)。把这些个盘子从A座移到C座，中间可以借用B座但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。

描述简化：把A柱上的n个盘子移动到C柱，其中可以借用B柱。

2. 简单分析

假设有n个盘子，我们把盘子从小到大标记为1、2、3…n。三柱子一共有三个状态：

1. 状态0 A: 按顺序堆放的n个盘子。 B：空的。 C：空的。
   目标需要把A上的n个盘子移动到C，而且C盘最下面的盘子应该是最大的盘子，标号为n。要取得A上的第n个盘子，需要把它上面的n-1个盘子拿开放在B柱上。当然B柱上的盘子也是按照大在下小在上的原则堆放的。

   这一步完成之后三个塔变为状态一。

2. 状态1 A：只有最大的一个盘子。 B:按规则堆放的n-1个盘子。 C:空的。
   这时候可以直接把A上的最大盘移动到C盘，移动后的状态：中间状态——A：空的。B：n-1个盘子。C：有一个最大盘（第n个盘子）。
   这时候C柱其实可以看做空的，因为剩下的的所有盘子都比它小，任何一个盘子都可以放在C柱上。所以现在的状态： 中间状态——A：空的。B：n-1个盘子。C：空的。
   现在的问题和原问题有些相似之处，如果把B柱上的n-1个盘子移动到A柱上，那么现在的问题和原问题相比就只是规模变小了而已。把B上的n-1个盘子移动到A上，其实和上文中把n-1个盘子从A柱移动到B柱是一样的，只是柱子的名称换了一下而已。（如果写成函数，只是参数的调用顺序改变了而已）

1. 状态2 A：按顺序对方的n-1个盘子。B：空的。C：按顺序堆放的第n个盘子（可看为空柱）

此时我们完成了一次完美的递归，从状态0到状态2，除了规模变小，其他方面没有任何区别了。

3. 算法实现

定义函数:

1
2

Hanoi(a,b,c,n)//表示把a上的n个盘子移动到c上，其中可以用到b。
move(m,n)//表示把m上的盘子移动到n上

算法流程：

1. 把A上的n-1个移动到B：Hanoi（a,c,b,n-1）//状态1
2. 把A上的最后一个大盘子移动到C：move（a,c）
3. 把B上的n-1个盘子移动到A: Hanoi（b,c,a,n-1）//状态2

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

main()
{
    int n;
    printf("请输入n阶汉诺塔：\n");
    scanf("%d",&n);
    hanoi(n,'A','B','C');
}

void hanoi(char A,char B,char C,int n)
{
    if(n==1)
    {
      printf("Move disk %d from %c to %c\n",A,C,n);
    }
    else
    {
      hanoi(A,C,B, n-1);
      printf("Move disk %d from %c to %c\n",n,A,C);
      hanoi(B,A,C,n-1,);
    }
}