强相关标的聚类
Cluster Correlated Tickers
开始编码risk 中台每天会从因子模型或者历史日收益里算出一份 N×N 的 ticker 相关系数矩阵,用来识别真正独立的风险敞口。如果两只 ticker 在过去窗口里的相关系数绝对值 ≥ 某个阈值(强负相关同样意味着「同一波动源在驱动」——只是符号相反),它们就被视为同一个风险簇,对外只算作一个独立头寸。给定 ticker 列表、相关矩阵和阈值,请把所有 ticker 划分成连通分量——每个连通分量就是一个风险簇。
请实现 solution(tickers: list[str], corr: list[list[float]], threshold: float) -> list[list[str]]。建图规则:节点是 ticker,对 i < j 当 abs(corr[i][j]) >= threshold 时连边(无向)。对角线 corr[i][i] = 1.0 不算自环——它的存在只是为了让矩阵看起来正常,孤立的 ticker 还是要单独成一族。返回所有连通分量;每个分量内部 ticker 按它们在 tickers 输入里的下标升序排列;外层按每族「最小下标 ticker 的下标」升序排列。
举例:tickers = ["AAPL", "MSFT", "GOOG", "XOM", "CVX", "TLT"],相关矩阵阈值 0.7 下满足 |corr| ≥ 0.7 的 pair 是 {AAPL, MSFT}、{AAPL, GOOG}、{XOM, CVX},那么连通分量是 [AAPL, MSFT, GOOG]、[XOM, CVX]、[TLT]——前两族是科技股 / 能源股各自相关;TLT(长债 ETF)和谁都不强相关,自己一族。返回 [["AAPL", "MSFT", "GOOG"], ["XOM", "CVX"], ["TLT"]]:外层按各族最小下标(AAPL=0 < XOM=3 < TLT=5)排序,内层按下标升序。
实现上 BFS 或 DFS 都行:从 i = 0 起遍历 tickers,如果 i 没被访问过,从它出发用队列 / 栈把这个连通分量整族挖出来,标记访问过的下标,然后继续往后扫。挖一个分量时邻居判定按 abs(corr[i][j]) >= threshold 即可。复杂度 O(n²) 来自必须看一遍相关矩阵的所有 off-diagonal 元素。
约束条件
- 0 ≤ len(tickers) ≤ 500,tickers 内字符串两两不同
- corr 是 n×n 的 list[list[float]],n = len(tickers);corr[i][i] == 1.0;|corr[i][j]| ≤ 1.0
- 0.0 ≤ threshold ≤ 1.0
- 对角线不视为「自环」——单只 ticker 单独成一族时返回 `[ticker]`,不会因 corr[i][i] = 1 ≥ threshold 而被算进别的簇
- 连边判据是 `abs(corr[i][j]) >= threshold`(含等号)
- 返回 `list[list[str]]`:内层按 ticker 在输入 `tickers` 里的下标升序排序;外层按每族「最小下标 ticker 的下标」升序排序
样例
Case 1 · example from statement
输入: [["AAPL","MSFT","GOOG","XOM","CVX","TLT"],[[1,0.82,0.75,0.1,0.12,-0.2],[0.82,1,0.68,0.08,0.05,-0.18],[0.75,0.68,1,0.15,0.11,-0.22],[0.1,0.08,0.15,1,0.91,-0.3],[0.12,0.05,0.11,0.91,1,-0.28],[-0.2,-0.18,-0.22,-0.3,-0.28,1]],0.7]
期望: [["AAPL","MSFT","GOOG"],["XOM","CVX"],["TLT"]]
阈值 0.7 下满足 |corr| ≥ 0.7 的 pair 是 (AAPL,MSFT)=0.82、(AAPL,GOOG)=0.75、(XOM,CVX)=0.91(其他要么 0.68 < 0.7、要么相关性弱)。注意 (MSFT,GOOG)=0.68 < 0.7 没有直接边,但通过 AAPL 间接连通,所以三只科技股仍归一族。TLT 和谁都不强相关,自己一族。外层按各族最小下标排序:AAPL=0、XOM=3、TLT=5。
Case 2 · two clearly correlated, one isolated
输入: [["A","B","C"],[[1,0.95,0.1],[0.95,1,0.05],[0.1,0.05,1]],0.8]
期望: [["A","B"],["C"]]
(A,B)=0.95 ≥ 0.8 连边;C 和 A、B 的相关都低于 0.8,自己一族。外层按各族最小下标:A=0 在前,C=2 在后。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · example from statement
输入: [["AAPL","MSFT","GOOG","XOM","CVX","TLT"],[[1,0.82,0.75,0.1,0.12,-0.2],[0.82,1,0.68,0.08,0.05,-0.18],[0.75,0.68,1,0.15,0.11,-0.22],[0.1,0.08,0.15,1,0.91,-0.3],[0.12,0.05,0.11,0.91,1,-0.28],[-0.2,-0.18,-0.22,-0.3,-0.28,1]],0.7]
期望: [["AAPL","MSFT","GOOG"],["XOM","CVX"],["TLT"]]
阈值 0.7 下满足 |corr| ≥ 0.7 的 pair 是 (AAPL,MSFT)=0.82、(AAPL,GOOG)=0.75、(XOM,CVX)=0.91(其他要么 0.68 < 0.7、要么相关性弱)。注意 (MSFT,GOOG)=0.68 < 0.7 没有直接边,但通过 AAPL 间接连通,所以三只科技股仍归一族。TLT 和谁都不强相关,自己一族。外层按各族最小下标排序:AAPL=0、XOM=3、TLT=5。
Case 2 · two clearly correlated, one isolated
输入: [["A","B","C"],[[1,0.95,0.1],[0.95,1,0.05],[0.1,0.05,1]],0.8]
期望: [["A","B"],["C"]]
(A,B)=0.95 ≥ 0.8 连边;C 和 A、B 的相关都低于 0.8,自己一族。外层按各族最小下标:A=0 在前,C=2 在后。