2018年7月19日-下-胡一凡.md

Graph and Map Visualization with Applications to Machine Learning

胡一凡，雅虎研究院

---

1. Graph Visualizaion

• 分析数据，发现数据的结构和内部的异常。
  //minhas

• a. 基本算法：

  • 力导向算法：Eades(1984), Fruchterman & Reigold(1991) ***
  • 弹簧力：拉近；电力：排斥 -> min energe state(step和energe的关系)
    • force directed
      i. Repulsive force
      ii. Attractive force
    • stress model

• b. 涉及到大图时large graph：

  • not scalable: all-to-all

  • easy to get trapped in a local minima

  • 将靠近的多个小点当成一个大点(super node, 平均中心)，减少计算复杂度reducing the Complexity ***

  • 用八叉树分割平面，根据远近判定点的哪些小点可以结合成大点 ***

  • 判定何时使用：###

  • Finding global optimum ***

  • Finding Global Minimum: Multilevel *** -graph coarsen, graph get smaller and smaller从整体到部分，简化

    • Edge coalescue:
    • a. Maximal independent edge set ***
    • b. Maximal independent vertex set filtering ***

  • Challenge: size, complexity, velocity(dinamic graphs)

  • 有些情况用弹簧-电力模型并不好用 ***

  • square, star, tree ***

  • Better coarsening *** star graph

  • website: tree if life, tolweb.org

• c. Stress Model(Spring Model) ###

  • 弹簧模型，近斥远拉
  • Scalable Stress Model ***
    • [1] PivotMDS: Classic MDS, multi dimendional scaling ###
    • [2] MaxEnt: Motivation ###
    • [3] Sparse Stress Model
  • Still an area of research.

• Sofoware

  • Graphivz
  • Gephi
  • D3
  • VivaGraphJS

2. Relationship between Visualization and Machine Learning

a. Vis ~= unsupervised ML Isomap机器学习中的降维算法 ***
b. force directed graph drawing ***

• Vis: Force-directed algorighm
• ML: Word2Vec关键字之间的相关度和力导向模型中主题之间距离的计算情形相似

c. PCA
d. HDE

3. Vis Explanation of ML

a. 推荐系统中的可视化解释

• Example: Netflix
• kNN(k-Nearest Neighbor) ***
• Gmap algorithm ***

b. Contact Challenge ***

• Name enbedding