一、概念性问题

1、架构的5个来源

需求、涉众、开发组织、架构师、技术环境

2、需求的3类，每一类的定义

功能性需求，质量需求、约束

功能需求：系统需要做什么，系统应当如何为涉众提供价值。

质量需求：系统应当满足的整个系统的理想特性。

约束：是预定义的设计决策。通过接受设计决策、与其他受影响的设计决策进行协调来满足约束。

3、架构的定义

SEI：是整个程序或计算系统的结构(Structure)，包含了程序的元素(Software Elements)和那些外部能看见的元素属性(Properties)和元素之间的关系(Relationship)

IEEE：一个系统的基本组织，包含了了它的所有组件(Components)、组件之间的关系、环境以及指导该系统的设计(Design)和演化(Evolution)的原则(Principle)

4、列举4种tactics

心跳机制：监控系统/服务的可用性，如果不再能收到服务的心跳，则认为服务已经失效/出了故障，可用来提高可用性、可靠性

提高内聚、降低耦合、重构、清晰定义接口：可以提高系统的可修改性，互操作性

提高资源效率，增加资源，控制资源需求、引入并发：系统接收到外部请求后可迅速响应。提高系统性能

时间戳：可用于发现错误序列，尤其是分布式信息传递系统中

事务机制，回滚：便于故障恢复

主动冗余：采用冗余的服务器的机制来保证系统出现故障时不发生可用性缺失。

5、软件架构中的4个活动及各自的输入输出（就是那张颜色丰富的图

确定ASR：发现一些候选ASR

输入：涉众 输出：带优先级的质量属性场景

架构设计：定位ASR，选择、生成和分析设计决策来达成这些质量属性

输入：带优先级的质量属性场景、需求、约束、patterns和tactics 输出：候选views

文档化：设计出来架构后还要让它可被涉众理解和使用

输入：候选view、涉众 输出：选中的views和其结合文本的表示

架构评估：关乎系统成败，有必要花时间确保架构设计可提供需要的东西

输入：涉众、带优先级的质量属性场景 输出：选中的views和其结合文本的表示

二、比较对比问题

1、架构VS设计

1）架构是设计的一部分：架构一定是软件设计，但并非所有的设计都是架构；

2）架构提供了设计的抽象视图，架构是一种high level的设计，是一系列设计决策。

2、架构VS结构

架构包括software elements和它们的外在特性、它们之间的关系。

结构定义了组件接口，但架构还说明组件间的交流和依赖

架构是一种high level的结构，架构定义了结构，结构特性由架构设计决定。

3、软件需求VS质量属性VS架构关键需求（ASR

软件需求 ：包括功能需求、非功能需求；非功能需求or架构需求则是QA的替代术语。

质量属性：在功能需求之上，系统应当满足的整个系统的理想特性

ASR：对于架构会产生重大影响的，会对架构设计决策产生关键影响的那部分质量属性。一个质量属性越困难、越重要，越倾向于成为ASR。

4、patterns VS tactics

1）tactics更加简单，使用单一结构或机制来达成单一架构目标

2）patterns是多种相关设计决策进行组合的结果

3）tactics是构建patterns的组成模块

4）大部分patterns由多种不同的tactics组成

5）二者共同构成软件架构的主要工具

5、styles vs patterns vs views

style：定义元素、元素间关系类型和元素用法约束，关注架构方法，不关注具体上下文和问题；=architecture approach

pattern：体现软件系统基本的结构组织模式。关注具体上下文中的问题和具体上下文中如何解决；=（problem+context）->architecture approach

view：表示系统中特定类型的元素及元素间关系；不同视图支持不同的目标和用户，强调不同系统元素和关系；不同视图在不能程度上表示不同的质量属性。

6、产品线VS单一产品

产品线SPL：一系列可满足特定市场部门或任务的特定需求的软件系统 共享 一组通用的、被管理的特性集，它们是以规定的方式，从一套共同的core assets中开发出来的。

SPL通常是多个同步的变体，而单一产品使用版本和发布来控制。

SPL不仅仅是一个可重构的架构，它可以使用系统的变化。

三、步骤问题

1、ADD

step1：确定有足够的需求(输入）

• 涉众根据业务目标为需求划分优先级
• 将质量属性表示为场景

Step2：选择一个系统的元素来分解

• 如果是第一次迭代，则选择整个系统进行本次分解，将所有需求都被分配给系统
• 如果系统已经根据需求被分解，则选择其中一个元素

Step3：为选择的元素定义ASRs

• H, M, L 的二维数组：(对利益相关者的重要性，对架构实现的影响)即(Importance，Difficulty)
• 第一个表示：这条需求对涉众的重要程度
• 第二个表示：这条需求对架构的影响有多大

Step4：选择一个符合架构必要需求的设计理念

• 确认设计关注点
  • 如何满足ASRs
• 为次要关注点列出不同的模式和策略
  • 需要为选择的模式选定度量值，估计度量值的取值
• 选择合适的模式和策略
  • 根据他们对ASRs的优缺点进行选择
• 决定架构必要需求和模式策略之间的关系(确定模式/战术与ASRs之间的关系)
• 得到架构视图
• 评估并解决不一致问题

Step5：列出架构元素并分配职责(实例化架构元素并分配职责)

• 将父元素的职责在子元素中进行分配,分析和文档化设计决定

Step6：定义元素接口

• 接口描述了元素需要什么和提供什么的假设

Step7：确认需求，为元素构造约束

Step8：重复以上步骤直到所有架构必要需求都被满足

2、ATAM

3、PK的4+1views

逻辑视图：描述架构中至关重要的架构元素和他们之间的关系 Logical

过程视图(进程视图)：描述元素之间的交流依赖 process

物理视图：主要的进程和组件是怎么映射到硬件 Physical

开发视图：捕捉软件组件的内部组织 Development

架构用例：+1，架构需求，与多个视图相关 Architecture use cases

4、文档化——如何选择view：

1）建立涉众/视图表格

2）合并视图（确定视图边缘，将边缘视图与其他视图结合）

3）对视图优先级排序

5、如何确定ASR：

四、Patterns/Style 这部分git上总结的很好

1、patterns分类

module关注组件内部结构

component-connector关注系统级 不同系统间的相互关系

allocation关注系统与外部环境

pattern是什么：一系列适用于多次出现的问题的架构设计决策，可根据问题出现的上下文进行参数化设置。

2、以MVC为例说明Component-connector模式

MVC模式把功能分解为3个组件：model view和controller

model：表示应用的核心数据和状态

view：是用户接口组件，用于向用户展示信息

controller：协调model和view，管理model和view间的交互，把用户行为转化为model或view的变化

而notifies relation把model view controller的实例连接起来。

3、分层模式的上下文、优缺点Layerd

分层模式：定义了层与层之间的单向允许使用关系，通常使用代表了层的方框的叠加来表示层的依赖关系。层：提供一组内聚服务的模块组。换句话说：层内是内聚服务，层间演个单向调用

优点：

把复杂的问题分解为多个组件；

提高可扩展性和可复用性；

缺点：

层的增加会带来系统的成本和复杂度的增加；

给性能带来负面影响

设计不好的层会妨碍到抽象；

过多的层间关系不利于可移植性和可修改性

4、代理模式的上下文、优缺点Broker

代理模式：broker是运行时组件，协调client和server之间的交流。

优点：

高可扩展性，高可用性；

server可以被动态修改

缺点：

延迟，通信瓶颈：增加了一层，会延迟client和server间通信，可能会成为通信瓶颈。

broker会增加系统复杂度

broker可能出现单点失效；

broker可能成为被攻击的目标

broker难于被测试

5、MVC模式

把系统功能分为3个组件：MVC，Controller是中介；

通知关系 连接三部分的实例，并通知相关元素的状态变化。

缺点：

用户接口简单的情况下，带来的复杂度是不值得的

不一定能很好地使用一些用户接口工具

6、piper and filter模式

数据从系统外部输入到输出的过程中，经过一系列由管道连接的过滤器的变化处理

过滤器：一种转化数据的组件，过滤器间可以并行处理

管道：将数据从过滤器的输出端口传递给另一个过滤器的输入端口的连接件，不会修改数据

缺点：

不适合交互式系统

有大量独立的过滤器会增大大量的计算开销

不适合长时间的计算任务

7、CS模式

客户端发起与服务器的交互，根据需要 调用服务 等待返回请求结果

客户端：调用服务器服务的组件，直到它所需要的服务的端口

服务器：给客户端提供服务的组件，有提供服务的端口。

请求/响应连接件：使用请求响应协议实现的连接件，客户端使用它来调用服务器的服务。

缺点：

服务器会成为性能瓶颈

服务器淡定失效

在哪里放置功能的决定是复杂的，切系统构建后很难改变

8、peer to peer模式

计算由多个节点合作完成，各个节点之间要通过网络相互提供服务和相互调用

点：网络节点上独立的组件

请求响应连接件：用于连接网络上的点，查找其他点，调用服务

缺点：

安全性，数据一致性，数据/服务的可用性，备援和恢复都变的复杂，

小的点对点系统可能无法实现质量目标，如性能和可用性

9、Service-oriented模式

计算由一组相互合作的组件提供，他们在网络上提供服务，包括服务提供者，服务消费者，SOAP连接件、REST连接件

缺点：

构建复杂

中间件带来性能开销

服务成为性能瓶颈，无法提供性能保证

10、publish-subscriber模式

组件发布和订阅时间，发布事件后，基础连接件将时间分发到所有注册的订阅者。

缺点：

增加通信延迟，对伸缩性降低，消息传递时间的预测降低

缺乏对消息顺序的控制，消息是不受保护的

11、shared-data模式

数据存取器通过共享的数据商店通信。数据商店负责实现数据持久化。

缺点：

数据商店性能瓶颈；单点失效；

数据的生产者和消费者可能耦合紧密

12、Map-reduce模式

提供了一个分析大规模分布式数据集合的框架，在一组处理器上并行处理。Map提取和转化；reduce转载结果

优点：并行，因而低延迟，高可用

缺点：

数据集小时，开销不合理

数据不能分为小的子集时，并行就没有优势

需要多reduce的操作是复杂的

13、multi-tier based模式

计算结构由多个逻辑划分的组件团体组成。每一个团体就是一个层(tier)。

缺点：前期成本高，复杂度高

Layer是实际存在的清晰的，有层次关系的组织

Tier 不是在物理上实际存在的，是一种逻辑上的，概念上的组合，没有明确的层次关系

五、Designing：

1、ADD

2、4+1 views

六、Documentation：views and beyond

1、structure views的3种类型：

Module view：一系列提供内聚职责的实现单元的集合。从属依赖衍生。

C&C style：展示有了运行时表现的元素 组件：程序、client、server、数据存储等，组件通过端口和连接器交互，连接器是组件间交互的通道。关联。

Allocation：软件单元和环境元素间的映射。目标是比较环境提供的特性与软件元素需要的特性是否相符，来判断分配是否成功。分配。

2、视图的4种分类和目标：

质量视图：用于表示质量属性是怎样的。

Module视图：在代码级别表达系统的功能，用于提供对工作任务定义的支持、提供预算信息和系统应管理的结构信息。

C&C视图：用于展示系统如何运行，通过确定运行时元素的结构和行为指导开发，帮助推导运行时系统质量属性。

Allocation视图：通过对比环境提供的特性与软件元素需要的属性，判断allocation成功与否。

3、列举3种结构视图各自包含哪些style：

Module：分解、使用、泛化、分层、切面、数据模块（分尸犯曾切树）

C&C：管道过滤器、C/S、P2P、SOA、发布者-订阅者、共享数据、多层（PCPSSSM）

Allocation：部署、安装、实现、工作分配、其他分配（不按时工作）

4、documentation package的两部分，各自的目标：

architecture view：

架构视图是一系列特定类型的系统元素和这些元素间关系的表示。

能帮助把系统实体分解为感兴趣和可管理的表示。

documentation beyond views：

超越视图的文档包括架构文档信息和架构信息。

展示了文档路线图，视图如何被文档化的方式，系统概述，视图间映射，基本理论和目录。

5、为什么需要使用多种不同视图来记录架构？

视图用来表示系统中特定类型的元素及元素间关系；

不同视图支持不同的目标和用户，强调不同系统元素和关系；

不同视图在不能程度上揭示不同的质量属性。

七、Evaluation：ATAM

考察方式：

ATAM每步中参与的涉众和涉众在其中的角色；

ATAM每步的输出

ATAM每步做什么

1、评估（why when how）：降成本、降风险、质量保障

why：

大型项目经常推迟交付或超支，或由于设计缺陷不能正常工作；

项目进行过程中有时需要评估并重新设计；

评估的好处：尽早发现问题，降低解决问题的成本；

可以传播架构设计的最佳实践，可以提供优秀项目技术管理。

when：

越早越好：升级更新时；设计时；构造时

尽早评估的原因：有时间修正；修正错误成本不高；有效的质量保障和降低风险；很好的商业活动。

How：

发现风险点；识别错误的架构选择；保证解决了质量属性；基于质量属性场景；场景与架构组件映射，评估架构是否满足质量属性；风险risks；敏感点sensitivity points；权衡点tradeoffs

2、ATAM涉众：

包括三类：设计者；伙伴；外界人士 designers peers outsiders

具体主要有：项目设计决策者，评估小组（评估小组组长），架构涉众，项目经理，系统客户，

每步参与者：

Phase0: 评估计划（评估小组组长，关键的项目设计决策者 （组长和关键策

Phase1: 评估1（评估小组，项目设计决策者（组策

Phase2: 评估2（评估小组，项目设计决策者和架构涉众（组策众

Phase3: 后续（评估小组，主要涉众（诅咒

3、ATAM步骤：Architecture tradeoff analysis method（4个phase：

Phase0: 参与者准备阶段

Phase1: 评估1 包括6步：

1）介绍ATAM方法（评估小组组长

2）介绍商业动机（项目经理或系统客户

3）介绍架构（首席结构师

4）识别使用的架构方法（评估小组

5）生成质量属性效用树（评估小组和项目设计决策者

6）分析架构方法，确保方法时正确的，获取风险点、非风险点、敏感点、权衡点列表（评估小组

Phase2: 评估2 包括9步（6+3）

1）介绍ATAM方法和之前的结果，重复以确保涉众也知道方法并回顾分享之前2-6步的结果

7）头脑风暴，场景划分优先级，与质量属性效用树进行比对（评估小组问涉众

8）分析架构方法，使用新产生的优先级靠前的场景，架构师解释与之相关的架构决定

9）展示结果：（评估小组

Phase3: 后续工作

1）参与者：评估小组和主要涉众（诅咒

4、ATAM每步输出

Phase0: 评估计划（谁、什么时间、提供什么样子的评估报告

Phase1: 评估1（架构简要展示、业务目标、质量属性和相关场景、效用树、风险和非风险点，敏感点，权衡点

Phase2: 评估2（优先级场景列表、风险主题和商业动机、每个涉众关心的业务目标

Phase3: 后续工作（最终的评估报告

八：质量属性和scenarios

availablility：可用性；

interoperability：互操作性。多个系统通过接口交换信息，包括交换和正确推断信息

modifiability：可修改性。一个更改所消耗的时间和金钱。

performance：性能。系统响应时间和系统满足时间需求的能力（=处理时间+等待时间

security：安全性。系统在向合法用户提供服务的同时，阻止非授权使用的能力。

Testablility：可测试性。通过测试揭示软件缺陷的容易程度。

Usability：易用性。用户完成特定任务的容易程度和系统提供的用户支持的种类

X-ability：可变性、可移植性、可伸缩性、可部署性、可复用性

Mobility：移动性，解决平台之间的移动和支持

safety：安全性，和security相比，不是有意为之，关注自身安全，防止偶然可能造成破坏的对象

Variability：可变性，特殊的可修改性

Portability：易于做改变，用于另一种平台

Development Distributability：支持分布式软件开发

Scalability：可伸缩性，对软件系统计算处理能力的设计指标

Deployability：可部署性

关于type inference

常见场景：
1、泛型
类实例化，调用构造器时：

1

Map<String, List<String>> myMap = new HashMap<>();

Java 7 diamond语法：调用泛型类的构造器时可以用空尖括号只要上下文可推断。称作diamond。
注意：想让type inference推断时必须要有尖括号，不写尖括号会导致unchecked。
2、调用普通泛型方法时：
例1:

1

BoxDemo.<Integer>addBox(Integer.valueOf(10), listOfIntegerBoxes);

可简写为：

1

BoxDemo.addBox(Integer.valueOf(10), listOfIntegerBoxes);

例2:

1
2
3

List<String> list = new ArrayList<>();
list.addAll(new ArrayList<? extends String>);//在java7中要具体写出
//list.addAll(new ArrayList<>());//也可以，java8允许

这里List的addAll方法的参数expect的是ArrayList<? extends String>()，根据第4种场景的说明，编译器推测newArrayList()是个newArrayList<? extends String>()，因此list.addAll(new ArrayList<>()) 也是允许的。
这里要记住的要点就是 要传给方法它expect的参数类型的实例。不管这个实例是个对象应用还是个基本类型的值。

3、调用有返回值的泛型方法并赋值时，根据target types推断参数类型：

1
2

static <T> List<T> emptyList();
List<String> listOne = Collections.emptyList();

4、java 8：根据target types推断参数类型扩展至可以根据target argument来推断
例子：

1
2
3
4

void processStringList(List<String> stringList) {
    // process stringList
}
processStringList(Collections.emptyList());

这里Collections.emptyList()返回的时List，而processStringList方法expect的参数时List，于是编译器推测T是String

5、泛型/非泛型类都可以有泛型的构造器。
泛型方法中的泛型构造器：

1
2
3
4
5

class MyClass<X> {
  <T> MyClass(T t) {
    // ...
  }
}

对它的调用：
1）

1

new MyClass<Integer>(“”)

//这句说明创建了一个X为Integer的MyClass实例，并调用的是这个构造器，且构造器的类型参数T是String，这是java通过参数””type inference出来的。
2）

1

MyClass<Integer> myObject = new MyClass<>("");

//这里的<>和“”都利用了type inference

哈密顿回路：
1、指一个对图的每个顶点都只穿越一次的回路。也可以 定义为n+1个相邻顶点v0, v1, … ,vn, v0的一个序列，其中序列的第一个顶点和最后一个顶点是相同的，而其他n-1个顶点是互不相同的。
2、当这个图是加权图时，求该图的最短哈密顿回路，就是传说中的旅行商问题（TSP）。

使用蛮力法求解：
1、首先规定作为起止点的顶点。由于回路是无向的，因此起止点可直接任选；
2、规定中间点的其中两点的先后次序。这步是对基本穷举的简单优化：对每对线路（每条回路都有顺时针和逆时针两种序列表示法）来说，不同的只是线路的方向，因此，若选择任意两个中间顶点，并规定该两顶点的先后次序（比如顶点a必须排在b前方），就可以把顶点序列的数量减半。
（这一改进后，排列的总次数仍需要(n-1)!/2次，这意味着除非问题规模很小，不然穷举查找法是不实用的）。
3、通过生成n-1个中间点的组合来得到所有的线路，计算这些线路的长度，排序求得最短线路。

分配问题：
已知成本矩阵，求最优分配方案。
成本矩阵：行列分别为worker和task，元素值为对应worker完成对应task的开销。
现只研究task数=worker数，且每个任务能且只能分配给一个人的情况。也就是说有效的方案的成本总和是从成本矩阵中取出n个既不同行又不同列的元素求和得到的。
解决算法：
1、蛮力：穷举法。对于n*n矩阵，要计算n!个成本值，时间复杂度O(n!)
2、匈牙利法：
方法步骤：
1、将成本矩阵的每行（列）减去该行（列）最小的元素；
2、用最少的划线覆盖成本矩阵中的所有零；
3、检查是否：最少划线数=矩阵行（列）数，若相等则完成，最优方案是当前的一个全零的成本组合；若小于行列数，则进行步骤4；
4、检查此时没有被划线覆盖的元素，其中最小值设为min，将没有被覆盖的每行减去min，被覆盖的每列加上min（注意这里的行或列并不因成本矩阵而异，且这里的行和列可以交换，得到的成本矩阵完全一样），再跳转至步骤3

原理、可行性分析：
1、如果从成本矩阵的任一行或列的所有元素中同时添加或减去数字，那么，所得矩阵的最优分配也是原始矩阵的最优分配。
这一原理很好理解：
对于同一任务，若对每个worker同等程度地降低难度（且这个降低程度不会使得某一worker完成的成本低于0），则使用穷举法计算总成本时，相当于每个方案同时减掉了一个值，显然对结果的排序没有影响。同理，对同一个人，若将其完成每个任务的成本同时降低一个值，也是相当于每个方案同时减掉了一个值，也是不会影响结果的。
为什么是相当于每个方案同时减掉一个值呢：因为一个人应该且只应该被分配一个任务，也就是说每个方案里，对每个人取且只取他的完成某一个任务的成本值，对一个任务也是取且只取它被某一个worker完成的成本值，那么所有行/列的成本值的同时加减肯定就是对每个方案的结果产生相同程度的影响啦。
但其实这个原理只是对匈牙利法的第一步的一个解释。
2、而对第4步，其实可以看出，这样操作之后是将未被划线覆盖的元素减去min，被一条线覆盖的元素值不变，处于被两条线覆盖的交点处的元素加min，这样做的意义在于：处于线覆盖交点处的元素是：虽然成本低，应优先分配这一方案，但由于1v1的分配要求，不能对同一人或同一任务多次分配，所以要酌情把交点处的值补偿回来。（是这样的吧？过几天再想想）

决策树：
非叶节点表示根据属性判断，分枝表示判断结果流向，叶节点表示分类结果（类标号）

主要流程：
1)选择在这一层用哪个属性作分类属性（这里的选择标准就是属性选择度量）
2)根据1)在当前节点进行数据的分类
3)按上两个步骤做下去，直到到达叶节点

问题细节：
何时到达叶节点、叶节点的节点值怎么确定：
1、如果流到这个分枝的所有数据都已经属于同一个类了，那么这就是个叶节点，节点值就是这个类的类标号。这就是可能会出现属性没用完但是已经分好类的情况；
2、如果流到这个分枝的所有数据属性取值都一致，但它们的类标号又是不一样的，也就是说没有哪个属性可以把这个分枝里的数据区分开了，那么这就是个叶节点，节点值按照少数服从多数来取。这就是可能会出现属性用完了但是没分好类的情况；

属性选择度量：
这个概念解决的是“如何选出一个最适合在这一层作为分类标准的属性”，最适合，在这里就是 “按照属性的不同取值来分类，分出了按照类标号分类的效果，或是最大程度上帮助数据朝着这个效果上进展”。
对于这个“最适合”，有几种经典的度量方式：ID3（信息增益）、C4.5（增益率）、GINI index（基尼指数）

ID3：
熵：混乱度
信息增益：混乱度变小的越多，信息增益越大
计算公式：blahblah

C4.5：
blah
好累，改天再写

分类算法：
使用训练集（数据元组+对应类标号），选用某种分类算法进行监督学习，得到一个分类器；再使用和训练集没有重合的检验集来使用分类器分类，检验分类器的准确率。如果准确率可以接受，那这个分类器就可以用啦。

朴素贝叶斯分类法：
用途：给定一个元组，可以计算出这个元组最应该被分到哪个类。使用条件概率来度量“应该程度”
原理：利用贝叶斯公式算出以给定元组矢量值为条件，在训练集上计算出现类i的概率，能使这个条件概率取最大值的类i就是该元组应该被分到的类。
基于类条件独立性的假定+贝叶斯定理，因此名叫朴素+贝叶斯。
类条件独立性：假定一个数据的各个属性对分类标号的影响是相互独立的。（其实也就是每个属性的取值之间没有相关性。和统计学中的条件概率要求随机事件之间相互独立是一回事）
贝叶斯定理公式（也就是条件概率公式）：P(A|B)=P(B|A)*P(A)/P(B)
大白话版本：朴素贝叶斯分类法，其实是提供打了标签的历史数据（这里就是训练集），然后对一条未打标签的新数据，利用条件概率算算这条历史数据中这条新数据的取值条件下应该被打上每种标签的概率，哪个概率最高就打哪个。

一些脑中预定义的感知：
1、每个元组都是一个向量，提供了这一条数据在不同属性维度上的取值。
2、具体有多少种分类是已知的：就看训练集上的类标号有多少种。
3、训练集数据提供：很多n维向量+每个向量对应的类标号，其实都可以理解成有很多n+1维向量，只不过其中一维是类标号这个特殊的属性。
4、于是：用C来表示类标号，现有m种分类结果（C1,C2,…,Cm），一个待求概率的n维向量X（在各维度上的值分别为x1,x2,…,xn），求发生X的条件下，类标号上出现Ci的条件概率，也就是对每条数据求m个条件概率，概率最大的Ci就是这个向量X的分类结果。
5、朴素贝叶斯分类器可以说是不存在训练的过程，一堆打了标签的数据加上贝叶斯公式其实就是分类器本器了。

具体思路：
1、这个问题下的公式写作：P(Ci|X)=P(X|Ci)P(Ci)/P(X)
2、比较哪个Ci能使P最大，只是个比较问题，不需要每个P都求出具体值。而每个P都有1/P(X)这个大于0小于1的因子，所以计算时可以同时忽略这个因子。于是问题转化为求哪个P(X|Ci)P(Ci)最大。
3、P(Ci)很好求， 看所有数据里属性C中C=Ci的占比就可以了
4、P(X|Ci)并不好求：因为X是个n维向量，对于每个元组依次匹配各个维度上的取值，在n很大的时候开销就变很大了。而发生Ci的条件下出现(x1,x2,…,xn)的概率，换个描述法就是发生Ci条件下，出现x1且x2且x3且…且xn的概率。于是这时引入了“朴素”的假设：假设这些且的属性怎么取值是相互独立的，那么P(X|Ci)=P(x1|Ci)P(x2|Ci)…P(xn|Ci)，而这里的每一项P(xk|Ci)都是很容易求出来的。
5、对求出来的m个P找到最大的那个Ci

问题细节：
a)前面所述是针对属性值是离散值的情况，当属性值是连续值时，有两种办法：
1、使用分箱等离散化方法把属性值分成几类，于是转化成离散值
2、假定连续值属性服从正态分布，那么由训练集数据可以求出正态分布的均值和方差，也就确定了正态分布的概率公式，把xk代进公式就得到概率啦
b)遇到零概率值：
如果乘积的因子中出现一个零概率值，那其余所有的因子就算再大，这个乘积也只能是0了，这显然是不合理的。
解决办法：
laplace校准：假设训练集非常大，那么对于出现0值的这种属性k-类标号Ci情况，如果属性k有t种取值，那就假设多了t条数据，它们分别是xk取t种取值，类标号为Ci的。这样再算概率，就会把0值变成一个合理的小值，非零值基本没变，这种校准方法还是很合理哒。

代码实现：
放到实际问题里基本就是很多查询语句select count(*)完了再各种求比值求乘积，没什么好实现的。

算法评价：
1、某些领域，它的准确率跟决策树或是神经网络这些复杂的分类算法可以相媲美了
2、假设类条件独立，但现实中不可能属性间都独立的，这是个局限
3、朴素贝叶斯分类器的思想，可以说是，计算已给特定值的数据 映射到 类标号集上的贴合程度，最贴合的就是结果。朴素贝叶斯里的贴合程度用条件概率来描述。基于这个思想应该还可以用其他的模型或是公式来求这个“贴合程度值”。总之公式很简单，思想很基本，但思想又很经典。

题目：求连续子数组的最大和
要求：时间复杂度O(n)
算法思路：
基于动态规划的思想：
1、算法中维护两个最大和：全局最大和max、局部最大和sum
2、全局最大和的维护：当局部>全局时，更新全局，将其赋值为局部值
3、局部最大和的维护：若当前局部<0，则新的最大和将不包含前面累积的最大和（因为前面的累积 对于 得到最大和 起的是负作用），那么新的最大和将是下一个元素本身。若当前局部>=0，则新的最大和将包含前面累积的最大和（前面的累积起正作用），那么新的最大和将是旧最大和（即前面累积）+下一个元素
4、这里的思想就是：根据前面累积的和起正作用还是负作用，来判断是否要重新起一个新的子数组的头；而往前面的累积上加新元素应当加到何时停止，则是通过max与sum的比较来看的：如果sum大，说明新加的元素起到的是正作用，如果sum不如max大，说明新加的元素起到的是负作用。直到sum中加的一系列连续的新元素起到正作用的时候，才更新max，不然max就一直停留在之前那个最好的局部最优的值上
5、也就是说局部sum维护的是子数组的头要从哪里开始才能达到最优，而全局的max维护的是子数组的尾在哪里结束
6、另外：如果要求的不止是最大和，还要求子数组（也就是记录产生这个最大和的子数组的起止下标，那就还是基于局部和全局的思想，维护两对起止下标就可以了，只有sum>max导致max更新时，全局下标才跟着局部下标更新；局部下标则在另起新数组时更新为起止都是新元素下标，不另起时，每加一个元素就把尾端下标+1更新就可以了）

java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class MaxSumSubset {
    private int p,q;//全局起止下标
    private int m,n;//局部起止下标
    public MaxSumSubset(){
        this.p=0;
        this.q=0;
        this.m=0;
        this.n=0;
    }

    public int getP(){
        return this.p;
    }

    public int getQ(){
        return this.q;
    }

    public int getMaxSum(int[] A){
        int max = 0;//全局最大和
        int sum = 0;//局部最大和
        for(int i=0;i<A.length;i++){
            if(sum<0){
                sum = A[i];//前面累积起负作用时，用下一个元素另起一个新累积
                m = i;
                n = i;
            }else{
                sum += A[i];//前面累积起正作用时，在累积基础上加新元素
                n++;
            }
            if(max<sum){//局部大于全局时，更新全局
                max = sum;
                p = m;
                q = n;
            }
        }
        return max;
    }
}

main函数测试：

1
2
3
4
5
6
7
8
9

public class Main {

    public static void main(String[] args) {
        int[] a = {1,-2,3,5,-4,9,16,-7,5};
        MaxSumSubset mss = new MaxSumSubset();
        int max = mss.getMaxSum(a);
        System.out.println("sub set is from "+ mss.getP() +" to "+ mss.getQ() + " and max is "+ max);
    }
}

一个关于spark的介绍：http://www.csdn.net/article/2015-07-10/2825184
课程实践：
目标一：系统搭建
目标二：使用spark进行数据处理
系统搭建步骤：
1、安装HDFS
·下载Hadoop：http://hadoop.apache.org/releases.html
·配置Hadoop集群：http://hadoop.apache.org/docs/r3.0.0-
alpha4/hadoop-project-dist/hadoop-common/ClusterSetup.html
· HDFS自然就可以使用了
2、安装Spark
·下载Spark：http://spark.apache.org/downloads.html
·配置Spark Standalone集群：http://spark.apache.org/docs/latest/sparkstandalone.html
3、安装MongoDB
·下载MongoDB：https://www.mongodb.com/downloadcenter?
jmp=nav#community (页面有安装指南)
·下载Mongo Spark Connector：https://www.mongodb.com/products/spark-connector
4、注：
Hadoop需要Linux操作系统，建议使用redhat
设置SSH无密码登录
安装JDK、Scala

1、首先在win10系统的主机上安装Linux双系统；或选择装虚拟机（更顺利）
安装双系统步骤：
(1)下载Linux系统镜像，可选择redhat、CentOS或Ubuntu等。这几种Linux发布版本的区别稍后可以再多了解一下。
(2)使用UltraISO软碟通的写入磁盘映像功能将Linux镜像写入到准备好的u盘（这个过程会首先把u盘格式化成fat32格式，所有数据会被覆盖，因此要提前对U盘做好备份）
(3)重启插且仅插上述u盘的电脑，开机过程中在合适的时机（还不是很清楚合适时机具体是什么时候，暂且常按）按下F12（或esc）进入启动设备菜单，选择usb并回车，下一步回车确认安装u盘所带系统。
(4)选择语言时区什么的，比较简单。复杂一点的是手动分区的过程，需要手动设置挂载点和分配空间。过后可以深入了解一下细节。一般包括根目录/，/boot，/home，/swap（交换分区，作用差不多类似于虚拟内存），剩余空间自动分给/vars。这里遇到了一个问题：最多只能添加3个挂载点，并不是顺序问题，不知道为什么。
(5)设置root密码和添加用户，重启电脑。这里遇到了一个问题：重启完仿佛什么都没发生一样回到了Windows，后来听到说原因可能是机房电脑装了增霸还原卡，需要先进入BIOS卸载掉它。还没有试，增霸还原卡也不是很了解，回头再去做一下。
PS:
格式化u盘为FAT32的步骤：http://www.ddsofts.com/windows/format2fat32/
安装centos系统步骤可以百度win10和centos双系统安装步骤，有很详细的图文教程。

2.于是我选择放弃，装了虚拟机。系统最初还是用的centOS镜像，但它某些设置不符合云计算实践要求，于是换了redhat
3.to be continued…

知识点提纲：

第二章：关系模型的基本概念与基本理论
2.1 数据库的基本概念
··数据库，数据库管理系统(DBMS - database management system)，数据模型(data model)
2.2 关系模型的基本概念
··数据结构：二维表(table/relation)，属性(column/attribute)，元组(row/tuple)，表头(table heading)，域(domain)
··约束规则(relational rule)
··键(key)与超键(superkey)
··空值(null value)
2.3 关系模型的基本理论 — 关系代数(relational algebra)
··表/关系在关系代数中的表示
··关系代数中的运算符：
··传统的集合运算符（并、交、差） & 纯粹的关系运算符（投影，选择，笛卡儿乘积，自然联接，除法，θ-联接）
··基本运算（并，差，投影，选择，笛卡儿乘积） & 扩充运算（交，自然联接，除法，……）
··难点：减法、除法和表自身的连接运算
··关系代数的应用

Ch2 知识点详解
2.1 数据库的基本概念
数据库：为一个共同的目的而保存起来的所有数据的集合。
数据库管理系统：DBMS，是一套计算机程序，它把企业的数据以记录的形式保存在计算机中。
数据模型：data model，是一套描述如何将现实世界的数据在概念上用电子信息表示的定义，它还表示为用来操作这些数据的一类操作。
几种数据模型：
Hierarchical Data Model/层次数据模型（树）
Network Data Model/网状数据模型（图）
Relational Model/关系模型（表）
Object-Relational Model/对象关系模型 （不受第一范式规则约束的关系模型、表中元素可以是集合）。
2.2 关系模型的基本概念
数据结构：
表/关系(table/relation)：file of records。表是以行和列的形式组织起来的数据的集合(wiki)。
列/属性(column/attribute)：field names of records。
行/元组(row/tuple)：records of a file。
表头/模式(table heading/schema)：列名的集合。
域(domain)：可以被用作表的属性值的常数的集合。
约束规则(relationarule)：
Rule 1. 第一范式规则：在定义的表中，关系模型坚持不允许含有多值属性和含有内部结构的列。
Rule 2. 只能基于内容取行规则：只可以通过行的内容，即每一行中所存在的属性值来检索列。
Rule 3. 行唯一性原则：关系中的任何两个元组的值在同一时刻不能是完全相同的。
Rule 4. 实体完整性规则：表T中的任意行在主键列的取值都不允许为空值。

超键(Superkey):表的任意两行数据在该列的集合上都有唯一的值，类似于线性代数中向量组的一个“代表”，且该向量组中的向量不需要是线性无关的。
键(Key)：组成键的列集合中再也没有子集也是表的超键。亦即不含有多余属性的超键。类似于线代中向量组的一个极大无关组。
候选键(Candidate Key)：关系的所有键。亦即不含有多余属性的超键的集合。类似于线代中向量组的全部极大无关组。
主键(Primary Key)：被数据库设计者选择出来作为表中特定行的唯一性标识符的某一个候选键。
空值(null value)：未知的或尚未定义的值。（计算平均值时被剔除）

2.3 关系模型的基本理论——关系代数(relational algebra)
表/关系在关系代数中的表示
关系代数中的运算符
1、集合运算：R ∪ S R ∩ S R – S R × S
兼容表：表头相同且属性的域相同。
并（∪）、交（∩）、差（-）是针对行的操作；
赋值（:=）是针对表的操作；
乘（×）即对两个表的所有做作笛卡尔乘积。
2、自然关系运算：投影、选择、连接、除
投影运算：R在Ai1, Ai2, … , Aik上的投影用R[Ai1, Ai2, … , Aik]表示，如CUSTOMER[name]。即把某几列从表中选出，重复的值会被合并。
选择运算：S where C，C也可以是C and C’，C or C’或者not C。
连接运算：R ∞ S，即选出属性重叠部分值相同的元组。没有共同属性时连接的结果与笛卡尔乘积相同。
除运算：乘积的逆运算（每行除后取交集），用于处理“所有”问题。
3、扩充运算：外连接、θ连接
外连接：R ∞0 S，即将两个表完全“并”起来，无对应值时补null。
左外链接：R ∞L0 S，即保留左边未匹配的行，右边补null。
右外链接：R ∞R0 S，即保留右边未匹配的行，左边补null。
θ连接：θ可以是{>, <, >=, <=, =, <>}中的一个。表示为R ∞Ai θ Bj S，即两个表满足θ条件的连接。若Ai和Bj同名，则表示为R ∞R.Ai θ S.Bj S。

难点：减法、除法和表自身的连接运算
关系代数的应用