聚类算法概述(k-Means++/FCM/凝聚层次聚类/DBSCAN)

参考自初识聚类算法:K均值、凝聚层次聚类和DBSCAN模糊聚类FCM算法

聚类的目的

将数据划分为若干个簇,簇内相似性大,簇间相似性小,聚类效果好。用于从数据中提取信息和规律。

聚类的概念

  • 层次与划分:当允许存在子簇时,将数据按照层次划分,最终得到的是一颗树。树中包含的层次关系即为聚类划分的层次关系。各个子簇不重叠,每个元素都隶属于某个level的子簇中。
  • 互斥、重叠与模糊:这个概念的核心在于,所有集合元素都不完全隶属于任何一个簇,而是按照一定隶属度归属于所有簇。对于任意一个元素,其隶属度和一般为1。
  • 完全与部分:完全聚类要求所有数据元素都必须有隶属,而部分聚类则允许噪音存在,不隶属于任何簇。

簇的分类

  • 明显分离:不同簇间任意元素距离都大于簇内元素距离。从图像上观察是明显分离类型的簇。
  • 基于原型:任意元素与它所隶属的簇的簇中心(簇内元素集合的质心)的距离大于到其他簇中心的距离。
  • 基于图:图中节点为对象,弧权值为距离。类似于明显分离的定义或基于原型的定义,只是用弧权值代替了人为规定的距离。
  • 基于密度:基于密度的簇分类是较为常用,也是应用范围最为广泛的一种分类方法。元素的稠密程度决定了簇的分布。当存在并希望分辨噪声时,或簇形状不规则时,往往采用基于密度的簇分类。

常用的聚类分析算法

  • 基本k均值:即k-means算法。簇的分类是基于原型的。用于已知簇个数的情况,且要求簇的形状基本满足圆形,不能区分噪声。
  • 凝聚层次聚类:起初各个点为一个簇,而后按照距离最近凝聚,知道凝聚得到的簇个数满足用户要求。
  • DBscan:基于密度和划分的聚类方法。

清华大学研读间预约应用

Tutu-Android 清华小图

  • 还在为预定不到文图研读间而愁眉苦脸,每晚熬到零点只为抢到一个研读间才能安心睡觉吗?
  • 还在因不知道文图剩余座位为零而白跑一趟,或傻傻苦等吗?
  • 总因为赶不上研读间预约时间而承担着违约的风险,最终导致一个月无法预订研读间吗?
  • 不用怕,不担心,清华小图来帮你:D!

清华小图的简介

清华小图是一款面向全清华的师生的文科图书馆研读间智能预约助手。小图会为你提供全方位的文图研读间预订服务。包括研读间的筛选、普通预约、修改、退订,研读间的智能预约、智能推荐,研读间的自动预约、定时轮询,个人预约信息和学籍信息的查询,文图剩余自习座位实时查询。您可以在任意时刻切换账户或退出登录,您也可以随时与开发者通过问题反馈沟通报告bug。

OpenCV实现图像搜索引擎

简单介绍一下OpenCV

OpenCV was designed for computational efficiency and with a strong focus on real-time applications. Written in optimized C/C++, the library can take advantage of multi-core processing. Enabled with OpenCL, it can take advantage of the hardware acceleration of the underlying heterogeneous compute platform. Adopted all around the world, OpenCV has more than 47 thousand people of user community and estimated number of downloads exceeding 9 million. Usage ranges from interactive art, to mines inspection, stitching maps on the web or through advanced robotics.

OpenCV(Open Source Computer Vision Library)的计算效率很高且能够完成实时任务。OpenCV库由优化的C/C++代码编写而成,能够充分发挥多核处理和硬件加速的优势。OpenCV有大量技术社区和超过900万的下载量,它的使用范围极为广泛,如人机互动、资源检查、拼接地图等。

0.Python+OpenCV实现图像搜索引擎

之前看到谷歌和百度出了图像搜索引擎,查阅了相关资料深入了解了图像搜索引擎的算法原理。一部分参考了用Python和OpenCV创建一个图片搜索引擎的完整指南。决定自己实现一个简单的图像搜索引擎,也可以让自己更快地查找mac中的图片。为什么使用OpenCV+Python实现图像搜索引擎呢?

  • 首先,OpenCV是一个开源的计算机视觉处理库,在计算机视觉图像处理模式识别中有广泛的应用。接口安全易用,而且跨平台做的相当不错,是一个不可多得的计算机图像及视觉处理库。

  • 其次,Python的语法更加易用,贴近自然语言,极为灵活。虽然计算效率并不高,但快速开发上它远胜于C++或其他语言,引入pysco能够优化python代码中的循环,一定程度上缩小与C/C++在计算上的差距。而且图像处理中需要大量的矩阵计算,引入numpy做矩阵运算能够降低编程的冗杂度,更多地把精力放在匹配的逻辑上,而非计算的细枝末节。

C++贪吃蛇

借鉴自C++贪吃蛇的实现,同时修改了其中的2个问题:

  • 其一,随机生成食物时应检查是否生成在蛇节点上;
  • 其二,检查碰撞时除与外围墙碰撞外,还需检查蛇头与蛇身的碰撞。

A-star算法概述及其在游戏开发中的应用分析

首先需要感谢Amit’s A star PageA-star算法中译本,让我能够全面地了解A-star算法,下面大部分内容也是由原文及中译文中提炼而得。

1. 从Dijkstra算法和最佳优先搜索到A-star算法

1.1 Dijkstra算法

核心思想:

每次都选取距离起始点最近的点,并加入完成列表。算法的效率并不高,但对于没有负数权值边的情况能够得到从起始点到大部分点的最短路径。Dijkstra算法相当于启发式函数h(x) = 0的A-star算法(在后面会详细说明)。

适用领域:

相对于A-star算法,Dijkstra算法也有它适用的领域。当移动单位需要找到从其当前位置出发到N个分散目的地中的一个的最短路径(比如盟军只需抢占N个据点中的任意一个就能取胜,此时盟军需要选择一个离自己最近的据点i即可),Dijkstra算法会比A-star算法更为合适。

原因在于,Dijkstra对所有中间节点一视同仁,并不考虑它们到目的地的实际代价,这就导致该算法会偏执地选择离起点最近的节点,而当当前扩展节点集中出现了任意一个目的地i,算法就可以终止,而得到的目的地i就是N个目的地中距起始点最近的目的地。相反地,A-star算法则需要找到从起始点出发到所有目的地的最短路径,通过比较得到所有最短路径中的最小值。而实际上我们并不需要知道除了最近的目的地之外的其他目的地的路径就是如何。

总而言之,A-star算法更适用于单点对单点的寻径;Dijkstra算法更适用于单点到多点的寻径。

Pseudo-random algorithm

计算机产生的大多数随机数都是伪随机数。是按照分布概率产生随机数字的过程,数字在概率分布上满足随机要求,但实际上是计算机通过随机函数模拟产生的。生成的方法包括直接法逆转法接受拒绝法等。本篇要介绍的是prd伪随机算法基于rsa的伪随机算法

Pseudo Random Distribution

这种伪随机算法在游戏中的应用非常广泛。游戏希望角色间应互相制衡,同时为增加游戏的不确定性,故引入了随机概念,如暴击率、回避率等都是一个随机概率的表现。prd伪随机算法能够尽量使触发事件的情况均匀地分布在多次事件中,从而避免了连续多次的暴击或回避,也可以减少长时间不暴击情况的发生。

实际上Pseudo Random Distribution是来自Warcraft3引擎,同时在dota2中得到了发扬。prd伪随机算法是计算触发角色特殊能力的概率的算法。对于普通的伪随机算法,我们能够发现,每次触发事件的概率都相同。但对于prd伪随机算法而言,每次触发事件的概率却不相同,它会随着暴击事件或非暴击事件的触发而改变。但在均摊概率上来说,却是满足角色能力要求的,也是满足随机概率要求的。

一定程度上prd算法改善了暴击的发生的频次和分布,使其更为均匀,从而保证了游戏的公平性和趣味性。

Android Studio应用指南

0、引言

本文转载自关于Android Studio,你需要知道的9件事

1、如何构建你的项目

点击Build然后选择Make Project,最后点击右下方的Gradle Console查看打印信息。

2、Gradle Tasks的使用

点击右侧的Gradle,依次展开项目名–>:app,可以查看所有的Gradle任务,比如双击assembleRelease,就可以执行此task。双击assemble,表示同时执行assembleDebugassembleRelease,会在目录app/build/apk/生成对应的debug和release的APK。

生成的APK命名规则:app-<flavor>-<buildtype>.apk; 比如: app-full-release.apkapp-demo-debug.apk.

也可以在左下角点击控制台进行相应的任务命令:比如输入gradle tasks命令可以查看所有的task、输入gradle build命令表示同时执行assemblecheck;同时命令还支持驼峰匹配:比如gradle aR等同于gradle assembleRelease

3、运行配置

点击Run选择Edit Configuration,展开Android Application,可以新建一个配置或者编辑一个现有的配置:可以配置是否自动启动默认Activity,启动特定Activity,部署目标是否手动选择,比如可以自动部署到USB(真机);模拟器网速控制:

网速规则如下所示:

1
None: no latency
2
GPRS: GPRS (min 150, max 550 milliseconds)
3
EDGE: EDGE/EGPRS (min 80, max 400 milliseconds)
4
UMTS: UMTS/3G (min 35, max 200 milliseconds)

同时可以配置模拟器启动时的额外命令行:

比如启动适配屏幕:-scale 96dpi;还有logcat配置:比如是否每次启动时自动清空。

CRC循环冗余校验码

Cyclic redundancy check

A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents. On retrieval, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption.

循环冗余校验CRC简介

  • CRC为校验和的一种,是两个字节数据流采用二进制除法(没有借位和进位,使用异或来代替减法)相除所得到的余数。
  • 其中被除数是需要计算校验和的信息数据流的二进制表示;除数是一个长度为(n+1)的预定义二进制数,通常用多项式的系数来表示。
  • 在做除法之前,要在信息数据之后先加上n个0。冗余码的位数是n位。冗余码的计算方法是,先将信息码后面补0,补0的个数是生成多项式最高次幂;将补零之后的信息码用模二除法(非二进制除法)除以G(X)对应的2进制码,注意除法过程中所用的减法是模2减法(注意是高位对齐),即没有借位的减法,也就是异或运算。
  • 当被除数逐位除完时,得到比除数少一位的余数。此余数即为冗余位,将其添加在信息位后便构成CRC码字。

例如,假设信息码字为11100011,生成多项式$G(X)=X^5+X^4+X+1$,计算CRC码字。$G(X)=X^5+X^4+X+1$,也就是110011,因为最高次是5,所以,在信息码字后补5个0,变为1110001100000。

用1110001100000模二除法除以110011,余数为11010,即为所求的冗余位。因此发送出去的CRC码字为原始码字11100011末尾加上冗余位11010,即 1110001111010。

接收端收到码字后,采用同样的方法验证,即将收到的码字用模二除法除以110011(是$G(X)$对应的二进制生成码),发现余数是0,则认为码字在传输过程中没有出错。

尽管在错误检测中非常有用,CRC并不能可靠地校验数据完整性(即数据没有发生任何变化),这是因为CRC多项式是线性结构,可以非常容易地故意改变量据而维持CRC不变。

浅谈Prisoner's Dilemma

转自How to beat the Prisoner’s Dilemma in the TV game show Golden Balls

Golden Balls is an amusing British game show. Especially interesting is the final contest which is a version of the Prisoner’s Dilemma.

If you’re never seen the show, here is how it works. Each of two contestants independently chooses to split or steal the final prize. If both choose split, then the prize is divided evenly. If one chooses split and the other steal, the person who steals gets the entire prize. If both choose steal, however, then both walk away with nothing.

Here’s the normal form representation of the game:

game matrix

How should you play this game?
One contestant had an amazingly brilliant strategy.

The wrong way to play the game

Contestants are allowed to discuss strategy before picking split or steal.

Both realize that split gives a fair 50 percent share to each side, but each also sees the advantage of back-stabbing and stealing the prize.

The discussion usually involves the following strategy. Each person tries to convince the other person to split, and they promise to do the same.

I discussed an example of this in a previous post: strategy in Golden Balls.
In that episode, both were promising they would split the prize, but then one person decided at the last minute to steal all the money. She said she was not proud of the decision, but she herself did not want to be cheated.

So trying to split the money in a conventional way doesn’t work. Is there a better strategy?

Loading data from multiple sources with RxJava

Simply copy from Loading data from multiple sources with RxJava

Suppose I have some Data

  • that I query from the network. I could simply hit the network each time I need the data, but caching the data on disk and in memory would be much more efficient.
  • More specifically, I want a setup that:
    Occasionally performs queries from the network for fresh data.
    Retrieves data as quickly as possible otherwise (by caching network results).

I’d like to present an implementation of this setup usingRxJava.

Basic Pattern

Given an Observable<Data> for each source (network, disk and memory), we can construct a simple solution using two operators, concat() and first().

concat() takes multiple Observables and concatenates their sequences. first() emits only the first item from a sequence. Therefore, if you use concat().first(), it retrieves the first item emitted by multiple sources.

Let’s see it in action:

1
// Our sources (left as an exercise for the reader)
2
Observable<Data> memory = ...;  
3
Observable<Data> disk = ...;  
4
Observable<Data> network = ...;
5
6
// Retrieve the first source with data
7
Observable<Data> source = Observable  
8
  .concat(memory, disk, network)
9
  .first();

The key to this pattern is that concat() only subscribes to each child Observable when it needs to. There’s no unnecessary querying of slower sources if data is cached, sincefirst() will stop the sequence early. In other words, if memory returns a result, then we won’t bother going to disk or network. Conversely, if neither memory nor disk have data, it’ll make a new network request.

Note that the order of the source Observables in concat() matters, since it’s checking them one-by-one.

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×