聚类算法:K-means

K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。 对于聚类问题,我们事先并不知道给定的一个训练数据集到底具有哪些类别(即没有指定类标签),而是根据需要设置指定个数类标签的数量(但不知道具体的类标签是什么),然后通过K-means算法将具有相同特征,或者基于一定规则认为某一些对象相似,与其它一些组明显的不同的数据聚集到一起,自然形成分组。之后,我们可以根据每一组的数据的特点,给定一个合适的类标签(当然,可能给出类标签对实际应用没有实际意义,例如可能我们就想看一下聚类得到的各个数据集的相似性)。 首先说明一个概念:质心(Centroid)。质心可以认为就是一个样本点,或者可以认为是数据集中的一个数据点P,它是具有相似性的一组数据的中心,即该组中每个数据点到P的距离都比到其

Impala与HBase整合实践

我们知道,HBase是一个基于列的NoSQL数据库,它可以实现的数据的灵活存储。它本身是一个大表,在一些应用中,通过设计RowKey,可以实现对海量数据的快速存储和访问。但是,对于复杂的查询统计类需求,如果直接基于HBase API来实现,性能非常差,或者,可以通过实现MapReduce程序来进行查询分析,这也继承了MapReduce所具备的延迟性。 实现Impala与HBase整合,我们能够获得的好处有如下几个: 可以使用我们熟悉的SQL,像操作传统关系型数据库一样,很容易给出复杂查询、统计分析的SQL设计 Impala查询统计分析,比原生的MapReduce以及Hive的执行速度快很多 Impala与HBase整合,需要将HBase的RowKey和列映射到Impala的Table字段中。Impala使用Hive的Metastore来存储元数据信息,与Hive类似,在于HBase进行整合时,也是通过外部表(EXTERNAL)的方式来实现。 准备工作 首先,我们需要做如下准备工作: 安装配置Hadoop集群(http://www.cloudera.com/content/c

Cloudera Impala架构设计要点

我们知道,在实时性要求不是很高的应用场景中,比如,月度统计报表生成等,我们基于传统的Hadoop MapReduce来处理海量大数据(包括使用Hive),在各方面表现都还不错,只需要离线处理数据,然后存储结果即可。但是如果在一些实时性要求相对较高的应用场景中,哪怕处理时间能够在原有的基础有大幅度地减少,也能很好地提升用户体验。对于大数据的实时性要求,其实是相对的,比如,传统使用MapReduce计算框架处理PB级别的查询分析请求,可能耗时30分钟甚至更多,但是如果能够使这个延迟大大降低,如3分钟计算出结果,这是很令人震撼的。Impala就是基于这样的需求驱动而出现的。 Impala是Cloudera开发的一款用来进行大数据实时查询分析的开源工具,它能够实现通过我们熟悉的传统关系数据库的SQL风格来操作大数据,数据可以是存储到HDFS或HBase中的。 下面,我们从不同的角度来认识和理解Cloudera Impala: 设计目标 官网给出的介绍是,使用Impala来实现SQL on H

基于C#+Thrift操作HBase实践

在基于HBase数据库的开发中,对应Java语言来说,可以直接使用HBase的原生API来操作HBase表数据,当然你要是不嫌麻烦可以使用Thrift客户端Java API,这里有我曾经使用过的 HBase Thrift客户端Java API实践,可以参考。对于具有其他编程语言背景的开发人员,为了获取HBase带来的好处,那么就可以选择使用HBase Thrift客户端对应编程语言的API,来实现与HBase的交互。 这里,我们使用C#客户端来操作HBase。HBase的Thrift接口的定义,可以通过链接http://svn.apache.org/viewvc/hbase/trunk/hbase-server/src/main/resources/org/apache/hadoop/hbase/thrift/Hbase.thrift?view=markup看到,我们需要安装Thrift编译器,才能生成HBase跨语言的API,这里,我使用的版本是0.9.0。需要注意的是,一定要保证,安装了某个版本Thrift的Thrift编译器,在导入对应语言库的时候,版本一定要统一,否则就会出现各种各样的问题,因为不同Thrift版本,对应编程语言的库API可能

ZooKeeper应用案例

我们通过学习借鉴,哪些项目或应用都使用了ZooKeeper,可以了解我们的应用使用ZooKeeper是否能真正地带来价值,当然,有些项目可能也未必非常适合使用ZooKeeper,我们要批判地学习、借鉴和吸收。 下面是一些使用了ZooKeeper实现的案例: HDFS HA(QJM) Hadoop 2.x之前的版本,HDFS集群中Namenode是整个集群的中央元数据存储和服务节点,它存在SPOF的问题。在2.x版本中,提出了各种HA方案,避免Namenode的SPOF问题,其中基于QJM(Quorum Journal Manager)的方案可以解决这个问题:使用QJM的方案中,HDFS集群中存在两类节点,一类是Namenode节点(包括Active状态的Namenode,和Standby状态的Namenode),另一类是JournalNode,进行容错。当Active状态的Namenode元数据发生改变时,通过JournalNode进程(ZooKeeper集群中)来监视这种变化,然后同步到Standby状态的Namenode节点(实际上同步的是EditLog镜像文件内容的变更)。 当Active状态的节点发生故障后,

ZooKeeper架构设计及其应用要点

ZooKeeper是一个开源的分布式服务框架,它是Apache Hadoop项目的一个子项目,主要用来解决分布式应用场景中存在的一些问题,如:统一命名服务、状态同步服务、集群管理、分布式应用配置管理等,它支持Standalone模式和分布式模式,在分布式模式下,能够为分布式应用提供高性能和可靠地协调服务,而且使用ZooKeeper可以大大简化分布式协调服务的实现,为开发分布式应用极大地降低了成本。 总体架构 ZooKeeper分布式协调服务框架的总体架构,如图所示: ZooKeeper集群由一组Server节点组成,这一组Server节点中存在一个角色为Leader的节点,其他节点都为Follower。当客户端Client连接到ZooKeeper集群,并且执行写请求时,这些请求会被发送到Leader节点上,然后Leader节点上数据变更会同步到集群中其他的Follower节点。 Leader节点在接收到数据变更请求后,首先将变更写入本地磁盘,以作恢复之用。当所有的写请求持久化到磁盘以后,才会将变更应用到内存中。 Z

ZooKeeper-3.3.4集群安装配置

ZooKeeper是一个分布式开源框架,提供了协调分布式应用的基本服务,它向外部应用暴露一组通用服务——分布式同步(Distributed Synchronization)、命名服务(Naming Service)、集群维护(Group Maintenance)等,简化分布式应用协调及其管理的难度,提供高性能的分布式服务。ZooKeeper本身可以以Standalone模式安装运行,不过它的长处在于通过分布式ZooKeeper集群(一个Leader,多个Follower),基于一定的策略来保证ZooKeeper集群的稳定性和可用性,从而实现分布式应用的可靠性。 有关ZooKeeper的介绍,网上很多,也可以参考文章后面,我整理的一些相关链接。 ZooKeeper的安装配置还算比较容易的,下面,我们简单说明一下ZooKeeper的配置。 ZooKeeper Standalone模式 从Apache网站上(zookeeper.apache.org)下载ZooKeeper软件包,我选择了3.3.4版本的(zookeeper-3.3.4.tar.gz),在一台Linux机器上安装非常容易,只需要解压缩后,简单配置一下即可以启动

基于Thrift实现跨语言服务

假设,现在我们有这样一个需求: 要通过一个代理平台,将查询请求转发到后端服务器进行查询。后端存在多种查询服务器,查询方式也不同,比如,有基于SQL的关系数据库查询,也有基于搜索引擎Solr的查询。通过代理平台,将 服务暴露给具有任何编程语言技能的开发人员进行调用。 我们可以选择Thrift来定义语言中性的服务接口,然后通过Thrift编译器将定义生成多种编程语言的客户端代码框架,服务器端使用指定语言进行开发,如Java,最后通过连接Thrift服务器来进行查 询调用。 根据我们的需求,后端服务使用Java实现,而外部使用C#进行调用返回结果,再执行进一步的处理。 Thrift服务定义 首先,看一下,我们给出的示例服务定义,文件命名为queryproxy.thrift,内容如下所示: namespace java org.shirdrn.queryproxy.thrift.protocol namespace csharp Query.Proxy.Thrift.Protocol namespace py queryproxy.thrift.protocol typedef i16 short typede

基于Solr DIH实现MySQL表数据全量索引和增量索引

实现MySQL表数据全量索引和增量索引,基于Solr DIH组件实现起来比较简单,只需要重复使用Solr的DIH(Data Import Handler)组件,对data-config.xml进行简单的修改即可。Solr DIH组件的实现类为org.apache.solr.handler.dataimport.DataImportHandler,在Solr的solrconfig.xml中配置两个handler,配置分别说明如下。 全量索引 solrconfig.xml配置如下: <requestHandler name="/dataimport" class="org.apache.solr.handler.dataimport.DataImportHandler"> <lst name="defaults"> <str name="config">data-config.xml</str> </lst> </requestHandler> 上面这个是针对全量索引的,主要是配置data-config.xml文件,示例如下所示: <dataConfig> <dataSource name="jdbc" driver=&

分类算法:决策树(C4.5)

C4.5是机器学习算法中的另一个分类决策树算法,它是基于ID3算法进行改进后的一种重要算法,相比于ID3算法,改进有如下几个要点: 用信息增益率来选择属性。ID3选择属性用的是子树的信息增益,这里可以用很多方法来定义信息,ID3使用的是熵(entropy, 熵是一种不纯度度量准则),也就是熵的变化值,而C4.5用的是信息增益率。 在决策树构造过程中进行剪枝,因为某些具有很少元素的结点可能会使构造的决策树过适应(Overfitting),如果不考虑这些结点可能会更好。 对非离散数据也能处理。 能够对不完整数据进行处理。 首先,说明一下如何计算信息增益率。 熟悉了ID3算法后,已经知道如何计算信息增益,计算公式如下所示(来自Wikipedia): 或者,用另一个更加直观容易理解的公式计算: 按照类标签对训练数据集D的属性集A进行划分,得到信息熵: 按照属性集A中每个属性进行划分,得到一组信息熵: 计算信息增益 然后计算信息增益,即前者对后者做差

Solr DIH: 基于MySQL表数据建立索引

选择使用Solr,对数据库中数据进行索引,可以单独写程序将数据库中的数据导出并建立索引,这个过程可能对于数据处理的控制更灵活一些,但是却可能带来很大的工作量。选择使用Solr的DIH组件,可以很方便的对数据库表中数据进行索引,下面基于MySQL数据库实现建立索引。 首先,需要设计你的schema,最主要的工作是,将数据库表中字段映射为Lucene索引(Solr直接使用Lucene的索引格式和数据)的Field,从而将数据表中的一条记录映射为Lucene中的Document,然后进行索引。另外,在schema.xml配置文件中,还需要指定各个字段在索引数据中的属性信息(如是否索引、是否存储、是否分词、排序规则等),以及Field所使用的分析器、过滤器等。在schema.xml文件进行配置,下面是配置实例: <?xml version="1.0" ?> <schema name="example core zero" version="1.1"> <types> <fieldtype name="int&quo

分类算法:决策树(ID3)

决策树是以实例为基础的归纳学习算法。 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较,并根据不同的属性值从该结点向下分支,叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则,整个决策树就对应着一组析取表达式规则。 一棵决策树由以下3类结点构成: 根结点 内部结点(决策结点) 叶结点 其中,根结点和内部结点都对应着我们要进行分类的属性集中的一个属性,而叶结点是分类中的类标签的集合。如果一棵决策树构建起来,其分类精度满足我们的实际需要,我们就可以使用它来进行分类新的数据集。 这棵决策树就是我们根据已有的训练数据集训练出来的分类模型,可以通过使用测试数据集来对分类模型进行验证,经过调整模型直到达到我们所期望的分类精度,然后就可以使用该模型来预测实际应用中的新数据,对新的数据进行分类。 通过上面描述,我们已经能