你真的适合当自由职业者吗?

你真的适合当自由职业者吗?

对于绝大多数人而言,大家基本上都是在公司,企业或者政府部门工作,借助平台和个人的力量来获得相应的报酬,那么一直从事这样的工作很可能会让人觉得日复一日,没有激情,创意不足。因此,就会有人向往一种自由自在的工作状态,看着别人发表旅游文章同时希望自己也能够过上说走就走的生活,看着别人开咖啡店的时候也想着自己啥时候也去开一个咖啡店。总之,最终要做到自己当自己的主人,不再为了一些工作上的琐碎事情所搅扰。

通常来说,自由职业者(self-employed)指的是自己雇佣自己,不属于任何组织,在自己的指导下找合适的项目做,通过自己的能力和付出来获取相应的报酬。如果要找到合适自己的项目,那么首先就要知道自己所擅长的领域是什么。有的人可能觉得自己特别擅长写作,可以靠自媒体写作来养活自己;有的人觉得自己擅长烹饪,因此可以通过开一家小店来盈利;有的人觉得自己讲课水平优秀,可以通过开一个培训班来实现财富自由。

说到这里,笔者就想到曾经在知乎上看到过一个问题,“普通人和专业运动员的差距有多大?”其中有一句话给我留下了深刻的印象,那就是“永远不要用你的业余爱好来挑战别人吃饭的本事”。意思就是你觉得你所擅长的东西其实在专业选手面前其实根本不值得一提。你觉得你自己擅长写作,但是你跟中文系,新闻转播专业的同学比起来怎么样?你觉得你擅长烹饪,但是你就能够保证做饭的水平能够超越专业厨师吗?你觉得你能够开培训班,但是你能够比专业的培训机构抢到更多的生源吗?结合自己的经历,之前也有不少的人说自己对数学有着浓厚的兴趣,特别想去攻读一个数学PHD学位,但是目前情况是只学过微积分,希望请教一下数学本科的相关书籍和学习步骤。这种时候只要向他推荐一本 Rudin 的《数学分析原理》,基本上也就没有然后了。因此,一个人觉得自己非常擅长的某个领域很可能只是一种错觉,因为在职业选手面前实在是不堪一击。

在公司的时候,基本上还不太需要担心自己没有事情可以做,按部就班地工作就能够获得相应的报酬。但是一旦成为了自由职业者,有很多的事情就必须要自己一个人去面对,例如如何选择合适的项目,如何与客户沟通,如何保证项目的合理进展,如何保证合同的顺利签署等等,所有繁杂的事情都压在了一个人的身上。在这种时候,自由职业者就必须要向市场证明自己的价值,否则很可能连一份合同都拿不到,甚至连自己的赚钱系统都无法顺利的搭建。最后很可能证明的事情就是,你之前觉得你所擅长的事情,其实在市场上根本一文不值。

就算有了自己的赚钱渠道,例如自媒体写作,开咖啡店等。怎么安排自己的工作时间就是另外一个问题了。读过PHD的人都知道,除了那些整天要去实验室做实验的PHD们,理论研究的PHD们时间一般来说是相对自由的。在自由的时间里,有多少PHD是做了有价值的事情呢?我想大部分可能还是陷入拖延症的漩涡里不能够自拔吧。每天早起就是看电视,中午玩游戏,下午稍微看看论文,然后晚上就外出吃饭聚餐。除此之外,如果家人或者朋友觉得你是自由职业者,都会觉得你十分的悠闲,时不时的可能让你去拿个快递,寄封信件,然后陪他们出去聚餐等。这样的话,其实每天的工作时间就会十分的有限,工作效率也会大打折扣。因此,即使有了工作渠道,能否制定合适的工作计划和时间安排,也是自由职业者必须面对的问题。

在读书或者工作的时候,都会有人觉得迷茫,觉得这份工作或者继续读书没有价值。在从事自由职业的时候,这种迷茫与彷徨的感觉可能会更加强烈。例如,上个月没怎么努力就赚到了5000块钱,但是这个月努力了很久,却只收到了3000块。不稳定性和不确定性很容易让一个人的内心产生迷茫与彷徨,而且这种时候身边的人也不会理解你,因为他们很可能不是自由职业者。要解决这种问题其实只能够靠自己或者进入一个自由职业者的圈子里面,看一看别人是怎么解决这类问题的。但是,即使别人告诉你他的经验,也不见得对你有多大的帮助。对于时间相对自由的工作岗位,例如拿到 tenure 的大学教授,工作不是很繁忙的职员。在保证工作稳定的情况下,可以在工作之余尝试一下自己的兴趣爱好能否挣到钱,是否在市场上具有一定的竞争力。这样做的话能够尽可能的降低自己的风险。

综上所述,要判断一个人是否适合自由职业,首先要看以下几点:

  1. 自己拥有的技能是否真的有市场,能否给自己真正带来收入;
  2. 对自己的要求是否高,在日常的生活中自律性是否足够强;
  3. 对自己的未来是否有较为清晰的规划,是否能够扛住短期没有收入的风险。

如果不清楚以上几点,那么就不适合当自由职业者;如果能够清楚的知道以上几点,可能就具备了自由职业者的基本素质。

张戎 数学人生 2017-04-04

美国官方:关于停止某些中国学生和研究人员非移民入境的公告

白宫官网

The People’s Republic of China (PRC) is engaged in a wide‑ranging and heavily resourced campaign to acquire sensitive United States technologies and intellectual property, in part to bolster the modernization and capability of its military, the People’s Liberation Army (PLA).  The PRC’s acquisition of sensitive United States technologies and intellectual property to modernize its military is a threat to our Nation’s long-term economic vitality and the safety and security of the American people.

中华人民共和国(PRC)正在进行广泛而资源丰富的运动,以获取敏感的美国技术和知识产权,部分是为了增强其军队人民解放军(PLA)的现代化和能力。中国获得敏感的美国技术和知识产权以使其军队现代化,这威胁到我们国家的长期经济活力以及美国人的安全与保障。

The PRC authorities use some Chinese students, mostly post‑graduate students and post-doctorate researchers, to operate as non-traditional collectors of intellectual property.  Thus, students or researchers from the PRC studying or researching beyond the undergraduate level who are or have been associated with the PLA are at high risk of being exploited or co-opted by the PRC authorities and provide particular cause for concern.  In light of the above, I have determined that the entry of certain nationals of the PRC seeking to enter the United States pursuant to an F or J visa to study or conduct research in the United States would be detrimental to the interests of the United States.

中国当局利用一些中国学生(主要是研究生和博士后研究人员)来作为非传统的知识产权收藏者。因此,与解放军有联系或曾经与解放军有联系的,在中国学习或研究的来自中国的学生或研究人员极有可能被中国当局剥削或选择,并引起特别关注。鉴于上述情况,我认为,某些想通过F或J签证进入美国学习或在美国进行研究的中国国民入境,将对美国的利益不利。 

NOW, THEREFORE, I, DONALD J. TRUMP, President of the United States, by the authority vested in me by the Constitution and the laws of the United States of America, including sections 212(f) and 215(a) of the Immigration and Nationality Act (INA), 8 U.S.C. 1182(f) and 1185(a), and section 301 of title 3, United States Code, hereby find that the unrestricted entry into the United States as nonimmigrants of persons described in section 1 of this proclamation would, except as provided for in section 2 of this proclamation, be detrimental to the interests of the United States, and that their entry should be subject to certain restrictions, limitations, and exceptions.  I therefore hereby proclaim the following:

现在,我是美国总统唐纳德·特鲁姆(DONALD J. TRUMP),由美国《宪法》和美国法律(包括移民法第212(f)和215(a)条)赋予我的权力和《国籍法》(INA),8 USC据此,《美国法典》第1182(f)和1185(a)条以及第3篇第301条由此认定,本条第1节所述的人作为非移民者不受限制地进入美国,除非本条第1节规定本公告的第2条不利于美国的利益,并且其加入应受到某些限制,限制和例外。因此,我在此宣布以下内容:

Section 1.  Suspension and Limitation on Entry.  The entry into the United States as a nonimmigrant of any national of the PRC seeking to enter the United States pursuant to an F or J visa to study or conduct research in the United States, except for a student seeking to pursue undergraduate study, and who either receives funding from or who currently is employed by, studies at, or conducts research at or on behalf of, or has been employed by, studied at, or conducted research at or on behalf of, an entity in the PRC that implements or supports the PRC’s “military-civil fusion strategy” is hereby suspended and limited subject to section 2 of this proclamation.  For the purposes of this proclamation, the term “military-civil fusion strategy” means actions by or at the behest of the PRC to acquire and divert foreign technologies, specifically critical and emerging technologies, to incorporate into and advance the PRC’s military capabilities.

第1节。暂停和进入限制。寻求通过F或J签证进入美国学习或进行美国研究的任何中国公民的非移民入境美国,但寻求本科学习的学生除外,并且接受或执行某实体的资金,或从某实体接受其资助或目前由该实体从事研究或以其名义进行研究,或已由该实体实施或支持的实体聘用,由其进行研究或以其名义进行研究因此,中华人民共和国的“军民融合战略”被中止,并受本公告第2条的限制。就本公告而言,“军民融合战略”一词是指中国采取或应中国的指示,采取行动,获取和转移外国技术,特别是关键的和新兴的技术,以纳入和提高中国的军事能力。

Sec. 2.  Scope of Suspension and Limitation on Entry.
(a)  Section 1 of this proclamation shall not apply to:

(i)    any lawful permanent resident of the United States;

(ii)   any alien who is the spouse of a United States citizen or lawful permanent resident;

(iii)  any alien who is a member of the United States Armed Forces and any alien who is a spouse or child of a member of the United States Armed Forces;

(iv)   any alien whose travel falls within the scope of section 11 of the United Nations Headquarters Agreement or who would otherwise be allowed entry into the United States pursuant to United States obligations under applicable international agreements;

(v)    any alien who is studying or conducting research in a field involving information that would not contribute to the PRC’s military‑civil fusion strategy, as determined by the Secretary of State and the Secretary of Homeland Security, in consultation with the appropriate executive departments and agencies (agencies);

(vi)   any alien whose entry would further important United States law enforcement objectives, as determined by the Secretary of State, the Secretary of Homeland Security, or their respective designees, based on a recommendation of the Attorney General or his designee; or

(vii)  any alien whose entry would be in the national interest, as determined by the Secretary of State, the Secretary of Homeland Security, or their respective designees.

(b)  Nothing in this proclamation shall be construed to limit the ability of an individual to seek asylum, refugee status, withholding of removal, or protection under the Convention Against Torture and Other Cruel, Inhuman or Degrading Treatment or Punishment, consistent with the laws of the United States.

第2节.暂停范围和进入限制。
(a)本公告第1条不适用于:

(i)美国的任何合法永久居民;

(ii)是美国公民的配偶或合法永久居民的任何外国人;

(iii)任何是美国武装部队成员的外国人以及任何是美国武装部队成员的配偶或子女的外国人;

(iv)任何旅行属于《联合国总部协定》第11条范围之内的外国人,或根据适用国际协定所规定的美国义务被允许进入美国的任何外国人;

(v)经国务卿和国土安全大臣确定,在与有关信息无助于中国军民融合战略的领域研究或进行研究的任何外国人,并与有关行政部门协商和机构(代理商);

(vi)根据国务卿,国土安全大臣或其各自指定人员根据总检察长或其指定人员的推荐决定,其入境将进一步促进美国重要的执法目标的任何外国人;要么

(vii)由国务卿,国土安全大臣或其各自指定人员确定的,符合国家利益的任何外国人。

(b)本声明中的任何内容均不得解释为限制个人根据法律禁止寻求庇护,难民身份,扣留遣返或根据《禁止酷刑和其他残忍,不人道或有辱人格的待遇或处罚公约》提供保护的能力。美国。

Sec. 3.  Implementation and Enforcement.  (a)  Persons covered by sections 1 or 2 of this proclamation shall be identified by the Secretary of State or the Secretary of State’s designee, in his or her sole discretion, pursuant to such standards and procedures as the Secretary of State may establish.  For purposes of subsections 2(a)(v), 2(a)(vi), and 2(a)(vii) of this proclamation, the Secretary of State shall provide for identifications of aliens based on the further determinations and recommendations provided for in those subsections by the Attorney General and the Secretary of Homeland Security.

(b)  The Secretary of State shall implement this proclamation as it applies to visas pursuant to such procedures as the Secretary of State, in consultation with the Secretary of Homeland Security, may establish in the Secretary of State’s discretion.  The Secretary of Homeland Security shall implement this proclamation as it applies to the entry of aliens pursuant to such procedures as the Secretary of Homeland Security, in consultation with the Secretary of State, may establish in the Secretary of Homeland Security’s discretion.

(c)  An alien who circumvents the application of this proclamation through fraud, willful misrepresentation of a material fact, or illegal entry shall be a priority for removal by the Department of Homeland Security.

第3节.实施和执行。 (a)本声明第1条或第2条所涵盖的人员,应由国务卿或国务卿指定人员根据国务卿制定的标准和程序,全权酌情确定。为了本公告第2(a)(v),2(a)(vi)和2(a)(vii)小节的规定,国务卿应根据所提供的进一步确定和建议规定对外国人的身份证明在总检察长和国土安全部部长的这些小节中。

(b)国务大臣应按照国务大臣与国土安全大臣协商,由国务大臣酌情决定的程序,执行适用于签证的本声明。国土安全部部长应按照国土安全部部长与国务卿协商,由国土安全部部长自行决定的程序,执行适用于外国人入境的这一声明。

(c)通过欺诈,故意虚假陈述重大事实或非法入境来规避本公告适用的外国人,应优先由国土安全部遣送。

Sec. 4.  Termination.  This proclamation shall remain in effect until terminated by the President.  The Secretary of State, in consultation with the Secretary of Homeland Security, may at any time recommend that the President continue, modify, or terminate this proclamation.

第四节.终止。该声明将继续有效直至总统终止。国务卿可在与国土安全部长协商后,随时建议总统继续,修改或终止该声明。

Sec. 5.  Effective Date.  This proclamation is effective at 12:00 p.m. eastern daylight time on June 1, 2020.

第5节.生效日期。该公告于下午12:00生效。东部夏令时为2020年6月1日。

Sec. 6.  Additional Measures.  (a)  The Secretary of State shall consider, in the Secretary’s discretion, whether nationals of the PRC currently in the United States pursuant to F or J visas and who otherwise meet the criteria described in section 1 of this proclamation should have their visas revoked pursuant to section 221(i) of the INA, 8 U.S.C. 1201(i).

(b)  Within 60 days of the effective date of this proclamation, the Secretary of State and the Secretary of Homeland Security, in consultation with the heads of appropriate agencies, shall review nonimmigrant and immigrant programs and shall recommend to the President, through the Assistant to the President for National Security Affairs, any other measures requiring Presidential action that would mitigate the risk posed by the PRC’s acquisition of sensitive United States technologies and intellectual property.

(c)  The Secretary of State and the Secretary of Homeland Security shall, within the scope of their respective authorities and in coordination with the heads of appropriate agencies, take action to further mitigate the risk posed by the PRC’s acquisition of sensitive United States technologies and intellectual property.  The Secretary of State and the Secretary of Homeland Security shall report to the President, within 60 days of the effective date of this proclamation, through the Assistant to the President for National Security Affairs, any such planned and executed actions.

(d)  The Secretary of State and the Secretary of Homeland Security shall consider issuing updated regulations and guidance, as appropriate, implementing the inadmissibility provisions in section 212(a)(3)(D) of the INA, 8 U.S.C. 1182(a)(3)(D).

第6节.附加措施。 (a)国务大臣应酌情考虑,是否根据F或J签证现居美国的中国公民以及其他符合本公告第1条所述标准的国民是否应根据其签证予以撤销符合INA的221(i),8 USC 1201(i)。

(b)在本公告生效之日起60天内,国务卿和国土安全部长应与有关机构负责人协商,审查非移民和移民计划,并应通过助手向总统推荐对于国家安全事务总统,任何其他需要采取总统行动的措施,都应减轻中国因购买敏感的美国技术和知识产权而带来的风险。

(c)国务卿和国土安全部长应在其各自职权范围内,并在有关机构负责人的协调下,采取行动,进一步减轻中国收购敏感的美国技术和知识产权。国务卿和国土安全部长应在本公告生效之日起60天内,通过国家安全事务总统助理向总统报告任何此类计划和执行的行动。

(d)国务卿和国土安全部长应考虑发布适当的最新法规和指南,以实施《美国法典》第8篇第212(a)(3)(D)条中的不可受理规定。 1182(a)(3)(D)。

Sec. 7.  General Provisions.  (a)  Nothing in this proclamation shall be construed to impair or otherwise affect:

(i)   the authority granted by law to an executive department or agency, or the head thereof; or

(ii)  the functions of the Director of the Office of Management and Budget relating to budgetary, administrative, or legislative proposals.

(b)  This proclamation shall be implemented consistent with applicable law and subject to the availability of appropriations.

(c)  This proclamation is not intended to, and does not, create any right or benefit, substantive or procedural, enforceable at law or in equity by any party against the United States, its departments, agencies, or entities, its officers, employees, or agents, or any other person.

第7节.一般规定。 (a)本声明中的任何内容均不得解释为损害或以其他方式影响:

(i)法律授予执行部门或机构或其负责人的权力;要么

(ii)管理和预算局局长与预算,行政或立法提案有关的职能。

(b)本公告应根据适用法律并在有拨款的情况下执行。

(c)此声明无意于也不会创造任何权利或利益,无论是实体还是程序上的任何权利或利益,任何一方均可针对美国,其部门,机关或实体,其高级职员,雇员在法律或权益上执行,代理商或任何其他人。

IN WITNESS WHEREOF, I have hereunto set my hand this twenty-ninth day of May, in the year of our Lord two thousand twenty, and of the Independence of the United States of America the two hundred and forty-fourth.

特此通知,我是在5月的第29天,即我们的大主2,000年,以及美利坚合众国的第二百四十四年,宣布我的这一手。

DONALD J. TRUMP

备注:以上翻译来自于 Google。

大数据领域的近似分析方法(一)

基数估算问题

基数估算(Cardinality Estimation),也称为 count-distinct problem,一直是大数据领域的重要问题之一。顾名思义,基数估算就是为了估算在一批数据中,它的不重复元素有多少个。

这个问题的应用场景十分广泛。例如:对于 Google 主页面而言,同一个账户可能会访问 Google 主页面多次。于是,在诸多的访问流水中,如何计算出 Google 主页面每天被多少个不同的账户访问过就是一个重要的问题。那么对于 Google 这种访问量巨大的网页而言,其实统计出有十亿 的访问量或者十亿零十万的访问量其实是没有太多的区别的,因此,在这种业务场景下,为了节省成本,其实可以只计算出一个大概的值,而没有必要计算出精准的值。

从数学上来说,基数估计这个问题的详细描述是:对于一个数据流 x_{1},x_{2}, \cdots, x_{s} 而言,它可能存在重复的元素,用 n 来表示这个数据流的不同元素的个数,i.e. n=|\{x_{1},\cdots,x_{s}\}|, 并且这个集合可以表示为 \{e_{1},\cdots,e_{n}\}. 目标是:使用 m 这个量级的存储单位,可以得到 n 的估计值 \hat{n}, 其中 m\ll n, 并且估计值 \hat{n} 和实际值 n 的误差是可以控制的。

如果是想得到精确的基数,可以使用字典(dictionary)这一个数据结构。对于新来的元素,可以查看它是否属于这个字典;如果属于这个字典,则整体计数保持不变;如果不属于这个字典,则先把这个元素添加进字典,然后把整体计数增加一。当遍历了这个数据流之后,得到的整体计数就是这个数据流的基数了。

cardinality_estimation_naive_solution
Naive Solution

这种算法虽然精准度很高,但是使用的空间复杂度却很高。那么是否存在一些近似的方法,可以估算出数据流的基数呢?其实,在近几十年,不少的学者都提出了很多基数估算的方法,包括 LogLog,HyperLogLog,MinCount 等等。下面将会简要的介绍一下这些方法。

cardinality_estimation_survey_table_1
基数估计的部分算法

HyperLogLog 的理论介绍

HyperLogLog 是大数据基数统计中的常见方法,无论是 Redis,Spark 还是 Flink 都提供了这个功能,其目的就是在一定的误差范围内,用最小的空间复杂度来估算一个数据流的基数。

Spark
Spark 的 Logo

HyperLogLog 算法简要思路是通过一个 hash 函数把数据流 \mathcal{D} 映射到 \{0,1\}^{\infty}, 也就是说用二进制来表示数据流中的元素。每一个数据流中的元素 x 都对应着一个 0,1 序列。

在介绍 HyperLogLog 之前,我们可以考虑这个实际的场景。在一个抛硬币的场景下,假设硬币的正面对应着 1, 硬币的反面对应着 0; 依次扔出 0,0,0,1 的概率是多少?通过概率计算可以得到是这个概率是 1/2^{4}=1/16. 那么相当于平均需要扔 16 次,才会获得 0001 这个序列。反之,如果出现了 0001 这个序列,说明起码抛了 16 次硬币。

考虑这样一个 0,1 序列,w=w_{1}w_{2}\cdots, w_{i}\in\{0,1\}, i\geq 1,k 表示第一个 1 出现的位置。也就是说 w_{1}=w_{2}=\cdots=w_{k-1}=0. 那么在扔硬币的场景下,出现这样的序列平均至少需要扔 2^{k} 次。对于一批大量的随机的 0,1 序列, 可以根据第一个 1 出现的位置来估算这批 0,1 序列的个数。也就是说:

  • 出现序列 1XXXXX 意味着不重复的元素估计有 2^1=2 个;
  • 出现序列 01XXXX 意味着不重复的元素估计有 2^2=4 个;
  • 出现序列 001XXX 意味着不重复的元素估计有 2^3=8 个;
  • 出现序列 0001XX 意味着不重复的元素估计有 2^4=16 个。

于是,对于随机的 0,1 序列,可以定义函数 \rho(w_{1}w_{2}\cdots) 来表示 1 出现的第一个位置。i.e. \rho(1XXXXX)=1, \rho(01XXXX)=2, \rho(001XXX)=3, \rho(0001XX)=4.

简单来看,其实 HyperLogLog 的基数统计就使用了这样的思想,通过二进制中 1 出现的第一个位置来估算整体的数量。首先把这批元素通过 hash 函数处理成 0,1 序列,然后把这批 0,1 序列都放入 1 个桶,然后通过计算这个桶里面所有 0,1 序列的 \rho(w) 的最大值,就可以预估出整体的数量。i.e. M=\max_{w}\rho(w), 整体的数量预估是 2^{M}=2^{\max_{w}\rho(w)}.

  • 1 个桶:计算出 M=\max_{w}\rho(w), 预估不重复的元素个数是 2^{M}.

那么如果只有 1 个桶,其实是会存在一定的偏差的。为了解决这个问题,一种想法就是重复以上操作,从 hash 函数开始处理成 0,1 序列,每次都把这批 0,1 序列放入 1 个桶,每次获得一个 M 值。总共操作 m 次,第 j 次操作得到的值记为 M_{j}; 于是就可以对 \{M_{1},\cdots,M_{m}\} 进行均值处理,可以使用以下方法:

  • 算术平均数:M=\sum_{j=1}^{m}M_{j};
  • 几何平均数:M=\sqrt[m]{M_{1}\cdots M_{m}};
  • 调和平均数:M=m/\sum_{j=1}^{m}M_{j}^{-1};
  • 中位数:M = median\{M_{1},\cdots,M_{m}\}.

从而可以预估整体的数量为 2^{M}.

如果按照以上的步骤进行操作,就是需要重复进行多次操作,在足够多的情况下,其实是没有必要那么操作的。HyperLogLog 也是用了多个桶,但是用了一个截断的技巧。对于一个 0,1 序列 x=\cdots x_{b+2}x_{b+1}x_{b}\cdots x_{1}, HyperLogLog 从某个位置 b 开始,低位 x_{b}\cdots x_{1} 用于决定桶的序号,也就是第几个桶。桶的个数就是 m=2^{b}, 高位 \cdots x_{b+2}x_{b+1} 用于估算放在桶里面的元素个数。

每次都可以获得一个值,也就是桶里面第一次出现

  • 第 1 个桶:计算出 M_{1}=\max_{w}\rho(w), 预估元素个数 2^{M_{1}};
  • 第 2 个桶:计算出 M_{2}=\max_{w}\rho(w), 预估元素个数 2^{M_{2}};
  • ….
  • m 个桶:计算出 M_{m}=\max_{w}\rho(w), 预估元素个数 2^{M_{m}};

均值的计算,HyperLogLog 使用了调和平均数 m/\sum_{j=1}^{m}2^{-M_{j}} 来估算桶里面的元素个数,那么在有 m 个桶的情况下,整体的元素个数就可以估算为 E=m^{2}\cdot\bigg(\sum_{j=1}^{m}2^{-M_{j}}\bigg)^{-1}.

hyperloglog_algorithm_simple
原始的 HyperLogLog 算法

其中的 \alpha_{m}=\bigg(\int_{0}^{+\infty}\bigg(\log_{2}\bigg(\frac{2+u}{1+u}\bigg)\bigg)^{m}du\bigg)^{-1}.m=1 的时候,\int_{0}^{+\infty}\log_{2}\bigg(\frac{2+u}{1+u}\bigg)du 是发散的;当 m\geq 2 的时候,\int_{0}^{+\infty}\bigg(\log_{2}\bigg(\frac{2+u}{1+u}\bigg)\bigg)^{m}du 是收敛的。因此,在使用这个算法的时候最好放入 m\geq 2 个桶。

HyperLogLog 分成两块,第一块就是 add 模块,用于分桶和统计;

for v in M:
    set x := h(v);
    set j = 1 + <x(b),...,x(2),x(1)>;
    set w := x(b+1)x(b+2)...; 
    set M[j] := max(M[j], \rho(w));

在 HyperLogLog 算法中,对于集合 \mathcal{M} 中的每一个元素 v\in\mathcal{M}, 可以通过 hash 函数转换成一个 0,1 序列 h(v)=x=<\cdots x_{b+2}x_{b+1}x_{b}\cdots x_{1}>, 其中 x_{1} 表示二进制中的最低位,x_{2} 表示次低位。

然后可以通过 <x_{b}\cdots x_{1}>_{2} 来计算放在第 j 个桶,这里 j=1+<x_{b}\cdots x_{1}>_{2}. 同时将 x 的高位拿出来,也就是 x_{b+1}x_{b+2}\cdots, 计算这批序列的 \rho 函数的最大值,然后记为 M_{j}; 这一步也可以称为 merge 模块,也就是进行更新合并。

compute Z := (\sum_{j=1}^{m}2^{-M[j]})^{-1};

上一步就是 HyperLogLog 的另外一步,count 模块,于是,进一步估算出 E=\alpha_{m}m^{2}Z.

HyperLogLog 的空间复杂度特别低,大约是 O(m\log_{2}\log_{2}n) 这个量级的,其中 m 是桶的个数,n 是基数。HyperLogLog 的时间复杂度则是 O(n), 只需要遍历一遍所有元素即可得到最终结果。

  • 假设基数为 2^{k}, 二进制就是 k 位,1 最晚就会出现在第 k 个位置上;而 k 只需要 log_{2}k 个 bit 就能够存储;
  • 假设基数为 2^{64}, 二进制就是 64 位,1 最晚会出现在第 64 个位置上;而 64 需要 6 个 bit 就可以存储。

hyperloglog_algorithm_compare
算法对比

在论文中,论文 “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm” 的作者们针对各种算法进行了对比,其实 HyperLogLog 的空间复杂度是非常小的,并且误差也在可控的范围内。

hyperloglog_algorithm_theorem
HyperLogLog 的定理证明

在论文 “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm” 作者们得到上述定理,精准的给出了 HyperLogLog 算法的误差估计。因此,HyperLogLog 算法其实是有数学定理证明的。

以上只是获得了理论上的 HyperLogLog 算法,但是在实战中,其实是需要进行微调的。主要的微调部分是根据理论中的 E 值来进行调整。将 E 值进行调整的话,情况可以分成三种:

  • 小范围;
  • 中等范围;
  • 大范围;

hyperloglog_algorithm_practical
实战中的 HyperLogLog

Case(1):小范围

在小范围的情况下,E\leq 5m/2, 此时的基数相对于桶的数量而言不算太多,因此可能存在多个空桶,需要进行调整。

可以思考这样一个问题:假设有 m 个桶,同时有 n 个球,把这 n 个球随机往这 m 个桶里面扔,每个球只能够进入一个桶,那么空桶个数的期望是多少个?

Answer:假设 A_{1},\cdots,A_{m}m 个桶,

P(A_{j}=\emptyset)=\bigg(1-\frac{1}{m}\bigg)^{n} 表示桶 A_{j} 空的概率;

P(A_{j}=\emptyset \cap A_{k}=\emptyset)=\bigg(1-\frac{2}{m}\bigg)^{n} 表示桶 A_{j}, A_{k} 同时为空的概率(j\neq k);

那么空桶个数的期望就是 m\cdot\bigg(1-\frac{1}{m}\bigg)^{n},m,n 充分大的时候,约为 me^{-n/m} 个。

因此,在小范围的情况下,如果空桶的个数 V\neq 0, 那么可以更新为 m\ln(m/V). 事实上,可以通过 V=me^{-n/m} 解出 n=m\ln(m/V).

Case(2):中等范围

E 值不作调整。

Case(3):大范围

E>2^{32}/30, 那么更新为 E^{*}=-2^{32}\ln(1-E/2^{32}), 其中 E^{*}>E.

通过这样的方法,E^{*} 的误差大约在 \pm 1.04/\sqrt{m} 左右。

除此之外,\alpha_{m} 其实也可以用近似值来代替,毕竟如下公式的计算是有一定的成本的。

\alpha_{m}=\bigg(\int_{0}^{+\infty}\bigg(\log_{2}\bigg(\frac{2+u}{1+u}\bigg)\bigg)^{m}du\bigg)^{-1}.

近似的值为 \alpha_{16}=0.673, \alpha_{32}=0.697, \alpha_{64}=0.709, \alpha_{m}=0.7213/(1+1.079/m)m\geq 128.

HyperLogLog 的案例分析

有一个关于 HyperLogLog 的 demo 网站可以看到 HyperLogLog 的算法过程,其链接是 http://content.research.neustar.biz/blog/hll.html

在这个 demo 中,作者对比了 LogLog 和 HyperLogLog 的区别和运行过程,有助于大家理解整个过程。其中 LogLog 与 HyperLogLog 的区别就在与它们平均值的处理方式不一样,前者是使用算术平均值,后者是使用调和平均值。

  • LogLog\alpha_{m}\cdot m\cdot 2^{\sum_{j=1}^{m}M_{j}/m};
  • HyperLogLog\alpha_{m}\cdot m^{2}\cdot\bigg(\sum_{j=1}^{m}2^{-M[j]}\bigg)^{-1};

hyperloglog_demo_1
HyperLogLog Demo:初始化

hyperloglog_demo_2
第一个 hash 值:3852172429

3852172429 的二进制是:11100101100110110111110010001101,可以划分为100 110110111110010 001101。最后的六位是 001101,十进制就是 13,那么这个数字就会被放入第 13 个桶;而 110110111110010(从低位到高位看),\rho 函数的值就是 2;于是在第 13 个桶就会把 0 更新成 2。

hyperloglog_demo_3
第二个 hash 值:2545698499

2545698499 的二进制是 10010111101111000100011011000011,用同样的分析可得结论。

hyperloglog_demo_4
第三个 hash 值:2577699815

2577699815 的二进制是 10011001101001001001001111100111。

hyperloglog_demo_5
第四个 hash 值:775376803

775376803 的二进制是 101110001101110100111110100011。

hyperloglog_demo_6
运行结束

从以上的 Demo 运行过程可以看出,整个 HyperLogLog 的算法逻辑还是相对清晰的,其整个算法的亮点应该在于借助了抛硬币的场景,用抛硬币的结果来估算抛硬币的次数。

参考文献:

  1. Count-distinct Problem 的维基百科:https://en.wikipedia.org/wiki/Count-distinct_problem
  2. Heule, Stefan, Marc Nunkesser, and Alexander Hall. “HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm.” Proceedings of the 16th International Conference on Extending Database Technology. 2013.
  3. Flajolet, Philippe, et al. “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.” 2007.
  4. HyperLogLog 的 demo 网站:http://content.research.neustar.biz/blog/hll.html

统计与大数据专业究竟在学什么?

统计学是一门关于数据分析的学科,用于测量,收集,整理,归纳和分析数据的真实情况和估算情况。统计学从 17 世纪的中期逐渐发展起来,不仅存在于概率与数理统计领域,还广泛应用在各种自然学科,社会科学和人文科学上,也会被用于各种团队,企业和国家的决策。随着大数据时代的到来,统计学也与计算机,信息学等领域紧密结合,是数学科学的有力工具之一。

概率论_2
正态分布

描述统计学(descriptive statistics)又称为叙述统计,是统计学中用于描述和总结所观察到对象的基本统计信息的一门学科。描述统计的结果是对当前已知的数据进行更精确的描述和刻画,分析已知数据的集中性和离散性。描述统计学通过一些数理统计方法来反映数据的特点,并通过图表形式对所收集的数据进行必要的可视化,进一步综合概括和分析得出数据的客观规律。与之相对应的是推断统计学(statistical inference),又称为推断统计,是统计学中研究如何用样本数据来推断总体特征的一门学科。推断统计学是在对样本数据描述的基础上,对总体的未知数据做出以概率形式来描述的推断。推断统计的结果通常是为了得到下一步的行动策略。以上的两个统计学方向都属于应用统计学。

population_and_sample
总体和样本

在有的学校,统计专业是放在数学系里面的,而有的学校则是把统计和数学分开,形成数学系(Department of Mathematics)和统计系(Department of Statistics)。无论分开还是合并,一般情况下都是放在理学院(Faculty of Science)的。

NUS_Stat_Logo
NUS 统计与应用概率系

统计系和数学系的低年级课程是十分接近的,基本上还是数学分析,线性代数,概率论等一系列的课程。

Module_Level_1_2
Level 1000 和 Level 2000

到了高年级之后,所学的课程与数学系的课程就会出现明显的区别。数学系的学生会学习实分析,复分析,泛函分析等一系列课程。而统计系的学生会学习回归分析,随机过程,数据分析,贝叶斯分析等诸多课程。统计系的学生更偏向应用一些,数学系的学生课程则会更加理论一些。

Module_Level_3_4
Level 3000 和 Level 4000

从 NUS 在 2020 的 E-Open House 的资料可以看出,统计专业的学生,其就业方向也是十分宽泛的,可以考虑去银行,金融机构就职;也可以考虑去咨询公司,也可以去政府或者教育机构找到合适自己的工作。

统计的行业需求
统计专业的行业需求

对于第四年的学生,如果在国内的话,一般情况下会选择保研,考研,找工作,甚至出国留学。有的学生也会选择去找一个长达半年到一年的实习。这个就根据每个同学的实际情况而定了,但是绝大部分也就是这几个选择,或者有人也会选择 gap 一年修正一下。

简要课程安排_3
最后一年的项目

相对于数学系,统计系的课程安排更加偏向于实战与应用,并且其实用性也会高于数学系的理论课程。如果未来要从事数据分析,商业分析等方向的话,其实攻读统计系是一个还不错的选择。

在新加坡国立大学的统计与应用概率系,除了统计系这一经典的专业之外,还提供了数据科学与分析(Data Science and Analytics)这一个新兴专业供学生选择。

众所周知,随着科技时代的到来,数据的增加是非常迅速的,无论是用户自身产生的数据,还是平台方产生的数据,都是十分巨大的。数据的增大那就意味着需要使用各种各样的计算机,统计,数学方面的技术来解决现有的疑难杂症,于是大数据时代的技术也逐渐映入大家的眼帘。

DataScience_1
数据趋势

无论是国内还是国外,都在提倡智慧城市这一概念,那么在智慧城市中,大数据技术就是一个绕不开的话题。各行各业都将会使用大数据系统来做各种服务,包括推荐系统(Recommender Systems),高频交易,风险管理,移动支付等等。通过这些技术,人们的生活质量将会大大提升。通过这些产品,科技将会给人们带来诸多便利。

DataScience_3
智慧城市

而数据科学是一门交叉学科,它需要使用到计算机科学(Computer Science)数学(Mathematics)统计学(Statistics)等多种学科的技术和知识点。如果要应用在金融领域,还会要求从业者掌握金融方面的知识。因此,数据科学在这个时代背景下是具有实用性的,也是很多行业的发展趋势。

DataScience_4
数据科学

从其课程设置也可以看出,学生们所学的课程包括编程,数据结构与算法,也包括微积分和线性代数,还有统计学等诸多基础课。在高年级的时候,将会学习人工智能,计算与优化,数据库,数据处理,机器学习等课程。除此之外,在具体做项目或者实习的时候,将会根据方向的需要来学习相关的业务知识,涵盖了金融,医药,调度优化等诸多领域。

DataScience_6_Essential_Modules

DataScience_7_Elective_Modules
课程设置

整体来看,统计与数据科学专业是以实用性为目的,培养学生的理科思维,动手能力和数据分析能力的一门学科。如果学生希望学习理科并且将来学以致用的话,其实选择统计或者数据科学是一个不错的选择。

参考资料:

  1. NUS E-Open House:2020,YouTube 视频;
  2. http://www.stat.nus.edu.sg:NUS 统计系官网。

《软技能:代码之外的生存指南》

《软技能:代码之外的生存指南》是笔者刚刚进入公司工作,开始职场生涯的时候,一个偶然的机会从同事那里看到的一本书。从其内容提要可以看出,这是一本关注软件开发人员自身发展的书籍,书中讲了 7 个部分,包括:

  1. 职业;
  2. 自我营销;
  3. 学习;
  4. 生产力;
  5. 理财;
  6. 健身;
  7. 精神。

软技能_Cover
《软技能:代码之外的生存指南》

本书的作者从自身的亲身经历出发,按照以上 7 个方面给大家介绍了软件开发人员的自我发展历程,包括程序员的职场发展,程序员的自我营销策略,程序员如何培养学习习惯,程序员如何提升自己的生产力,如何培养良好的理财习惯健身将会带来多少好处,精神将会如何提升自我的能力。通过阅读这本书,程序员确实可以从作者的字里行间学习到很多东西,并且积极思考自己的职业生涯,丰富自己的业余生活,让自己的生活更加丰富多彩。

从作者的自我介绍可以得知:John Z. Sonmez 是 “Simple Programmer” 网站的创始人,他为在线培训机构 Pluralsight 开发了 50 多门在线课程,其领域涉及 iOS,Android,.NET,Java 和游戏开发等诸多主题。他还是 “Get Up and CODE” 的主持人,并且在这里讨论关于程序员健身的话题;他也是 “Entreprogrammers” 的播客主持人,他在此与其他人分享构建在线业务的真实故事。

John Z. Sonmez 是不少程序员的人生导师,通过他写的教材,讲授的课程,传递的人生故事,让不少的程序员了解到了前辈的发展历程,并且能够启发程序员如何才能够过上更加充实的生活。通过“化繁为简”的方法,传授给程序员让他们达成自身目标的力量与动力。

下面来摘选一下本书中的经典语录:

Chapter 1:职业

就业选择:列出你的选择:

  1. 雇员:对广大软件开发者而言,这是一项常见的,默认的就业选择。身为雇员的最大好处就是稳定。
  2. 独立咨询师:独立咨询师通常有自己的公司,依照合同为客户工作,但并不与任何一个客户绑定。做独立咨询师最大的好处可能就是赚钱的潜力。
  3. 创业者:创业之路可能是你职业生涯中最难,最不确定但却最具回报潜力的选择。雇员和独立咨询师都在以时间换金钱,而创业者尽管换不来预付的报酬,但是他却有机会在未来获得更大的收益。创业者的两大优势:完全自由和完全不封顶的赚钱潜力。

软技能_Table_6_1
优点与缺点

选择什么完全取决于你自己,并且你也可以随时切换路径。

成为专业人士:

  1. 一切都始于习惯。习惯是成为专业人士必不可少的部分。需要培养自己的专业习惯,需要具备时间管理技能。
  2. 坚守正道。专业人士必须对工作的优先级做出艰难的抉择。
  3. 追求品质,完善自我。你必须不断改善和提高自己的工作品质。

Chapter 2:自我营销

自我营销的正确方式就是为他人提供价值。成功进行自我营销的关键在于:如果想让别人喜欢你,想和你一起工作,你就必须要为他们提供价值。

你也许是世界上最有天赋的软件开发人员,但是如果没有人知道你的存在,你也只不过是浮云一片。

软技能_Table_19_1
自我营销的方式

打造引人注目的品牌

  1. 品牌所需要传递的信息;
  2. 品牌的一致性;
  3. 品牌的视觉符号;
  4. 品牌的曝光率。

创建大获成功的博客

  1. 打造成功博客的最大秘诀有且仅有一个—持之以恒;
  2. 只是持之以恒还不足以使你的博客大获成功,你还应该确保你写的都是高质量的内容。
  3. 重视博客内容品质的另一个重要原因是为你的博客提供更有价值的链接。
  4. 在起步之初,你的博客很可能会很糟糕。但是,随着不断尝试贡献出优秀的内容,而不是将自己脑子里的东西随意丢在网上,不考虑格式和结构还有一大堆拼写错误,你终会成功。

软技能_Table_23_1
通过社交媒体分享的内容

Chapter 3:学习

十步学习法

  1. 第 1 步:了解全局;
  2. 第 2 步:确定范围;
  3. 第 3 步:定义目标;
  4. 第 4 步:寻找资源;
  5. 第 5 步:创建学习计划;
  6. 第 6 步:筛选资源;
  7. 第 7 步:开始学习,浅尝辄止;
  8. 第 8 步:动手操作,边玩边学;
  9. 第 9 步:全面掌握,学以致用;
  10. 第 10 步:乐为人师,融会贯通

知识短板会阻碍你的进步。准确识别它们的最佳方式之一就是看看自己在哪些工作上花费了大量的时间。或者一直在进行重复性劳动。

任何你所做的重复性工作都值得彻查一番。

另一种识别知识短板的方法就是,时刻都要试图了解自己不理解或不清楚的事物。

软技能_Table_35_1
检查知识短板

Chapter 4:生产力

生产力提升计划:我的生产力提升计划的基本思路就是,我把一周的时间分配给一个一个用时不超过两小时的小任务。

  1. 季度计划:在做季度计划时,我会尽力列出我想在本季度完成的每一个大项目,我还会制定一些较小的目标。
  2. 月计划;每个月的第一天我会打印出当月的月历,并且规划出每天要完成的工作。
  3. 周计划;每周一的早晨,我会做我的周计划。
  4. 日计划及执行:要计划好这一天,我首先要把对应日期里的卡片移到“今天”这一栏,并把它们按照重要性排序。我要保证自己优先完成最重要的事情。

一些常见的时间杀手

  1. 看电视;
  2. 社交媒体;
  3. 新闻网站;
  4. 不必要的会议;
  5. 烹饪:因人而异;
  6. 玩电子游戏(尤其是网络游戏);
  7. 工间喝咖啡休息:因人而异。

软技能_Table_48_1
任何行动都比不采取行动好

Chapter 5:理财

软技能_Table_49_1
资产与负债

Chapter 6:健身

可能的健身目标:

  1. 减肥(减掉脂肪);
  2. 增肌(增长肌肉);
  3. 增加力量(不一定是增长肌肉);
  4. 增加肌肉耐力(改善运动表现);
  5. 改善心血管健康;
  6. 在某些运动上表现更好。

Chapter 7:精神

积极思考问题的根源是这样一种信念—你比你所处的环境更伟大。这种信念让你总能先看到事物好的一面,因为无论身处任何环境,你都有能力改变自己的未来。这是人类成就的最高信念,是世界上最强大的力量。

从更现实的层面来讲,积极思考就是选择从好的一面(而不是从坏的一面)去思考问题。

畏惧失败似乎是大多数人的本能。

失败不同于被打败。失败是暂时的,被打败是永恒的。

不要畏惧失败,要拥抱失败。不只是因为失败和被打败不同,还因为失败是通往成功的必经之路。

结束语

感谢你抽出时间来阅读这本书,并真诚地希望你能在本书中发现一些永久的价值。

 

时间序列异常检测—节假日效应的应对之道

在时间序列异常检测中,通常有一个较为常见的场景就是“节假日效应”。所谓节假日效应,指的就是在节假日的时候,其时间序列的走势跟日常有着明显的差异性,但是又属于正常的情况。从国内 2020 年的节假日安排可以看出,一年中有好几个关键的假日:

  1. 元旦:1 天;
  2. 春节:7 天;
  3. 清明节:3 天;
  4. 五一劳动节:5 天;
  5. 端午节:3 天;
  6. 国庆节:8 天。

在这些节假日的时候,为了调休,自然也会带来工作日上的调整。例如:在 2020 年 1 月 19 日,2020 年 2 月 1 日是需要上班的(虽然今年受疫情影响最终也没上班)。因此,在这些节假日进行调整和变化的时候,各种各样的业务指标(时间序列)通常也会发生变化,变得跟以往的走势不太一致。因此,如何解决节假日效应的时间序列异常检测就是业务上所面临的问题之一。

£¨Í¼±í£©[Éç»á]2020Äê½Ú¼ÙÈշżٰ²ÅŹ«²¼
2020 年的放假安排
清华大学的 Netman 实验室在 2019 年发表了一篇论文,专门用于解决时间序列异常检测中的节假日效应问题,论文的标题是《Automatic and Generic Periodic Adaptation for KPI Anomaly Detection》。在本文中,所用的时间序列是关于各种各样的业务指标的,包括搜索引擎,网上的应用商店,社交网络数据等等。作者们针对 KPI(Key Performance Indicator)做了时间序列异常检测,并且发明了一种方法来避免节假日效应的问题。论文针对时间序列的工作日(work days),休息日(off days),节假日(festival)做了必要的区分,然后将时间序列的不同时间段进行合理地拆分和组装,再进行时间序列异常检测,从而在一定的程度上解决节假日效应问题。

节假日效应_Fig1
实际案例(1)

在实际的案例中,我们可以看到,同一条时间序列的走势在工作日(work day),休息日(off day),春节(Spring Festival)明显是不一样的。因此,根据工作日的时间序列走势来预测春节的走势明显是不太合理的;同理,根据春节的走势来预测休息日的走势也会带来一定的偏差的。那么如何解决节假日效应的问题就成为了本篇论文的关键之一。

节假日效应_Fig3
实际案例(2)

在上图中,我们可以看到论文中使用的数据都具有某种周期性(Periodicity)。KPI A,B,C 都是具有明显具有工作日和周末特点的,在工作日和周末分别有着不同的形状;KPI D 则是关于网上应用商店周五促销的,因此在周五周六的时候,其实时间序列会出现一个尖峰(peak);KPI E 的话则是每隔 7 天,会有两个尖刺,然后并且迅速恢复;KPI F 的话则是可以看出时间序列在十一的走势跟其余的时间点明显有区别。除此之外,对于一些做旅游,电商等行业的公司,其节假日效应会更加突出一点,而且不同的业务在节假日的表现其实也是不一样的。有的时间序列在节假日当天可能会上涨(电商销售额),有的时间序列在节假日当天反而会下降(订车票,飞机票的订单量)。因此,在对这些时间序列做异常检测的同时,如何避免其节假日效应就是一个关键的问题了。

而在实际处理的时候,通常也会遇到几个常见的问题;

  1. 周期性的多样性:通过实际案例可以看出,对于不同的时间序列,其周期是完全不一样的,而且在不同的周期上也有着完全不同的表现;
  2. KPI 数量巨大:这个通常来说都是智能运维领域中的常见问题;
  3. 周期的漂移:一般来说,通过时间序列的走势我们只能够看出一个大致的变化,但是具体到细节的话,周期是存在一定的波动的。例如不一定恰好是 7 天,有可能是 7 天加减 5 分钟之类的周期。这个跟业务的具体场景有关系,也跟当时的实际情况有关。

于是,基于这些挑战,作者们希望提出一个健壮的机器学习算法来解决这个问题,本文的系统被作者们称之为 Period,正好也象征着解决节假日效应这个寓意。

Period_Fig7
Period 的整体架构

从论文中可以看出 Period 的整体架构如上图所示,包括两个部分:

  1. 离线周期性检测(offline periodicity detection);
  2. 在线适应性异常检测(online anomaly detection adaptation)。

在第一部分,每一条时间序列都会被按天切分成很多子序列(subsequence),然后将其聚集起来,把相似的时间序列放在一类,不相似的放在另外一类;在第二部分,新来的时间序列会根据其具体的日期,分入相应的聚类,然后用该类的时间序列异常检测方法来进行异常检测。

Period_Fig6
Period 的核心思路

从上图可以看到 Period 的核心思路(core idea)。在本文使用的数据中,时间序列的长度较长,一般来说都是好几个月到半年不等,甚至更长的时间。对于一条时间序列(a given KPI),可以将它的历史数据(historical data)进行按天切分,获得多个子序列(sub KPIs)。对于这多个子序列,需要进行聚类以得到不同类别。或者按照日历直接把时间序列的工作日(work day),休息日(off day),春节(spring festival)序列进行切分,将工作日放在一起,休息日放在一起,春节放在一起。把这些子序列进行拼接就可以得到三条时间序列数据,分别是原时间序列的工作日序列(work day subsequence),休息日序列(off day subsequence),春节序列(spring festival subsequence)。然后分别对着三条时间序列训练一个异常检测的模型(例如 Holt-Winters 算法,简写为 HW)。对于新来的时间序列,可以根据当日具体的日期(工作日,休息日或者春节)放入相应的模型进行异常检测,从而进一步地得到最终的结果。

在离线周期性检测的技术方案里面,是需要对时间序列进行周期性检测(Periodicity Detection)。而周期性检测有多个方案可以选择。第一种就是周期图方法(Periodogram),另外一种就是自相关函数(Auto-correlation function)。但是在这个场景下,用这些方法就不太合适了。作者们提出了别的解决方案。

在本文中,作者们提出了一种 Shape-based distance(SBD)的方法,针对两条时间序列 X=(x_{1},x_{2},\cdots,x_{m})Y=(y_{1},y_{2},\cdots,y_{m}),提出了相似性的计算方法。

X_{(s)}=\begin{cases}(0,\cdots,0,x_{1},\cdots,x_{m-s}), &\text{ if } s\geq 0 \\ (x_{1-s},x_{1-s+1},\cdots,x_{m},0,\cdots,0), &\text{ else } s<0.\end{cases}

其中 0 的个数都是 |s|. 进一步可以定义,当 s\in[-w,w]\cap\mathbb{Z} 时,

CC_{s}(X,Y)=\begin{cases}\sum_{i=1}^{m-s}x_{i}\cdot y_{s+i}, &\text{ if } s\geq 0 \\ \sum_{i=1}^{m+s}x_{i-s}\cdot y_{i}, &\text{ else } s<0.\end{cases}

于是,选择令 CC_{s}(X,Y) 归一化之后的最大值作为 X,Y 的相似度,i.e.

NCC(X,Y)=\max_{s\in[-w,w]\cap\mathbb{Z}}\frac{CC_{s}(X,Y)}{\|x\|_{2}\cdot\|y\|}.

而基于 SBD 的距离公式则可以定义为:

SBD(X,Y) = 1-NCC(X,Y).

Period_Fig8
Periodicity Drift

那么为什么需要考虑一个漂移量 s 呢,因为在一些实际的情况下,时间序列是会存在漂移的,例如上图所示。该时间序列在 10 月 30 日,31 日,11 月 1 日 都出现了一个凸起,但是如果考虑它的同比图,其实是可以清楚地看出该时间序列就存在了漂移,也就是说并不是在一个固定的时间戳就会出现同样的凸起,而是间隔了一段时间。这就是为什么需要考虑 s 的由来。

Period_Alg1
聚类的命名算法

通过相似性和距离的衡量工具,我们可以将时间序列进行聚类,然后通过上述算法也可以对每一个聚类的结果进行命名。

Period_Table1
实验数据

Period_Table2
实验数据的聚类结果

在本文中,针对以上六条时间序列,作者们做了详细的分析,也对其余的 50 条时间序列进行了实验。其使用的方法包括 HW,TSD,Diff,MA,EWMA,Donut。在 HW 中,针对不同的日期使用了不同的方法,例如 HW-day,HW-week,HW-period;其余的方法也是针对不同的日期来做的。

Period_Table3
实验方法

Period_Table12
实验效果

从实验效果来看,Period 方法的话相对于其他方法有一定的优势。

结论:Period 方法包括两个部分,第一部分是离线周期性检测,第二部分是在线适应性异常检测。通过这样的方法,可以有效地减缓时间序列异常检测受节假日效应的影响。除此之外,想必未来也会有其余学者提出相应的问题和解决方案,敬请期待。

信息与计算科学是一门什么专业?

信息与计算科学是一门什么专业?

在 2005 年刚进入大学校门的时候,数学分析和高等代数就是大一新生的必修课,当年讲高等代数的是丁老师与何老师。由于个人的姓氏英语字母是 Z,则被安排在二班,于是恰好就由何老师教授高等代数课程。刚入学没多久,何老师则在课堂上问大家,“你们当时为什么选择信息与计算科学?”下面顿时一片寂静。何老师紧接着就说可能是因为专业名字的原因,在填写志愿的时候,高中生一看这个专业的名字,既有信息又有计算,就会觉得这是一个非常偏应用的专业,于是就果断地将其填写在第一志愿上。结果入学之后傻眼了,这个专业是被安排在数学系,也就是属于数学这个一级学科。

信息与计算科学(Information and Computing Science)从名字上来看,确实像一个计算机方向的学科,但是它的原名却是计算数学,后来教育部在 1998 年改成了信息与计算科学。该专业强调以信息领域为背景,数学,信息,计算机管理相结合的数学类专业。目的是培养有良好的数学基础,能够熟练使用计算机,初步具备在信息与计算机科学领域的某个方向从事科学研究,解决实际问题,设计开发有关计算机软件的能力的学生。

在数学系的话,就不可避免地要学习各种数学系的课程,通常来说数学系的前两年都是基础课的教育,包括:数学分析,高等代数,解析几何,C++,离散数学,常微分方程,抽象代数,复变函数,数值计算等课程。

到了第三年才开始逐渐分流,学习不同的课程。如果是在数学与应用数学专业,就是学习实变函数,泛函分析,拓扑学,微分几何等课程。如果是在信息与计算科学,则是学习实变函数,泛函分析,偏微分方程数值解,运筹学,计算机图形学,信号处理等课程。在不同的专业上面,所学习到的课程内容则是完全不一样的。而该专业的编程工具主要还是使用 Matlab,毕竟用 C++ 这种编程语言写矩阵运算一类的确实不太合适。

如果是想在信息与计算科学这个专业上学习很多计算机方面的基础课,例如操作系统,计算机网络,计算机组成原理等课程,估计会让学生们大失所望。因为,信息与计算科学是属于数学这个一级学科,是数学系的专业,而不是计算机系的专业。于是,绝大部分高校还是会把它设置在数学学院下面,而不是计算机学院下。不过,确实也听说有的工科学校确实也给数学系的学生传授了很多计算机方面的知识,但整体来看信息与计算科学方面的学生所学的计算机知识还是相对偏少的。PS:当年读书的时候,该专业确实没有设置计算机方面的课程,例如数据结构等计算机的经典课程其实都是相对缺失的。

在校园招聘的时候,信息与计算科学这个名字也具有一定的迷惑性,因为总有很多面试官会认为这是一个计算机的专业,而没有意识到这个是一个数学类的方向。结果问了一堆计算机方面的问题,学生都不一定能够回答得上来。

近些年的机器学习方向很火,有的公司确实也会考虑从数学系招聘一些相关的人才。数学系所学的课程其实整体来看还是偏理论,实践方面的偏少许多,即使是信息与计算科学这个专业,教授的也是矩阵运算,偏微分方程数值解等课程,在工业界确实也有一定的应用,但是确实也算是脱离了实际。一般情况下,在工业界哪能够精准地写出一个偏微分方程或者常微分方程,最常见的都是一大堆表格数据,各种图片和文本数据,极端情况下,连数据都还没有收集好。数学系的学生实践方面的能力在刚毕业的时候确实不太行,不如计算机专业的学生上手极快,但是确实应该给予数学系的学生一定的耐心和鼓励。毕竟两者思考问题的思路和方向是不太一样的,从不同的角度看问题确实能够带来不同的启发。

提到机器学习,不知道现在的课程安排有没有做适当的改进和迭代。如果想要从事数据挖掘和机器学习相关工作的话,光靠信息与计算科学专业所教授的数学课程内容应该是远远不够的,无法满足工业界对人才的需求,因此建议在编程方面还应该补充一些 SQL,Python,C++,Java,Golang 方面的基础知识,也要掌握数据结构中的常见算法,更要把机器学习的相关课程尽量补上。只有这样,才能够在求职就业的时候占据一定的优势。只靠数学系所教的数学想找工作是非常困难的,只有把数学和计算机相结合之后才能够发挥数学系专业人才的优势。

如果学生恰好在信息与计算科学专业就读,最担心的一种情况就是不仅数学没学好,计算机方面的技能也稀松平常,最终耽误了自己。因此,在学习的时候还是建议先打好数学和计算机方面的基础,然后加强社会实践,多参与实习和各种社会活动,通过实习来了解业务问题,才能把所学到的数学知识应用到实践中产生价值。

 

zr9558's Blog