Java is one of the provinces that has the potential in Regency/City to sustain the national economy growth. To optimize the economic potential, cluster analysis is needed to comprehend the economic potential mapping of a region to accommodate the difference in economic growth occurred in each region. This research is executed to establish clusters of regency/city in East Java Province based on subsector variables chosen from the result of factor analysis from 6 main sectors of Gross Domestic Regional Product (GDRP) of East Java Province. In order to achieve the best cluster result, grouping to discover the mapping of economic potential (subsector with dominant contribution) in every cluster will be performed with Fuzzy C-Means (FCM) Cluster method that will be compared to conventional method C-means. Moreover, a comparison between clusters as the result based on chosen subsector variables with factor analysis and cluster result based on all of subsector variables (without factor analysis) will be performed. The research data is the GDRP of East Java province in 2015 obtained from Statistics Indonesia's catalogue with observation units of 28 regency/city (based on the result of data exploration test, 52.6% is outlier data). The result of the research showed that the use of factor analysis, both on FCM and C-means, produces better cluster result (smaller icd rate value). Furthermore, based on chosen subsector with factor analysis, the best cluster result (with the smallest icd rate value of 0.0040) is the one that applies FCM method with membership function of trapezoidal curve, with nine clusters as the optimum cluster. Based on the characteristics description, economic potential of regency/city in East Java province are food and beverage industry subsector and big trading and retail that is not cars/motorcycles subsector. Those lie in three or more cluster. Other than that, Surabaya as the capital city of East Java province has the most diverse economic potential.