序列图变换（sgt）是一种序列嵌入函数。sgt提取序列的短期和长期特征，并将其嵌入到有限维特征空间中。使用SGT，可以调整嵌入中提取的短到长模式的数量，而不增加计算量。
sgt的Python项目详细描述
序列图变换（sgt）
维护者：Chitta Ranjan，博士（cran2367@gmail.com）。
这是一个用于sgt的开源代码库，序列图转换提取了序列的短期和长期特征，并将它们嵌入到一个有限维的特征空间中。重要的是，sgt计算量小，可以在不增加计算量的情况下提取任意数量的短期到长期模式。这些性质在理论上得到了证明，并在实际数据上得到了证明：https://arxiv.org/abs/1608.03533 rel="nofollow">https://arxiv.org/abs/1608.03533
如果使用此代码或数据集，请引用以下内容：
[1]兰扬、奇塔、萨曼尼·易卜拉希米和卡姆兰·佩纳巴尔。"序列图转换（SGT）：序列数据挖掘的特征提取功能。"ARXIV预打印ARXIV:1608.03533（2016）。
@文章{ranjan2016sequence， title={sequence graph transform（sgt）：序列数据挖掘的特征提取函数}， 作者{ranjan，chitta和ebrahimi，samaneh和paynabar，kamran}， 日记本{arxiv预印本arxiv:1608.03533}， 年= { 2016 } }
快速验证代码
将算法应用于序列bbacacaaba。[1]中算法1&2中的sgt，w（0）和w（\kappa），以及由此得到的sgt估计将是（逐行执行main.r）：
alphabet_set <- c("A", "B", "C") # Denoted by variable V in [1]
seq <- "BBACACAABA"
kappa <- 5
###### Algorithm 1 ######
sgt_parts_alg1 <- f_sgt_parts(sequence = seq, kappa = kappa, alphabet_set_size = length(alphabet_set))
print(sgt_parts_alg1)
结果
$W0
A B C
A 10 4 3
B 11 3 4
C 7 2 1
$W_kappa
A B C
A 0.006874761 6.783349e-03 1.347620e-02
B 0.013521602 6.737947e-03 4.570791e-05
C 0.013521604 3.059162e-07 4.539993e-05
sgt <- f_SGT(W_kappa = sgt_parts_alg1$W_kappa, W0 = sgt_parts_alg1$W0,
Len = sgt_parts_alg1$Len, kappa = kappa) # Set Len = NULL for length-sensitive SGT.
print(sgt)
结果
A B C
A 0.3693614 0.44246287 0.5376371
B 0.4148844 0.46803816 0.1627745
C 0.4541361 0.06869332 0.2144920
类似地，算法2的执行如main.r
代码的说明和使用
打开filemain.r并逐行执行以了解过程。在这个示例执行中，我们给出了[1]中两个算法中任意一个的sgt估计。第一部分是了解sgt的计算过程。
在下一部分中，我们将展示在合成样本集上使用sgt的序列聚类。数据集中的序列长度在（45711）之间，分布均匀（因此，平均长度为~365）。数据集中的相似序列有一些相似的模式，依次是公共子字符串。这些公共子串可以是任意长度的。此外，这些子串的实例在不同序列中的顺序是任意的和随机的。例如，以下两个序列具有共同的模式。两个序列中的一个常见子串是qzta，它在两个序列中任意出现。这两个序列也有其他的公共子串。除了这些共性之外，序列中还存在大量的噪声。平均而言，数据集中所有序列中约有40%的字母是噪声。
AKQZTAEEYTDZUXXIRZSTAYFUIXCPDZUXMCSMEMVDVGMTDRDDEJWNDGDPSVPKJHKQBRKMXHHNLUBXBMHISQ
WEHGXGDDCADPVKESYQXGRLRZSTAYFUOQZTAWTBRKMXHHNWYRYBRKMXHHNPRNRBRKMXHHNPBMHIUSVXBMHI
WXQRZSTAYFUCWRZSTAYFUJEJDZUXPUEMVDVGMTOHUDZUXLOQSKESYQXGRCTLBRKMXHHNNJZDZUXTFWZKES
YQXGRUATSNDGDPWEBNIQZMBNIQKESYQXGRSZTTPTZWRMEMVDVGMTAPBNIRPSADZUXJTEDESOKPTLJEMZTD
LUIPSMZTDLUIWYDELISBRKMXHHNMADEDXKESYQXGRWEFRZSTAYFUDNDGDPKYEKPTSXMKNDGDPUTIQJHKSD
ZUXVMZTDLUINFNDGDPMQZTAPPKBMHIUQIUBMHIEKKJHK
SDBRKMXHHNRATBMHIYDZUXMTRMZTDLUIEKDEIBQZTAZOAMZTDLUILHGXGDDCAZEXJHKTDOOHGXGDDCAKZH
NEMVDVGMTIHZXDEROEQDEGZPPTDBCLBMHIJMMKESYQXGRGDPTNBRKMXHHNGCBYNDGDPKMWKBMHIDQDZUXI
HKVBMHINQZTAHBRKMXHHNIRBRKMXHHNDISDZUXWBOYEMVDVGMTNTAQZTA
由于，
不同长度的序列：由于长度不同，要找出两个序列具有相同的固有模式并不容易。按序列长度规范化模式特征是一个非常重要的问题。
共性不是按顺序排列的：如上面的示例序列所示，公共子串在任何地方。这使得基于对齐的方法等方法不可行。
大量噪声：大量噪声是大多数序列相似算法的天敌。它通常会导致高误报率。
< > >- 简单性：sgt的实现很简单。估计sgt不需要数值优化或其他解搜索算法。这使得它具有确定性和强大的功能。
- 长度敏感型：可以通过更改
main.r中的标记参数来轻松尝试长度敏感型sgt。
< > >
SGT群集
这里的数据集是上述挑战的一个很好的例子。我们在main.r中对数据集运行集群。数据集中的序列来自5（=k）个簇。我们使用这个关于集群数量的基本事实作为下面执行的输入。虽然，实际上，对于一个数据，集群的真实数量是未知的，但在这里我们演示了sgt imple心理状态。不管怎样，使用[1]中sec.sgt-算法中讨论的随机搜索过程，我们可以找到等于5的簇数。为了简单起见，本演示不包含此功能。
其他最新的序列聚类方法即使在真实聚类数（k=5）的情况下，其性能也明显较差。隐马尔可夫模型有很好的性能，但计算时间却大大增加。
## The dataset contains all roman letters, A-Z.
dataset <- read.csv("dataset.csv", header = T, stringsAsFactors = F)
sgt_parts_sequences_in_dataset <- f_SGT_for_each_sequence_in_dataset(sequence_dataset = dataset,
kappa = 5, alphabet_set = LETTERS,
spp = NULL, sgt_using_alphabet_positions = T)
input_data <- f_create_input_kmeans(all_seq_sgt_parts = sgt_parts_sequences_in_dataset,
length_normalize = T,
alphabet_set_size = 26,
kappa = 5, trace = TRUE,
inv.powered = T)
K = 5
clustering_output <- f_kmeans(input_data = input_data, K = K, alphabet_set_size = 26, trace = T)
cc <- f_clustering_accuracy(actual = c(strtoi(dataset[,1])), pred = c(clustering_output$class), K = K, type = "f1")
print(cc)
结果
$cc
Confusion Matrix and Statistics
Reference
Prediction a b c d e
a 50 0 0 0 0
b 0 66 0 0 0
c 0 0 60 0 0
d 0 0 0 55 0
e 0 0 0 0 68
Overall Statistics
Accuracy : 1
95% CI : (0.9877, 1)
No Information Rate : 0.2274
P-Value [Acc > NIR] : < 2.2e-16
Kappa : 1
Mcnemar's Test P-Value : NA
Statistics by Class:
Class: a Class: b Class: c Class: d Class: e
Sensitivity 1.0000 1.0000 1.0000 1.0000 1.0000
Specificity 1.0000 1.0000 1.0000 1.0000 1.0000
Pos Pred Value 1.0000 1.0000 1.0000 1.0000 1.0000
Neg Pred Value 1.0000 1.0000 1.0000 1.0000 1.0000
Prevalence 0.1672 0.2207 0.2007 0.1839 0.2274
Detection Rate 0.1672 0.2207 0.2007 0.1839 0.2274
Detection Prevalence 0.1672 0.2207 0.2007 0.1839 0.2274
Balanced Accuracy 1.0000 1.0000 1.0000 1.0000 1.0000
$F1
F1
1
我们可以看到聚类结果是准确的，没有误报。F1的分数是1.0。
< Buff行情>注意：当k较大（>；7）时，不要运行函数f_clustering戋u acciency，因为它执行的排列操作将变得昂贵。
SGT&Clustering上的PCA
为了在sgt上演示pca进行降维，然后执行聚类，我们添加了另一个代码片段。主成分分析在sgt稀疏的数据集上变得更加重要。当字母集较大但观察到的序列只包含其中的一些字母时，会出现稀疏sgt。例如，音乐收听历史序列数据集的字母表集合将有数千到数百万首歌曲，但单个序列将只有其中的少数歌曲
######## Clustering on Principal Components of SGT features ########
num_pcs <- 5 # Number of principal components we want
input_data_pcs <- f_pcs(input_data = input_data, PCs = num_pcs)$input_data_pcs
clustering_output_pcs <- f_kmeans(input_data = input_data_pcs, K = K, alphabet_set_size = sqrt(num_pcs), trace = F)
cc <- f_clustering_accuracy(actual = c(strtoi(dataset[,1])), pred = c(clustering_output_pcs$class), K = K, type = "f1")
print(cc)
结果
$cc
Confusion Matrix and Statistics
Reference
Prediction a b c d e
a 50 0 0 0 0
b 0 66 0 0 0
c 0 0 60 0 0
d 0 0 0 55 0
e 0 0 0 0 68
Overall Statistics
Accuracy : 1
95% CI : (0.9877, 1)
No Information Rate : 0.2274
P-Value [Acc > NIR] : < 2.2e-16
Kappa : 1
Mcnemar's Test P-Value : NA
Statistics by Class:
Class: a Class: b Class: c Class: d Class: e
Sensitivity 1.0000 1.0000 1.0000 1.0000 1.0000
Specificity 1.0000 1.0000 1.0000 1.0000 1.0000
Pos Pred Value 1.0000 1.0000 1.0000 1.0000 1.0000
Neg Pred Value 1.0000 1.0000 1.0000 1.0000 1.0000
Prevalence 0.1672 0.2207 0.2007 0.1839 0.2274
Detection Rate 0.1672 0.2207 0.2007 0.1839 0.2274
Detection Prevalence 0.1672 0.2207 0.2007 0.1839 0.2274
Balanced Accuracy 1.0000 1.0000 1.0000 1.0000 1.0000
$F1
F1
1
在序列的sgt上对pc进行聚类时，聚类结果仍然准确。
