XW.Xiong's HomePage


  • 首页

  • 标签

  • 分类

  • 归档

  • 资源

  • 关于

  • 搜索

备忘

置顶 | 发表于 2019-01-20 | 分类于 备忘 | 阅读次数:
「这不是一篇正常的博客」
阅读全文 »

2019 新年目标

置顶 | 发表于 2019-01-15 | 分类于 杂谈 | 阅读次数:
「这是一篇私密博客」
阅读全文 »

模式识别与机器学习课程笔记

发表于 2019-01-11 | 分类于 机器学习 | 阅读次数:
  • 考点
    • 概念题
  • Part I
    • 概率论基础
    • 贝叶斯判别
      • 正态概率贝叶斯判别
    • 线性判别
    • 广义线性判别
    • 模式空间和权空间
    • Fisher 准则函数
    • 感知器算法
    • 最小平方误差(LMSE)
    • 势函数法
    • 特征选择
    • 离散K-L变换(PCA)
  • Part II
    • 正则化
    • VC Dimension
    • Logistic Regression
    • 多元高斯混合模型
  • Part III
    • K-Means 聚类
    • GMM 聚类
    • 维数灾难
    • 降维主要思想
    • 矩阵分解
      • 特征分解
      • SVD 分解
    • PCA
      • 求解算法
      • PCA 总结
    • 非线性方法
      • KPCA(Kernel Method + PCA)
    • 流形学习
      • ISOMAP算法
      • 全局嵌入/局部嵌入
      • 拉普拉斯特征映射(Laplacian Eigenmap)
      • 自编码器
    • 概率图模型
    • HMM
      • HMM 概率计算问题
  • Part IV
    • 目标检测
    • BP 算法
    • CNN
  • References
阅读全文 »

loj 6226. 「网络流 24 题」骑士共存问题

发表于 2019-01-07 | 分类于 算法 | 阅读次数:

1. 题目链接

[loj 6226. 「网络流 24 题」骑士共存问题]

2. 题目描述

Problem Description

3. 解题思路

题目中要求如果一个顶点被选择,那么8个方向上的顶点就不能被选择。显然,这很像二分图的染色问题。
将每个非障碍的顶点与其8个方向上的非障碍顶点连一条边,那么本题就是一个求最大独立集的问题,而且是一个求二分图的最大独立集的问题。
为什么是二分图呢?可以从下面两条性质来分析:

  • 对于任意节点$u$,不可能经过奇数步回到节点$u$,实际上,这就是 匈牙利算法 Hungary 的进行二分图的判断的主要思想;
  • 按照题目中那个图,将所有顶点划分成红色、黄色两类节点,可以发现同色的节点之间没有边。

而二分图上有很好的性质,比如:

  • 最大匹配数 = 最小点覆盖;
  • 最大独立集 = 最小边覆盖 = 顶点数 $\lvert V \lvert$ - 最大匹配数;
  • DAG 的最小路径覆盖数 = DAG 图中的节点数 - 相应二分图中的最大匹配数。
    • DAG 的最小路径覆盖是指找最小数目的互相不相交的有向路径,满足 DAG 的所有顶点都被覆盖。
    • DAG 对应的二分图这样构造:对于 DAG 中的一个顶点 $p$,二分图中有两个顶点 $p$ 和 $p’$,对应 DAG 中的一条有向边 $p\to q$,二分图中有 $p\to q’$ 的一条无向边。二分图中 $p$ 属于 $S$ 集合,$p’$ 属于 $T$ 集合.
  • ……

求二分图的最大匹配数的方法有 匈牙利算法(复杂度$\mathcal O(VE)$) 和 网络流(代表算法就是Dinic/Hopcroft-carp 算法,复杂度$\mathcal O(\sqrt{V}E)$)。

阅读全文 »

[hdu 5988. Coding Contest] zkw 最小费用最大流

发表于 2019-01-04 | 分类于 算法 | 阅读次数:

1. 题目链接

[hdu 5988. Coding Contest]

2. 题目描述

有 $N$ 个点,$M$ 条边的有向图 $(N\le 100, M\le 5000)$。任意一个点 $i$ 上有$s_i$ 个人,$b_i$ 份食物$(s_i, b_i\le 200)$。

任意一条边 $i$ 有几个属性 $u_i, v_i, c_i, p_i$ $(c_i\le 100, 0\lt p_i\lt 1)$。$u_i, v_i$ 分别表示有向边的两个顶点编号;$c_i$ 表示这条边的最大容量(最多允许几个人通过);点$u_i$ 中的每个人可以沿着这条有向边移动到点 $v_i$,但是除了第一个经过这条边的人不会破坏这条边,剩下的人都会有 $p_i$ 的概率把这条边破坏。图中只要有一条边被破坏了,就认为图被破坏了。

现在需要保证所有人都能拿到一份食物的情况下,求出图被破坏的最小概率。

数据范围:

3. 解题思路

主要思路:拆边 + 对数函数将积性函数转为和性函数 + zkw 最小费用最大流。

阅读全文 »

NumPy ndarray 用法

发表于 2018-12-30 | 分类于 Python | 阅读次数:
  • NumPy ndarray 初始化
  • 排序
  • 数值计算
    • 协方差/Pearson相关系数矩阵
  • References
阅读全文 »

运筹学通论(下)课程笔记

发表于 2018-12-18 | 分类于 数学 | 阅读次数:

Overview

KeyNotes

  1. 遍历$\Leftrightarrow$不可约+正常返;
阅读全文 »

网络数据挖掘课程笔记

发表于 2018-12-13 | 分类于 机器学习 | 阅读次数:

Overview

搜索/广告-徐

  • 置信度、支持度
  • 决策树
  • 监督学习评价指标:Accuracy/Precision/Recall/F1
  • SVD 分解
    • Fold-in 算法
  • AdaBoost算法
  • BM25
  • 语言模型Language Model for IR(LM4IR)、平滑化
  • 排序学习:基于有序对
  • 排序学习评价方法:MAP、NDCG(Normalized Discounted Cumulative Gain)
  • TF-IDF计算公式
  • 线性感知器
  • SVM
    • 硬边距:
    • 软边距: 松弛变量$\xi$、参数$C$

图数据挖掘-沈

  • 无标度网络:数据分布
  • 复杂网络的小世界特性
  • 连边关系的结构平衡
  • 影响最大化问题
  • PageRank
  • 图聚类算法:Normalized Cut、模块度优化、InfoMap、非负矩阵分解等

推荐系统-罗

  • 矩阵分解的核心思想
  • 矩阵分解和U-U CF、I-I CF的区别
  • U-U CF 的评分
  • 相关度的度量:Pearson Correlation
阅读全文 »

机器学习基本概念(未完待补)

发表于 2018-12-04 | 分类于 机器学习 | 阅读次数:
Nearest Neighbors# 无监督最近邻: 返回每个数据样本点的$k$近邻节点或者距离,无训练集 应用:流行学习(manifold learning)、谱聚类(spectral clustering) 有监督最近邻 返回训练集中的$k$近邻 应用:数据分类/回归 VC-Dimen ...
阅读全文 »

Git 常见错误

发表于 2018-11-15 | 分类于 Git | 阅读次数:

Github 大文件删除之后依旧push不上

Counting objects: 24, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (23/23), done.
Writing objects: 100% (24/24), 201.06 MiB | 1.36 MiB/s, done.
Total 24 (delta 5), reused 0 (delta 0)
remote: Resolving deltas: 100% (5/5), completed with 2 local objects.
remote: warning: File model/news.model is 73.08 MB; this is larger than GitHub’s recommended maximum file size of 50.00 MB
remote: warning: File data/user_click_data.tar.gz is 74.27 MB; this is larger than GitHub’s recommended maximum file size of 50.00 MB
remote: error: GH001: Large files detected. You may want to try Git Large File Storage - https://git-lfs.github.com.
remote: error: Trace: a092a0b034ec52cbdd5c6fda7852c00c
remote: error: See http://git.io/iEPt8g for more information.
remote: error: File src/data-utils/train_original.csv is 155.62 MB; this exceeds GitHub’s file size limit of 100.00 MB
To github.com:XingwXiong/NewsRS.git
! [remote rejected] master -> master (pre-receive hook declined)
error: failed to push some refs to ‘git@github.com:XingwXiong/NewsRS.git’

解决办法:

1
2
3
$ git filter-branch --index-filter \
'git rm -r --cached --ignore-unmatch src/data-utils/train_original.csv' HEAD
$ git push origin master

阅读全文 »
12
Xingwang Xiong

Xingwang Xiong

Go big or go home

14 日志
9 分类
21 标签
RSS
GitHub E-Mail Instagram Weibo
友情链接
  • My CSDN Blog
  • yumh
© 2019 Xingwang Xiong
由 Hexo 强力驱动
|
主题 — NexT.Gemini v5.1.4
访问人数 总访问量