# 聚类算法（二）

### 流式聚类的算法细节：

$K$ 表示在聚类的过程中允许形成的簇的最大个数；

$D$ 表示距离的阀值，在这里两个点之间的距离可以使用 $L^{1}, L^{2}, L^{\infty}$ 范数；

Step 1：对于 $dataMat[0]$ 而言，自成一类。i.e. 质心就是它本身 $C[0]=dataMat[0]$，该聚簇的元素个数就是 $num[0]=1$，当前所有簇的个数是 $K^{'}=1$

Step 2:  对于每一个 $1\leq i\leq m-1$，进行如下的循环操作：

（i）如果当前 $K'=K$ 或者 $d\leq D$，则把 $dataMat[i]$ 加入到第 $j^{'}$ 个聚簇。也就是说：

（ii）否则，$dataMat[i]$ 需要自成一类。i.e. $K^{'} \leftarrow K^{'}$ + $1$$num[K'-1]=1$$C[K'-1]=dataMat[i]$

### 注：

（1）数据的先后顺序对聚类的效果有一定的影响。

（2）该算法的时间复杂度与簇的个数是相关的，通常来说，如果形成的簇越多，对于一个新的样本与质心的比较次数就会越多。

（3）如果设置簇的最大个数是一个比较小的数字的时候，那么对于一个新的样本，它需要比较的次数就会大量减少。如果最小距离小于 D 或者目前已经达到最大簇的个数的话，那么把新的样本放入某个类。此时，可能会出现某个类由于这个新的样本导致质心偏移的情况。如果设置 $K$ 很大，那么计算的时间复杂度就会增加。因此，在保证计算实时性的时候，需要考虑到 $K$ 的设置问题。

# Theoretical & empirical analysis of Expected Sarsa

Jupyter Notebook submitted as an assignment for the Reinforcement Learning class at McGill analyzing the theoretical and empirical performance of Expected Sarsa.

View original post 1,845 more words

# UCL course – 2016

GOOD

Together with Joseph Modayil, this year I am teaching the part on reinforcement learning of the Advanced Topics in Machine Learning course at UCL.

# Lectures

Note that there will be two lectures about AlphaGo on March 24.  We will talk about AlphaGo in the context of the whole course at the normal place and time (9:15am in Roberts 412), and in addition David Silver will give a seminar that afternoon.  Neither of these will be required for the exam.

1. Introduction to reinforcement learning updated January 14 (Lecture: January 14)
2. Exploration and Exploitation updated January 21 (Lecture: January 21)
3. Markov decision processes updated January 27 (Lecture: January 28)
4. Dynamic programming updated February 3 (Lecture: February 4)
5. Learning to predict updated February 10 (Lecture: February 11)
6. Learning to control updated March 16 (Lecture: February 25)
7. Value function approximation updated March 2 (Lecture: March 3)
8. Policy-gradient algorithms updated March 9 (Lecture:…

View original post 51 more words

# 用强化学习玩文本游戏

$Q^{\pi}(s,a)=E[\sum_{i=0}^{\infty}\gamma^{i}r_{t+i}|s_{t}=s, a_{t}=a]$.

$\pi(a_{t}=a_{t}^{i}|s_{t}) = \exp(\alpha\cdot Q(s_{t},a_{t}^{i}))/\sum_{j=1}^{|A_{t}|}\ \exp(\alpha\cdot Q(s_{t},a_{t}^{j})),$

$h_{1,s} = f(W_{1,s}s_{t}+b_{1,s}),$

$h_{1,a}^{i} = f(W_{1,a}a_{t}^{i}+b_{1,a}),$

$h_{\ell,s} = f(W_{\ell,s}h_{\ell-1,s}+b_{\ell,s}),$

$h_{\ell,a}^{i} = f(W_{\ell,a}h_{\ell-1,a}^{i}+b_{\ell,a}),$

DRRN 相比另外两个模型其创新点在于分别使用了两个网络来映射状态文本和动作文本，因为如果将长文本和短文本直接拼接输入单个神经网络结构的时候，可能会降低 Q 值的质量，所以把 state-text 和 action-text 分别放入不同的网络结构进行学习，最后使用内积合并的方式获得 Q 值的方法会更加优秀。

1. Deep Reinforcement Learning with a Natural Language Action Space

# 《大数据智能》第2章：知识图谱

http://blog.sina.com.cn/s/blog_574a437f0102w2bk.html

# 第2章：知识图谱——机器大脑中的知识库

2.2.1  大规模知识库

2.2.2  互联网链接数据

2.2.3  互联网网页文本数据

2.2.4  多数据源的知识融合

## 2.3  知识图谱的典型应用

2.3.1  查询理解（Query Understanding）

2.3.3  文档表示（Document Representation）

## 2.4  知识图谱的主要技术

2.4.2  关系抽取（Relation Extraction）

2.4.3  知识推理（Knowledge Reasoning）

2.4.4  知识表示（Knowledge Representation）

## 2.5  前景与挑战

1. 知识类型与表示。知识图谱主要采用（实体1，关系，实体2）三元组的形式来表示知识，这种方法可以较好地表示很多事实性知识。然而，人类知识类型丰富多样，面对很多复杂知识，三元组就束手无策了。例如，人们的购物记录信息，新闻事件等，包含大量实体及其之间的复杂关系，更不用说人类大量的涉及主观感受、主观情感和模糊的知识了。有很多学者针对不同场景设计了不同的知识表示方法。知识表示是知识图谱构建与应用的基础，如何合理设计表示方案，更好地涵盖人类不同类型的知识，是知识图谱的重要研究问题。最近认知领域关于人类知识类型的探索（Tenenbaum, et al. 2011）也许会对知识表示研究有一定启发作用。

2. 知识获取。如何从互联网大数据萃取知识，是构建知识图谱的重要问题。目前已经提出各种知识获取方案，并已经成功抽取出大量有用的知识。但在抽取知识的准确率、覆盖率和效率等方面，都仍不尽如人意，有极大的提升空间。

3. 知识融合。从不同来源数据中抽取的知识可能存在大量噪声和冗余，或者使用了不同的语言。如何将这些知识有机融合起来，建立更大规模的知识图谱，是实现大数据智能的必由之路。

4. 知识应用。目前大规模知识图谱的应用场景和方式还比较有限，如何有效实现知识图谱的应用，利用知识图谱实现深度知识推理，提高大规模知识图谱计算效率，需要人们不断锐意发掘用户需求，探索更重要的应用场景，提出新的应用算法。这既需要丰富的知识图谱技术积累，也需要对人类需求的敏锐感知，找到合适的应用之道。

## 2.6  内容回顾与推荐阅读

— 知识图谱是下一代搜索引擎、自动问答等智能应用的基础设施。

— 互联网大数据是知识图谱的重要数据来源。

— 知识表示是知识图谱构建与应用的基础技术。

— 实体链指、关系抽取和知识推理是知识图谱构建与应用的核心技术。

## 2.7  参考文献

[1] (Bordes, et al. 2013) Bordes, A.,Usunier, N., Garcia-Duran, A., Weston, J., & Yakhnenko, O. (2013). Translatingembeddings for modeling multi-relational data. In Proceedings of NIPS.

[2] (Dong, et al. 2014) Dong, X., Gabrilovich,E., Heitz, G., Horn, W., et al. Knowledge Vault A web-scale approach toprobabilistic knowledge fusion. In Proceedings of KDD.

[3]   (Lao & Cohen 2010) Lao, N., & Cohen, W. W. (2010). Relationalretrieval using a combination of path-constrained random walks. Machinelearning, 81(1), 53-67.

[4]   (Nauseates,et al. 2013) Nastase, V., Nakov, P., Seaghdha, D. O., & Szpakowicz, S. (2013). Semanticrelations between nominals. Synthesis Lectures on Human Language Technologies,6(1), 1-119.

[5]   (Nickel,et al. 2015) Nickel, M., Murphy, K., Tresp, V., & Gabrilovich, E. A Review of RelationalMachine Learning for Knowledge Graphs.

[6] (Russell & Norvig 2009) Russell, S., & Norvig, P. (2009). ArtificialIntelligence: A Modern Approach, 3rd Edition. Pearson Press.（中文译名：人工智能——一种现代方法）.

[7]   (Schuhmacher,et al. 2014) Schuhmacher, M., & Ponzetto, S. P. Knowledge-based graphdocument modeling. In Proceedings of the 7th ACM international conference onWeb search and data mining. In Proceedings of WSDM.

# How AI is helping detect fraud and fight criminals

http://venturebeat.com/2017/02/18/how-ai-is-helping-detect-fraud-and-fight-criminals/

AI is about to go mainstream. It will show up in the connected home, in your car, and everywhere else. While it’s not as glamorous as the sentient beings that turn on us in futuristic theme parks, the use of AI in fraud detection holds major promise. Keeping fraud at bay is an ever-evolving battle in which both sides, good and bad, are adapting as quickly as possible to determine how to best use AI to their advantage.

There are currently three major ways that AI is used to fight fraud, and they correspond to how AI has developed as a field. These are:

1. Rules and reputation lists
2. Supervised machine learning
3. Unsupervised machine learning

## Rules and reputation lists

Rules and reputation lists exist in many modern organizations today to help fight fraud and are akin to “expert systems,” which were first introduced to the AI field in the 1970s. Expert systems are computer programs combined with rules from domain experts.They’re easy to get up and running and are human-understandable, but they’re also limited by their rigidity and high manual effort.

A “rule” is a human-encoded logical statement that is used to detect fraudulent accounts and behavior. For example, an institution may put in place a rule that states, “If the account is purchasing an item costing more than $1000, is located in Nigeria, and signed up less than 24 hours ago, block the transaction.” Reputation lists, similarly, are based on what you already know is bad. A reputation list is a list of specific IPs, device types, and other single characteristics and their corresponding reputation score. Then, if an account is coming from an IP on the bad reputation list, you block them. While rules and reputation lists are a good first attempt at fraud detection and prevention, they can be easily gamed by cybercriminals. These days, digital services abound, and these companies make the sign-up process frictionless. Therefore, it takes very little time for fraudsters to make dozens, or even thousands, of accounts. They then use these accounts to learn the boundaries of the rules and reputation lists put in place. Easy access to cloud hosting services, VPNs, anonymous email services, device emulators, and mobile device flashing makes it easy to come up with unsuspicious attributes that would miss reputation lists. Since the 1990s, expert systems have fallen out of favor in many domains, losing out to more sophisticated techniques. Clearly, there are better tools at our disposal for fighting fraud. However, a significant number of fraud-fighting teams in modern companies still rely on this rudimentary approach for the majority of their fraud detection, leading to massive human review overhead, false positives, and sub-optimal detection results. ## Supervised machine learning (SML) Machine learning is a subfield of AI that attempts to address the issue of previous approaches being too rigid. Researchers wanted the machines to learn from data, rather than encoding what these computer programs should look for (a different approach from expert systems). Machine learning began to make big strides in the 1990s, and by the 2000s it was effectively being used in fighting fraud as well. Applied to fraud, supervised machine learning (SML) represents a big step forward. It’s vastly different from rules and reputation lists because instead of looking at just a few features with simple rules and gates in place, all features are considered together. There’s one downside to this approach. An SML model for fraud detection must be fed historical data to determine what the fraudulent accounts and activity look like versus what the good accounts and activity look like. The model would then be able to look through all of the features associated with the account to make a decision. Therefore, the model can only find fraud that is similar to previous attacks. Many sophisticated modern-day fraudsters are still able to get around these SML models. That said, SML applied to fraud detection is an active area of development because there are many SML models and approaches. For instance, applying neural networks to fraud can be very helpful because it automates feature engineering, an otherwise costly step that requires human intervention. This approach can decrease the incidence of false positives and false negatives compared to other SML models, such as SVM and random forest models, since the hidden neurons can encode many more feature possibilities than can be done by a human. ## Unsupervised machine learning (UML) Compared to SML, unsupervised machine learning (UML) has cracked fewer domain problems. For fraud detection, UML hasn’t historically been able to help much. Common UML approaches (e.g., k-means and hierarchical clustering, unsupervised neural networks, and principal component analysis) have not been able to achieve good results for fraud detection. Having an unsupervised approach to fraud can be difficult to build in-house since it requires processing billions of events all together and there are no out-of-the-box effective unsupervised models. However, there are companies that have made strides in this area. The reason it can be applied to fraud is due to the anatomy of most fraud attacks. Normal user behavior is chaotic, but fraudsters will work in patterns, whether they realize it or not. They are working quickly and at scale. A fraudster isn’t going to try to steal$100,000 in one go from an online service. Rather, they make dozens to thousands of accounts, each of which may yield a profit of a few cents to several dollars. But those activities will inevitably create patterns, and UML can detect them.

The main benefits of using UML are:

• You can catch new attack patterns earlier
• All of the accounts are caught, stopping the fraudster from making any money
• Chance of false positives is much lower, since you collect much more information before making a detection decision

## Putting it all together

Each approach has its own advantages and disadvantages, and you can benefit from each method. Rules and reputation lists can be implemented cheaply and quickly without AI expertise. However, they have to be constantly updated and will only block the most naive fraudsters. SML has become an out-of-the box technology that can consider all the attributes for a single account or event, but it’s still limited in that it can’t find new attack patterns. UML is the next evolution, as it can find new attack patterns, identify all of the accounts associated with an attack, and provide a full global view. On the other hand, it’s not as effective at stopping individual fraudsters with low-volume attacks and is difficult to implement in-house. Still, it’s certainly promising for companies looking to block large-scale or constantly evolving attacks.

A healthy fraud detection system often employs all three major ways of using AI to fight fraud. When they’re used together properly, it’s possible to benefit from the advantages of each while mitigating the weaknesses of the others.

AI in fraud detection will continue to evolve, well beyond the technologies explored above, and it’s hard to even grasp what the next frontier will look like. One thing we know for sure, though, is that the bad guys will continue to evolve along with it, and the race is on to use AI to detect criminals faster than they can use it to hide.

Catherine Lu is a technical product manager at DataVisor, a full-stack online fraud analytics platform.