1 最int 型数组,子数组的最大和

#get max array
#得到 最大 子数组
def getmaxarray(arraylist):
    
    currentsum = arraylist[1]
    currentsumlist = [arraylist[1]]
    maxsum = arraylist[1]
    maxsumlist = [arraylist[1]]

    for i in range(len(arraylist)):
        # 如果加入后面的数据大于当前的sum
        if( (currentsum +  arraylist[i]) >  currentsum):
            # 更新当前的currentsum 数据
            currentsum += arraylist[i]
            # 更新当前的currentsumlist 列表
            currentsumlist.append(arraylist[i])

            # 如果当前的sum 大于最大sum  更新最大sum
            if(currentsum >= maxsum):
                maxsum = currentsum
                maxsumlist = currentsumlist
        else:
            currentsum = arraylist[i]
            currentsumlist= []
            currentsumlist.append(arraylist[i])
            # 如果当前的sum 大于最大sum  更新最大sum
            if(currentsum >= maxsum):
                maxsum = currentsum
                maxsumlist = currentsumlist
    return maxsumlist


print(getmaxarray([-1,-3,-10,-5]))
print(getmaxarray([-1,-3,-0,-10,-5]))
print(getmaxarray([1,-3,0,10,-5]))
print(getmaxarray([1,3,0,10,5]))

Continue reading

150 题数据挖掘

https://www.jianshu.com/p/37b5d84a3481

 

 

[机器学习]以下不属于有监督的词义消歧方法的是

  • Flip-Flop算法
  • 贝叶斯分类器
  • 最大熵消歧
  • 基于词典的消歧

 

机器学习模型 error 和模型 bias 和 variance 之间的关系:

  • 没有关系
  • error = bias^2+variance
  • error = bias+variance^0.5
  • error = bias + variance

 

决策树是机器学习中一种基本的分类和回归算法,是依托于决策抉择而建立起来的树。
原理:依托树中的决策规则来预测未知样本的类别和值。
过程:决策树学习算法包含特征选择(从训练数据的特征中选择一个特征作为当前节点的分裂标准),决策树的生成(依据选择特征标准,从上至下递归生成子节点,直到数据集不可再分则停止)与决策树的剪枝(决策树易过拟合,需要通过剪枝来缩小树的结构和规模)。
终止条件:依据选择特征标准,从上至下递归生成子节点,直到数据集不可再分则停止
防止过拟合:剪枝

Continue reading

1.(机器学习理论)请描述推荐系统中协同过滤算法的原理

协同过滤算法,主要的功能是预测和推荐。通过对用户历史行为数据的挖掘发现用户的偏好,基于不同的偏好对用户进行群组划分并推荐品味相似的商品。分为两大类,一类为基于memory的(Memory-based),包括:基于用户的协同过滤算法(user-based collaboratIve filtering)和基于物品的协同过滤算法(item-based collaborative filtering),两种方法都是将用户的所有数据读入到内存中进行运算的;另一类为基于Model的(Model-based),包括Aspect Model,pLSA,LDA,聚类,SVD,Matrix Factorization等,这种方法训练过程比较长,但是训练完成后,推荐过程比较快。
分为

以下三个步骤:
1.收集数据
2.找到相似用户和物品
3.进行推荐
具体请参考:

 
Continue reading

数据结构—拓扑排序详解

1、拓扑排序的介绍

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。
拓扑排序对应施工的流程图具有特别重要的作用,它可以决定哪些子工程必须要先执行,哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用一个有向图来表示,图中的顶点代表活动(子工程),图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行。通常,我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简称AOV网。
一个AOV网应该是一个有向无环图,即不应该带有回路,因为若带有回路,则回路上的所有活动都无法进行(对于数据流来说就是死循环)。在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列(Topological order),由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的,满足上述定义的任一线性序列都称作它的拓扑序列。
Continue reading

1. 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

方案1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

s 遍历文件a,对每个url求取clip_image002,然后根据所取得的值将url分别存储到1000个小文件(记为clip_image004)中。这样每个小文件的大约为300M。

s 遍历文件b,采取和a相同的方式将url分别存储到1000各小文件(记为clip_image006)。这样处理后,所有可能相同的url都在对应的小文件(clip_image008)中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

s 求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

方案2:如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。

Continue reading

Data-Mining试题

2011Alibaba数据分析师(实习)试题解析

一、异常值是指什么?请列举1种识别连续型变量异常值的方法?

异常值(Outlier) 是指样本中的个别值,其数值明显偏离所属样本的其余观测值。在数理统计里一般是指一组观测值中与平均值的偏差超过两倍标准差的测定值。
Grubbs’ test(是以Frank E.Grubbs命名的),又叫maximumnormed residual test,是一种用于单变量数据集异常值识别的统计检测,它假定数据集来自正态分布的总体。
未知总体标准差σ,在五种检验法中,优劣次序为:t检验法、格拉布斯检验法、峰度检验法、狄克逊检验法、偏度检验法。

二、什么是聚类分析?聚类算法有哪几种?请选择一种详细描述其计算原理和步骤。

聚类分析(clusteranalysis)是一组将研究对象分为相对同质的群组(clusters)的统计分析技术。 聚类分析也叫分类分析(classification analysis)或数值分类(numerical taxonomy)。聚类与分类的不同在于,聚类所要求划分的类是未知的。
聚类分析计算方法主要有: 层次的方法(hierarchical method)、划分方法(partitioning method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)、基于模型的方法(model-based method)等。其中,前两种算法是利用统计学定义的距离进行度量。

k-means 算法的工作过程说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。
其流程如下:
(1)从 n个数据对象任意选择 k 个对象作为初始聚类中心;     
(2)根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;  
(3)重新计算每个(有变化)聚类的均值(中心对象);
(4)循环(2)、(3)直到每个聚类不再发生变化为止(标准测量函数收敛)。
优 点:本算法确定的K 个划分到达平方误差最小。当聚类是密集的,且类与类之间区别明显时,效果较好。对于处理大数据集,这个算法是相对可伸缩和高效的,计算的复杂度为 O(NKt),其中N是数据对象的数目,t是迭代的次数。一般来说,K< Continue reading

HMM 概念原理(Viterbi算法)
BEMS序列组合
P(E|B) = 0.851, P(M|B) = 0.149,说明当我们处于一个词的开头时,下一个字是结尾的概率
要远高于下一个字是中间字的概率,符合我们的直觉,因为二个字的词比多个字的词更常见

Viterbi算法

KNN 概念
kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性

NLTK 中文进度

CF(协同过滤)

CW(模型概念)

PMI值 的计算
衡量两个词的共现程度:PMI (Point mutual information) .

问神经网络的实现机制、目标函数的选取、怎么优化的、怎么处理文本、自然语言处理的方法、tesorflow的细节问题等

机器学习和数据挖掘常用的模型和公式,比如回归、HMM等。