Wang Yu Aço

(University School Liaoning de Engenharia Mecânica e Automação, Liaoning, Jinzhou 121000)

Para distorcido C-means algoritmo (FCM) não é sensível aos centros dos grupos iniciais, facilmente presa em solução óptima local, a melhoria da partícula - agrupamento algoritmo combinado com FCM algoritmo é proposto, baseado no optimização enxame de partícula algoritmo de agrupamento C-meio distorcido. O algoritmo PSO é inicializar a velocidade máxima das partículas que se deslocam e o espaço é optimizada, ao mesmo tempo introduzindo topologia em anel vizinhança, capacidade de procura mundial para melhorar partícula agrupamento algoritmo baseado. 3 da UCI resultados de simulação conjuntos de dados demonstram que em comparação com o C-distorcido meios de agrupamento algoritmo baseado no algoritmo de agrupamento com base algoritmo PSO FCM proposto partículas elementares que têm uma melhor eficiência e precisão do agrupamento.

Clustering; PSO; distorcido C-means algoritmo; algoritmo de agrupamento à base de partícula

CLC: TP301 código do documento: A DOI: 10,19358 / j.issn.2096-5133.2018.08.009

formato de citação: aço CDC distorcido C-means algoritmo baseado na tecnologia PSO [J] e informações de segurança de rede, 2018,37 (8): 36-39,44.

Distorcido C-means algoritmo baseado na optimização enxame de partícula

Wang Yugang

(Faculdade de Engenharia Mecânica e Automação, Universidade de Liaoning of Technology, Jinzhou 121000, China)

Resumo: FCM algoritmo é sensível ao centro de agrupamento inicial e susceptível de ser preso em uma solução óptima local. Combinando com o algoritmo PSO melhorada, um distorcido C-means algoritmo baseado na optimização enxame de partículas foi proposto. O algoritmo de optimizar o espaço enxame de partículas de inicialização e a velocidade máxima de partícula, e adopta a vizinhança da topologia de anel. o método melhorado da capacidade de pesquisa global de partícula enxame agrupamento algoritmo. os resultados da experiência de conjunto de dados UCI demonstrar que o algoritmo proposto tem melhor validade agrupamento e precisão de FCM e enxame de partículas agrupamento algoritmo.

Palavras-chave: enxame optimização das partículas;; agrupamento difuso C-means algoritmo; enxame de partículas agrupamento algoritmo

0 Introdução

Com o rápido desenvolvimento da tecnologia, big data, computação em nuvem, análise de cluster tornou-se um dos principais meios de mineração de dados. De cumprir com cognição humana, os investigadores teoria dos conjuntos difusos é introduzido análise de agrupamento, um distorcido C-means algoritmo (C-distorcido meios Clustering algoritmo, FCM). Desde o algoritmo FCM clássico é um algoritmo de busca melhor local, há um centros de cluster iniciais sensível, fácil de cair defeito óptimo local, limitar a aplicação de algoritmos [1-2]. Portanto, os pesquisadores tentam melhorar o algoritmo FCM clássica através de uma variedade de algoritmos inteligentes. PSO (Particle Swarm Optimization, PSO) em nome de um algoritmo de inteligência de enxame, contando com interações simples entre indivíduos dentro de uma população de busca de auto-organização, tem uma capacidade de aprendizagem forte e adaptabilidade [3]. Alguns estudiosos usar PSO algoritmo supera as deficiências de algoritmo FCM tradicional, o algoritmo PSO e integração algoritmo FCM tornou-se um tema quente nos últimos anos [4].

[5] é utilizado para Cluster amostras elevados de dados dimensionais é menos do que o algoritmo FCM algoritmo de agrupamento proposto FCM menos eficaz com base no grupo de partículas. Os satisfaz a condição algoritmo premissa de algoritmo FCM limita a adesão, de acordo com a distância entre a amostra e o centro da associação do cluster redistribuído, comparando amostras de cada agrupamento centro aceleração convergem óptima de partícula. [6] para o centro do aglomerado inicial e codificação partículas índice ponderado distorcido, o melhor valor de busca de ginástica e o índice ponderado distorcido pelo algoritmo de optimização enxame de partículas, os dados de conjuntos de dados artificiais definido experiências UCI mostram que este método do que tradicional a exactidão e a estabilidade da classe algoritmo algoritmo FCM agrupamento e aglomeração partícula tem melhorado. [7] intuição distorcido optimização enxame de partículas (IFPSO) e FCM algoritmo baseado em mistura, usando uma hesitação dos parâmetros de atributos e uma função objectivo de encontrar a semelhança entre os centros do conjunto, alta-dimensional do conjunto de dados de agrupamento atingir melhores resultados. [8] proposto um algoritmo de peso pesado índice de partícula inércia baseado agrupamento (ACL-PSO) com base. O algoritmo PSO modificado e algoritmo FCM combinando melhorada algoritmo FCM facilmente cai no melhor local, a base de dados dos dados padrão define os resultados dos testes da UCI mostram a efetividade do algoritmo.

FCM algoritmo para superar os defeitos e melhorar a qualidade do agrupamento, o algoritmo de agrupamento com base em papel é melhorado partículas elementares, e combinado com o algoritmo FCM, um algoritmo de agrupamento melhorada enxame de partículas de optimização distorcido C-meios (Improved distorcido Clustering C-significativo Algorithm Based on Particle Swarm Optimization, IFCM-PSO). Primeiro inicializado, seleccionando um Espaço de partícula razoável para reduzir a sensibilidade dos centros do conjunto inicial para melhorar a taxa de convergência; seguido de optimizar os parâmetros do movimento das partículas e a velocidade máxima de topologia em anel vizinhança, aglomerando algoritmo baseado para resolver a convergência partícula prematura defeitos. UCI seleccionado bancos de dados de três conjuntos de dados reais IRIS, vinho e experimentos cancro da mama Wisconsin (BCW) de simulação para verificar a validade do algoritmo.

1 distorcido C-meios de agrupamento algoritmo (FCM)

É dividido em conjunto as classes L amostra de dados conjunto X = {x1, x2, ..., xn} R p, n é o número de amostras, p é a dimensão do espaço da amostra, L é entre 2 ~ n. FCM algoritmo erro quadrático em função da função objetivo, que é definida como a fórmula:

Em que, dij = || x j-vi || distância e de fragmentação centros inter-amostra, tipicamente a distância euclidiana; m é ponderado índice difusa; uij conjunto de dados X representa o j ° amostras do grau de adesão de classe I ( 0 < uij < 1); vi representam cada agrupamento centro.

filiação Uij deve satisfazer as restrições:

FCM algoritmo é iterativo e função critério de erro quadrático como um algoritmo de ponto-a-clustering. Calcular matriz associação do cluster U e V centros de fórmula (2) e (3) a iteração, a função de objectivo J (U, V) valores decrescentes. Quando é obtida a função de critério de convergência, o resultado final do agrupamento de amostras de dados, isto é, a matriz de adesão distorcido L e o centro aglomerado dividido V.

2 - partículas elementares algoritmo de agrupamento

2.1 PSO

Em PSO, cada partícula Si captada como um indivíduo, a população é constituída por estas partículas, a solução para o problema consiste em encontrar a posição óptima da partícula no espaço. No decurso de cada iteração, o extremo corrente e melhor pi posição de cada grupo g o melhor valor global da avaliação de acordo com a adaptação da partícula de todas as partículas. Baseia-se em duas posições Extrema, actualizar a partícula de velocidade e posição em movimento, até a convergência para a solução óptima de posição do território.

Actualmente, a velocidade das partículas e forma actualização deslocamento comumente utilizados são:

Em que, c1, c2 factor de aprendizagem, e, geralmente, C1 = C2; R1, R2 é um número aleatório entre [0,1]; W é o peso de inércia, o valor é definido entre [Wmin, wmax]. Em um processo iterativo, peso inércia descendente geralmente linear pelo valor máximo torna-se o mínimo, isto é:

Que, iter é o número de iteração atual, itertotle para o número máximo de iterações.

2.2 FCM-PSO algoritmo

A fim de conseguir um avanço nos defeitos método de agrupamento tradicionais, os pesquisadores vão tentar algoritmo de otimização por enxame de partículas combinada com agrupamento tradicional, otimização e a capacidade de resolver busca aleatória distribuída apresenta algoritmo de agrupamento tradicional pelo algoritmo PSO global está fácil cair ótimo local e sensível aos problemas iniciais. O problema de agrupamento como uma optimização para alcançar perto particionamento óptima do conjunto de dados. Processar algoritmo funciona grupo de agrupamento elementares da seguinte forma:

(1) um dado número de agrupamentos, matriz de inicialização agrupamento centro, e atribuído às partículas individuais, gerado aleatoriamente velocidade inicial das partículas.

(2) O cálculo de adesão para cada partícula de, actualizar todos aptidão centros de fragmentação calcule da cada partícula, um extremo actualização indivíduo.

(3) As partículas individuais nos respectivos extremos, e para encontrar a melhor posição de extremo Global.

(4) De acordo com a taxa de fórmula PSO actualização de velocidade das partículas, e um limite para a velocidade máxima.

(5) actualizar a posição das partículas de acordo com a posição da fórmula enxame de partículas optimização.

(6) a condição de encerramento não for satisfeita, o retorno para o passo (2) Continuar iteração; se a condição de terminação é satisfeita, a posição ideal da partícula é um óptimo resultado classificadas isto é, o centro da matriz.

Actualmente, o algoritmo de agrupamento (distorcido C-Meio Clustering algoritmo baseado em partículas Swarm Optimization, FCM-PSO) e FCM algoritmo integração algoritmo PSO tornou-se uma classe de forma principal elementar algoritmo partícula agrupamento [9]. Este método está representado por cada centro de aglomerado de partículas seleccionar uma forma, a aplicação de FCM valor de função objectivo de cada partícula é calculada adaptação, correspondente ao centro do conjunto como uma base para a avaliação do efeito de aglomeração, a saída geral do algoritmo converge a maioria das partículas excelente localização, isto é, os centros do conjunto ideal.

3 Melhoria PSO distorcido C-means Algoritmo

Improved Particle 3.1 - algoritmo de agrupamento

(1) partículas de algoritmo PSO geralmente distribuído uniformemente entre o valor inicial de [0,1], em vez do espaço na vizinhança da solução óptima das partículas, que as partículas irão aumentar o tempo de busca de iteração da solução óptima, o efeito de aglomeração pobre [10]. Esse artigo vai provar centros do conjunto como indivíduos de uma população, e, por conseguinte, a distribuição de espaço é as amostras solução óptima do espaço de partículas. A posição inicial de partículas distribuídos aleatoriamente dentro do intervalo [Xmin, Xmax], Xmin, Xmax, respectivamente em cada composição mínima da amostra dimensão máxima e vector. Tais partículas são inicializados na busca espaço perto da solução ideal começou a evoluir operação, que pode efetivamente reduzir o tempo de convergência e melhorar a qualidade de clustering.

(2) O Vmax velocidade máxima determina a distância máxima de partículas que se deslocam em uma iteração cálculo, Vmax é fácil de fazer grandes demais para perder as partículas solução óptima, muito pequeno fará com que as partículas caem em solução ótima local. Assim, tipicamente as partículas para uma velocidade máxima constante. No entanto, grandes diferenças nos valores de dimensão de cada amostra de dimensão, porque várias dimensões espaciais na gama, as partículas em uma amostra de cada espaço dimensional Vmax são ajustados para uma constante, a solução ideal é, obviamente, em falta ou propenso a cair em locais Caso a solução ideal, os resultados afetar a convergência global do algoritmo. espaço amostra de papel em cada partícula de dimensão define uma velocidade máxima, a velocidade máxima Vmax dimensional faixa de variação é definido de acordo com cada amostra.

Em que, é uma constante.

(3) Em aplicações práticas, PSO algoritmo ainda é propenso na iteração anterior e choque convergência prematura ocorre. Portanto, os pesquisadores tentam usar o conceito de locais vizinhos, o bairro também servir como uma fonte de evolução partícula de regulação, reduzir a probabilidade de convergência prematura.

O algoritmo PSO, o alcance da informação grupo partilha de partículas é a topologia de vizinhança de partícula. topologia em anel bairro usa o conceito de vizinhos locais, cada partícula comunicar apenas com os vizinhos mais próximos, uma melhor coordenação entre as próprias partículas e grupos. algoritmo de agrupamento PSO a melhorar o desempenho aqui através da introdução de um bairro topologia em anel. Na fase inicial, cada partícula é a própria vizinhança, com o aumento do número de iterações, cada partícula comunicar apenas com o mais próximo vizinhos, vizinhança e gradualmente ampliado para incluir todas as partículas [11]. A nova estratégia é ajustada para a velocidade de atualização:

Onde, pl extremo bairro de partículas.

3,2 melhorada enxame de partículas optimização distorcido C-meios de agrupamento

A análise anterior, algoritmo IFCM-PSO proposto como a posição de centro de aglomerado de partículas na população, como um função da função de adaptação algoritmo alvo FCM, condição de terminação, ou menos do que um número limite de iterações atinge a função objectiva é definido como o valor óptimo mudança adaptação partícula definindo itertotle, o algoritmo pode ser resumido como se segue:

(1) parâmetros iniciais configuração de cluster: o número de agrupamentos, o número da população, o coeficiente de velocidade máxima, erro iterativo.

(2) No intervalo de valores [Xmin, Xmax] para inicializar a matriz de centro de cluster, e atribuindo a cada partícula.

(3) A fórmula (1) adaptado para os valores individuais calculados para cada população inicial.

(4) a velocidade das partículas em movimento calculado de acordo com a equação (9), em partículas de actualização de acordo com a equação (6) posição.

(5) adaptado para calcular o valor das partículas individuais da população, se a condição de terminação é satisfeita, a posição da partícula como uma saída global de solução óptima óptimo, caso contrário retorna ao passo (3) para continuar o cálculo iterativo.

4 Resultados e Análise Experimental

A fim de verificar o desempenho do algoritmo, seleccionado a partir do banco de dados de aprendizagem máquina UCI em conjuntos de dados reais 3 experiências, respectivamente IRIS, cancro VINHO, e da mama Wisconsin (BCW). Três ou mais conjuntos de dados são muitas vezes utilizados detalhes teste de validade algoritmo conjunto de dados de agrupamento mostrado na Tabela 1.

Tabela 1 Data Set Informações

testes de validação 4.1 algoritmo

Dos seleccionados três conjuntos de dados, respectivamente algoritmo FCM, algoritmo FCM-PSO e algoritmo IFCM-PSO aqui descrito para simulação de cluster. parâmetros experimentais foram os seguintes: número de partículas populações algoritmo FCM-PSO é de 20, o número máximo de iterações 500, o valor de limiar de mudança é a solução ideal 0,001; número de partículas populações algoritmo IFCM-PSO é 20, o coeficiente de velocidade máxima permitida = 0,15, o número máximo de iterações a 100, a solução óptima consiste em alterar a quantidade limiar de 0,001. Cada conjunto de dados de operação de três algoritmos de simulação de 10 vezes, 10 vezes o valor médio de cada um dos índices calculados resultados agrupamento mostrados na Tabela 2.

Tabela 2 Resultados dados Clustering

A Tabela 2 mostra que, para os três conjuntos de dados, um número mínimo de iterações FCM, mostraram a convergência mais rápida, mas devido a defeitos na sua precisão do algoritmo de agrupamento tal pobre; algoritmo FCM-PSO e poli IRIS BCW dois conjuntos de dados exatidão classe de alta algoritmo FCM, mas número máximo iterativo de convergência mais lento em três tipos de algoritmos; algoritmo IFCM-PSO deste trabalho, três conjuntos de dados em após iteração 100 receberam a mais alta taxa de precisão, mostram que o algoritmo desempenho global em termos de velocidade e clustering precisão dos melhores.

4.2 Resultados da análise de algoritmo

Correspondentes aos três conjuntos de dados, algoritmo FCM, algoritmo FCM-PSO e a selecção de cada algoritmo IFCM-PSO e um agrupamento agrupamento média aritmética da análise iterativa mais próxima curva de função de destino, o gráfico iteração valor de função objectivo mostrado na Figura 1 .

FIG gráfico iteração valor de função objectivo

Pode ser encontrado a partir da Figura 1 (a), quando os dados da íris por agrupamento, FCM valor da função algoritmo diminuiu rapidamente e em breve; converge. FCM-PSO algoritmo de valor de função objectivo ainda é apertando depois de 100 iterações, não convergência significativa; e IFCM -PSO algoritmo porque o valor de inicialização perto da solução ideal, convergência rápida, o valor da função objetivo a menor.

FIG 1 (b) mostra o conjunto de dados de VINHO, FCM algoritmo converge de forma rápida, FCM-PSO algoritmo iterativo converge para cerca de 30 vezes, mas nenhum decréscimo significativo na função de objectivo, indica a presença de convergência prematura; IFCM-PSO algoritmo de iteração 100 após a convergência básica valor da função objetivo do valor da função objetivo perto de algoritmo FCM.

A figura 1 (c) mostram o conjunto de dados de cancro da mama Wisconsin Embora algoritmo IFCM-PSO e algoritmo FCM-PSO são aqui choque ocorre, mas menor IFCM-PSO volatilidade algoritmo do artigo final, melhor convergência.

3 corresponde ao conjunto de dados por os acima de três algoritmos pode ser encontrada na comparação função alvo curva: agrupamento IFCM-OSP no agrupamento aqui já que o valor de inicialização, melhorias valor da velocidade máxima prevista, e a introdução de vizinhança anular auxiliar evolução, de modo que o algoritmo pode efetivamente superar o algoritmo FCM é sensível ao valor inicial, a iteração inicial fácil cair optima e elementares partículas locais - choque algoritmo de agrupamento, problema de convergência prematura, e, assim, obter o melhor efeito de aglomeração.

5 Conclusão

Neste documento, os principais problemas existem distorcido C-means algoritmo, a melhoria da partícula - algoritmo de agrupamento, distorcido C-means algoritmo baseado na optimização enxame de partículas. Ao optimizar o espaço de inicialização configurações partículas e parâmetros de partícula de movimento de dois velocidade máxima, e topologia em anel de vizinhança e melhorar o efeito de agregação algoritmo baseado partícula agrupamento. Os resultados das simulações mostram que a velocidade de convergência algoritmo de agrupamento e precisão são melhores do que distorcido C-means clustering (FCM) algoritmo de agrupamento e classes elementares (FCM-PSO) algoritmo.

Referências

meios de agrupamento estudo C algoritmo [J] [1.] foguetes, controle fuzzy e decisão intuitiva LEI Ying-jie, 2011, 26 (6): 847-850,856.

[2] Um PIMENTEL B, a Souza R M. Um ponderada multivariada distorcido método C-meio dos dados de produção científicos intervalo de valor [J]. Os sistemas especialistas com Applications, 41, 2014 (7), 3223-3236.

[3] Yang Hui, Wu Peize, Niji Liang Engenharia de Computação e melhorias no projeto PSO algoritmo parâmetro de confiança de formação de base de regra [J], 2017,38 (2):. 400-404.

[4] farhad S, AN AMIN, SHAHIN RN, et ai Avaliar o potencial de optimização enxame de partículas em aglomeração de imagens hiperespectral usando C-meio distorcido [C] // Conferência Internacional sobre Ásia Agricultura e animal, Singapura :. IACSIT, 2011 : 201-207.

[5] Niu Qiang, Huang Xinjian Um melhorado distorcido C-means algoritmo baseado em PSO [J] Journal of Software, 2011,6 (5): 873-879 ...

[6] Wang tigre longitudinal, espelho Liu, Donghui em meios C- distorcido de agrupamento algoritmo baseado na optimização enxame de partículas [J] Computer Science, 2012,39 (9): 166-169.

[7] KUMUTHA V, Palaniammal S. melhorado método agrupamento difuso baseado na optimização enxame de partículas distorcido intuitionistic [J] Journal of Theoretical Aplicada e Tecnologia da Informação, 2014, 62 (1) :. 15/08.

. [8] Chen Shouwen, Xu Zhuoming, Tang Yan Um algoritmo híbrido agrupamento com base no C-means fuzzy e enxame optimização melhorada partícula [J] Jornal Arábica para Ciência e Engenharia, 2014, 39 (12) :. 8875-8887.

[9] ouro Li Jun, ensolarado, Lu sábio, etc. Resumo do algoritmo de agrupamento à base de partícula [J] Computer Research, 2009,26 (12): 4423-4427.

.. [10] FILHO TMS, Pimentel BA, a Souza RMCR, et al métodos híbridos para agrupamento difuso com base em C-means fuzzy e enxame optimização melhorada partícula [J] Sistemas Especializados com Applications, 2015, 42 (17): 6315-6328 .

[11] Licopódio, Yun dinâmico grupo partícula algoritmo hierarquia topologia em anel [J] Computer Engineering and Applications, 2013, 49 (8): 1-5.

(Data de recebimento: 2018/04/29)

Sobre o autor:

Wang Yu Aço (1977-),, Ph.D., professor, interesses de pesquisa masculinos incluem: automação da manufatura.

* Projeto Fundo: Liaoning Provincial Natural Science Foundation da China (20170540445)